Aufgaben:Aufgabe 3.5Z: Nochmals Kullback-Leibler-Distanz

• Zurück zum Buch

Die Wahrscheinlichkeitsfunktion lautet:

$$P_Y(X) = [\hspace{0.03cm}0.25\hspace{0.03cm}, \hspace{0.03cm} 0.25\hspace{0.03cm},\hspace{0.03cm} 0.25 \hspace{0.03cm}, \hspace{0.03cm} 0.25\hspace{0.03cm}]\hspace{0.05cm}$$ Die Zufallsgröße $X$ ist also gekennzeichnet

• durch den Symbolumfang $M=4$,
• mit gleichen Wahrscheinlichkeiten.

Die Zufallsgröße $Y$ ist stets eine Näherung für $X$. Sie wurde per Simulation aus einer Gleichverteilung gewonnen, wobei jeweils nur $N$ Zufallswerte ausgewertet wurden. Das heißt: $P_Y(1)$,...,$P_Y(4)$ sind im herkömmlichen Sinn keine Wahrscheinlichkeiten. Sie beschreiben vielmehr relative Häufigkeiten.

Das Ergebnis der sechsten Versuchsreihe (mit $N=1000$) ird demnach durch die folgende Wahrscheinlichkeitsfunktion zusammengefasst:

$$P_Y(X) = [\hspace{0.05cm}0.225\hspace{0.05cm}, \hspace{0.05cm} 0.253\hspace{0.05cm},\hspace{0.05cm} 0.250 \hspace{0.05cm}, \hspace{0.05cm} 0.272\hspace{0.05cm}] \hspace{0.05cm}$$ Bei dieser Schreibweise ist bereits berücksichtigt, dass die Zufallsgrößen $X$ und $Y$ auf dem gleichen Alphabet $X =$ {1, 2, 3, 4} basieren.

Mit diesen Voraussetzungen gilt für die relative Entropie (englisch: Informational Divergence) zwischen den Wahrscheinlichkeitsfunktionen $P_X(.)$ und $P_Y(.)$ :

$D( P_X || P_Y) = E_X [ log_2 \frac{P_X(X)}{P_Y(Y)}] = \sum\limits_{\mu=1}^M P_X(\mu) . log_2 \frac{P_X(\mu)}{P_Y(\mu)}$

Man bezeichnet $D( P_X || P_Y)$ als Kullback–Leibler–Distanz. Diese ist ein Maß für die Ähnlichkeit zwischen den beiden Wahrscheinlichkeitsfunktionen $P_X(.)$ und $P_Y(.)$. Die Erwartungswertbildung geschieht hier hinsichtlich der (tatsächlich gleichverteilten) Zufallsgröße $X$. Dies wird durch die Nomenklatur $E_X[.]$ angedeutet.

Eine zweite Form der Kullback–Leibler–Distanz ergibt sich durch die Erwartungswertbildung hinsichtlich der Zufallsgröße $Y \Rightarrow E_Y[.]$:

$D( P_Y || P_X) = E_Y [ log_2 \frac{P_Y(Y)}{P_Y(Y)}] = \sum\limits_{\mu=1}^M P_Y(\mu) . log_2 \frac{P_Y(\mu)}{P_X(\mu)}$

Hinweis: Die Aufgabe bezieht sich auf das Kapitel 3.1 dieses Buches. Die Angaben der Entropie $H(Y)$ und der Kullback–Leibler–Distanz $D( P_X || P_Y)$ in obiger Grafik sind in „bit” zu verstehen. die mit „???" versehenen Felder sollen von Ihnen in dieser Aufgabe ergänzt werden.

Fragebogen

1

Welche Entropie besitzt die Zufallsgröße $X$ ?

$H(X)$ = $bit$

2

Wie groß sind die Entropien der Zufallsgrößen $Y$ (Näherungen für $X$)?

$N=1000$ : $H(Y)$ = $bit$

$N=100$ : $H(Y)$ = $bit$

$N=10$ : $H(Y)$ = $bit$

3

Berechnen Sie die folgenden Kullback–Leibler–Distanzen.

$N=1000$ : $D( P_X || P_Y)$ = . 10 ( )$bit$

$N=100$ : $D( P_X || P_Y)$= . 10 ( )$bit$

$N=10$ : $D( P_X || P_Y)$= . 10 ( )$bit$

4

Liefert $D(P_Y||P_X)$ jeweils exakt das gleiche Ergebnis?

	Falsch
	Richtig

5

Welche Aussagen gelten für die Kullback–Leibler–Distanzen bei $N = 4$?

	Es gilt $D(P_X||P_Y) = 0$.
	Es gilt $D(P_X||P_Y) = 0.5 bit$
	$D(P_X||P_Y)$ ist unendlich groß
	Es gilt $D(P_Y||P_X) = 0$.
	Es gilt $D(P_Y||P_X) = 0.5 bit$.
	$D(P_Y||P_X)$ ist unendlich groß.

6

Ändern sich $H(Y)$ und $D(P_X||P_Y)$monoton mit $N$?

	Falsch
	Richtig

Musterlösung

Musterlösung

1.Bei gleichen Wahrscheinlichkeiten gilt mit $M = 4$ :

$H(X) = log_2 M = 2 (bit)$

2. Die Wahrscheinlichkeiten für die empirisch ermittelten Zufallsgrößen $Y$ weichen im Allgemeinen (nicht immer!) von der Gleichverteilung um so mehr ab, je kleiner der Parameter $N$ ist. Man erhält

• $N = 1000 \Rightarrow P_Y(Y) = [0.225, 0.253, 0.250, 0.272]$ :

$H(Y) = 0.225 . log_2 \frac{1}{0.225} +0.253. log_2 \frac{1}{0.253} + 0.250 . log_2 \frac{1}{0.250}+ 0.272 . log_2 \frac{1}{0.272} = 1.9968 (bit)$

• $N = 100\Rightarrow P_Y(Y) = [0.24, 0.16, 0.30, 0.30]$ :

$H(Y) =$......$= 1.9410$

• $N = 10 \Rightarrow P_Y(Y) = [0.5, 0.1, 0.3, 0.1]$:

$H(Y) =$......$= 1.6855$

3. Die Gleichung für die gesuchte Kullback–Leibler–Distanz lautet:

$$D(P_X||P_Y) = \sum\limits_{\mu=1}^4 P_X(\mu) . log_2 \frac{P_X(\mu)}{P_Y(\mu)} =$$

$$= \frac{1/4}{lg(2)} .[lg \frac{0.25}{P_Y(1)}+\frac{0.25}{P_Y(2)}+\frac{0.25}{P_Y(3)} + \frac{0.25}{P_Y(4)}] =$$

$$=\frac{1}{4 . lg(2)} . [lg \frac{0.25^4}{P_Y(1) . P_Y(2) . P_Y(3) . P_Y(4)}]$$ Der Logarithmus zur Basis 2 $\Rightarrow log_2(.)$ wurde zur einfachen Nutzung des Taschenrechners durch den Zehnerlogarithmus $\Rightarrow lg(.)$ ersetzt. Man erhält die folgenden numerischen Ergebnisse:

• $N=1000$ :

$$D(P_X||P_Y)=\frac{1}{4 . lg(2)} . [lg \frac{0.25^4}{0,225 . 0,253 . 0,250 . 0,272}] = 3,28 . 10^{-3} (bit)$$

• $N=100$ :

$$D(P_X||P_Y)=\frac{1}{4 . lg(2)} . [lg \frac{0.25^4}{0,24 . 0,16 . 0,30 . 0,30}] = 4,42 . 10^{-2} (bit)$$

• $N=100$ :

$$D(P_X||P_Y)=\frac{1}{4 . lg(2)} . [lg \frac{0.25^4}{0,5 . 0,1. 0,3 . 0,1}] = 3,45. 10^{-1} (bit)$$

5. Richtig ist Nein, wie am Beispiel $N = 100$ gezeigt werden soll:

$$D(P_X||P_Y) = \sum\limits_{\mu=1}^M P_X(\mu) . log_2 \frac{P_X(\mu)}{P_Y(\mu)} =$$

$$ = 0.24 . log_2 \frac{0.24}{0.25} +0.16. log_2 \frac{16}{0.25} +2 . 0,30 . log_2 \frac{0.30}{0.25} = 0.0407 (bit)$$ In der Teilaufgabe (c) haben wir stattdessen $D(P_X||P_Y)$ = 0.0442 erhalten. Das bedeutet auch: Der Name „Distanz” ist etwas irreführend. Danach würde man eigentlich $D(P_Y||P_X)$ = $D(P_X||P_Y)$ erwarten.

6. Mit $P_Y(X) = [0, 0.25, 0.5, 0.25]$ erhält man:

$$D(P_X||P_Y) = 0,25 . log_2 \frac{0.25}{0} +2 . 0,25 . log_2 \frac{0.25}{0.25} +0,25 . log_2 \frac{0.25}{0.50}$$

Aufgrund des ersten Terms ergibt sich für $D(P_X||P_Y)$ ein unendlich großer Wert. Für die zweite Kullback–Leibler–Distanz gilt:

$$D(P_Y||P_X) = 0 . log_2 \frac{0}{0.25} +2 . 0,25 . log_2 \frac{0.25}{0.25} +0,25 . log_2 \frac{0.5}{0.25}$$

Nach einer Grenzwertbetrachtung erkennt man, dass der erste Term das Ergebnis $0$ liefert. Auch der zweite Term ergibt sich zu $0$, und man erhält als Endergebnis:

$D(P_Y||P_X) = 0,50 . log_2(2) = 0.5 (bit)$

Richtig sind somit die Aussagen $3$ und $5$. Auch aus diesem Extrembeispiel wird deutlich, dass sich $D(P_Y||P_X)$ stets von $D(P_X||P_Y)$ unterscheidet. Nur für den Sonderfall P_Y = P_X sind beide Kullback–Leibler–Distanzen gleich, nämlich $0$. Die folgende Tabelle zeigt das vollständige Ergebnis dieser Aufgabe.

7. Die richtige Antwort ist Nein. Die Tendenz ist zwar eindeutig: Je größer $N$ ist,

• desto mehr nähert sich $H(Y)$ im Prinzip dem Endwert $H(X) = 2$ bit an.

• um so kleiner werden die Distanzen $D(P_X||P_Y)$ und $D(P_Y||P_X)$.

Man erkennt aus obiger Tabelle aber auch, dass es Ausnahmen gibt:

• Die Entropie $H(Y)$ ist für $N = 1000$ kleiner als für $N = 400$,

• Die Distanz $D(P_X||P_Y)$ ist für $N = 1000$ größer als für $N = 400$.

Der Grund hierfür ist, dass das hier dokumentierte empirische Experiment mit $N = 400$ eher zu einer Gleichverteilung geführt hat als das Experiment mit $N = 1000$.

Würde man dagegen sehr (unendlich) viele Versuche mit $N = 400$ und $N = 1000$ starten und über diese mitteln, ergäbe sich tatsächlich der eigentlich erwartete monotone Verlauf.