Exercise 3.6: Partitioning Inequality

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.05cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.05cm} x_M \}$ 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},$$

$$Q_X(X) =Q_X ( x_1, \hspace{0.05cm} x_2, \text{...} \hspace{0.05cm}, \hspace{0.05cm} 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:

$X = \big \{ \hspace{0.05cm} x_1, \hspace{0.05cm} x_2, ... \hspace{0.05cm}, \hspace{0.05cm} x_M \hspace{0.05cm} \big \}$ * Die Wahrscheinlichkeitsfunktionen bezüglich der Partitionierungen $A_1, A_2, \text{...} , A_K$ bezeichnen wir im Folgenden mit :'"`UNIQ-MathJax19-QINU`"' :'"`UNIQ-MathJax20-QINU`"' $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)$ Die $Partitionierungsungleichung$ liefert folgende Größenrelation hinsichtlich der Kullback–Leibler–Distanzen: $D(P_X^{ (A) } \parallel Q_X^{ (A) } ) \leq D(P_X \parallel Q_X)$ 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. ''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 – Kullback-Leibler-Distanz]]. *Die Angaben der Entropie $H(Y)$ und der Kullback–Leibler–Distanz $D( P_X \hspace{0.05cm}|| \hspace{0.05cm}P_Y)$ in obiger Grafik sind in „bit” zu verstehen. * Die in der Grafik mit „???" versehenen Felder sollen von Ihnen in dieser Aufgabe ergänzt werden. *Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein. '''Hinweis:''' Die Aufgabe gehört zu [http://en.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]$ ==='"`UNIQ--h-0--QINU`"'Fragebogen=== '"`UNIQ--quiz-00000002-QINU`"' ==='"`UNIQ--h-1--QINU`"'Musterlösung=== '"`UNIQ--html-00000003-QINU`"' '''1.''' Für die Kullback–Leibler–Distanz (KLD) gilt: '"`UNIQ-MathJax21-QINU`"' '"`UNIQ-MathJax22-QINU`"' '"`UNIQ-MathJax23-QINU`"' '''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: '"`UNIQ-MathJax24-QINU`"' '"`UNIQ-MathJax25-QINU`"' 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\}$. Analog zur Teilaufgabe (b) erhält man nun: '"`UNIQ-MathJax26-QINU`"' $\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 $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 $\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}$, $\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 also für alle $x \epsilon X$ gelten : $\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_1)}{Q_X(B_1)} $ , falls $ x \epsilon B_1$ $\frac{P_X(x)}{Q_X(x)} = \frac{P_X(B_2)}{Q_X(B_2)} $ , falls $ x \epsilon B_2$ Durch Verallgemeinerung erhält man, dass $beide Lösungsvorschläge$ richtig sind.