Alexei Kurgansky
Alexei Kurgansky
Mathematiker
Nov 18, 2021 6 min read

Informationsentropie kinderleicht definiert

thumbnail for this post

Was ist die Informationsentropie?

Nehmen wir an, dass wir im Sommer unseren Freunden jeden Tag ein Telegramm aus Hamburg nach Sankt Petersburg über den Wetterzustand senden möchten: sonnig, leicht bewölkt, bedeckt, regnerisch. Das Wetter ist für uns ein Zufallsereignis, allerdings erwarten wir im Sommer sonniges Wetter für ca. $1/2$ der Tage, leicht bewölkt für $1/4$ der Tage, bedeckt für $1/8$ der Tage und regnerisch für $1/8$ der Tage. Es können nur Nullen ($0$) und Einsen (1) telegrafisch gesendet werden. Ein Symbol kostet $1$ Euro. Wenn man die Nachrichten mit Symbolpaaren $00$, $01$, $10$ und $11$ kodiert, werden jeden Tag zwei Bit zu Gesamtkosten von $2$ Euro gesendet. Die Telegramme kosten dann $184$ Euro für $92$ Sommer Tage insgesamt. Wenn man die Nachrichten “sonnig”, “leicht bewölkt”, “bedeckt”, “regnerisch” mit $0$, $10$, $110$, $111$ kodiert, werden im Durchschnitt jeden Tag

$$ (1/2)\cdot 1 + (1/4)\cdot 2 + (1/8)\cdot 3 + (1/8)\cdot 3 = 7/4 $$

Bit gesendet, und für $92$ Sommer Tage werden etwa $7/4 \cdot 1 \cdot 92 = 161$ Euro ausgegeben. Man sieht den Unterschied, manche Kodierungen sind teurer und manche sind billiger, und es ist offensichtlich, dass es die billigste Kodierung gibt.

Wenn die Kodierung so intelligent ist, dass sie über den Sommer hinweg die geringsten Kosten der Telegramme mit den Ereignisberichten verursacht, dann wird die Anzahl der durchschnittlich pro Tag gesendeten Bit als Informationsentropie dieses Ereignisses bezeichnet.

Die Verallgemeinerung der Definition auf beliebige zufällige Ereignisse ist nun einfach.

Wie berechnet man Informationsentropie?

Diese Frage hängt mit der Frage zusammen, was eine Kodierung ist. Angenommen, es gibt ein Territorium von Nachrichten, das in der Abbildung durch das erste Rechteck dargestellt ist. Nehmen wir an, dass die Fläche des gesamten Territoriums gleich $1$ ist. Wenn das Territorium in zwei Teile unterteilt ist, sind jedem Teil die Codenamen (Koordinaten) $0$ und $1$ gegeben so, wie es im zweiten Rechteck gezeigt ist. Die Flächengrößen von $0$ und $1$ sind gleich $1/2$. Wenn nun jeder Nachrichten-Territorium-Bereich $0$ und $1$ ebenfalls in zwei Teile geteilt wird, dann erteilt man diesen kleinen Bereichen des Territoriums die Codes $00$, $01$, $10$, $11$ so, wie es durch das dritte Rechteck dargestellt ist. Die Flächengrößen dieser Teile sind gleich $1/4$. Daraus erschließt sich, wie die Codes für die Bereiche mit den Flächengrößen $1/8$, $1/16$ usw. lauten. Man erkennt, dass die Flächengröße von einem Nachrichten-Territorium-Bereich gleich $\frac{1}{2^n}$ ist, wo $n$ die Länge seines Codes ist. Mit anderen Worten: wenn $q$ die Fläche des Bereichs ist, ist seine Codelänge $\log_2 \frac{1}{q}=-\log_2 q$. Je größer ist der Bereich, desto kürzer ist der Code.

Die 4. und 5. Rechtecke zeigen Beispiele für die Platzierung von Nachrichten über das Nachrichten-Territorium.

Ein_Bild_für_Entropie_Blog

Es seien $N$ Nachrichten gegeben, so dass die Wahrscheinlichkeit der $i$-ten Nachricht gleich $p_i$ ist und die $i$-te Nachricht einen Nachrichten-Territorium-Bereich mit der Flächengrößen $q_i$ und einem Code der Länge $-\log_2 q_i$ belegt. Die durchschnittliche Anzahl der täglich gesendeten Bit bei dieser Kodierung ist

$$ -p_1\cdot \log_2 q_1 -\ldots -p_N\cdot \log_2 q_N. $$

Für welche Werte von $q_i$ ist diese Summe minimal?

Wir erinnern an die Tatsache

$$ p_1 +…+p_N = 1 $$

und eine Nebenbedingung

$$ q_1 +…+q_N = 1. $$

Lösen wir das Problem mit Lagrange-Multiplikatoren. Wir vergessen nicht, dass $p_i$ Konstanten und $q_i$ Variablen sind.

Die Lagrange-Funktion ist

$$ \Lambda(q_1,\ldots,q_N,\lambda) =-p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N + \lambda\cdot (q_1+…+q_N). $$

Finden wir die Ableitungen von $\Lambda$ nach $q_i$ und setzen sie gleich $0$:

$$ -\frac{p_i}{q_i\cdot \ln 2} + \lambda = 0. $$

Zur Errinerung,

$$ \frac{d}{dx}\log_2x = \frac{d}{dx} \frac{\ln x}{\ln 2} = \frac{1}{x \ln 2}. $$

Daraus folgt

$$ p_i = \lambda\cdot q_i\cdot\ln 2. $$

Summiert man diese Gleichungen für alle $i$, erhält man

$$ \lambda\cdot\ln 2 = 1. $$

Wenn man $\lambda\cdot \ln 2 = 1$ in $p_i = \lambda\cdot q_i\cdot\ln 2$ einsetzt, bekommt man $p_i = q_i$. Die optimale Kodierung wird also erreicht, wenn $q_i = p_i$ ist, was bedeutet, dass die Formel zur Berechnung der Entropie $H$ nach Definition lautet:

$$ H = -p_1\cdot \log_2 p_1 -…-p_N\cdot \log_2 p_N. $$

Kreuzentropie

Man muss beachten, dass $q_i$ sich wie Wahrscheinlichkeitsgrößen verhalten: sie sind größer als $0$ und ihre Summe ist gleich $1$. Die Größe

$$ H(p,q)=-p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N $$

wird als Kreuzentropie der beiden Wahrscheinlichkeitsverteilungen $(p_i)$ und $(q_i)$ bezeichnet, aber $q_i$ hat eigentlich keine Wahrscheinlichkeitsrolle. Der Wert $H(p,q)$ liefert die durchschnittlichen Bit-Kosten für die Übertragung von Nachrichten, die nach Bereichen $q_i$ kodiert sind, aber mit Wahrscheinlichkeiten $p_i$ übertragen werden.

Kullback-Leibler-Divergenz

Die Differenz zwischen

$$ -p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N $$

und

$$ -p_1\cdot \log_2 p_1 -…-p_N\cdot \log_2 p_N $$

ist der Wert von durchschnittlichen zusätzlichen Bitkosten für die Nachrichtenübertragung aufgrund der suboptimalen Kodierung. Diese Größe wird als Kullback-Leibler-Divergenz zwischen den Verteilungen $(p_i)$ und $(q_i)$ bezeichnet.

Eine Bemerkung

Lass uns nun einfachheitshalber annehmen, dass man im Sommer nur $2$ Wetterzustände unterscheidet: ein gutes Wetter $G$ und ein schlechtes Wetter $S$. Nehmen wir auch die Wahrscheinlichkeiten $P(G)=3/4$, $P(S)=1/4$ an. Die Informationsentropie des Wetters ist dementsprechend gleich

$$ -\frac{3}{4}\cdot \log_2 \frac{3}{4} -\frac{1}{4}\cdot \log_2 \frac{1}{4} \approx 0.8113. $$

Für die optimale Kodierung des Erreignisses $S$ braucht man $\log_2 \frac{1}{4}=2$ Bit. Hier ist alles im grünen Bereich. Allerdings für das $G$ braucht man etwa $\log_2 \frac{3}{4}\approx 0.415$ Bit. Das ist weniger als $1$ Bit und passt mit der Realität nicht zusammen, dass man in den Telegrammen nach Definition nur ganze Symbole $0$ und $1$ schreibt. Es geht nicht anders und wir müssen beide Erreignisse mit $1$ Bit kodieren: $0$ und $1$, genau wie im Fall $P(G)=P(S)=1/2$. Also wenn wir jeden Tag ein Telegramm senden möchten, können wir nicht sparen und sind gezwungen, $92$ Bit für $92$ Tage zu telegrafieren. Es bedeutet den Entropiewert gleich $1$ und scheint als Wiederspruch zur Theorie.

Allerdings spart man tatsächlich, wenn man nicht jeden Tag sondern nur am Ende der Sommer ein einziges Telegramm mit Wetter Bericht für alle Tage sendet. Man sieht es an einem Beispiel mit $2$ Tagen.

Bei $P(G)=P(S)=1/2$ sind die Wahrscheinlichkeiten für alle mögliche 2-Tage-Varianten gleich

$$ P(GG)=P(GS)=P(SG)=P(SS)=1/4. $$

Die Informationsentropie ist hier für $2$-Tage-Wetter-Erreignis gleich $2$ und für $1$-Tag-Wetter-Erreignis gleich $1$. Die Wetter-Entropie ist also $1$.

Im Fall $P(G)=3/4$, $P(S)=1/4$ gilt es $P(GG)=9/16$, $P(GS)=P(SG)=3/16$, $P(SS)=1/16$. Die optimalste Kodierung für das Ereignis $GG$ benötigt man etwa $\log_2 \frac{9}{16} \approx 0.83$ Bit. Ähnlich für die Ereignisse $GS$, $SG$, $SS$ braucht man etwa $2.415$, $2.415$ und $4$ Bit entsprechend.

Die optimalste Kodierung sieht so $GG\rightarrow 0$, $GS\rightarrow 10$, $SG\rightarrow 110$, $SS\rightarrow 111$ aus. Bei dieser Kodierung berichtet man im Durchschnitt für beide Tage dann nur

$$ \frac{9}{16}\cdot 1 + \frac{3}{16}\cdot 2 + \frac{3}{16}\cdot 3 + \frac{1}{16}\cdot 3 = 1.6875 \quad (\text{Bit}) $$

und für einen Tag:

$$ \frac{1.6875}{2} = 0.84375 \quad (\text{Bit}). $$

Die Informationsentropie des Wetter-Ereignisses ist hier gleich $0.84375$. Schon günstiger.

Je längere Folge der Ereignissen auf einmal man kodiert, desto optimaler ist die Kodierung. Geht man in die Unendlichkeit, nähert sich man an den theoretischen Informationsentropiewert in praxi.