Aufgaben:Aufgabe 3.6: Partitionierungsungleichung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(23 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
−
[[Datei:P_ID2812__Inf_A_3_5.png|right|]]
+
[[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: Partition Unequality) verwendet:  
+
Die  '''Kullback–Leibler–Distanz'''  (kurz KLD) wird auch in der „Partitionierungsungleichung”  (englisch:  "Partition Unequality")  verwendet:  
−
:* Wir gehen von der Menge
+
* 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.
  
−
$$X=\{ x_1,x_2,.....,x_M \}$$
+
* 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:
−
und den Wahrscheinlichkeitsfunktionen
+
:$$\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 .$$
  
−
$P_X(X) = P_X(x_1,x_2,....,x_M)$ ,
+
* 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}. $$
  
−
$Q_X(X) = Q_X(x_1,x_2,....,x_M)$
+
{{BlaueBox|TEXT=
−
aus, die in irgendeiner Form „ähnlich” sein sollen
+
$\text{Bitte beachten Sie:}$  Die  '''Partitionierungsungleichung'''  liefert  hinsichtlich der Kullback–Leibler–Distanzen folgende Größenrelation:
−
:* Die Menge $X$ unterteilen wir in die Partitionen $A_1, ..., A_K$ , die zueinander disjunkt sind und ein $vollständiges System$ ergeben:
+
:$$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}.$$}}
  
−
$\bigcup_{i=_1}^K A_i = X$ , $A_i \cap A_j = \phi$    für  $1 \leq i \neq j \leq K$
 
−
:* Die Wahrscheinlichkeitsfunktionen bezüglich der Partitionierungen $A=\{ A_1,A_2,.....,A_K \}$bezeichnen wir im Folgenden mit
 
  
−
$P_X^{ (A) } = [ P_X(A_1),.......,P_X(A_K)]$ ,  wobei    $P_X(A_i) = \sum\limits_{ x \epsilon A_i } P_X(x)$
+
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.
  
−
$Q_X^{ (A) } = [ Q_X(A_1),.......,Q_X(A_K)]$ ,  wobei    $Q_X(A_i) = \sum\limits_{ x \epsilon A_i } Q_X(x)$
+
*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\}$,
  
−
Die $Partitionierungsungleichung$ liefert folgende Größenrelation hinsichtlich der Kullback–Leibler–Distanzen:
+
*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) } )$.
  
−
$D(P_X^{ (A) } \parallel Q_X^{ (A) } ) \leq D(P_X \parallel Q_X)$
+
*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.
  
  
−
In der Aufgabe (a) soll die Kullback–Leibler–Distanz der beiden Wahrscheinlichkietsfunktionen $P_X(X)$ und $Q_X(X)$ für $X = \{0, 1, 2\} \Rightarrow  |X| = 3$ ermittelt werden. Anschließend soll die Menge $X$ 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\}$ ,
 
−
 
−
mit $K = 2$ partitioniert werden und es sollen die jeweiligen Kullback–Leibler–Distanzen
 
−
:* $D(P_X^{ (A) } \parallel Q_X^{ (A) } )$
 
−
 
−
:* $D(P_X^{ (B) } \parallel Q_X^{ (B) } )$ ,
 
−
 
−
:* $D(P_X^{ (C) } \parallel Q_X^{ (C) } )$
 
−
angegeben werden. In Aufgabe (e) wird schließlich nach den Bedingungen gefragt, damit in der obigen Ungleichung das Gleichheitszeichen zutrifft.
 
−
'''Hinweis:''' Die Aufgabe gehört zu
 
−
[http://www.lntwww.de/Informationstheorie/Einige_Vorbemerkungen_zu_zweidimensionalen_Zufallsgr%C3%B6%C3%9Fen Kapitel 3.1].Die Wahrscheinlichkeitsfunktionen können aus obiger Grafik abgelesen werden:
 
−
 
−
$P_X(X) = [1/4 , 1/2 , 1/4]$
 
−
 
−
$Q_X(X) = [1/8 , 3/4, 1/8]$
 
  
  
Zeile 53: Zeile 45:
  
  
 +
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:
 +
:$$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 59: 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 \parallel Q_X)$ = { 0.2075 3% } $bit$
+
$ D(P_X \hspace{0.05cm} \vert \vert \hspace{0.05cm}  Q_X) \ = \ $ { 0.2075 3% } $\ \rm bit$
  
−
{Welche KLD 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) } \parallel Q_X^{ (A) } )$ = { 0.0832 3% } $bit$
+
$D(P_X^{ (A) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (A) } ) \ = \ $ { 0.0832 3% } $\ \rm bit$
  
−
{Welche KLD ergibt sich für die Partitionierung  $ B_1 = \{1\}, A_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) } \parallel Q_X^{ (B) } )$ = { 0.2075 3% } $bit$
+
$D(P_X^{ (B) } \hspace{0.05cm} \vert \vert \hspace{0.05cm} Q_X^{ (B) } ) \ = \ $ { 0.2075 3% } $\ \rm bit$
−
 
 
  
−
{Welche KLD ergibt sich für die Partitionierung  $ C_1 = \{2\}, A_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 \epsilon A_i$ muss gelten : $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 88: Zeile 85:
 
{{ML-Kopf}}
 
{{ML-Kopf}}
  
−
'''1.'''  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 \parallel P_Y) = E [ log_2 \frac{P_X(X)}{P_Y(X)}] = \sum\limits_{ x \epsilon X} P_X(x) . log_2 \frac{P_X(x)}{P_Y(x)} =$$
 
  
−
$$\frac{1}{2} . log_2 \frac{1/2}{3/4} + 2 . \frac{1}{4} . log_2 \frac{1/4}{1/8}   +log_2 \frac{2}{3} + \frac{1}{2} . log_2(2) =$$
+
:$$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}.$$
  
−
$$1 -  \frac{1}{2} . log_2(3) = 0.2075 (bit)$$
 
  
  
−
'''2.'''  $Partitionierung  A  \Rightarrow  A_1 = \{0\}$ ,  $A_2 = \{ 1 , 2 \}$ :  Man erhält 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^{ (A) } \parallel Q_X^{ (A) } )$ =   \frac{1}{4} . log_2 \frac{1/4}{1/8} + \frac{3}{4} . log_2 \frac{3/4}{7/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} +
 +
\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}.$$  
  
−
$$ =  \frac{1}{4} . log_2 (2) +  \frac{3}{4} . log_2 \frac{6}{7} = 0.0832 (bit)$$
 
−
Es ergibt sich also eine kleinere KLD als in Teilaufgabe (a).
 
  
  
−
'''3.''' $Partitionierung  B \Rightarrow B_1 = \{1\}$ ,  $B_2 = \{ 0 , 2 \}$ : Man erhält die Wahrscheinlichkeitsfunktionen  $P_X^{ (B) } (X) = \{1/2 , 1/2\}$ und $Q_X^{ (B) } (X) = \{3/4 , 1/4\}$.
+
'''(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 (b) erhält man nun:  
+
*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} +
 +
\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&nbsp; '''(1)'''&nbsp; überein &nbsp; &rArr; &nbsp; Bei der  Mit Partitionierung&nbsp; $B$&nbsp; gilt das Gleichheitszeichen.
  
−
$$D(P_X^{ (B) } \parallel Q_X^{ (B) } ) =  \frac{1}{2} . log_2 \frac{1/2}{3/4} +  \frac{1}{2} . log_2 \frac{1/2}{1/4} = 0.2075$$
 
−
$\Rightarrow$ gleiches Ergebnis wie in Aufgabe (a) $\Rightarrow$ Bei Partitionierung (B) gilt das Gleichheitszeichen.
 
  
  
−
'''4.'''$Partitionierung  C \Rightarrow C_1 = \{2\}$ ,  $C_2 = \{ 0 , 1\}$ :  Man erhält  $P_X^{ (C) } (X) = \{1/4, 3/4\}$  , $Q_X^{ (C) } (X) = \{1/8, 7/8\}$ . also die gleichen Funktionen wie bei der Partitionierung  
+
'''(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>.
−
$A \Rightarrow  Lösungsvorschlag 1$.
 
  
  
−
'''5.'''  Partitionierung $B$ hat zum Ergebnis $D(P_X^{ (B) } \parallel Q_X^{ (B) } ) = D(P_X \parallel Q_X)$ geführt. Für diesen Fall ist
 
  
 +
'''(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(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(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} = \frac{2}{3}$,
+
*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(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$,
+
*Durch Verallgemeinerung erkennt man, dass&nbsp; <u>beide Lösungsvorschläge</u>&nbsp; richtig sind.
  
−
$\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$
 
−
'''6.'''
 
−
'''7.'''
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
−
[[Category:Aufgaben zu Informationstheorie |^3.1 Einige Vorbemerkungen zu zweidimensionalen Zufallsgrößen^]]
+
[[Category:Aufgaben zu Informationstheorie |^3.1 Allgemeines zu 2D-Zufallsgrößen^]]

Aktuelle Version vom 31. August 2021, 17: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

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.

Abgerufen von „http://www.lntwww.de/index.php?title=Aufgaben:Aufgabe_3.6:_Partitionierungsungleichung&oldid=32185“
  • Powered by MediaWiki