Aufgaben:Aufgabe 3.5Z: Nochmals Kullback-Leibler-Distanz: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie/3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen}} [[Datei:|right|]] ===Fragebogen=== <quiz disp…“)
 
 
(34 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie/3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen}}
+
{{quiz-Header|Buchseite=Informationstheorie/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
 +
}}
  
[[Datei:|right|]]
+
[[Datei:P_ID2762__Inf_Z_3_4.png|right|frame|Ermittelte Wahrscheinlichkeitsfunktionen]]
 +
Die Wahrscheinlichkeitsfunktion lautet:
 +
:$$P_X(X) = \big[\hspace{0.03cm}0.25\hspace{0.03cm}, \hspace{0.15cm} 0.25\hspace{0.15cm},\hspace{0.15cm} 0.25 \hspace{0.03cm}, \hspace{0.15cm} 0.25\hspace{0.03cm}\big]\hspace{0.05cm}.$$
 +
Die Zufallsgröße&nbsp; $X$&nbsp; ist also gekennzeichnet durch
 +
* den Symbolumfang&nbsp; $M=4$,
 +
* gleiche Wahrscheinlichkeiten $P_X(1) = P_X(2) = P_X(3) = P_X(4) = 1/4$ .
 +
 
 +
 
 +
Die Zufallsgröße&nbsp; $Y$&nbsp; ist stets eine Näherung für&nbsp; $X$:
 +
*Sie wurde per Simulation aus einer Gleichverteilung gewonnen, wobei jeweils nur&nbsp; $N$&nbsp; Zufallszahlen ausgewertet wurden.
 +
*Das heißt: &nbsp; $P_Y(1)$, ... , $P_Y(4)$&nbsp; sind im herkömmlichen Sinn keine Wahrscheinlichkeiten.&nbsp; Sie beschreiben vielmehr&nbsp; [[Stochastische_Signaltheorie/Wahrscheinlichkeit_und_relative_H%C3%A4ufigkeit#Bernoullisches_Gesetz_der_gro.C3.9Fen_Zahlen| relative Häufigkeiten]].
 +
 
 +
 
 +
Das Ergebnis der sechsten Versuchsreihe&nbsp; (mit&nbsp;  $N=1000)$&nbsp; wird demnach durch die folgende Wahrscheinlichkeitsfunktion zusammengefasst:
 +
 
 +
:$$P_Y(X) = \big [\hspace{0.05cm}0.225\hspace{0.15cm}, \hspace{0.05cm} 0.253\hspace{0.05cm},\hspace{0.15cm} 0.250 \hspace{0.05cm}, \hspace{0.15cm} 0.272\hspace{0.05cm}\big]
 +
\hspace{0.05cm}.$$
 +
Bei dieser Schreibweise ist berücksichtigt, dass die Zufallsgrößen&nbsp; $X$&nbsp; und&nbsp; $Y$&nbsp; auf dem gleichen Alphabet&nbsp; $X = \{1,\ 2,\ 3,\ 4\}$ basieren.
 +
 
 +
Mit diesen Voraussetzungen gilt für die&nbsp; '''relative Entropie'''&nbsp; (englisch:&nbsp; "Informational Divergence")&nbsp; zwischen den beiden Wahrscheinlichkeitsfunktionen&nbsp;  $P_X(.)$&nbsp; und&nbsp; $P_Y(.)$ :
 +
 
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) =  {\rm E}_X \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M}  P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)} \hspace{0.05cm}.$$
 +
 
 +
Man bezeichnet&nbsp;  $D( P_X\hspace{0.05cm} || \hspace{0.05cm}P_Y)$&nbsp;  als (erste) Kullback–Leibler–Distanz.
 +
*Diese ist ein Maß für die Ähnlichkeit zwischen den zwei Wahrscheinlichkeitsfunktionen&nbsp; $P_X(.)$&nbsp; und&nbsp; $P_Y(.)$. 
 +
*Die Erwartungswertbildung geschieht hier hinsichtlich der (tatsächlich gleichverteilten) Zufallsgröße&nbsp; $X$.&nbsp; Dies wird durch die Nomenklatur&nbsp;  ${\rm E}_X\big[.\big]$&nbsp; angedeutet.
 +
 
 +
 
 +
Eine zweite Form der Kullback–Leibler–Distanz ergibt sich durch die Erwartungswertbildung  hinsichtlich der Zufallsgröße&nbsp; $Y$ &nbsp; &rArr; &nbsp;  ${\rm E}_Y\big [.\big ]$:
 +
 
 +
:$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) =  {\rm E}_Y \hspace{-0.1cm} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_Y(X)}{P_X(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^M  P_Y(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_Y(\mu)}{P_X(\mu)} \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Hinweise:
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen]].
 +
*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Relative_Entropie_.E2.80.93_Kullback.E2.80.93Leibler.E2.80.93Distanz|Relative Entropie &ndash; Kullback-Leibler-Distanz]].
 +
*Die Angaben der Entropie&nbsp;  $H(Y)$&nbsp; und der Kullback–Leibler–Distanz&nbsp;  $D( P_X \hspace{0.05cm}|| \hspace{0.05cm}P_Y)$&nbsp;  in obiger Grafik sind in „bit” zu verstehen.
 +
* Die in der Grafik  mit&nbsp; „???"&nbsp;  versehenen Felder sollen von Ihnen in dieser Aufgabe ergänzt werden.
 +
  
  
Zeile 8: Zeile 51:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
 
|type="[]"}
 
- Falsch
 
+ Richtig
 
  
 +
{Welche Entropie besitzt die Zufallsgröße&nbsp; $X$ ?
 +
|type="{}"}
 +
$H(X)\ = \ $ { 2 1% } $\ \rm bit$
 +
 +
{Wie groß sind die Entropien der Zufallsgrößen&nbsp; $Y$&nbsp; $($Näherungen für&nbsp; $X)$?
 +
|type="{}"}
 +
$N=10^3\text{:} \hspace{0.5cm} H(Y) \ = \ $ { 1.9968 1% } $\ \rm bit$
 +
$N=10^2\text{:} \hspace{0.5cm} H(Y) \ = \ $ { 1.941 1% } $\ \rm bit$
 +
$N=10^1\text{:} \hspace{0.5cm} H(Y) \ = \ $ { 1.6855 1%  } $\ \rm bit$
  
{Input-Box Frage
+
{Berechnen Sie die folgenden Kullback–Leibler–Distanzen.
 
|type="{}"}
 
|type="{}"}
$\alpha$ = { 0.3 }
+
$N=10^3\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm}  P_Y) \ = \ $ { 0.00328 1% } $\ \rm bit$
 +
$N=10^2\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm}  P_Y) \ = \ $ { 0.0442 1% } $\ \rm bit$
 +
$N=10^1\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)  \ = \ $  { 0.345 1% } $\ \rm bit$
  
 +
{Liefert&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$&nbsp; jeweils exakt das gleiche Ergebnis?
 +
|type="()"}
 +
- Ja.
 +
+ Nein.
 +
 +
{Welche Aussagen gelten für die Kullback–Leibler–Distanzen bei&nbsp; $N = 4$?
 +
|type="[]"}
 +
- Es gilt&nbsp; $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0$.
 +
- Es gilt&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.5 \ \rm  bit$.
 +
+ $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; ist unendlich groß.
 +
-  Es gilt&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0$.
 +
+ Es gilt&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0.5 \ \rm bit$.
 +
-  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$&nbsp; ist unendlich groß.
 +
 +
{Ändern sich sowohl&nbsp; $H(Y)$&nbsp; als auch&nbsp;  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; monoton mit&nbsp; $N$?
 +
|type="()"}
 +
- Ja,
 +
+ Nein.
  
  
Zeile 24: Zeile 92:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
 
'''2.'''
+
'''(1)'''&nbsp; Bei gleichen Wahrscheinlichkeiten gilt mit&nbsp; $M = 4$:
'''3.'''
+
:$$H(X) = {\rm log}_2 \hspace{0.1cm} M
'''4.'''
+
\hspace{0.15cm} \underline {= 2\,{\rm (bit)}}  \hspace{0.05cm}.$$
'''5.'''
+
 
'''6.'''
+
 
'''7.'''
+
 
 +
'''(2)'''&nbsp; Die Wahrscheinlichkeiten für die empirisch ermittelten Zufallsgrößen&nbsp; $Y$&nbsp; weichen im Allgemeinen&nbsp; (nicht immer!)&nbsp; von der Gleichverteilung um so mehr ab, je kleiner der Parameter&nbsp; $N$&nbsp; ist.&nbsp; Man erhält für die dokumentierten Versuchsreihen:
 +
* $N = 1000 \ \ \Rightarrow \ \ P_Y(Y) =  \big [0.225, \ 0.253, \ 0.250, \ 0.272 \big ]$:
 +
:$$H(Y) =
 +
0.225 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.225} +
 +
0.253 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.253} +
 +
0.250 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.250} +
 +
0.272 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.272}
 +
\hspace{0.15cm} \underline {= 1.9968\ {\rm (bit)}}  \hspace{0.05cm},$$
 +
* $N = 100 \ \ \Rightarrow \ \  P_Y(Y) = \big[0.24, \ 0.16, \ 0.30,  \ 0.30\big]$:
 +
:$$H(Y) = \hspace{0.05cm}\text{...} \hspace{0.15cm} \underline {= 1.9410\ {\rm (bit)}}  \hspace{0.05cm},$$
 +
* $N = 10 \ \ \Rightarrow \ \  P_Y(Y) =  \big[0.5, \ 0.1, \ 0.3, \ 0.1 \big]$:
 +
:$$H(Y) = \hspace{0.05cm}\text{...} \hspace{0.15cm} \underline {= 1.6855\ {\rm (bit)}}  \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Die Gleichung für die gesuchte Kullback–Leibler–Distanz lautet:
 +
 
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \sum_{\mu = 1}^{4}  P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)}
 +
=  \frac{1/4}{{\rm lg} \hspace{0.1cm}(2)} \cdot
 +
\left [ {\rm lg} \hspace{0.1cm} \frac{0.25}{P_Y(1)} + \frac{0.25}{P_Y(2)} + \frac{0.25}{P_Y(3)} + \frac{0.25}{P_Y(4)}
 +
\right ] $$
 +
:$$\Rightarrow \hspace{0.3cm} D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)  =  \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot
 +
\left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{P_Y(1) \cdot P_Y(2)\cdot P_Y(3)\cdot P_Y(4)}
 +
\right ] \hspace{0.05cm}.$$
 +
 
 +
Der Logarithmus zur Basis&nbsp; $ 2$&nbsp; &rArr;  &nbsp; $\log_2(.)$&nbsp; wurde zur einfachen Nutzung des Taschenrechners durch den Zehnerlogarithmus &nbsp; &rArr;  &nbsp; $\lg(.)$  ersetzt.
 +
 
 +
Man erhält die folgenden numerischen Ergebnisse:
 +
* für $N=1000$:
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot
 +
\left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.225 \cdot 0.253\cdot 0.250\cdot 0.272}
 +
\right ] \hspace{0.15cm} \underline {= 0.00328 \,{\rm (bit)}}  \hspace{0.05cm},$$
 +
* für $N=100$:
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot
 +
\left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.24 \cdot 0.16\cdot 0.30\cdot 0.30}
 +
\right ] \hspace{0.15cm} \underline {= 0.0442 \,{\rm (bit)}}  \hspace{0.05cm},$$
 +
* für $N=10$:
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot
 +
\left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.5 \cdot 0.1\cdot 0.3\cdot 0.1}
 +
\right ] \hspace{0.15cm} \underline {= 0.345 \,{\rm (bit)}}  \hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Richtig ist&nbsp; <u>'''Nein'''</u>, wie am Beispiel&nbsp; $N = 100$&nbsp; gezeigt werden soll:
 +
:$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) =  \sum_{\mu = 1}^M  P_Y(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_Y(\mu)}{P_X(\mu)} = 0.24\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.24}{0.25} + 0.16\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.16}{0.25} +2 \cdot 0.30\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.30}{0.25}  = 0.0407\ {\rm (bit)}\hspace{0.05cm}.$$
 +
 
 +
*In der Teilaufgabe&nbsp; '''(3)'''&nbsp; haben wir stattdessen&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.0442$&nbsp; erhalten.
 +
*Das bedeutet auch: &nbsp; Die Bezeichnung „Distanz” ist etwas irreführend.
 +
*Danach würde man eigentlich&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$ = $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; erwarten.
 +
 
 +
 
 +
 
 +
 
 +
[[Datei:P_ID2763__Inf_Z_3_4e.png|right|frame|Wahrscheinlichkeitsfunktion, Entropie und Kullback–Leibler–Distanz]]
 +
'''(5)'''&nbsp; Mit&nbsp; $P_Y(X) = \big [0, \ 0.25, \ 0.5, \ 0.25 \big ]$&nbsp; erhält man:
 +
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0} + 2 \cdot 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.25}+0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.50}\hspace{0.05cm}.$$
 +
 
 +
*Aufgrund des ersten Terms ergibt sich für&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm}P_Y)$&nbsp; ein unendlich großer Wert.
 +
*Für die zweite Kullback–Leibler–Distanz gilt:
 +
:$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0\cdot {\rm log}_2 \hspace{0.1cm} \frac{0}{0.25} + 2 \cdot 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.25}+
 +
0.50\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.5}{0.25}
 +
\hspace{0.05cm}.$$
 +
 
 +
*Nach einer Grenzwertbetrachtung erkennt man, dass der erste Term das Ergebnis&nbsp; $0$&nbsp; liefert.&nbsp; Auch der zweite Term ergibt sich zu Null, und man erhält als Endergebnis:
 +
:$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0.50\cdot {\rm log}_2 \hspace{0.1cm} (2) \hspace{0.15cm} \underline {= 0.5\,{\rm (bit)}} \hspace{0.05cm}.$$
 +
 
 +
Richtig sind somit die&nbsp; <u>Aussagen 3 und 5</u>:
 +
*Aus diesem Extrembeispiel wird deutlich, dass sich&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$&nbsp; stets von&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; unterscheidet.
 +
*Nur für den Sonderfall&nbsp; $P_Y \equiv P_X$&nbsp; sind beide Kullback–Leibler–Distanzen gleich, nämlich Null.
 +
*Die nebenstehende Tabelle zeigt das vollständige Ergebnis dieser Aufgabe.
 +
 
 +
 
 +
 
 +
 
 +
'''(6)'''&nbsp; Richtig ist wiederum&nbsp; <u>'''Nein'''</u>.&nbsp; Die Tendenz ist zwar eindeutig: &nbsp; Je größer&nbsp; $N$&nbsp; ist,
 +
* desto mehr nähert sich&nbsp; $H(Y)$&nbsp; im Prinzip dem Endwert&nbsp; $H(X) = 2 \ \rm bit$&nbsp; an.
 +
* um so kleiner werden die Distanzen&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; und&nbsp; $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$.
 +
 
 +
 
 +
Man erkennt aus der Tabelle aber auch, dass es Ausnahmen gibt:
 +
* Die Entropie&nbsp; $H(Y)$&nbsp; ist für&nbsp; $N = 1000$&nbsp; kleiner als für&nbsp; $N = 400$.
 +
* Die Distanz&nbsp; $D(P_X\hspace{0.05cm}|| \hspace{0.05cm}P_Y)$&nbsp; ist für&nbsp; $N = 1000$&nbsp; größer als für&nbsp; $N = 400$.
 +
*Der Grund hierfür ist, dass das hier dokumentierte Experiment mit&nbsp; $N = 400$&nbsp; eher zu einer Gleichverteilung geführt hat als das Experiment mit&nbsp; $N = 1000$.
 +
*Würde man dagegen unendlich viele Versuche mit&nbsp; $N = 400$&nbsp; und&nbsp; $N = 1000$&nbsp; starten und über all diese mitteln, ergäbe sich tatsächlich der eigentlich erwartete monotone Verlauf.
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie|^3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen^]
+
[[Category:Aufgaben zu Informationstheorie|^3.1 Allgemeines zu 2D-Zufallsgrößen^]]

Aktuelle Version vom 31. August 2021, 14:57 Uhr

Ermittelte Wahrscheinlichkeitsfunktionen

Die Wahrscheinlichkeitsfunktion lautet:

$$P_X(X) = \big[\hspace{0.03cm}0.25\hspace{0.03cm}, \hspace{0.15cm} 0.25\hspace{0.15cm},\hspace{0.15cm} 0.25 \hspace{0.03cm}, \hspace{0.15cm} 0.25\hspace{0.03cm}\big]\hspace{0.05cm}.$$

Die Zufallsgröße  $X$  ist also gekennzeichnet durch

  • den Symbolumfang  $M=4$,
  • gleiche Wahrscheinlichkeiten $P_X(1) = P_X(2) = P_X(3) = P_X(4) = 1/4$ .


Die Zufallsgröße  $Y$  ist stets eine Näherung für  $X$:

  • Sie wurde per Simulation aus einer Gleichverteilung gewonnen, wobei jeweils nur  $N$  Zufallszahlen 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)$  wird demnach durch die folgende Wahrscheinlichkeitsfunktion zusammengefasst:

$$P_Y(X) = \big [\hspace{0.05cm}0.225\hspace{0.15cm}, \hspace{0.05cm} 0.253\hspace{0.05cm},\hspace{0.15cm} 0.250 \hspace{0.05cm}, \hspace{0.15cm} 0.272\hspace{0.05cm}\big] \hspace{0.05cm}.$$

Bei dieser Schreibweise ist 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 beiden Wahrscheinlichkeitsfunktionen  $P_X(.)$  und  $P_Y(.)$ :

$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = {\rm E}_X \hspace{-0.1cm}\left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^{M} P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)} \hspace{0.05cm}.$$

Man bezeichnet  $D( P_X\hspace{0.05cm} || \hspace{0.05cm}P_Y)$  als (erste) Kullback–Leibler–Distanz.

  • Diese ist ein Maß für die Ähnlichkeit zwischen den zwei Wahrscheinlichkeitsfunktionen  $P_X(.)$  und  $P_Y(.)$.
  • Die Erwartungswertbildung geschieht hier hinsichtlich der (tatsächlich gleichverteilten) Zufallsgröße  $X$.  Dies wird durch die Nomenklatur  ${\rm E}_X\big[.\big]$  angedeutet.


Eine zweite Form der Kullback–Leibler–Distanz ergibt sich durch die Erwartungswertbildung hinsichtlich der Zufallsgröße  $Y$   ⇒   ${\rm E}_Y\big [.\big ]$:

$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = {\rm E}_Y \hspace{-0.1cm} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_Y(X)}{P_X(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 1}^M P_Y(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_Y(\mu)}{P_X(\mu)} \hspace{0.05cm}.$$




Hinweise:


Fragebogen

1

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

$H(X)\ = \ $

$\ \rm bit$

2

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

$N=10^3\text{:} \hspace{0.5cm} H(Y) \ = \ $

$\ \rm bit$
$N=10^2\text{:} \hspace{0.5cm} H(Y) \ = \ $

$\ \rm bit$
$N=10^1\text{:} \hspace{0.5cm} H(Y) \ = \ $

$\ \rm bit$

3

Berechnen Sie die folgenden Kullback–Leibler–Distanzen.

$N=10^3\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) \ = \ $

$\ \rm bit$
$N=10^2\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) \ = \ $

$\ \rm bit$
$N=10^1\text{:} \hspace{0.5cm} D( P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) \ = \ $

$\ \rm bit$

4

Liefert  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$  jeweils exakt das gleiche Ergebnis?

Ja.
Nein.

5

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

Es gilt  $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0$.
Es gilt  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.5 \ \rm bit$.
$D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  ist unendlich groß.
Es gilt  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0$.
Es gilt  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0.5 \ \rm bit$.
$D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$  ist unendlich groß.

6

Ändern sich sowohl  $H(Y)$  als auch  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  monoton mit  $N$?

Ja,
Nein.


Musterlösung

(1)  Bei gleichen Wahrscheinlichkeiten gilt mit  $M = 4$:

$$H(X) = {\rm log}_2 \hspace{0.1cm} M \hspace{0.15cm} \underline {= 2\,{\rm (bit)}} \hspace{0.05cm}.$$


(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 für die dokumentierten Versuchsreihen:

  • $N = 1000 \ \ \Rightarrow \ \ P_Y(Y) = \big [0.225, \ 0.253, \ 0.250, \ 0.272 \big ]$:
$$H(Y) = 0.225 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.225} + 0.253 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.253} + 0.250 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.250} + 0.272 \cdot {\rm log}_2 \hspace{0.1cm} \frac{1}{0.272} \hspace{0.15cm} \underline {= 1.9968\ {\rm (bit)}} \hspace{0.05cm},$$
  • $N = 100 \ \ \Rightarrow \ \ P_Y(Y) = \big[0.24, \ 0.16, \ 0.30, \ 0.30\big]$:
$$H(Y) = \hspace{0.05cm}\text{...} \hspace{0.15cm} \underline {= 1.9410\ {\rm (bit)}} \hspace{0.05cm},$$
  • $N = 10 \ \ \Rightarrow \ \ P_Y(Y) = \big[0.5, \ 0.1, \ 0.3, \ 0.1 \big]$:
$$H(Y) = \hspace{0.05cm}\text{...} \hspace{0.15cm} \underline {= 1.6855\ {\rm (bit)}} \hspace{0.05cm}.$$


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

$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \sum_{\mu = 1}^{4} P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)} = \frac{1/4}{{\rm lg} \hspace{0.1cm}(2)} \cdot \left [ {\rm lg} \hspace{0.1cm} \frac{0.25}{P_Y(1)} + \frac{0.25}{P_Y(2)} + \frac{0.25}{P_Y(3)} + \frac{0.25}{P_Y(4)} \right ] $$
$$\Rightarrow \hspace{0.3cm} D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot \left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{P_Y(1) \cdot P_Y(2)\cdot P_Y(3)\cdot P_Y(4)} \right ] \hspace{0.05cm}.$$

Der Logarithmus zur Basis  $ 2$  ⇒   $\log_2(.)$  wurde zur einfachen Nutzung des Taschenrechners durch den Zehnerlogarithmus   ⇒   $\lg(.)$ ersetzt.

Man erhält die folgenden numerischen Ergebnisse:

  • für $N=1000$:
$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot \left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.225 \cdot 0.253\cdot 0.250\cdot 0.272} \right ] \hspace{0.15cm} \underline {= 0.00328 \,{\rm (bit)}} \hspace{0.05cm},$$
  • für $N=100$:
$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot \left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.24 \cdot 0.16\cdot 0.30\cdot 0.30} \right ] \hspace{0.15cm} \underline {= 0.0442 \,{\rm (bit)}} \hspace{0.05cm},$$
  • für $N=10$:
$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{1}{4 \cdot {\rm lg} \hspace{0.1cm}(2)} \cdot \left [ {\rm lg} \hspace{0.1cm} \frac{0.25^4}{0.5 \cdot 0.1\cdot 0.3\cdot 0.1} \right ] \hspace{0.15cm} \underline {= 0.345 \,{\rm (bit)}} \hspace{0.05cm}.$$


(4)  Richtig ist  Nein, wie am Beispiel  $N = 100$  gezeigt werden soll:

$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = \sum_{\mu = 1}^M P_Y(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_Y(\mu)}{P_X(\mu)} = 0.24\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.24}{0.25} + 0.16\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.16}{0.25} +2 \cdot 0.30\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.30}{0.25} = 0.0407\ {\rm (bit)}\hspace{0.05cm}.$$
  • In der Teilaufgabe  (3)  haben wir stattdessen  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.0442$  erhalten.
  • Das bedeutet auch:   Die Bezeichnung „Distanz” ist etwas irreführend.
  • Danach würde man eigentlich  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$ = $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  erwarten.



Wahrscheinlichkeitsfunktion, Entropie und Kullback–Leibler–Distanz

(5)  Mit  $P_Y(X) = \big [0, \ 0.25, \ 0.5, \ 0.25 \big ]$  erhält man:

$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0} + 2 \cdot 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.25}+0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.50}\hspace{0.05cm}.$$
  • Aufgrund des ersten Terms ergibt sich für  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm}P_Y)$  ein unendlich großer Wert.
  • Für die zweite Kullback–Leibler–Distanz gilt:
$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0\cdot {\rm log}_2 \hspace{0.1cm} \frac{0}{0.25} + 2 \cdot 0.25\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.25}{0.25}+ 0.50\cdot {\rm log}_2 \hspace{0.1cm} \frac{0.5}{0.25} \hspace{0.05cm}.$$
  • Nach einer Grenzwertbetrachtung erkennt man, dass der erste Term das Ergebnis  $0$  liefert.  Auch der zweite Term ergibt sich zu Null, und man erhält als Endergebnis:
$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) = 0.50\cdot {\rm log}_2 \hspace{0.1cm} (2) \hspace{0.15cm} \underline {= 0.5\,{\rm (bit)}} \hspace{0.05cm}.$$

Richtig sind somit die  Aussagen 3 und 5:

  • Aus diesem Extrembeispiel wird deutlich, dass sich  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$  stets von  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  unterscheidet.
  • Nur für den Sonderfall  $P_Y \equiv P_X$  sind beide Kullback–Leibler–Distanzen gleich, nämlich Null.
  • Die nebenstehende Tabelle zeigt das vollständige Ergebnis dieser Aufgabe.



(6)  Richtig ist wiederum  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 \ \rm bit$  an.
  • um so kleiner werden die Distanzen  $D(P_X\hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  und  $D(P_Y\hspace{0.05cm}|| \hspace{0.05cm} P_X)$.


Man erkennt aus der 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\hspace{0.05cm}|| \hspace{0.05cm}P_Y)$  ist für  $N = 1000$  größer als für  $N = 400$.
  • Der Grund hierfür ist, dass das hier dokumentierte Experiment mit  $N = 400$  eher zu einer Gleichverteilung geführt hat als das Experiment mit  $N = 1000$.
  • Würde man dagegen unendlich viele Versuche mit  $N = 400$  und  $N = 1000$  starten und über all diese mitteln, ergäbe sich tatsächlich der eigentlich erwartete monotone Verlauf.