Aufgaben:Aufgabe 3.5: Kullback-Leibler-Distanz & Binominalverteilung

From LNTwww

P ID2759 Inf A 3 4 A.png

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 PX(X = μ) der hier betrachteten Binomialverteilung angegeben. In der Teilaufgabe (a) 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 λ:

  • 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 PX(X) ausreichend gut durch PY(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.

P ID2760 Inf A 3 4 B.png

In nebenstehender Ergebnistabelle ist die sog. Kullback–Leibler–Distanz D(PX||PY) in „bit” zwischen der Binomial–PMF PX und einigen Poisson–Näherungen PY (mit fünf verschiedenen Raten λ) eingetragen. Die jeweilige Entropie H(Y), die ebenfalls von der Rate λ abhängt, ist in der ersten Zeile angegeben.


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

Hinweis: Die Aufgabe gehört zu Kapitel 3.1. Um die numerischen Berechnungen in Grenzen zu halten, werden folgende Hilfsgrößen vorgegeben; „lg” bezeichnet den Logarithmus zur Basis 10:

$$A' \hspace{0.15cm} = \hspace{0.15cm} 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} +\\ + \hspace{0.15cm} 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.15cm} \underline {= 0.021944} \hspace{0.05cm},$$
$$B' \hspace{0.15cm} = \hspace{0.15cm} 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) +\\ + \hspace{0.15cm} 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) \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$ =

$p$ =

$m_x$ =

$\sigma^2_x$ =

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 bezeichnet) für λ = 1. Berücksichtigen Sie die angegebene Hilfsgröße A′.

$\lambda = 1:\ D$ =

$bit$

4

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

$\lambda = 1:\ H(Y)$ =

$bit$

5

Welche der folgenden Aussagen sind zutreffend?

H(Y)–Berechnung: Alle Terme haben gleiches Vorzeichen.
D(PX||PY)–Berechnung: Alle Terme haben 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}.$$

Damit 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 der Kullback–Leibler–Distanz 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:

$$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) \hspace{0.15cm} = \hspace{0.15cm} -{\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}' =\\ = \hspace{0.15cm} 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(μ).

6.  Zutreffend ist der Lösungsvorschlag 1. Auch aus der nachfolgenden Grafik ist ersichtlich, dass D(PX||PY) = 0.0182 bit von keinem anderen λ–Wert als λ = 1 unterschritten wird (grüne Kreuze).

P ID2761 Inf A 3 4 C.png

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. Anzumerken ist:

  • 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.