Bedingte Entropie

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Die bedingte Entropie einer Zufallsvariable $X$ gegeben eines Ereignisses $A$ bzw. einer Zufallsvariablen $Y$ ist die Unsicherheit über $X$ , die verbleibt, wenn $A$ bzw. $Y$ bereits bekannt ist. Sind $X$ und $Y$ stochastisch unabhängig, dann bleibt die Entropie von $X$ vollständig erhalten.

[Bearbeiten] Definition

Es sei $X$ eine diskrete Zufallsvariable und sei $M$ ihr Wertevorrat, d.h. $M$ ist eine höchstens abzählbare Menge mit $P(X\in M)=1$ . $X$ soll jedes Element von $M$ mit positiver Wahrscheinlichkeit annehmen. Dann ist die Entropie von $X$ durch

$H(X) := -\sum_{x\in M}P(X=x)\log P(X=x)$

definiert.

Es sei nun $A$ ein Ereignis mit $P (A) > 0$ . Dann definiert man die bedingte Entropie von $X$ gegeben $A$ durch Ersetzen der Wahrscheinlichkeit durch die bedingte Wahrscheinlichkeit, d.h.

$H(X|A) := -\sum_{x\in M}P(X=x|A)\log P(X=x|A)$ .

Jetzt sei $Y$ eine diskrete Zufallsvariable mit Wertevorrat $L$ . Dann ist die bedingte Entropie von $X$ gegeben $Y$ definiert als gewichtetes Mittel der bedingten Entropien von $X$ gegeben den Ereignissen $Y = y$ für $y\in L$ , d.h.

$H(X|Y) := \sum_{y\in L:P(Y=y)>0}P(Y=y)H(X|Y=y)$ .

[Bearbeiten] Eigenschaften

Ein gedächtnisloser Kanal verbindet zwei Quellen. Die Transinformation I(x;y) ist diejenige Information, die von X gesendet und auch von Y empfangen wurde.

Eine einfache Rechnung zeigt

H (X | Y) = H (X, Y) - H (Y)

also ist die Unsicherheit von $X$ gegeben $Y$ gleich der Unsicherheit von $X$ und $Y$ abzüglich der Unsicherheit von $Y$ .

Es ist $H(X|Y) \leq H(X)$ mit Gleichheit genau dann, wenn $X$ und $Y$ stochastisch unabhängig sind. Dies folgt aus der Tatsache, dass $H (X, Y) = H (X) + H (Y)$ genau dann gilt, wenn $X$ und $Y$ stochastisch unabhängig sind. Außerdem bedeutet es, dass $H (Y) = H (Y | X)$ ist, also die komplette empfangene Information nur Fehlinformation ist. Analog geht die komplette Information von der Quelle X verloren, so dass dann auch keine Transinformation vorhanden ist.

Außerdem gilt

$H(X|Y) \geq 0$ ,

mit Gleichheit genau dann, wenn $X$ funktional von $Y$ abhängt, d.h. $X = f (Y)$ für eine Funktion $f$ .

[Bearbeiten] Blockentropie

Übertragen auf eine multivariate Zufallsvariable $X$ der Länge $k$ , als Darstellung für einen $k$ -Block von Symbolen $(x_1,\dots,x_k)$ , lässt sich die bedingte Entropie $h k$ definieren als die Unsicherheit eines Symbols $x k + 1$ (nach einem bestimmten vorgegebenen $k$ -Block):

h k : = H k + 1 - H k

mit

h 0 : = H 1

wobei $H i$ die Blockentropie bezeichnet. Für die bedingte Entropie $h 1$ , also die Unsicherheit eines Symbols nach einem $1$ -Block, folgt:

h 1 = H 2 - H 1 = H (X) + H (Y | X) - H (X) = H (Y | X)

Die Definitionen der Blockentropie und der bedingten Entropie sind im Grenzübergang gleichwertig, vgl. Quellentropie.

In engem Zusammenhang zur bedingten Entropie steht auch die Transinformation, die die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen angibt.

[Bearbeiten] Beispiel

Sei eine Quelle X, die wiederholende Zeichensequenzen ...001000100010... sendet.

Nun soll unter Berücksichtung vorangegangener Zeichen die bedingte Entropie berechnet werden.

[Bearbeiten] Keine berücksichtigten Zeichen:

$p_0 = P(X=0)= \textstyle \frac{3}{4}$

$p_1 = P(X=1)= \textstyle \frac{1}{4}$

$H(X) = H(p_0,p_1)= - \textstyle \frac{3}{4} \sdot \log_2{ ( \textstyle \frac{3}{4} )} - \textstyle \frac{1}{4} \sdot \log_2{ (\textstyle \frac{1}{4})} = 0,811\,bit$

Die Berechnung erfolgt nach Definition der Entropie.

Wahrscheinlichkeitstabelle:

	x=0	x=1
P(X=x)	$\textstyle \frac{3}{4}$	$\textstyle \frac{1}{4}$

[Bearbeiten] Ein berücksichtigtes Zeichen

Sei nun x:=x_t und y:=x_t-1. Es ergeben sich folgende Wahrscheinlichkeiten:

$P(X=0|Y=0) = \textstyle \frac{2}{3} \qquad P(X=1|Y=0) = \textstyle \frac{1}{3}$

$P(X=0|Y=1) = 1 \qquad P(X=1|Y=1) = 0$

$H(X|Y) = \sum_{y \in Y}^{} \sum_{x \in X}^{} P(Y=y) \sdot H(X = x|Y = y)$

$\qquad = \sum_{y \in Y}^{} P(Y=y) \sdot H(X|Y=y)$

$\qquad = P(Y=0) \sdot H(X|Y=0) + P(Y=1) \sdot H(X|Y=1)$

$\qquad = \textstyle \frac{3}{4} \sdot \begin{matrix} \underbrace{H(X|Y=0)} \\ {}^{\rm H(P(X=0|Y=0),\,P(X=1|Y=0)) }\\[-4.5ex] \end{matrix} + \textstyle \frac{1}{4} \sdot \begin{matrix} \underbrace{H(X|Y=1)} \\ {}^{\rm H(P(X=0|Y=1),\,P(X=1|Y=1)) }\\[-4.5ex] \end{matrix}$

$\qquad = \textstyle \frac{3}{4} \sdot H (\textstyle \frac{2}{3}|\textstyle \frac{1}{3} ) + \begin{matrix} \underbrace{\textstyle \frac{1}{4} \sdot H(1|0)} \\ {}^{\rm = 0}\\[-4.5ex] \end{matrix} =0,689 \, bit$

Wahrscheinlichkeitstabellen:

P(X\|Y)	x=0	x=1
y=0	$\textstyle \frac{2}{3}$	$\textstyle \frac{1}{3}$
y=1	$\textstyle 1$	$\textstyle 0$

Wobei gilt:
P(X|Y) = P( X=x|Y=y )
= P( X=x_t|Y=x_t-1 )

	y=0	y=1
P(Y=y)	$\textstyle \frac{3}{4}$	$\textstyle \frac{1}{4}$

[Bearbeiten] Zwei berücksichtigte Zeichen

Sei x:=x_t und y:=(x_t-2, x_t-1). Es ergeben sich folgende Wahrscheinlichkeiten:

$P(X=0|Y=(0,0)) = \textstyle \frac{1}{2} \qquad P(X=1|Y=(0,0)) = \textstyle \frac{1}{2}$

$P(X=0|Y=(0,1)) = 1 \qquad P(X=1|Y=(0,1)) = 0$

$P(X=0|Y=(1,0)) = 1 \qquad P(X=1|Y=(1,0)) = 0$

$P(X=0|Y=(1,1)) \quad \mathrm{und} \quad P(X=0|Y=(1,1)) \quad$ sind unmögliche Ereignisse, da Y(1,1) nie in der Quelle autritt.

$H(X|Y) = \sum_{y \in Y}^{} P(Y=y) \sdot H(X|Y=y)$

$= \textstyle \frac{1}{2} \sdot H(X|Y=(0,0)) + \textstyle \frac{1}{4} \sdot H(X|Y=(0,1)) + \textstyle \frac{1}{4} \sdot H(X|Y=(1,0))$

$= \textstyle \frac{1}{2} \sdot H(\textstyle \frac{1}{2}|\textstyle \frac{1}{2}) + \begin{matrix} \underbrace{\textstyle \frac{1}{4} \sdot H(1|0)} \\ {}^{\rm = 0}\\[-4.5ex] \end{matrix} + \begin{matrix} \underbrace{\textstyle \frac{1}{4} \sdot H(0|1)} \\ {}^{\rm = 0}\\[-4.5ex] \end{matrix}$

$= \textstyle \frac{1}{2} \, bit$

Wahrscheinlichkeitstabellen:

P(X\|Y)	X=0	X=1
y=(0,0)	$\textstyle \frac{1}{2}$	$\textstyle \frac{1}{2}$
y=(0,1)	$\textstyle 1$	$\textstyle 0$
y=(1,0)	$\textstyle 1$	$\textstyle 0$
y=(1,1)	$\textstyle -$	$\textstyle -$

Wobei gilt: P(X|Y)
= P( X=x_t | Y=(x_t-2,x_t-1) )

	y=(0,0)	y=(0,1)	y=(1,0)	y=(1,1)
P(Y=y)	$\textstyle \frac{1}{2}$	$\textstyle \frac{1}{4}$	$\textstyle \frac{1}{4}$	$\textstyle 0$

Wobei gilt:
P(Y) = P( Y=(y_t, y_t-1) ) = P( p(y_t), p(y_t-1) )

[Bearbeiten] Drei berücksichtigte Zeichen

$H(X|Y) = 0 \,$

Sind bereits drei nacheinander folgende Zeichen bekannt, so kann man auch das folgende Zeichen sicher ausmachen. Werden also bereits drei Zeichen berücksichtigt, so ist das nächste Zeichen auch bekannt. Somit erhält man keine neue Information (bzw. nicht weniger Unsicherheit) über das nächste Zeichen. Demnach muss die Entropie null sein. Dies kann man auch an der Wahrscheinlichkeitstabelle ablesen:

P(X\|Y)	X=0	X=1
y=(0,0,0)	$\textstyle 0$	$\textstyle 1$
y=(0,0,1)	$\textstyle 1$	$\textstyle 0$
y=(0,1,0)	$\textstyle 1$	$\textstyle 0$
y=(0,1,1)	$\textstyle -$	$\textstyle -$
y=(1,0,0)	$\textstyle 1$	$\textstyle 0$
y=(1,0,1)	$\textstyle -$	$\textstyle -$
y=(1,1,0)	$\textstyle -$	$\textstyle -$
y=(1,1,1)	$\textstyle -$	$\textstyle -$

Wobei gilt:
P(X|Y) = P( X=x | Y=y )
= P( X=x_t | Y=(x_t-3, x_t-2, x_t-1) )

Unmögliche Ereignisse werden mit "−" gekennzeichnet. Bsp. y=(1,0,1) Diese Ausgabe wird die gegebene Quelle nie liefern, da nach einer Eins mindestens drei Nullen folgen.

Man sieht, dass in der Tabelle keine anderen Wahscheinlichkeiten auftreten als 0 oder 1. Da nach der Definition der Entropie gilt H(1) = H(0) = 0, muss schließlich die Entropie H(X|Y) = 0 sein.

Erläuterung zu den Wahrscheinlichkeitstabellen

Die Tabellen beziehen sich auf die obige Beispielzeichensequenz.

P(X\|Y)	x=0	x=1
y=0	$\textstyle \frac{2}{3}$	$\textstyle \frac{1}{3}$
y=1	$\textstyle 1$	$\textstyle 0$

Wobei gilt:
P(X|Y) = P( X=x|Y=y ) = P( X=x_t|Y=x_t-1 ) = p(x_t| x_t-1)

Hier betrachtet man ein Zeichen X unter der Bedingung des vorangegangenen Zeichens Y. Ist beispielsweise ein Zeichen Y=1, so lautet die Frage: Mit welcher Wahrscheinlichkeit ist das darauffolgende Zeichen X=0 bzw. X=1 ? Für Y=1 ist das nächste Zeichen X immer 0. Somit ist P(X=0|Y=1) = 1. Außerdem folgt daraus, dass P(X=1|Y=1) = 0 ist, da die Zeilensumme immer Eins ist.

P(X)	x_t=0	x_t=1
x_t-1=0	$\textstyle \frac{1}{2}$	$\textstyle \frac{1}{4}$
x_t-1=1	$\textstyle \frac{1}{4}$	$\textstyle 0$

Wobei gilt:
P(X) = P( X=(x_t, x_t-1) ) = P( p(x_t), p(x_t-1) ) = p(x_t, x_t-1)

Hier betrachtet man die Auftrittshäufigkeit einer Zeichenkombination. Man kann aus der Tabelle lesen, dass die Buchstabenkombinationen (0,1) und (1,0) genauso häufig auftreten. Die Summe aller Matrixeinträge ergibt Eins.

[Bearbeiten] Entropie und Informationsgehalt

Die Entropie fällt umso stärker, desto mehr Zeichen berücksichtigt werden. Wenn die Anzahl der berücksichtigten Zeichen hinreichend groß gewählt wird, so konvergiert die Entropie gegen Null.

Möchte man den Informationsgehalt der gegebenen Zeichenkette aus n=12 Zeichen berechnen, so erhält man nach Definition I_ges = n⋅H(X|Y) bei...

...keinem berücksichtigten Zeichen 9,39 bit Gesamtinformation. (Informationsgehalt statistisch unabhänger Ereignisse)

...einem berücksichtigten Zeichen 8,26 bit Gesamtinformation.

...zwei berücksichtigten Zeichen 6 bit Gesamtinformation.

...drei berücksichtigten Zeichen 0 bit Gesamtinformation.

Von „http://de.wikipedia.org../../../b/e/d/Bedingte_Entropie_b774.html“

Kategorien: Stochastik | Bedingte Wahrscheinlichkeit | Informationstheorie