Informationstheorie nach Shannon

Die Informationstheorie, die von Claude Shannon in den 40er/50er Jahren entwickelt wurde, stellt ein Maß bzw. Kalkül zur Verfügung den Begriff "Information" und "Informationsgehalt" zu quantisieren um damit rechnen zu können.

Vorbemerkungen

In der Informationstheorie betrachten wir stets Quellen die Zeichen aussenden. Die Menge aller möglichen Zeichen die auftreten können heißt Alphabet und wird in der Regel mit $X$ bezeichnet. Ein Beobachter, der die Zeichenquelle betrachtet möchte nun wissen, welche "Information" in den Zeichen steckt, die die Quelle aussendet.

Um dies zu modellieren bedient man sich der Wahrscheinlichkeitstheorie. Man definiert eine Wahrscheinlichkeitsverteilung auf dem Alphabet. Man weiß dadurch mit welcher Wahrscheinlichkeit welches Zeichen ausgesendet wird. Zum Beispiel sendet eine Quelle die Zeichenkette $S$:

\begin{gather*} X := \{0,1\} \qquad \text{und} \qquad S := 00111101101101 \end{gather*}

Nachzählen ergibt also dass wir insgesamt $14$ Zeichen bekommen haben und davon $5$ Mal die $0$ und $9$ Mal die $1$. Das heißt unsere Wahrscheinlichkeitsverteilung ist

\begin{gather*} P(0) = \frac{5}{14} \qquad \text{und} \qquad P(1) = \frac{9}{14} \end{gather*}

Die Information

Wie bringen wir nun die Information herein? Shannon definierte die Information $I$, die ein Zeichen $x_i \in X$ enthält durch

\displaytyle I(x_i) = - \log_2(P(X = x_i))

Die Einheit der Information ist bit. Man beachte, dass dies eine reelle Zahl sein kann (und meistens auch ist), und daher nicht mit dem normal üblichen Bit (Großgeschrieben) zu verwechseln ist!

Es ist also gerade der negative Logarithmus über die relative Auftrittswahrscheinlichkeit des Zeichens $x_i$! Das macht auch Sinn, denn der Logarithmus ist zwischen $0$ und $1$ immer negativ, und eine relative Wahrscheinlichkeit ist stets im Bereich $0$ bis $1$. Somit ist die Information eines Zeichens $x_i$ stets größer als $0$.

Für unser Beispiel ausgerechnet ist demnach

\begin{gather*} I(0) = - \log_2 \frac{5}{14} \approx 1,485426827 \text{ bit} \end{gather*}

und

\begin{gather*} I(1) = - \log_2 \frac{9}{14} \approx 0,6374299205 \text{ bit} \end{gather*}

Warum ist die Information von $0$ höher? Weil sie seltener vorkommt. Wenn die Quelle eine $1$ ausspuckt ist das weitaus weniger "überraschend". Man würde eine $1$ also eher erwarten, und erhält damit weniger Information, als wenn eine $0$ kommt, da diese verhältnismäßig selten vorkommen.

Durchschnittlicher Informationsgehalt aka "Entropie"

Mit der oberen Formel können wir nun den Informationsgehalt eines Zeichens schön berechnen. Nun möchte man aber vielleicht wissen wieviel Information ein Zeichen in einer Zeichenkette "im Mittel" enthält. Aus der Wahrscheinlichkeit weiß man, dass dies gerade der Erwartungswert der statistischen Variable - in unserem Fall also $X$ - ist. Also

\begin{gather*} E = \sum_{i} P(X = x_i) x_i \end{gather*}

Übertragen wir das auf die Informationstheorie. Wir können für jedes Zeichen $x_i$ ja die Einzelinformationen berechnen. Nun bilden wir einfach den Erwartungswert und das liefert die Formel für die Entropie

\displaystyle H = \sum_i P(X = x_i) I(x_i)

Wir können das noch etwas vereinfach, nämlich

\begin{align*} H &= \sum_i P(X=x_i) I(x_i) \\ &= \sum_i P(X=x_i) (- \log_2 (P(X=x_i))) \\ &= - \sum_i P(X=x_i) \log_2 (P(X=x_i)) \\ &= - \sum_i P_i \log_2(P_i) \qquad \text{(Kurzschreibweise)} \end{align*}

Anschaulich ist dies also der durchschnittliche Informationsgehalt eines Zeichens; Und zwar der Zeichen die die Quelle ausspuckt.

Man notiert auch - analog zur Wahrscheinlichkeitstheorie - die Entropie $H$ durch $H(P_1, \ldots, P_k)$. Wichtig ist dabei dass die Wahrscheinlichkeiten $P_i$ aufsummiert gerade $1$ ergeben, da der Wert $H$ sonst illegal ist, bzw. überhaupt keinen Sinn ergibt.

Unser Beispiel von oben mit der Zeichenkette $S$ liefert nun eingesetzt in die Formel

\begin{align*} H &= - \frac{5}{14} \log_2 \frac{5}{14} - \frac{9}{14} \log_2 \frac{9}{14} \\ &\approx 0,9402859585 \text{ bit} \end{align*}

Dies ist also die Entropie, also der durchschnittliche Informationsgehalt pro Zeichen der Zeichenkette $S$.

Wollten wir den Informationsgehalt der kompletten Zeichenkette, so müssen wir unser $H$ noch mit der Länge der Zeichenkette multiplizieren, also

\begin{gather*} H_{S} = |S| \cdot H \approx 14 \cdot 0,9402859585 \approx 13,16400342 \text{ bit} \end{gather*}

Die Zeichenkette $S$ enthält also eine Information von ungefähr $13$ bit!

Der Kanal

Man möchte nun noch einen Schritt weiter gehen, und betrachtet nicht nur die Information von Zeichenketten die eine Quelle ausspuckt, sondern man betrachtet einen Übetragungskanal durch den wir einen Datenstrom schicken wollen. Wir brauchen also jetzt zwei Alphabete $X$ und $Y$, nämlich die des Senders und die des Empfängers.

Nun kann es passieren, dass der Kanal gestört wird, das heißt Informationen des Senders verloren gehen, oder ungewollte Informationen hinzukommen. Die Quelle wird also in der Regel nicht das gleiche Empfangen wie der Sender ausgespuckt hat. Schematisch kann man das am folgenden Bild illustrieren:

Schema

Keine Panik, das Bild ist schnell erklärt!

Die Quelle (links) sendet Zeichen aus einem Alphabet $X$ in den Kanal. Die Quelle empfängt irgendwelche Zeichen aus $Y$ vom Kanal. Hier muss man jetzt ein wenig aufpassen. Es können in der Praxis $X$ und $Y$ die gleichen Alphabete sein, aber es sind trotzdem verschiedene stochastische Variablen! Der Anteil von Information, der an der Quelle ankommt und tatsächlich vom Sender stammt heißt Transinformation. Der verlorengegangene Anteil an Information von der Quelle heißt auch Äquivokation und der hinzugekommene Anteil heißt Fehlinformation. Man kann sich aus dem Diagramm jetzt wunderbar folgende Beziehungen herleiten:

Transinformation:

\begin{gather*} H(X;Y) := H(X) - H(X|Y) = H(Y) - H(Y|X) \end{gather*}

Äquivokation:

\begin{gather*} H(X|Y) := H(X) - H(X;Y) \end{gather*}

Fehlinformation (Irrelevanz):

\begin{gather*} H(Y|X) := H(Y) - H(X;Y) \end{gather*}

Totalinformation:

\begin{gather*} H(X,Y) := H(X|Y) + H(X;Y) + H(Y|X) \end{gather*}

Diese Formeln lassen sich natürlich auch (durch ineinander Einsetzen bzw. anderes Ablesen aus dem Diagramm) anders formulieren.

OK, schlagen wir wieder einen Bogen zur Wahrscheinlichkeitstheorie. Man kann $X$ und $Y$ wieder als Zufallsvariablen ansehen. Diese sind in der regel stochastisch Abhängig - Außer der Sender hat mit der Quelle nichts am Hut, aber was wär das für ein Kanal? Betrachten wir die Verbundwahrscheinlichkeit stochastisch Abhängiger Größen einmal genauer im Vergleich zu den Informationsgehalten

\begin{gather*} P(X,Y) = P(Y|X) \cdot P(X) \qquad \leftrightarrow \qquad H(X,Y) = H(Y|X) + H(X) \end{gather*}

Diese Beziehung sollte man stets im Kopf behalten. Es gilt: Ein Produkt der Wahrscheinlichkeiten entspricht einer Summation der Entropien, was aus der isomorphen Beziehung zwischen der Multiplikation reeller Zahlen und der Summierung ihrer Logarithmen herrührt.

Nun gibt es noch ein paar Eigenschaften von Kanälen:

Deterministischer Kanal

Ein Kanal heißt deterministisch, wenn für jedes Eingabezeichen klar ist, was deren Ausgabezeichen sein wird. Es muss also gelten $H(Y|X) = 0$, es darf keine Fehlinformation geben!

Verlustfreier Kanal

Ein Kanal heißt verlustfrei, wenn es keine Äquivokation (verlorene Information) gibt, also $H(X|Y) = 0$ gilt.

Störungsfreier Kanal

Ein Kanal heißt störungsfrei (oder ungestört), wenn er verlustfrei und deterministisch ist.

Nutzloser Kanal

Ein Kanal heißt nutzlos wenn er keine Information überträgt, bzw. wenn gilt $H(X;Y) = 0$. In diesem Fall sind die Zufallsvariablen für $X$ und $Y$ stochastisch unabhängig.

Schließlich gibt es noch eine Größe, die angibt wieviel Information man maximal durch einen Kanal schicken kann, die sogenannte Kanalkapazität. Diese ist definiert durch

\displaystyle C = \max_{P(X)}(H(X;Y))

Anschaulich ist dies also unter allen möglichen Wahrscheinlichkeitsverteilungen der Quelle diejenige zugehörige Transinformation, die am größten ist.

Definition von Kanälen

OK, genug der trockenen Theorie. Wie definiert man im Allgemeinen einen Kanal? Eine Möglichkeit ist zum Beispiel durch Angabe der bedingten Wahrscheinlichkeiten $P(Y|X)$. Sowas könnte zum Beispiel für einen Kanal mit $X = \{0,1\}$ und $Y = \{0,1\}$ so aussehen:

Beispiel

Links haben wir $X$ und rechts $Y$. Die Pfeile geben die bedingte Wahrscheinlichkeit $P(Y=y | X=x)$ an. Hat man nun noch eine passende Quellenstatistik gegeben, zum Beispiel

\begin{gather*} P(X = 0) := \frac{1}{2} \qquad P(X=1) := \frac{1}{2} \end{gather*}

so lassen sich ALLE Größen des Kanals berechnen. Folgende Größen lassen sich direkt berechnen:

Informationsgehalt der Qelle

\begin{gather*} H(X) = H(P(X=x_1), \ldots, P(X=x_n)) \end{gather*}

Informationsgehalt des Empfängers

\begin{gather*} H(Y) = H(P(Y=y_0), \ldots, P(Y=y_n)) \end{gather*}

Totalinformation

\begin{align*} H(X,Y) =\;&H(P(X=x_0)P(Y=y_0|X=x_0), \ldots, P(X=x_0)P(Y=y_n|X=x_0), \ldots,\\& \ldots, P(X=x_n)P(Y=y_n|X=x_n)) \end{align*}

Die restlichen Größen lassen sich mit den Beziehungen aus dem Diagramm leicht herleiten. Für unser Beispiel ergibt sich die Quelleninformation durch:

\begin{align*} H(X) &= H(P(X=0), P(X=1)) \\ &= H(\frac{1}{2},\frac{1}{2}) \\ &= - \frac{1}{2} \log_2\frac{1}{2} - \frac{1}{2} \log_2 \frac{1}{2} \\ &= 1 \text{ bit} \end{align*}

Die Information $H(Y)$ lässt sich auch berechnen:

\begin{align*} H(Y) &= H(P(Y=0), P(Y=1)) \\ &= H(\frac{1}{2} \cdot 0.2 + \frac{1}{2} \cdot 0.4, \frac{1}{2} \cdot 0.8 + \frac{1}{2} \cdot 0.6) \\ &= H(0.3, 0.7) \\ &\approx 0.88 \text{ bit} \end{align*}

Und schließlich $H(X,Y)$:

\begin{align*} H(X,Y) &= H(P(X=0)P(Y=0|X=0), P(X=0)P(Y=1|X=0),\\&\qquad P(X=1)P(Y=0|X=1), P(X=1)P(Y=1|X=1)) \\ &= H(\frac{1}{2} \cdot 0.2, \frac{1}{2} \cdot 0.8, \frac{1}{2} \cdot 0.4, \frac{1}{2} \cdot 0.6) \\ &= H(0.1, 0.2, 0.4, 0.3) \\ &\approx 1.85 \text{ bit} \end{align*}

Die restlichen Werte lassen sich durch die oberen Formeln ausrechnen, in unserem Fall:

\begin{align*} H(X|Y) &= H(X,Y) - H(Y) \approx 0.97 \text{ bit}\\ H(Y|X) &= H(X,Y) - H(X) \approx 0.84 \text{ bit}\\ H(X;Y) &= H(X) - H(X|Y) \approx 0.03 \text{ bit} \end{align*}

Die Transinformation, also die Information, die der Kanal wirklich überträgt ist mit $0.03$ bit in unserem Beispiel leider extrem gering.

Redundanz

Redundanz bezeichnet in der Informationstheorie "überflüssige Information". Diese kommt dann zustande, wenn man einen Text mit mehr Bits kodiert, als eigentlich nötig, also mehr als die enthaltene Information des Textes.

Definieren wir zunächst einmal die tatsächliche Anzahl bits. Wir haben also wieder ein Alphabet $X$ mit Zeichen $x_i \in X$. Dann bezeichnet $\text{code}(x_i)$ das zu $x_i$ gehörende Kodewort. Zum Beispiel beim Alphabet der ASCII Zeichen hat der Buchstabe $a$ das Kodewort $01100001$, also $\text{code}(a) = 01100001$. Analog zur Entropie $H$, die ein Erwartungswert über die Information der Zeichen ist, ist die Nominalinformation $\tilde{H}$ als Erwartungswert über die Kodewortlänge definiert:

\displaystyle \tilde{H} = \sum_{i} P(X=x_i) \cdot |\text{code}(x_i)|

Diese ist quasi die "durchschnittliche Kodewortlänge pro Zeichen".

Wir haben nun also zwei Größen, die wir gegenüberstellen können, nämlich die tatsächliche Kodelänge ($\tilde{H}$) und die eigentlich bloß benötigte Kodelänge aufgrund der Information ($H$). Damit ist die absolute Redundanz $R_{\text{abs}}$ folgendermaßen definiert

\displaystyle R_{\text{abs}} = \tilde{H} - H

Die relative Redundanz ist dementsprechend ein Wert zwischen 0 und 1 und ist

\displaystyle R_{\text{rel}} = \frac{R_{\text{abs}}}{\tilde{H}} = 1 - \frac{H}{\tilde{H}}

Ein kleines Beispiel. Betrachten wir die Zeichenkette "Hallo". Offenbar ist das Alphabet $X = \{H,a,l,o\}$. Die Wahrscheinlichkeitsverteilung ergibt sich durch nachzählen und ist

\begin{gather*} P(X=H) = \frac{1}{5} \quad P(X=a) = \frac{1}{5} \quad P(X=l) = \frac{2}{5} \quad P(X=o) = \frac{1}{5} \end{gather*}

Damit können wir die Entropie $H$ berechnen

\begin{align*} H &= H(\frac{1}{5}, \frac{1}{5}, \frac{2}{5}, \frac{1}{5}) \\ &= - 3 \cdot (\frac{1}{5} \log_2 \frac{1}{5}) - (\frac{2}{5} \log_2 \frac{2}{5}) \\ &\approx 1.92 \text{ bit} \end{align*}

Da bei der ASCII Kodierung jedes Zeichen durch $8$ Bit repräsentiert wird, können wir $\tilde{H} = 8$ setzen. Somit ergibt sich eine absolute Redundanz von

\begin{gather*} R_{\text{abs}} \approx 8 - 1.92 = 6.08 \text{ bit} \end{gather*}

und eine relative Redundanz von

\begin{gather*} R_{\text{rel}} \approx 1 - \frac{1.92}{8} = 0.76 \;\hat{=}\; 76\% \end{gather*}

Um die Information, die die Zeichenkette "Hallo" enthält zu Kodieren, reichen also $1.92$ bit pro Zeichen aus. Im ASCII Kode sind also pro Zeichen $6.08$ bit ($76\%$) "überflüssig".

Maximale und minimale Information

Sehr interessant ist noch, dass der Informationsgehalt (Entropie) zu einer Zufallsvariable (und einem Alphabet) $X$ dann maximal wird, wenn auf dem Alphabet eine Gleichverteilung vorliegt. Intuitiv ist das klar, denn bei einer Gleichverteilung der Zeichen weiß man am wenigsten welches Zeichen als nächstes auftreten wird, daher wird jedes eine hohe Information mitsich bringen.

Der Informationsgehalt wird im Gegenzug dann minimal, wenn die Wahrscheinlichkeitsverteilung so aussieht, dass ein Zeichen $x_i$ eine Auftrittswahrscheinlichkeit von $100\%$ besitzt (Die restlichen Zeichen haben dann natürlich eine Auftrittswahrscheinlichkeit von $0$). Dann bringt ein Auftauchen von $x_i$ nämlich überhaupt keine Information mitsich, da man ja eh schon wusste dass $x_i$ kommt.

Website by: Thomas Pajor, Augartenstr. 56, 76137 Karlsruhe - www.darkviper.de - with help from: flowhase