View source for Exercise 3.5: Kullback-Leibler Distance and Binomial Distribution


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

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

* Wertebereich:
:$$X = \{\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.15cm} 1\hspace{0.05cm},\hspace{0.15cm}
2\hspace{0.05cm},\hspace{0.15cm}  \text{...}\hspace{0.1cm} ,\hspace{0.15cm} {\mu}\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm} , \hspace{0.15cm} 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 der Tabelle sind die Wahrscheinlichkeiten&nbsp; $P_X(X = \mu$)&nbsp; der betrachteten Binomialverteilung angegeben.&nbsp; In der Teilaufgabe&nbsp; '''(1)'''&nbsp; sollen Sie die dazugehörigen Verteilungsparameter &nbsp;$I$&nbsp; und &nbsp;$p$&nbsp; bestimmen.


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

* Wertebereich:
:$$Y = \{\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.15cm} 1\hspace{0.05cm},\hspace{0.05cm}
2\hspace{0.05cm},\hspace{0.15cm}  \text{...}\hspace{0.1cm} ,\hspace{0.15cm} {\mu}\hspace{0.05cm}, \hspace{0.05cm}\text{...}\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&nbsp; $P_X(X)$&nbsp; ausreichend gut durch&nbsp; $P_Y(Y)$&nbsp; approximiert wird, kann man auf die so genannten&nbsp; <i>Kullback&ndash;Leibler&ndash;Distanzen</i>&nbsp; ('''KLD''')&nbsp; zurückgreifen, in der Literatur teilweise  auch&nbsp;  "relative Entropien"&nbsp; 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},$$
[[File:P_ID2760__Inf_A_3_4_B.png|right|frame|Beiliegende Ergebnistabelle]]
:$$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 von&nbsp; $\log_2$&nbsp; ist dem Zahlenwert die Pseudo&ndash;Einheit "bit" hinzuzufügen.

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

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




''Hinweise:'' 
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Information_Theory/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[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;&nbsp;  hierbei bezeichnet&nbsp; $\rm \lg$&nbsp; den Logarithmus zur Basis&nbsp; $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?&nbsp; <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.
+ $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&nbsp; ist besser geeignet.
- $D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X)$&nbsp; ist besser geeignet.
- Beide Kullback&ndash;Leibler&ndash;Distanzen sind anwendbar.


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


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


{Welche der folgenden Aussagen sind zutreffend?
|type="[]"}
+ Bei der &nbsp;$H(Y)$&ndash;Berechnung haben alle Terme gleiches Vorzeichen.
- Bei der&nbsp; $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)$&ndash;Berechnung haben alle Terme gleiches Vorzeichen.


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



</quiz>

===Musterlösung===
{{ML-Kopf}}
'''(1)'''&nbsp; Bei der Binomialverteilung sind alle Wahrscheinlichkeiten&nbsp; ${\rm Pr}(X > I) = 0$ &nbsp; &#8658; &nbsp; $\underline{I = 5}$.&nbsp; Damit ergibt sich für die Wahrscheinlichkeit, dass&nbsp; $X =I = 5$&nbsp; 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&nbsp; $D(P_Y \hspace{0.05cm}|| \hspace{0.05cm} P_X)$&nbsp; würde sich unabhängig von&nbsp; $&lambda;$&nbsp; stets ein unendlicher Wert ergeben, da für&nbsp; $\mu &#8805; 6$&nbsp; 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&nbsp; $P_Y (Y = \mu)$&nbsp; für große&nbsp; $&mu;$&nbsp; sehr klein werden, sind sie doch "unendlich viel größer" als&nbsp; $P_X (X = \mu)$.




'''(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&nbsp; $(\lg)$&nbsp; erhalten wir für die Poisson&ndash;Näherung mit &nbsp;$\lambda = 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&nbsp; $(\log_2)$&nbsp;  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&nbsp; $(\lambda = 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>.&nbsp; Bei der numerischen Berechnung der Kullback&ndash;Leibler&ndash;Distanz ist
* der Beitrag des&nbsp; $&mu;$&ndash;ten Terms positiv, falls&nbsp; $P_Y(\mu) > P_X(\mu)$,
* der Beitrag des&nbsp; $&mu;$&ndash;ten Terms negativ, falls&nbsp; $P_Y(\mu) < P_X(\mu)$.


[[File:P_ID2761__Inf_A_3_4_C.png|right|frame|Kullback–Leibler–Distanz und Entropie]]



'''(6)'''&nbsp; Zutreffend ist der <u>Lösungsvorschlag 1</u>: 
*Auch aus der Grafik ist ersichtlich, dass&nbsp; $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y) =0.0182$&nbsp; bit&nbsp; von keinem anderen &nbsp;$&lambda;$&ndash;Wert als &nbsp;$&lambda; = 1$&nbsp; unterschritten wird (grüne Kreuze).
*Weiter erkennt man aus dieser Darstellung, dass man mit &nbsp;$&lambda; = 0.9$&nbsp; eine bessere Entropie&ndash;Approximation als mit &nbsp;$&lambda; = 1$&nbsp; 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. 

* Mit &nbsp;$&lambda; = 1$&nbsp; stimmen die&nbsp; <u>linearen Mittelwerte</u>&nbsp; der beiden Zufallsgrößen  überein: 
:$$m_X = m_Y= 1.$$
* Mit &nbsp;$&lambda; = 0.9$ stimmen die&nbsp; <u>quadratischen Mittelwerte</u>&nbsp; überein: 
:$$m_X + \sigma_X^2 = m_Y + \sigma_Y^2= 1.8.$$

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



[[Category:Information Theory: Exercises|^3.1 Allgemeines zu 2D-Zufallsgrößen^]]