Aufgaben:Aufgabe 3.6: Partitionierungsungleichung: Unterschied zwischen den Versionen
Aus LNTwww
| (10 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
}} | }} | ||
| − | [[Datei:P_ID2812__Inf_A_3_5.png|right|frame|Wahrscheinlichkeitsfunktionen $P_X$, $Q_X$]] | + | [[Datei:P_ID2812__Inf_A_3_5.png|right|frame|Wahrscheinlichkeitsfunktionen $P_X$, $Q_X$]] |
| − | Die ''Kullback–Leibler–Distanz'' (kurz KLD) wird auch in der „Partitionierungsungleichung” (englisch: | + | Die '''Kullback–Leibler–Distanz''' (kurz KLD) wird auch in der „Partitionierungsungleichung” (englisch: "Partition Unequality") verwendet: |
| − | * Wir gehen von der Menge $X = \{ x_1, \hspace{0. | + | * Wir gehen von der Menge $X = \{ x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M \}$ und den Wahrscheinlichkeitsfunktionen |
| − | :$$P_X(X) = P_X ( x_1, \hspace{0. | + | :$$P_X(X) = P_X ( x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M )\hspace{0.05cm},$$ |
| − | :$$Q_X(X) =Q_X ( x_1, \hspace{0. | + | :$$Q_X(X) =Q_X ( x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M ), $$ |
| − | aus, die „in irgendeiner Form ähnlich” sein sollen. | + | :aus, die „in irgendeiner Form ähnlich” sein sollen. |
| − | * Die Menge $X$ unterteilen wir in die Partitionen $A_1, \text{...} , A_K$ , die zueinander [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjunkt]] sind und ein [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|vollständiges System]] ergeben: | + | * Die Menge $X$ unterteilen wir in die Partitionen $A_1, \text{...} , A_K$, die zueinander [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjunkt]] sind und ein [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|vollständiges System]] ergeben: |
| − | :$$ | + | :$$\bigcup_{i=1}^{K} = X, \hspace{0.5cm} A_i \cap A_j = {\it \phi} \hspace{0.25cm}\text{für}\hspace{0.25cm} 1 \le i \ne j \le K .$$ |
| − | * Die Wahrscheinlichkeitsfunktionen bezüglich der Partitionierungen $A_1, A_2, \text{...} , A_K$ bezeichnen wir im Folgenden mit | + | * Die Wahrscheinlichkeitsfunktionen bezüglich der Partitionierungen $A_1,\ A_2, \text{...} ,\ A_K$ bezeichnen wir im Folgenden mit |
| − | :$$P_X^{\hspace{0.15cm}(A)} = \ | + | :$$P_X^{\hspace{0.15cm}(A)} = \big [ P_X ( A_1 )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},P_X ( A_K ) \big ],\hspace{0.05cm}\hspace{0.5cm}{\rm wobei}\hspace{0.15cm} P_X ( A_i ) = \sum_{ x \in A_i} P_X ( x )\hspace{0.05cm},$$ |
| − | :$$Q_X^{\hspace{0.15cm}(A)}= \ | + | :$$Q_X^{\hspace{0.15cm}(A)}= \big [ Q_X ( A_1 )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},Q_X ( A_K ) \big ],\hspace{0.05cm}\hspace{0.40cm}{\rm wobei}\hspace{0.15cm} Q_X ( A_i ) = \sum_{ x \in A_i} Q_X ( x )\hspace{0.05cm}. $$ |
{{BlaueBox|TEXT= | {{BlaueBox|TEXT= | ||
| − | Die '''Partitionierungsungleichung''' liefert | + | $\text{Bitte beachten Sie:}$ Die '''Partitionierungsungleichung''' liefert hinsichtlich der Kullback–Leibler–Distanzen folgende Größenrelation: |
:$$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) | :$$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) | ||
\hspace{0.25cm}\le \hspace{0.25cm}D(P_X \hspace{0.05cm}\vert \vert \hspace{0.05cm} Q_X) \hspace{0.05cm}.$$}} | \hspace{0.25cm}\le \hspace{0.25cm}D(P_X \hspace{0.05cm}\vert \vert \hspace{0.05cm} Q_X) \hspace{0.05cm}.$$}} | ||
| − | In Teilaufgabe (1) soll die Kullback–Leibler–Distanz der beiden Wahrscheinlichkeitsfunktionen $P_X(X)$ und $Q_X(X)$ für $X = \{0, 1, 2\}$ ⇒ $|X| = 3$ ermittelt werden. | + | In Teilaufgabe '''(1)''' soll die Kullback–Leibler–Distanz der beiden Wahrscheinlichkeitsfunktionen $P_X(X)$ und $Q_X(X)$ für $X = \{0,\ 1,\ 2\}$ ⇒ $|X| = 3$ ermittelt werden. |
| − | |||
| − | |||
| − | |||
| − | + | *Danach soll die Menge $X$ mit $K = 2$ partitioniert werden entsprechend | |
| − | * $ | + | :* $A = \{A_1 ,\ A_2\}$ mit $A_1 =\{0\}$ und $A_2 = \{ 1,\ 2 \}$ , |
| − | * $ | + | :* $B = \{B_1 ,\ B_2\}$ mit $B_1 =\{1\}$ und $B_2 = \{ 0,\ 2 \}$, |
| − | * $ | + | :* $C = \{C_1 ,\ C_2\}$ mit $C_1 =\{2\}$ und $C_2 = \{ 0,\ 1\}$, |
| − | + | *Anschließend sollen die jeweiligen Kullback–Leibler–Distanzen angegeben werden: | |
| + | :* $D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } )$, | ||
| + | :* $D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } )$, | ||
| + | :* $D(P_X^{ (C) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (C) } )$. | ||
| + | *In der Teilaufgabe '''(5)''' wird schließlich nach den Bedingungen gefragt, die erfüllt sein müssen, damit in der obigen Ungleichung das Gleichheitszeichen zutrifft. | ||
| − | + | ||
| − | *Die Aufgabe gehört zum Kapitel [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu | + | |
| − | *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 – Kullback-Leibler-Distanz]]. | + | |
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | Hinweise: | ||
| + | *Die Aufgabe gehört zum Kapitel [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu zweidimensionalen 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 – Kullback-Leibler-Distanz]]. | ||
*Die beiden Wahrscheinlichkeitsfunktionen können aus obiger Grafik wie folgt abgelesen werden: | *Die beiden Wahrscheinlichkeitsfunktionen können aus obiger Grafik wie folgt abgelesen werden: | ||
| − | :$$P_X(X) = [1/4 , 1/2 , 1/4],\hspace{0.5cm} Q_X(X) = [1/8 , 3/4, 1/8].$$ | + | :$$P_X(X) = \big [1/4 , \ 1/2 , \ 1/4 \big ],\hspace{0.5cm} Q_X(X) = \big [1/8, \ 3/4, \ 1/8 \big].$$ |
| Zeile 48: | Zeile 57: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Berechnen Sie die Kullback–Leibler–Distanz | + | {Berechnen Sie die Kullback–Leibler–Distanz allgemein. |
|type="{}"} | |type="{}"} | ||
$ D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X) \ = \ $ { 0.2075 3% } $\ \rm bit$ | $ D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X) \ = \ $ { 0.2075 3% } $\ \rm bit$ | ||
| − | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ A_1 = \{0\}, A_2 = \{1, 2\}$? | + | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ A_1 = \{0\},\ A_2 = \{1, 2\}$? |
|type="{}"} | |type="{}"} | ||
$D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } ) \ = \ $ { 0.0832 3% } $\ \rm bit$ | $D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } ) \ = \ $ { 0.0832 3% } $\ \rm bit$ | ||
| − | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ B_1 = \{1\}, B_2 = \{0, 2\}$? | + | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ B_1 = \{1\}, \ B_2 = \{0, 2\}$? |
|type="{}"} | |type="{}"} | ||
$D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } ) \ = \ $ { 0.2075 3% } $\ \rm bit$ | $D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } ) \ = \ $ { 0.2075 3% } $\ \rm bit$ | ||
| − | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ C_1 = \{2\}, C_2 = \{0, 1\}$? | + | {Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung $ C_1 = \{2\},\ C_2 = \{0, 1\}$? |
| − | |type=" | + | |type="()"} |
| − | + Das gleiche Ergebnis wie für die Partitionierung $A$. | + | + Das gleiche Ergebnis wie für die Partitionierung $A$. |
| − | - Das gleiche Ergebnis wie für die Partitionierung $B$. | + | - Das gleiche Ergebnis wie für die Partitionierung $B$. |
- Ein ganz anderes Ergebnis. | - Ein ganz anderes Ergebnis. | ||
| − | {Unter welchen Bedingungen ergibt sich für allgemeines $K$ die Gleichheit? | + | {Unter welchen Bedingungen ergibt sich für allgemeines $K$ die Gleichheit? |
|type="[]"} | |type="[]"} | ||
| − | + Es müssen $|X|$ Gleichungen erfüllt sein. | + | + Es müssen $|X|$ Gleichungen erfüllt sein. |
| − | + Für $x \in A_i$ muss gelten: $P_X(x)/Q_X(x) = P_X(A_i)/ Q_X(A_i)$ | + | + Für alle Mengenelemente $x \in A_i$ muss gelten: $P_X(x)/Q_X(x) = P_X(A_i)/ Q_X(A_i)$. |
</quiz> | </quiz> | ||
| Zeile 76: | Zeile 85: | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Für die Kullback–Leibler–Distanz | + | '''(1)''' Für die Kullback–Leibler–Distanz der nicht partitionierten Mengen $X$ und $Y$ gilt: |
:$$D(P_X \hspace{0.05cm} || \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{x \hspace{0.05cm}\in \hspace{0.05cm}X} | :$$D(P_X \hspace{0.05cm} || \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{x \hspace{0.05cm}\in \hspace{0.05cm}X} | ||
| Zeile 87: | Zeile 96: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | '''(2)''' Mit der | + | |
| + | |||
| + | '''(2)''' Mit der Partitionierung $A$ ⇒ $A_1 = \{0\}$ , $A_2 = \{ 1 , 2 \}$ erhält man $P_X^{ (A) } (X) = \{1/4 , \ 3/4\}$ und $Q_X^{ (A) } (X) = \{1/8 , \ 7/8\}$. Daraus folgt: | ||
:$$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) = \frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/4}{1/8} + | :$$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) = \frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/4}{1/8} + | ||
| Zeile 93: | Zeile 104: | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | '''(3)''' Mit | + | |
| + | |||
| + | '''(3)''' Mit Partitionierung $B$ ⇒ $B_1 = \{1\}$ , $B_2 = \{ 0 ,\ 2 \}$ lauten die Wahrscheinlichkeitsfunktionen $P_X^{ (B) } (X) = \{1/2 , \ 1/2\}$ und $Q_X^{ (B) } (X) = \{3/4 , \ 1/4\}$. | ||
| + | *Analog zur Teilaufgabe '''(2)''' erhält man so: | ||
:$$D(P_X^{\hspace{0.15cm}(B)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(B)}) = \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{3/4} + | :$$D(P_X^{\hspace{0.15cm}(B)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(B)}) = \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{3/4} + | ||
\frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{1/4} \hspace{0.15cm} \underline {=0.2075\,{\rm (bit)}} | \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{1/4} \hspace{0.15cm} \underline {=0.2075\,{\rm (bit)}} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
| − | Das Ergebnis stimmt mit dem der Teilaufgabe (1) überein ⇒ Bei der ''' | + | *Das Ergebnis stimmt mit dem der Teilaufgabe '''(1)''' überein ⇒ Bei der Mit Partitionierung $B$ gilt das Gleichheitszeichen. |
| + | |||
| + | |||
| + | |||
| + | '''(4)''' Mit der Mit Partitionierung $C$ ⇒ $C_1 = \{2\}$ , $C_2 = \{ 0 , \ 1\}$ erhält man $P_X^{ (C) } (X) = \{1/4, \ 3/4\}$ , $Q_X^{ (C) } (X) = \{1/8, \ 7/8\}$, <br>also die gleichen Funktionen wie bei der Partitionierung $A$ ⇒ <u>Lösungsvorschlag 1</u>. | ||
| − | |||
| − | '''(5)''' | + | '''(5)''' DiePartitionierung $B$ hat zum Ergebnis $D(P_X^{ (B) } \hspace{0.05cm} || \hspace{0.05cm}Q_X^{ (B) } ) = D(P_X \hspace{0.05cm} || \hspace{0.05cm}Q_X)$ geführt. |
| + | *Für diesen Fall ist also | ||
:$$\frac{P_X(1)}{Q_X(1)} = \frac{1/2}{3/4} = \frac{2}{3}, \ \frac{P_X(B_1)}{Q_X(B_1)} = \frac{1/2}{3/4} = {2}/{3},$$ | :$$\frac{P_X(1)}{Q_X(1)} = \frac{1/2}{3/4} = \frac{2}{3}, \ \frac{P_X(B_1)}{Q_X(B_1)} = \frac{1/2}{3/4} = {2}/{3},$$ | ||
:$$\frac{P_X(0)}{Q_X(0)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2,$$ | :$$\frac{P_X(0)}{Q_X(0)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2,$$ | ||
:$$\frac{P_X(2)}{Q_X(2)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2.$$ | :$$\frac{P_X(2)}{Q_X(2)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2.$$ | ||
| − | Es muss | + | *Es muss demnach für alle $x \in X$ gelten: |
:$$\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_1)}{Q_X(B_1)}, \text{falls } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_2)}{Q_X(B_2)}, \text{falls } x \in B_2.$$ | :$$\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_1)}{Q_X(B_1)}, \text{falls } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_2)}{Q_X(B_2)}, \text{falls } x \in B_2.$$ | ||
| − | Durch Verallgemeinerung | + | *Durch Verallgemeinerung erkennt man, dass <u>beide Lösungsvorschläge</u> richtig sind. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 31. August 2021, 16:20 Uhr
Wahrscheinlichkeitsfunktionen $P_X$, $Q_X$
Die Kullback–Leibler–Distanz (kurz KLD) wird auch in der „Partitionierungsungleichung” (englisch: "Partition Unequality") verwendet:
- Wir gehen von der Menge $X = \{ x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M \}$ und den Wahrscheinlichkeitsfunktionen
- $$P_X(X) = P_X ( x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M )\hspace{0.05cm},$$
- $$Q_X(X) =Q_X ( x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M ), $$
- aus, die „in irgendeiner Form ähnlich” sein sollen.
- Die Menge $X$ unterteilen wir in die Partitionen $A_1, \text{...} , A_K$, die zueinander disjunkt sind und ein vollständiges System ergeben:
- $$\bigcup_{i=1}^{K} = X, \hspace{0.5cm} A_i \cap A_j = {\it \phi} \hspace{0.25cm}\text{für}\hspace{0.25cm} 1 \le i \ne j \le K .$$
- Die Wahrscheinlichkeitsfunktionen bezüglich der Partitionierungen $A_1,\ A_2, \text{...} ,\ A_K$ bezeichnen wir im Folgenden mit
- $$P_X^{\hspace{0.15cm}(A)} = \big [ P_X ( A_1 )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},P_X ( A_K ) \big ],\hspace{0.05cm}\hspace{0.5cm}{\rm wobei}\hspace{0.15cm} P_X ( A_i ) = \sum_{ x \in A_i} P_X ( x )\hspace{0.05cm},$$
- $$Q_X^{\hspace{0.15cm}(A)}= \big [ Q_X ( A_1 )\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.1cm},Q_X ( A_K ) \big ],\hspace{0.05cm}\hspace{0.40cm}{\rm wobei}\hspace{0.15cm} Q_X ( A_i ) = \sum_{ x \in A_i} Q_X ( x )\hspace{0.05cm}. $$
$\text{Bitte beachten Sie:}$ Die Partitionierungsungleichung liefert hinsichtlich der Kullback–Leibler–Distanzen folgende Größenrelation:
- $$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) \hspace{0.25cm}\le \hspace{0.25cm}D(P_X \hspace{0.05cm}\vert \vert \hspace{0.05cm} Q_X) \hspace{0.05cm}.$$
In Teilaufgabe (1) soll die Kullback–Leibler–Distanz der beiden Wahrscheinlichkeitsfunktionen $P_X(X)$ und $Q_X(X)$ für $X = \{0,\ 1,\ 2\}$ ⇒ $|X| = 3$ ermittelt werden.
- Danach soll die Menge $X$ mit $K = 2$ partitioniert werden entsprechend
- $A = \{A_1 ,\ A_2\}$ mit $A_1 =\{0\}$ und $A_2 = \{ 1,\ 2 \}$ ,
- $B = \{B_1 ,\ B_2\}$ mit $B_1 =\{1\}$ und $B_2 = \{ 0,\ 2 \}$,
- $C = \{C_1 ,\ C_2\}$ mit $C_1 =\{2\}$ und $C_2 = \{ 0,\ 1\}$,
- Anschließend sollen die jeweiligen Kullback–Leibler–Distanzen angegeben werden:
- $D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } )$,
- $D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } )$,
- $D(P_X^{ (C) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (C) } )$.
- In der Teilaufgabe (5) wird schließlich nach den Bedingungen gefragt, die erfüllt sein müssen, damit in der obigen Ungleichung das Gleichheitszeichen zutrifft.
Hinweise:
- Die Aufgabe gehört zum Kapitel Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen.
- Insbesondere wird Bezug genommen auf die Seite Relative Entropie – Kullback-Leibler-Distanz.
- Die beiden Wahrscheinlichkeitsfunktionen können aus obiger Grafik wie folgt abgelesen werden:
- $$P_X(X) = \big [1/4 , \ 1/2 , \ 1/4 \big ],\hspace{0.5cm} Q_X(X) = \big [1/8, \ 3/4, \ 1/8 \big].$$
Fragebogen
Musterlösung
(1) Für die Kullback–Leibler–Distanz der nicht partitionierten Mengen $X$ und $Y$ gilt:
- $$D(P_X \hspace{0.05cm} || \hspace{0.05cm}P_Y) = {\rm E} \left [ {\rm log}_2 \hspace{0.1cm} \frac{P_X(X)}{P_Y(X)}\right ] \hspace{0.2cm}=\hspace{0.2cm} \sum_{x \hspace{0.05cm}\in \hspace{0.05cm}X} P_X(x) \cdot {\rm log}_2 \hspace{0.1cm} \frac{P_X(x)}{P_Y(x)}$$
- $$\Rightarrow D(P_X \hspace{0.05cm} || \hspace{0.05cm}P_Y) = \hspace{-0.15cm} \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{3/4} + 2 \cdot \frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/4}{1/8} = \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{2}{3} + \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} (2) = 1- \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} (3) \hspace{0.15cm} \underline {=0.2075\,{\rm (bit)}} \hspace{0.05cm}.$$
(2) Mit der Partitionierung $A$ ⇒ $A_1 = \{0\}$ , $A_2 = \{ 1 , 2 \}$ erhält man $P_X^{ (A) } (X) = \{1/4 , \ 3/4\}$ und $Q_X^{ (A) } (X) = \{1/8 , \ 7/8\}$. Daraus folgt:
- $$D(P_X^{\hspace{0.15cm}(A)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(A)}) = \frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/4}{1/8} + \frac{3}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{3/4}{7/8} =\frac{1}{4}\cdot {\rm log}_2 \hspace{0.1cm} (2) + \frac{3}{4}\cdot {\rm log}_2 \hspace{0.1cm} \frac{6}{7} \hspace{0.15cm} \underline {=0.0832\,{\rm (bit)}} \hspace{0.05cm}.$$
(3) Mit Partitionierung $B$ ⇒ $B_1 = \{1\}$ , $B_2 = \{ 0 ,\ 2 \}$ lauten die Wahrscheinlichkeitsfunktionen $P_X^{ (B) } (X) = \{1/2 , \ 1/2\}$ und $Q_X^{ (B) } (X) = \{3/4 , \ 1/4\}$.
- Analog zur Teilaufgabe (2) erhält man so:
- $$D(P_X^{\hspace{0.15cm}(B)} \hspace{0.05cm}|| \hspace{0.05cm} Q_X^{\hspace{0.15cm}(B)}) = \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{3/4} + \frac{1}{2}\cdot {\rm log}_2 \hspace{0.1cm} \frac{1/2}{1/4} \hspace{0.15cm} \underline {=0.2075\,{\rm (bit)}} \hspace{0.05cm}.$$
- Das Ergebnis stimmt mit dem der Teilaufgabe (1) überein ⇒ Bei der Mit Partitionierung $B$ gilt das Gleichheitszeichen.
(4) Mit der Mit Partitionierung $C$ ⇒ $C_1 = \{2\}$ , $C_2 = \{ 0 , \ 1\}$ erhält man $P_X^{ (C) } (X) = \{1/4, \ 3/4\}$ , $Q_X^{ (C) } (X) = \{1/8, \ 7/8\}$,
also die gleichen Funktionen wie bei der Partitionierung $A$ ⇒ Lösungsvorschlag 1.
(5) DiePartitionierung $B$ hat zum Ergebnis $D(P_X^{ (B) } \hspace{0.05cm} || \hspace{0.05cm}Q_X^{ (B) } ) = D(P_X \hspace{0.05cm} || \hspace{0.05cm}Q_X)$ geführt.
- Für diesen Fall ist also
- $$\frac{P_X(1)}{Q_X(1)} = \frac{1/2}{3/4} = \frac{2}{3}, \ \frac{P_X(B_1)}{Q_X(B_1)} = \frac{1/2}{3/4} = {2}/{3},$$
- $$\frac{P_X(0)}{Q_X(0)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2,$$
- $$\frac{P_X(2)}{Q_X(2)} = \frac{1/4}{1/8} = 2, \ \frac{P_X(B_2)}{Q_X(B_2)} = \frac{1/2}{1/4} = 2.$$
- Es muss demnach für alle $x \in X$ gelten:
- $$\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_1)}{Q_X(B_1)}, \text{falls } x \in B_1, \hspace{0.5cm}\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_2)}{Q_X(B_2)}, \text{falls } x \in B_2.$$
- Durch Verallgemeinerung erkennt man, dass beide Lösungsvorschläge richtig sind.
