Aufgaben:Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2759__Inf_A_3_4_A.png|right|]]
+
[[Datei:P_ID2759__Inf_A_3_4_A.png|right|Vorgegebene Wahrscheinlichkeiten]]
Wir gehen hier von der Binomialverteilung aus, die durch die Parameter <i>I</i> und <i>p</i> gekennzeichnet ist &#8658; siehe  Buch &bdquo;Stochastische Signaltheorie&rdquo;:
+
Wir gehen hier von der [[Stochastische_Signaltheorie/Binomialverteilung|Binomialverteilung]] aus, die durch die Parameter $I$ und $p$ gekennzeichnet ist &#8658; siehe  Buch &bdquo;Stochastische Signaltheorie&rdquo;:
  
:* Wertebereich:
+
* Wertebereich:
 
:$$X = \{\hspace{0.05cm}0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}
 
:$$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},$$
 
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:
+
* Wahrscheinlichkeiten:
 
:$$P_X (X = \mu) = {I \choose \mu} \cdot p^{\mu} \cdot (1-p)^{I-\mu} \hspace{0.05cm},$$
 
:$$P_X (X = \mu) = {I \choose \mu} \cdot p^{\mu} \cdot (1-p)^{I-\mu} \hspace{0.05cm},$$
:* linearer Mittelwert:
+
* linearer Mittelwert:
 
:$$m_X = I  \cdot p \hspace{0.05cm},$$
 
:$$m_X = I  \cdot p \hspace{0.05cm},$$
:* Varianz:
+
* Varianz:
 
:$$\sigma_X^2 = I  \cdot p \cdot (1-p)\hspace{0.05cm}.$$
 
:$$\sigma_X^2 = I  \cdot p \cdot (1-p)\hspace{0.05cm}.$$
Im rot hinterlegten Teil obiger Tabelle sind die Wahrscheinlichkeiten <i>P<sub>X</sub></i>(<i>X</i> = <i>&mu;</i>) der hier betrachteten Binomialverteilung angegeben. In der Teilaufgabe (a) sollen Sie die dazugehörigen Verteilungsparameter <i>I</i> und <i>p</i> bestimmen.
+
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 Poissonverteilung <i>Y</I> approximiert werden, gekennzeichnet durch die Rate <i>&lambda;</i>:
 
  
:* Wertebereich:
+
Diese vorgegebene Binomialverteilung soll hier durch eine [[Stochastische_Signaltheorie/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}
 
:$$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},$$
 
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:
+
* Wahrscheinlichkeiten:
 
:$$P_Y (Y = \mu) = \frac{\lambda^{\mu}}{\mu !} \cdot {\rm e}^{\lambda} \hspace{0.05cm},$$
 
:$$P_Y (Y = \mu) = \frac{\lambda^{\mu}}{\mu !} \cdot {\rm e}^{\lambda} \hspace{0.05cm},$$
:* Erwartungswerte:
+
* Erwartungswerte:
 
:$$m_Y = \sigma_Y^2 = \lambda\hspace{0.05cm}.$$
 
:$$m_Y = \sigma_Y^2 = \lambda\hspace{0.05cm}.$$
Um abschätzen zu können, ob die Wahrscheinlichkeitsfunktion <i>P<sub>X</sub></i>(<i>X</i>) ausreichend gut durch <i>P<sub>Y</sub></i>(<i>Y</i>) 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},\\
+
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_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}.$$
+
:$$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 &bdquo;bit&rdquo; hinzuzufügen.
 
Bei Verwendung des <i>Logarithmus dualis</i> (zur Basis 2) ist hierbei dem Zahlenwert die Pseudo&ndash;Einheit &bdquo;bit&rdquo; hinzuzufügen.
[[Datei:P_ID2760__Inf_A_3_4_B.png|right|]]
 
In nebenstehender Ergebnistabelle ist die sog. Kullback&ndash;Leibler&ndash;Distanz <i>D</i>(<i>P<sub>X</sub></i>||<i>P<sub>Y</sub></i>) in &bdquo;bit&rdquo; zwischen der Binomial&ndash;PMF <i>P<sub>X</sub></i> und einigen Poisson&ndash;Näherungen <i>P<sub>Y</sub></i>  (mit fünf verschiedenen Raten <i>&lambda;</i>) eingetragen.  Die jeweilige Entropie <i>H</i>(<i>Y</i>), die ebenfalls von der Rate <i>&lambda;</i> abhängt, ist in der ersten Zeile angegeben.
 
  
<br>Die Spalten für <i>&lambda;</i> = 1 sind in den Teilaufgaben (3) und (4) zu ergänzen. In der Teilaufgabe (f) sollen diese Ergebnisse interpretriert werden.
+
[[Datei: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 &bdquo;bit&rdquo;) 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.
  
<b>Hinweis:</b> Die Aufgabe gehört zu Kapitel 3.1. Um die numerischen Berechnungen in Grenzen zu halten, werden folgende Hilfsgrößen vorgegeben; &bdquo;lg&rdquo;  bezeichnet den Logarithmus zur Basis 10:
+
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.
:$$A' \hspace{0.15cm}  = \hspace{0.15cm}
+
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu den 2D-Zufallsgrößen]].
 +
*Insbesondere wird Bezug genommen auf die Seite [[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]].
 +
 +
*Um die numerischen Berechnungen in Grenzen zu halten, werden folgende Hilfsgrößen vorgegeben; &bdquo;lg&rdquo;  bezeichnet den Logarithmus zur Basis 10:
 +
:$$A' =
 
0.4096 \cdot {\rm lg} \hspace{0.1cm} \frac{0.4096}{0.3679} +
 
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.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.0512 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0512}{0.0613} +
+  \hspace{0.15cm}
 
 
0.0064 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0064}{0.0153} +
 
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} =
+
0.0003 \cdot {\rm lg} \hspace{0.1cm} \frac{0.0003}{0.0031} \hspace{0.05cm},$$
\hspace{0.15cm} \underline {= 0.021944}  \hspace{0.05cm},$$
+
:$$B' =
:$$B' \hspace{0.15cm}  = \hspace{0.15cm}
 
 
0.1839 \cdot {\rm lg} \hspace{0.1cm} (0.1839) +
 
0.1839 \cdot {\rm lg} \hspace{0.1cm} (0.1839) +
 
0.0613 \cdot {\rm lg} \hspace{0.1cm} (0.0613) +
 
0.0613 \cdot {\rm lg} \hspace{0.1cm} (0.0613) +
0.0153 \cdot {\rm lg} \hspace{0.1cm} (0.0153) +\\
+
0.0153 \cdot {\rm lg} \hspace{0.1cm} (0.0153) +
+  \hspace{0.15cm}
 
 
0.0031 \cdot {\rm lg} \hspace{0.1cm} (0.0031) +
 
0.0031 \cdot {\rm lg} \hspace{0.1cm} (0.0031) +
 
0.0005 \cdot {\rm lg} \hspace{0.1cm} (0.0005) +
 
0.0005 \cdot {\rm lg} \hspace{0.1cm} (0.0005) +
0.0001 \cdot {\rm lg} \hspace{0.1cm} (0.0001)  
+
0.0001 \cdot {\rm lg} \hspace{0.1cm} (0.0001)$$
\hspace{0.15cm} \underline {= -0.24717}  \hspace{0.05cm}.$$
+
:$$\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}.$$
  
  
Zeile 60: Zeile 66:
 
{Wie lauten die Kenngrößen der vorliegenden Binomialverteilung?<br> <i>Hinweis:</i> Geben Sie (maximal) eine Nachkommastelle ein.
 
{Wie lauten die Kenngrößen der vorliegenden Binomialverteilung?<br> <i>Hinweis:</i> Geben Sie (maximal) eine Nachkommastelle ein.
 
|type="{}"}
 
|type="{}"}
$I$ = { 5 3% }
+
$I \hspace{0.47cm}  = \ $ { 5 3% }
$p$ = { 0.2 3% }
+
$p \hspace{0.47cm} = \ $ { 0.2 3% }
$m_x$ = { 5 3% }
+
$m_x \ = \ $ { 1 3% }
$\sigma^2_x$ = { 5 3% }
+
$\sigma^2_x \hspace{0.25cm}  = \ $ { 0.8 3% }
  
  
Zeile 74: Zeile 80:
  
  
{Berechnen Sie die geeignete Kullback&ndash;Leibler&ndash;Distanz  (hier mit <i>D</i> bezeichnet) für <i>&lambda;</i> = 1. Berücksichtigen Sie die angegebene Hilfsgröße <i>A</i>&prime;.
+
{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="{}"}
 
|type="{}"}
$\lambda = 1:\ D$ = { 0.0182 3% } $bit$
+
$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 angegebene Hilfsgröße <i>B</i>&prime;.
+
{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="{}"}
 
|type="{}"}
$\lambda = 1:\ H(Y)$ = { 1.864 3% } $bit$
+
$H(Y) \ = \ $ { 1.864 3% } $\ \rm bit$
  
  
 
{Welche der folgenden Aussagen sind zutreffend?
 
{Welche der folgenden Aussagen sind zutreffend?
 
|type="[]"}
 
|type="[]"}
+ <i>H</i>(<i>Y</i>)&ndash;Berechnung: Alle Terme haben gleiches Vorzeichen.
+
+ Bei der <i>H</i>(<i>Y</i>)&ndash;Berechnung haben alle Terme gleiches Vorzeichen.
- <i>D</i>(<i>P<sub>X</sub></i>||<i>P<sub>Y</sub></i>)&ndash;Berechnung: Alle Terme haben 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.
  
  
Zeile 101: Zeile 108:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;Bei der Binomialverteilung sind alle Wahrscheinlichkeiten Pr(<i>X</i> > <i>I</i>) = 0 &nbsp;&#8658;&nbsp; <u><i>I</i> = 5</u>. Damit ergibt sich für die Wahrscheinlichkeit, dass <i>X</i> gleich <i>I</i> = 5 ist:
+
'''(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}.$$
 
:$${\rm Pr} (X = 5) = {5 \choose 5} \cdot p^{5} =  p^{5}  \approx 0.0003 \hspace{0.05cm}.$$
Damit erhält man für
+
Somit erhält man für
  
:* die charakteristische Wahrscheinlichkeit:
+
* die charakteristische Wahrscheinlichkeit: &nbsp; $p= (0.0003)^{1/5} = 0.1974 \hspace{0.15cm} \underline {\approx 0.2}\hspace{0.05cm},$
:$$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}.$
  
:* den linearen Mittelwert (Erwartungswert):
 
:$$m_X = I  \cdot p  \hspace{0.15cm} \underline {= 1}\hspace{0.05cm},$$
 
  
:* die Varianz:
+
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
:$$\sigma_X^2 = I  \cdot p \cdot (1-p) \hspace{0.15cm} \underline {= 0.8}\hspace{0.05cm}.$$
+
*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 &bdquo;unendlich viel größer&rdquo; als <i>P<sub>X</sub></i>(<i>X</i> = <i>&mu;</i>).
  
<b>2.</b>&nbsp;&nbsp;Richtig ist der <u>Lösungsvorschlag 2</u>. Bei Verwendung der Kullback&ndash;Leibler&ndash;Distanz <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 &bdquo;unendlich viel größer&rdquo; als <i>P<sub>X</sub></i>(<i>X</i> = <i>&mu;</i>).
 
  
<b>3.</b>&nbsp;&nbsp;Wir verwenden die erste Kullback&ndash;Leibler&ndash;Distanz:
+
'''(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}.$$
 
:$$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 (&bdquo;lg&rdquo;) erhalten wir für die Poisson&ndash;Näherung mit <i>&lambda;</i> = 1:
 
Bei Verwendung des Zehnerlogarithmus (&bdquo;lg&rdquo;) 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}' =  
 
:$$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}.$$
 
-0.016468 + 0.021944 = 0.005476 \hspace{0.05cm}.$$
Nach Umrechnung auf den Zweierlogarithmus (&bdquo;log<sub>2</sub>&rdquo;)  erhält man:
+
Nach Umrechnung auf den Zweierlogarithmus (&bdquo;log<sub>2</sub>&rdquo;)  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}.$$
 
:$$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}.$$
  
<b>4.</b>&nbsp;&nbsp;Unter Verwendung des Zehnerlogarithmus lautet die Entropie der Poisson&ndash;Näherung (<i>&lambda;</i> = 1):
+
'''(4)'''&nbsp; Unter Verwendung des Zehnerlogarithmus lautet die Entropie der Poisson&ndash;Näherung (<i>&lambda;</i> = 1):
:$$H\hspace{0.05cm}'(Y) \hspace{0.15cm}  = \hspace{0.15cm} -{\rm E} \left [{\rm lg} \hspace{0.1cm} {P_Y(Y)} \right ]
+
:$$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}' =\\
+
= -2 \cdot 0.3679 \cdot {\rm lg} \hspace{0.1cm} (0.3679) - B\hspace{0.05cm}' = 0.31954 + 0.24717 = 0.56126.$$
=  \hspace{0.15cm} 0.31954 + 0.24717 = 0.56126$$
 
 
Die Umrechnung in &bdquo;bit&rdquo; liefert das gesuchte Ergebnis:
 
Die Umrechnung in &bdquo;bit&rdquo; liefert das gesuchte Ergebnis:
 
:$$H(Y) = \frac{0.56126}{{\rm lg} \hspace{0.1cm}(2)}
 
:$$H(Y) = \frac{0.56126}{{\rm lg} \hspace{0.1cm}(2)}
 
\hspace{0.15cm} \underline {= 1.864\,{\rm (bit)}} \hspace{0.05cm}.$$
 
\hspace{0.15cm} \underline {= 1.864\,{\rm (bit)}} \hspace{0.05cm}.$$
  
<b>5.</b>&nbsp;&nbsp;Richtig ist die <u>Aussage 1</u>. Bei der numerischen Berechnung der Kullback&ndash;Leibler&ndash;Distanz ist
+
'''(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>).
  
:* 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>).
+
[[Datei:P_ID2761__Inf_A_3_4_C.png|right|Kullback–Leibler–Distanz und Entropie]]
 
+
'''(6)'''&nbsp; Zutreffend ist der <u>Lösungsvorschlag 1</u>:
<b>6.</b>&nbsp;&nbsp;Zutreffend ist der <u>Lösungsvorschlag 1</u>. Auch aus der nachfolgenden 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).
+
*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).
[[Datei:P_ID2761__Inf_A_3_4_C.png|center|]]
+
*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):
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}.$$
 
:$$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. Anzumerken ist:
+
:Der zweite Lösungsvorschlag ist also falsch.  
  
:* 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.
+
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.
  
:* 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.
 
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ß}}
 
{{ML-Fuß}}
 
 
 
[[Category:Aufgaben zu Informationstheorie|^3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen^]]
 

Aktuelle Version vom 8. Oktober 2018, 11:07 Uhr

Vorgegebene Wahrscheinlichkeiten

Wir gehen hier von der Binomialverteilung aus, die durch die Parameter $I$ und $p$ gekennzeichnet ist ⇒ 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 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 Kullback–Leibler–Distanzen (KLD) zurückgreifen, teilweise in der Literatur auch relative Entropien 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 Logarithmus dualis (zur Basis 2) ist hierbei dem Zahlenwert die Pseudo–Einheit „bit” hinzuzufügen.

Beiliegende Ergebnistabelle

In nebenstehender Ergebnistabelle ist die sog. Kullback–Leibler–Distanz $D(P_X \hspace{0.05cm}|| \hspace{0.05cm} P_Y)$ (in „bit”) zwischen der Binomial–PMF $P_X(\cdot)$ und einigen Poisson–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:

  • 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

1

Wie lauten die Kenngrößen der vorliegenden Binomialverteilung?
Hinweis: Geben Sie (maximal) eine Nachkommastelle ein.

$I \hspace{0.47cm} = \ $

$p \hspace{0.47cm} = \ $

$m_x \ = \ $

$\sigma^2_x \hspace{0.25cm} = \ $

2

Welche Kullback–Leibler–Distanz sollte man hier verwenden?

Keine der beiden Distanzen ist anwendbar.
D(PX||PY) ist besser geeignet.
D(PY||PX) ist besser geeignet.
Beide Kullback–Leibler–Distanzen sind anwendbar.

3

Berechnen Sie die geeignete Kullback–Leibler–Distanz (hier mit D abgekürzt) für λ = 1. Berücksichtigen Sie die Hilfsgröße $A'$.

$D \ = \ $

$\ \rm bit$

4

Berechnen Sie die Entropie H(Y) der Poisson–Näherung mit der Rate λ = 1. Berücksichtigen Sie die Hilfsgröße B′.

$H(Y) \ = \ $

$\ \rm bit$

5

Welche der folgenden Aussagen sind zutreffend?

Bei der H(Y)–Berechnung haben alle Terme gleiches Vorzeichen.
Bei der D(PX||PY)–Berechnung haben alle Terme gleiches Vorzeichen.

6

Wie interpretieren Sie die vervollständigte Ergebnistabelle?

Nach der Kullback–Leibler–Distanz sollte man λ = 1 wählen.
λ = 1 garantiert auch die beste Approximation H(Y) ≈ H(X).


Musterlösung

(1)  Bei der Binomialverteilung sind alle Wahrscheinlichkeiten Pr(X > I) = 0  ⇒  I = 5.
Damit ergibt sich für die Wahrscheinlichkeit, dass X gleich 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:   $p= (0.0003)^{1/5} = 0.1974 \hspace{0.15cm} \underline {\approx 0.2}\hspace{0.05cm},$
  • den linearen Mittelwert (Erwartungswert):   $m_X = I \cdot p \hspace{0.15cm} \underline {= 1}\hspace{0.05cm},$
  • die Varianz:   $\sigma_X^2 = I \cdot p \cdot (1-p) \hspace{0.15cm} \underline {= 0.8}\hspace{0.05cm}.$


(2)  Richtig ist der Lösungsvorschlag 2:

  • Bei Verwendung von D(PY||PX) würde sich unabhängig von λ stets ein unendlicher Wert ergeben, da für μ ≥ 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 PY(Y = μ) für große μ sehr klein werden, sind sie doch „unendlich viel größer” als PX(X = μ).


(3)  Wir verwenden die erste Kullback–Leibler–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–Näherung mit λ = 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 („log2”) 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)  Unter Verwendung des Zehnerlogarithmus lautet die Entropie der Poisson–Näherung (λ = 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)  Richtig ist die Aussage 1. Bei der numerischen Berechnung der Kullback–Leibler–Distanz ist

  • der Beitrag des μ–ten Terms positiv, falls PY(μ) > PX(μ),
  • der Beitrag des μ–ten Terms negativ, falls PY(μ) < PX(μ).


Kullback–Leibler–Distanz und Entropie

(6)  Zutreffend ist der Lösungsvorschlag 1:

  • Auch aus der Grafik ist ersichtlich, dass D(PX||PY) = 0.0182 bit von keinem anderen λ–Wert als λ = 1 unterschritten wird (grüne Kreuze).
  • Weiter erkennt man aus dieser Darstellung, dass man mit λ = 0.9 eine bessere Entropie–Approximation als mit λ = 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 λ = 1 stimmen die linearen Mittelwerte der beiden Zufallsgrößen überein: mX = mY = 1.
  • Mit λ = 0.9 stimmen die quadratischen Mittelwerte überein: mX + σX2 = mY + σY2 = 1.8.


Ob diese Aussage relevant ist, lasse ich dahingestellt. Denn: Aufgrund der stetigen Zunahme von H(Y) mit zunehmendem λ ist klar, dass für irgendeinen λ–Wert tatsächlich H(Y) = H(X) gelten muss.