View source for Aufgaben:Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung


{{quiz-Header|Buchseite=Informationstheorie/Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen
}}

[[File:P_ID2759__Inf_A_3_4_A.png|right|Vorgegebene Wahrscheinlichkeiten]]
Wir gehen hier von der [[Theory_of_Stochastic_Signals/Binomialverteilung|Binomialverteilung]] aus, die durch die Parameter $I$ und $p$ gekennzeichnet ist &#8658; siehe  Buch "Stochastische Signaltheorie":

* Wertebereich:
:$$X = \{\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}
2\hspace{0.05cm},\hspace{0.05cm}  ...\hspace{0.1cm} ,\hspace{0.05cm} {\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm} , \hspace{0.05cm} I\hspace{0.05cm}\}\hspace{0.05cm},$$
* Wahrscheinlichkeiten:
:$$P_X (X = \mu) = {I \choose \mu} \cdot p^{\mu} \cdot (1-p)^{I-\mu} \hspace{0.05cm},$$
* linearer Mittelwert:
:$$m_X = I  \cdot p \hspace{0.05cm},$$
* Varianz:
:$$\sigma_X^2 = I  \cdot p \cdot (1-p)\hspace{0.05cm}.$$
Im rot hinterlegten Teil obiger Tabelle sind die Wahrscheinlichkeiten $P_X(X = \mu$) der hier betrachteten Binomialverteilung angegeben. In der Teilaufgabe (1) sollen Sie die dazugehörigen Verteilungsparameter $I$ und $p$ bestimmen.


Diese vorgegebene Binomialverteilung soll hier durch eine [[Theory_of_Stochastic_Signals/Poissonverteilung|Poissonverteilung]] $Y$ approximiert werden, gekennzeichnet durch die Rate $\lambda$:

* Wertebereich:
:$$Y = \{\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}
2\hspace{0.05cm},\hspace{0.05cm}  ...\hspace{0.1cm} ,\hspace{0.05cm} {\mu}\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm}\}\hspace{0.05cm},$$
* Wahrscheinlichkeiten:
:$$P_Y (Y = \mu) = \frac{\lambda^{\mu}}{\mu !} \cdot {\rm e}^{\lambda} \hspace{0.05cm},$$
* Erwartungswerte:
:$$m_Y = \sigma_Y^2 = \lambda\hspace{0.05cm}.$$

Um abschätzen zu können, ob die Wahrscheinlichkeitsfunktion $P_X(X)$ ausreichend gut durch $P_Y(Y)$ approximiert wird, kann man auf die so genannten <i>Kullback&ndash;Leibler&ndash;Distanzen</i> (KLD) zurückgreifen, teilweise in der Literatur auch  <i>relative Entropien</i> genannt. Angepasst an das vorliegende Beispiel lauten diese:
:$$D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) \hspace{0.15cm}  =  \hspace{0.15cm}  {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 0}^{I}  P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)} \hspace{0.05cm},$$
:$$D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X) \hspace{0.15cm}  =  \hspace{0.15cm}  {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_Y(X)}{P_X(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{\mu = 0}^{\infty}  P_Y(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_Y(\mu)}{P_X(\mu)} \hspace{0.05cm}.$$
Bei Verwendung des <i>Logarithmus dualis</i> (zur Basis 2) ist hierbei dem Zahlenwert die Pseudo&ndash;Einheit "bit" hinzuzufügen.

[[File:P_ID2760__Inf_A_3_4_B.png|right|Beiliegende Ergebnistabelle]]
In nebenstehender Ergebnistabelle ist die sog. Kullback&ndash;Leibler&ndash;Distanz $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)$  (in "bit") zwischen der Binomial&ndash;PMF $P_X(\cdot)$ und einigen Poisson&ndash;Näherungen $P_Y(\cdot)$  (mit fünf verschiedenen Raten $\lambda$) eingetragen.  Die jeweilige Entropie $H(Y)$, die ebenfalls von der Rate $\lambda$ abhängt, ist in der ersten Zeile angegeben.

Die Spalten für $\lambda = 1$ sind in den Teilaufgaben (3) und (4) zu ergänzen. In der Teilaufgabe (6) sollen diese Ergebnisse interpretriert werden.


''Hinweise:'' 
*Die Aufgabe gehört zum  Kapitel [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
*Insbesondere wird Bezug genommen auf die Seite [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen#Relative_Entropie_.E2.80.93_Kullback.E2.80.93Leibler.E2.80.93Distanz|Relative_Entropie &ndash; Kullback-Leibler-Distanz]].
 
*Um die numerischen Berechnungen in Grenzen zu halten, werden folgende Hilfsgrößen vorgegeben; "lg"  bezeichnet den Logarithmus zur Basis 10:
:$$A' =
0.4096 \cdot {\rm lg} \hspace{0.1cm} \frac{0.4096}{0.3679} +
0.2048 \cdot {\rm lg} \hspace{0.1cm} \frac{0.2048}{0.1839} +
0.0512 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0512}{0.0613} +
0.0064 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0064}{0.0153} +
0.0003 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0003}{0.0031} \hspace{0.05cm},$$
:$$B' =
0.1839 \cdot {\rm lg} \hspace{0.1cm} (0.1839) +
0.0613 \cdot {\rm lg} \hspace{0.1cm} (0.0613) +
0.0153 \cdot {\rm lg} \hspace{0.1cm} (0.0153) +
0.0031 \cdot {\rm lg} \hspace{0.1cm} (0.0031) +
0.0005 \cdot {\rm lg} \hspace{0.1cm} (0.0005) +
0.0001 \cdot {\rm lg} \hspace{0.1cm} (0.0001)$$
:$$\Rightarrow \hspace{0.3cm} A'  \hspace{0.15cm} \underline {= 0.021944}  \hspace{0.05cm},\hspace{0.5cm}
B'  \hspace{0.15cm} \underline {= -0.24717}  \hspace{0.05cm}.$$


===Fragebogen===

<quiz display=simple>
{Wie lauten die Kenngrößen der vorliegenden Binomialverteilung?<br> <i>Hinweis:</i> Geben Sie (maximal) eine Nachkommastelle ein.
|type="{}"}
$I \hspace{0.47cm}  = \ $ { 5 3% }
$p \hspace{0.47cm} = \ $ { 0.2 3% }
$m_x \ = \ $ { 1 3% }
$\sigma^2_x \hspace{0.25cm}  = \ $ { 0.8 3% }


{Welche Kullback&ndash;Leibler&ndash;Distanz sollte man hier verwenden?
|type="[]"}
- Keine der beiden Distanzen ist anwendbar.
+ <i>D</i>(<i>P<sub>X</sub></i>||<i>P<sub>Y</sub></i>) ist besser geeignet.
- <i>D</i>(<i>P<sub>Y</sub></i>||<i>P<sub>X</sub></i>) ist besser geeignet.
- Beide Kullback&ndash;Leibler&ndash;Distanzen sind anwendbar.


{Berechnen Sie die geeignete Kullback&ndash;Leibler&ndash;Distanz  (hier mit <i>D</i> abgekürzt) für <i>&lambda;</i> = 1. Berücksichtigen Sie die Hilfsgröße $A'$.
|type="{}"}
$D \ = \ $ { 0.0182 3% } $\ \rm bit$


{Berechnen Sie die Entropie <i>H</i>(<i>Y</i>) der Poisson&ndash;Näherung mit der Rate <i>&lambda;</i> = 1. 
Berücksichtigen Sie die Hilfsgröße <i>B</i>&prime;.
|type="{}"}
$H(Y) \ = \ $ { 1.864 3% } $\ \rm bit$


{Welche der folgenden Aussagen sind zutreffend?
|type="[]"}
+ Bei der <i>H</i>(<i>Y</i>)&ndash;Berechnung haben alle Terme gleiches Vorzeichen.
- Bei der <i>D</i>(<i>P<sub>X</sub></i>||<i>P<sub>Y</sub></i>)&ndash;Berechnung haben alle Terme gleiches Vorzeichen.


{Wie interpretieren Sie die vervollständigte Ergebnistabelle?
|type="[]"}
+ Nach der Kullback&ndash;Leibler&ndash;Distanz sollte man <i>&lambda;</i> = 1 wählen.
- <i>&lambda;</i> = 1 garantiert auch die beste Approximation <i>H</i>(<i>Y</i>) &asymp; <i>H</i>(<i>X</i>).



</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; Bei der Binomialverteilung sind alle Wahrscheinlichkeiten Pr(<i>X</i> > <i>I</i>) = 0 &nbsp;&#8658;&nbsp; <u><i>I</i> = 5</u>. <br>Damit ergibt sich für die Wahrscheinlichkeit, dass <i>X</i> gleich <i>I</i> = 5 ist:
:$${\rm Pr} (X = 5) = {5 \choose 5} \cdot p^{5} =  p^{5}  \approx 0.0003 \hspace{0.05cm}.$$
Somit erhält man für

* die charakteristische Wahrscheinlichkeit: &nbsp; $p= (0.0003)^{1/5} = 0.1974 \hspace{0.15cm} \underline {\approx 0.2}\hspace{0.05cm},$
* den linearen Mittelwert (Erwartungswert): &nbsp; $m_X = I  \cdot p  \hspace{0.15cm} \underline {= 1}\hspace{0.05cm},$
* die Varianz: &nbsp; $\sigma_X^2 = I  \cdot p \cdot (1-p)  \hspace{0.15cm} \underline {= 0.8}\hspace{0.05cm}.$


'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
*Bei Verwendung von <i>D</i>(<i>P<sub>Y</sub></i>||<i>P<sub>X</sub></i>) würde sich unabhängig von <i>&lambda;</i> stets ein unendlicher Wert ergeben, da für <i>&mu;</i> &#8805; 6 gilt:
:$$P_X (X = \mu) = 0 \hspace{0.05cm},\hspace{0.3cm}P_Y (Y = \mu) \ne 0 \hspace{0.05cm}.$$
*Auch wenn die Wahrscheinlichkeiten <i>P<sub>Y</sub></i>(<i>Y</i> = <i>&mu;</i>) für große <i>&mu;</i> sehr klein werden, sind sie doch "unendlich viel größer" als <i>P<sub>X</sub></i>(<i>X</i> = <i>&mu;</i>).


'''(3)'''&nbsp; Wir verwenden die erste Kullback&ndash;Leibler&ndash;Distanz:
:$$D = D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) =\hspace{0.2cm} \sum_{\mu = 0}^{5}  P_X(\mu) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(\mu)}{P_Y(\mu)} \hspace{0.05cm}.$$
Bei Verwendung des Zehnerlogarithmus ("lg") erhalten wir für die Poisson&ndash;Näherung mit <i>&lambda;</i> = 1:
:$$D \hspace{0.05cm}' = 0.3277 \cdot {\rm lg} \hspace{0.1cm} \frac{0.3277}{0.3679} + A \hspace{0.05cm}' = 
-0.016468 + 0.021944 = 0.005476 \hspace{0.05cm}.$$
Nach Umrechnung auf den Zweierlogarithmus ("log<sub>2</sub>")  erhält man schließlich:
:$$D = D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) = \frac{0.005476}{{\rm lg} \hspace{0.1cm}(2)} \hspace{0.15cm} \underline {\approx 0.0182\,{\rm (bit)}}\hspace{0.05cm}.$$

'''(4)'''&nbsp; Unter Verwendung des Zehnerlogarithmus lautet die Entropie der Poisson&ndash;Näherung (<i>&lambda;</i> = 1):
:$$H\hspace{0.05cm}'(Y) = -{\rm E} \left [{\rm lg} \hspace{0.1cm} {P_Y(Y)} \right ]
= -2 \cdot 0.3679 \cdot {\rm lg} \hspace{0.1cm} (0.3679) - B\hspace{0.05cm}' = 0.31954 + 0.24717 = 0.56126.$$
Die Umrechnung in "bit" liefert das gesuchte Ergebnis:
:$$H(Y) = \frac{0.56126}{{\rm lg} \hspace{0.1cm}(2)}
\hspace{0.15cm} \underline {= 1.864\,{\rm (bit)}} \hspace{0.05cm}.$$

'''(5)'''&nbsp; Richtig ist die <u>Aussage 1</u>. Bei der numerischen Berechnung der Kullback&ndash;Leibler&ndash;Distanz ist
* der Beitrag des <i>&mu;</i>&ndash;ten Terms positiv, falls <i>P<sub>Y</sub></i>(<i>&mu;</i>) > <i>P<sub>X</sub></i>(<i>&mu;</i>),
* der Beitrag des <i>&mu;</i>&ndash;ten Terms negativ, falls <i>P<sub>Y</sub></i>(<i>&mu;</i>) < <i>P<sub>X</sub></i>(<i>&mu;</i>).


[[File:P_ID2761__Inf_A_3_4_C.png|right|Kullback–Leibler–Distanz und Entropie]]
'''(6)'''&nbsp; Zutreffend ist der <u>Lösungsvorschlag 1</u>: 
*Auch aus der Grafik ist ersichtlich, dass <i>D</i>(<i>P<sub>X</sub></i>||<i>P<sub>Y</sub></i>)&nbsp;=&nbsp;0.0182 bit von keinem anderen <i>&lambda;</i>&ndash;Wert als <i>&lambda;</i>&nbsp;=&nbsp;1 unterschritten wird (grüne Kreuze).
*Weiter erkennt man aus dieser Darstellung, dass man mit <i>&lambda;</i> = 0.9 eine bessere Entropie&ndash;Approximation als mit <i>&lambda;</i> = 1 erreicht  (blaue Kreise):
:$$H(Y) = 1.795\,{\rm bit} \hspace{0.15cm}\approx \hspace{0.15cm} H(X) = 1.793\,{\rm bit}\hspace{0.05cm}.$$
:Der zweite Lösungsvorschlag ist also falsch. 

Weiter ist anzumerken:
* Mit <i>&lambda;</i> = 1 stimmen die <u>linearen</u> Mittelwerte der beiden Zufallsgrößen  überein: <i>m<sub>X</sub></i> = <i>m<sub>Y</sub></i> = 1.
* Mit <i>&lambda;</i> = 0.9 stimmen die <u>quadratischen</u> Mittelwerte überein: <i>m<sub>X</sub></i> + <i>&sigma;<sub>X</sub></i><sup>2</sup> = <i>m<sub>Y</sub></i> + <i>&sigma;<sub>Y</sub></i><sup>2</sup> = 1.8.


Ob diese Aussage relevant ist, lasse ich dahingestellt. Denn: Aufgrund der stetigen Zunahme von <i>H</i>(<i>Y</i>) mit zunehmendem <i>&lambda;</i> ist klar, dass für irgendeinen <i>&lambda;</i>&ndash;Wert tatsächlich <i>H</i>(<i>Y</i>) = <i>H</i>(<i>X</i>) gelten muss.
{{ML-Fuß}}