Informations­entropie kinder­leicht definiert!

Es seien $N$ Nachrichten gegeben, so dass die Wahrschein­lich­keit der $i$-ten Nachricht gleich $p_i$ ist und die $i$-te Nachricht einen Nachrichten-Terri­to­rium-Bereich mit der Flächen­größen $q_i$ und einem Code der Länge $-\log_2 q_i$ belegt. Die durch­schnitt­liche Anzahl der täglich gesen­deten Bit bei dieser Kodie­rung 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 Neben­be­din­gung $$ q_1 +…+q_N = 1. $$ Lösen wir das Problem mit Lagrange-Multi­pli­ka­toren. Wir vergessen nicht, dass $p_i$ Konstanten und $q_i$ Varia­blen 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 Ablei­tungen von $\Lambda$ nach $q_i$ und setzen sie gleich $0$: $$ -\frac{p_i}{q_i\cdot \ln 2} + \lambda = 0. $$ Zur Erinne­rung, $$ \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 Kodie­rung wird also erreicht, wenn $q_i = p_i$ ist, was bedeutet, dass die Formel zur Berech­nung der Entropie $H$ nach Defini­tion lautet: $$ H = -p_1\cdot \log_2 p_1 -…-p_N\cdot \log_2 p_N. $$

Kreuz­entropie

Man muss beachten, dass $q_i$ sich wie Wahrschein­lich­keits­größ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 Kreuz­entropie der beiden Wahrschein­lich­keits­ver­tei­lungen $(p_i)$ und $(q_i)$ bezeichnet, aber $q_i$ hat eigent­lich keine Wahrschein­lich­keits­rolle. Der Wert $H(p,q)$ liefert die durch­schnitt­li­chen Bit-Kosten für die Übertra­gung von Nachrichten, die nach Berei­chen $q_i$ kodiert sind, aber mit Wahrschein­lich­keiten $p_i$ übertragen werden.

Kullback-Leibler-Diver­genz

Die Diffe­renz 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 durch­schnitt­li­chen zusätz­li­chen Bitkosten für die Nachrich­ten­über­tra­gung aufgrund der subop­ti­malen Kodie­rung. Diese Größe wird als Kullback-Leibler-Diver­genz zwischen den Vertei­lungen $(p_i)$ und $(q_i)$ bezeichnet.

Eine Bemer­kung

Lass uns nun einfach­heits­halber annehmen, dass man im Sommer nur $2$ Wetter­zu­stände unter­scheidet: ein gutes Wetter $G$ und ein schlechtes Wetter $S$. Nehmen wir auch die Wahrschein­lich­keiten $P(G)=3/4$, $P(S)=1/4$ an. Die Infor­ma­ti­ons­en­tropie des Wetters ist dementspre­chend 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 Kodie­rung des Erreig­nisses $S$ braucht man $\log_2 \frac{1}{4}=2$ Bit. Hier ist alles im grünen Bereich. Aller­dings 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 Defini­tion nur ganze Symbole $0$ und $1$ schreibt. Es geht nicht anders und wir müssen beide Erreig­nisse 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 telegra­fieren. Es bedeutet den Entro­pie­wert gleich $1$ und scheint als Wieder­spruch zur Theorie. Aller­dings spart man tatsäch­lich, 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 Wahrschein­lich­keiten für alle mögliche 2-Tage-Varianten gleich $$ P(GG)=P(GS)=P(SG)=P(SS)=1/4. $$ Die Infor­ma­ti­ons­en­tropie 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 Kodie­rung für das Ereignis $GG$ benötigt man etwa $\log_2 \frac{9}{16} \approx 0.83$ Bit. Ähnlich für die Ereig­nisse $GS$, $SG$, $SS$ braucht man etwa $2.415$, $2.415$ und $4$ Bit entspre­chend. Die optimalste Kodie­rung sieht so $GG\rightarrow 0$, $GS\rightarrow 10$, $SG\rightarrow 110$, $SS\rightarrow 111$ aus. Bei dieser Kodie­rung berichtet man im Durch­schnitt 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 Infor­ma­ti­ons­en­tropie des Wetter-Ereig­nisses ist hier gleich $0.84375$. Schon günstiger. Je längere Folge der Ereig­nissen auf einmal man kodiert, desto optimaler ist die Kodie­rung. Geht man in die Unend­lich­keit, nähert sich man an den theore­ti­schen Infor­ma­ti­ons­en­tro­pie­wert in praxi.