Aufgaben:Aufgabe 3.6: Partitionierungsungleichung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(14 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2812__Inf_A_3_5.png|right|Wahrscheinlichkeitsfunktionen <i>P<sub>X</sub></i> und <i>Q<sub>X</sub></i>]]
+
[[Datei:P_ID2812__Inf_A_3_5.png|right|frame|Wahrscheinlichkeitsfunktionen&nbsp; $P_X$,&nbsp; $Q_X$]]
Die ''Kullback–Leibler–Distanz'' (kurz KLD) wird auch in der „Partitionierungsungleichung” (englisch: ''Partition Unequality'') verwendet:  
+
Die&nbsp; '''Kullback–Leibler–Distanz'''&nbsp; (kurz KLD) wird auch in der „Partitionierungsungleichung”&nbsp; (englisch:&nbsp; "Partition Unequality")&nbsp; verwendet:  
* Wir gehen von der Menge $X =  \{ x_1, \hspace{0.05cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.05cm} x_M  \}$ und den Wahrscheinlichkeitsfunktionen  
+
* Wir gehen von der Menge&nbsp; $X =  \{ x_1, \hspace{0.15cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.15cm} x_M  \}$&nbsp; und den Wahrscheinlichkeitsfunktionen  
:$$P_X(X) = P_X (  x_1, \hspace{0.05cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.05cm} x_M  )\hspace{0.05cm},$$
+
:$$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.05cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.05cm} x_M  ), $$  
+
:$$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&nbsp; $X$&nbsp; unterteilen wir in die Partitionen&nbsp; $A_1, \text{...} ,&nbsp; A_K$, die zueinander&nbsp; [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Disjunkte_Mengen|disjunkt]]&nbsp; sind und ein&nbsp; [[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Vollst.C3.A4ndiges_System|vollständiges System]]&nbsp; ergeben:
:$X$$ = \big \{ \hspace{0.05cm} x_1, \hspace{0.05cm} x_2, ... \hspace{0.05cm}, \hspace{0.05cm} x_M  \hspace{0.05cm} \big \}$$
+
:$$\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&nbsp; $A_1,\ A_2, \text{...} ,\ A_K$&nbsp; bezeichnen wir im Folgenden mit  
:$$P_X^{\hspace{0.15cm}(A)} = \left [ P_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm},P_X (  A_K  ) \right ],\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},$$
+
:$$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)}= \left [ Q_X (  A_1  )\hspace{0.05cm}, \hspace{0.05cm}...\hspace{0.1cm},Q_X (  A_K  ) \right ],\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}. $$
+
:$$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 folgende Größenrelation hinsichtlich der Kullback–Leibler–Distanzen:
+
$\text{Bitte beachten Sie:}$ &nbsp;Die&nbsp; '''Partitionierungsungleichung'''&nbsp; 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\}$ &nbsp;&rArr;&nbsp; $|X| = 3$ ermittelt werden. Anschließend soll die Menge $X$ mit $K = 2$ partitioniert werden entsprechend
+
In Teilaufgabe&nbsp; '''(1)'''&nbsp; soll die Kullback–Leibler–Distanz der beiden Wahrscheinlichkeitsfunktionen&nbsp; $P_X(X)$&nbsp; und&nbsp; $Q_X(X)$&nbsp; für&nbsp; $X = \{0,\ 1,\ 2\}$ &nbsp; &rArr; &nbsp; $|X| = 3$&nbsp; ermittelt werden.  
* $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:
+
*Danach soll die Menge&nbsp; $X$&nbsp; mit&nbsp; $K = 2$&nbsp; partitioniert werden entsprechend
* $D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } )$,
+
:* $A = \{A_1 ,\ A_2\}$&nbsp;  mit&nbsp;  $A_1 =\{0\}$&nbsp;  und&nbsp; $A_2 = \{ 1,\ 2 \}$ ,  
* $D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } )$,
+
:* $B = \{B_1 ,\ B_2\}$&nbsp;  mit&nbsp;  $B_1 =\{1\}$&nbsp;  und&nbsp; $B_2 = \{ 0,\ 2 \}$,  
* $D(P_X^{ (C) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (C) } )$.
+
:* $C = \{C_1 ,\ C_2\}$&nbsp;  mit&nbsp;  $C_1 =\{2\}$&nbsp;  und&nbsp; $C_2 = \{ 0,\ 1\}$,
  
In der Teilaufgabe (5) wird schließlich nach den Bedingungen gefragt, damit in der obigen Ungleichung das Gleichheitszeichen zutrifft.
+
*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&nbsp; '''(5)'''&nbsp;  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 [[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]].
+
 
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
 
 +
 
 +
 
 +
 
 +
 
 +
Hinweise:  
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgrößen|Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen]].
 +
*Insbesondere wird Bezug genommen auf die Seite&nbsp; [[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]].
 +
 
*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 (KLD) allgemein.
+
{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&nbsp; $ 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&nbsp; $ 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&nbsp; $ 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&nbsp; $A$.
- Das gleiche Ergebnis wie für die Partitionierung $B$.
+
- Das gleiche Ergebnis wie für die Partitionierung&nbsp; $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&nbsp; $K$&nbsp; die Gleichheit?
 
|type="[]"}
 
|type="[]"}
+ Es müssen $|X|$ Gleichungen erfüllt sein.
+
+ Es müssen&nbsp; $|X|$&nbsp; Gleichungen erfüllt sein.
+ Für $x \in A_i$ muss gelten: &nbsp; $P_X(x)/Q_X(x) = P_X(A_i)/ Q_X(A_i)$
+
+ Für alle Mengenelemente &nbsp; $x \in A_i$&nbsp; muss gelten: &nbsp; $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)'''&nbsp;  Für die Kullback–Leibler–Distanz (KLD) gilt:
+
'''(1)'''&nbsp;  Für die Kullback–Leibler–Distanz der nicht partitionierten Mengen&nbsp; $X$&nbsp; und&nbsp; $Y$&nbsp; 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)'''&nbsp;  Mit der '''Partitionierung A''' &nbsp; &rArr; &nbsp;  $A_1 = \{0\}$ ,  $A_2 = \{ 1 , 2 \}$ erhält man die Wahrscheinlichkeitsfunktionen $P_X^{ (A) } (X) = \{1/4 , 3/4\}$ und $Q_X^{ (A) } (X) = \{1/8 , 7/8\}$.  Daraus folgt:  
+
 
 +
 
 +
'''(2)'''&nbsp;  Mit der Partitionierung&nbsp; $A$ &nbsp; &rArr; &nbsp;  $A_1 = \{0\}$ ,&nbsp; $A_2 = \{ 1 , 2 \}$&nbsp; erhält man&nbsp; $P_X^{ (A) } (X) = \{1/4 , \ 3/4\}$&nbsp; und&nbsp; $Q_X^{ (A) } (X) = \{1/8 , \ 7/8\}$.&nbsp; 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)'''&nbsp; Mit der '''Partitionierung B''' &nbsp; &rArr; &nbsp;  $B_1 = \{1\}$ ,  $B_2 = \{ 0 , 2 \}$ erhält man 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:  
+
 
 +
 
 +
'''(3)'''&nbsp; Mit Partitionierung&nbsp; $B$ &nbsp; &rArr; &nbsp;  $B_1 = \{1\}$ ,&nbsp; $B_2 = \{ 0 ,\ 2 \}$&nbsp; lauten die  Wahrscheinlichkeitsfunktionen&nbsp; $P_X^{ (B) } (X) = \{1/2 , \ 1/2\}$&nbsp; und&nbsp; $Q_X^{ (B) } (X) = \{3/4 , \ 1/4\}$.&nbsp;
 +
*Analog zur Teilaufgabe&nbsp; '''(2)'''&nbsp; 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 &nbsp; &rArr; &nbsp; Bei der '''Partitionierung B''' gilt das Gleichheitszeichen.
+
*Das Ergebnis stimmt mit dem der Teilaufgabe&nbsp; '''(1)'''&nbsp; überein &nbsp; &rArr; &nbsp; Bei der Mit Partitionierung&nbsp; $B$&nbsp; gilt das Gleichheitszeichen.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Mit der  Mit Partitionierung&nbsp; $C$ &nbsp; &rArr; &nbsp;  $C_1 = \{2\}$ ,  $C_2 = \{ 0 , \ 1\}$&nbsp; erhält man&nbsp;  $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&nbsp; $A$ &nbsp; &rArr; &nbsp; <u>Lösungsvorschlag 1</u>.
  
'''(4)'''&nbsp; Mit der '''Partitionierung C''' &nbsp; &rArr; &nbsp;  $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''' &nbsp; &rArr; &nbsp; <u>Lösungsvorschlag 1</u>.
 
  
  
'''(5)'''&nbsp; Die '''Partitionierung C''' 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  
+
'''(5)'''&nbsp; DiePartitionierung&nbsp; $B$&nbsp; hat zum Ergebnis&nbsp; $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 also für alle $x \in X$ gelten :  
+
*Es muss demnach für alle&nbsp; $x \in X$&nbsp; 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 erhält man, dass <u>beide Lösungsvorschläge</u> richtig sind.
+
*Durch Verallgemeinerung erkennt man, dass&nbsp; <u>beide Lösungsvorschläge</u>&nbsp; richtig sind.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}
Zeile 116: Zeile 134:
  
  
[[Category:Aufgaben zu Informationstheorie |^3.1 Vorbemerkungen zu 2D-Zufallsgrößen^]]
+
[[Category:Aufgaben zu Informationstheorie |^3.1 Allgemeines zu 2D-Zufallsgrößen^]]

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

1

Berechnen Sie die Kullback–Leibler–Distanz allgemein.

$ D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X) \ = \ $

$\ \rm bit$

2

Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung  $ A_1 = \{0\},\ A_2 = \{1, 2\}$?

$D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } ) \ = \ $

$\ \rm bit$

3

Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung  $ B_1 = \{1\}, \ B_2 = \{0, 2\}$?

$D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } ) \ = \ $

$\ \rm bit$

4

Welche Kullback–Leibler–Distanz ergibt sich für die Partitionierung  $ C_1 = \{2\},\ C_2 = \{0, 1\}$?

Das gleiche Ergebnis wie für die Partitionierung  $A$.
Das gleiche Ergebnis wie für die Partitionierung  $B$.
Ein ganz anderes Ergebnis.

5

Unter welchen Bedingungen ergibt sich für allgemeines  $K$  die Gleichheit?

Es müssen  $|X|$  Gleichungen erfüllt sein.
Für alle Mengenelemente   $x \in A_i$  muss gelten:   $P_X(x)/Q_X(x) = P_X(A_i)/ Q_X(A_i)$.


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.