Bedingte Entropie

Bedingte Entropie

In der Informationstheorie ist die bedingte Entropie ein Maß für die „Ungewissheit“ über den Wert einer Zufallsvariablen X, welche verbleibt, nachdem das Ergebnis einer anderen Zufallsvariable Y bekannt wird. Die bedingte Entropie wird H(X | Y) geschrieben und hat einen Wert zwischen 0 und H(X), der ursprünglichen Entropie von X. Sie wird in der gleichen Maßeinheit wie die Entropie gemessen.

Speziell hat sie den Wert 0, wenn aus Y der Wert von X funktional bestimmt werden kann, und den Wert H(X), wenn X und Y stochastisch unabhängig sind.

Inhaltsverzeichnis

Definition

Seien X eine diskrete Zufallsvariable und M ihr Wertevorrat, das heißt M ist eine höchstens abzählbare Menge mit P(X\in M)=1. X soll jedes Element von M mit nicht negativer Wahrscheinlichkeit annehmen. Dann ist die Entropie von X durch

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

definiert, wobei für b typischerweise die Werte 2 (Bit) oder e (Nat) für die entsprechenden Einheiten angenommen werden.

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_b 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).

Auf höherer Abstraktionsebene handelt es sich bei H(X) um den Erwartungswert der Informationsfunktion IX(x): = log bP(X = x | A) und bei H(X | Y) um die bedingte Erwartung der Informationsfunktion IX bezüglich der von Y aufgespannten σ-Algebra.[1]

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.

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 hk definieren als die Unsicherheit eines Symbols xk + 1 (nach einem bestimmten vorgegebenen k-Block):

hk: = Hk + 1Hk mit h0: = H1,

wobei Hi die Blockentropie bezeichnet. Für die bedingte Entropie h1, also die Unsicherheit eines Symbols nach einem 1-Block, folgt:

h1 = H2H1 = 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.

Beispiel

Sei X eine Quelle, die periodisch die Zeichen ...00100010001000100010... sendet.

Nun soll unter Berücksichtung vorangegangener Zeichen die bedingte Entropie des aktuell zu beobachtenden Zeichens berechnet werden.

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}

Ein berücksichtigtes Zeichen

Sei nun X:=xt und Y:=xt-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}
  \textstyle \frac{1}{4} \sdot \underbrace{ 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( xt=x | xt-1=y )

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

Zwei berücksichtigte Zeichen

Sei X:=xt und Y:=(xt-2, xt-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
Y=(1,1) kommt in der Quelle nie vor, braucht also nicht betrachtet zu werden.
 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( xt | (xt-2,xt-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( yt, yt-1 )

Drei berücksichtigte Zeichen

H(X|Y) = 0 \,

Sind bereits drei nacheinander folgende Zeichen bekannt, so ist damit auch das folgende Zeichen determiniert (denn die Quelle verhält sich ja periodisch). Somit erhält man keine neue Information ü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=xt | Y=(xt-3, xt-2, xt-1) )

Unmögliche Ereignisse werden hier mit "-" gekennzeichnet, z.B. bei y=(1,0,1). Diese Ausgabe wird die gegebene Quelle nie liefern, da nach einer Eins immer drei Nullen folgen.

Man sieht, dass in der Tabelle keine anderen Wahrscheinlichkeiten auftreten als 0 oder 1. Da nach der Definition der Entropie gilt H(0,1) = H(1,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=xt|Y=xt-1 ) = p(xt| xt-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) xt=0 xt=1
xt-1=0 \textstyle \frac{1}{2} \textstyle \frac{1}{4}
xt-1=1 \textstyle \frac{1}{4} \textstyle 0

Wobei gilt:
P(X) = P( X=(xt, xt-1) ) = P( p(xt), p(xt-1) ) = p(xt, xt-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.

Entropie und Informationsgehalt

Die Entropie fällt bei diesem Beispiel umso stärker, je mehr Zeichen berücksichtigt werden (siehe auch: Markow-Prozess). 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 Zeichenfolge aus n=12 Zeichen berechnen, so erhält man nach Definition Iges = n⋅H(X|Y) bei...

...keinem berücksichtigten Zeichen 9,39 bit Gesamtinformation. (Informationsgehalt statistisch unabhängiger Ereignisse)
...einem berücksichtigten Zeichen 8,26 bit Gesamtinformation.
...zwei berücksichtigten Zeichen 6 bit Gesamtinformation.
...drei berücksichtigten Zeichen 0 bit Gesamtinformation.

Einzelnachweise

  1. Olav Kallenberg: Foundations of Modern Probability. Springer, New York 2002, ISBN 0387953132, S. 220.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Entropie (Informationstheorie) — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Das… …   Deutsch Wikipedia

  • Entropie — Der Begriff Entropie (griechisches Kunstwort εντροπία [entropía], von εν [en ] – ein , in und τροπή [tropē] – Wendung, Umwandlung) steht für: Mathematik Entropieschätzung, verschiedene Methoden zur statistischen Schätzung der Shannon Entropie auf …   Deutsch Wikipedia

  • Maximale Entropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Shannon-Entropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Bedingte Informationsentropie — Während ordinale Insolvenzprognosen lediglich eine Reihung von Unternehmen entsprechend den erwarteten Ausfallwahrscheinlichkeiten vornehmen, ordnen kardinale Insolvenzprognosen jedem Unternehmen explizit eine Ausfallwahrscheinlichkeit zu.[1]… …   Deutsch Wikipedia

  • Informationsdichte — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Informationsentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Maximalentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Shannonentropie — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide… …   Deutsch Wikipedia

  • Überraschungswert — Der Begriff der Information, wie er in der Informationstheorie nach Shannon[1] verwendet wird, ist streng von dem gewöhnlichen Gebrauch dieses Begriffes zu unterscheiden. Insbesondere darf darin die Information nicht mit dem Begriff der Bedeutung …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”