Entropie (Informationstheorie)

Entropie als Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Beide Begriffe haben Gemeinsamkeiten, deren Erkennen allerdings Kenntnisse in beiden Fachgebieten voraussetzt.

Das informationstheoretische Verständnis des Begriff Entropie geht auf Claude Shannon und existiert seit etwa 1948. In diesem Jahr veröffentliche Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prägte damit die moderne Informationstheorie.

Definition

Shannon definierte die Entropie H einer gegebenen Information I über einem Alphabet Z durch

$H(I)=-\sum _{j=1}^{|Z|}{p_{j}\cdot \log _{2}{p_{j}}}$,

wobei p_j die Wahrscheinlichkeit ist, mit der das j-te Symbol z_j des Alphabet Z im Informationtext I auftritt. Die Einheit der Entropie wird mit bit bezeichnet. H multipliziert mit der Anzahl der Zeichen im Informationstext ergibt dann die mindestens notwendige Anzahl von Bits, die zur Darstellung der Information notwendig sind.

Prinzipiell lässt dich die Berechnung der Entropie auch auf andere Zahlensysteme (Oktalsystem, Hexadezimalsystem, ...) als das Binärssystem (Basis 2) übertragen. In diesem Fall wird nicht der Logarithmus zur Basis 2 sondern zur entsprechenden informationstheoretischen Basis des Zahlensystems gebildet.

Interpretation

Shannons ursprüngliche Absicht, diese Entropie als das Maß der benötigten Bandbreite eines Übertragungskanals zu nutzen, wurde schnell verallgemeinert. Die Entropie wurde generell als ein Maß für den Informationsgehalt betrachtet. Wenn die Entropie etwa einen Wert von 1 hat, dann gilt die Information als zufällig. Bei einer kleinen Entropie enthält der Informationstext Redundanzen oder statistische Regelmäßigkeiten.

Die rein statistische Berechnung der informationstheoretischen Entropie nach obiger Formel ist gleichzeitig ihre Beschränkung. Beispielsweise ist die Wahrscheinlichkeit, eine 0 oder 1 in einer geordneten Zeichenkette "1010101010..." zu finden, genauso groß, wie in einer Zeichenkette, die durch statistisch unabhängige Ereignisse (etwa wiederholten Münzwurf) entstanden ist. Daher ist Shannons Entropie für beide Zeichenketten identisch, obwohl man intuitiv die erste Kette als weniger zufällig bezeichnen würde. Eine angemessenere Definition der Entropie einer Zeichenkette liefert die Bedingte Entropie und Quellentropie (siehe Blockentropie), die beide auf Verbundwahrscheinlichkeiten aufbauen.

Maximaler Entropiewert und Normierung

Möchte man ein normiertes Maß für die Entropie einer beliebigen diskreten Verteilung haben, ist es von Vorteil, die maximal mögliche Entropie, die bei Gleichverteilung der p_j erreicht wird, zur Normierung heranzuziehen. Sei z = |Z| die Anzahl der erlaubten Symbole in I über dem Alphabet Z, dann ist die maximale Entropie H_max gegeben durch:

$H_{max}(I)=-\sum _{i}{{\frac {1}{z}}\log _{2}{\frac {1}{z}}}=\log _{2}{z}{\mbox{ , falls }}\forall \;p_{j}={\frac {1}{|Z|}}$

Daraus folgt beispielsweise H_max=1 für eine Binärverteilung (Z={0,1}), also benötigt man 1 Bit pro Zeichen und |I| Zeichen für die komplette Information I. Dieser Wert wird erreicht, wenn 0en und 1en gleich häufig vorkommen. Normiert man nun die Entropie einer beliebigen Verteilung mit z verschiedenen Symbolen mit H_max erhält man:

$H(I)/H_{max}=-\sum _{j=1}^{b}{p_{j}\cdot {\frac {\log _{2}{p_{j}}}{\log _{2}{b}}}}=-\sum {p_{j}\cdot log_{b}{p_{j}}}\leq 1$

Die so erhaltene Entropie wird immer maximal gleich 1.

Datenkompression und Entropie

Die Entropiekodierung ist ein Kompressionsalgorithmus, um Daten verlustfrei zu komprimieren.

Beispiel

• Gegeben sei die Zeichenkette ABBCAADA (siehe auch Entropiekodierung).
• Die Buchstaben-Wahrscheinlichkeit: $p_{a}=4/8=0.5$; $p_{b}=0.25$; $p_{c}=p_{d}=0.125$

• $Entropie=-(0.5*\log _{2}{0.5}+0.25*\log _{2}{0.25}+2*(0.125*\log _{2}{0.125})=1.75Bit/Zeichen$
• Maximalentropie ($p_{a}=p_{b}=p_{c}=p_{d}=0.25$):
  $Entropie_{max}=-4*(0.25*log_{2}{0.25})=-log_{2}{4^{-1}}=2Bit/Zeichen$

Alternative Möglichkeiten der Informationsquantifizierung

Ein anderer Zugang, den Gehalt einer Information zu messen, ist durch die Kolmogorov Komplexität gegeben, worin der kürzestmögliche Algorithmus zur Darstellung einer gegebenen Zeichenkette die Komplexität derselben angibt. Gregory Chaitin ist ebenfalls über die Shannonsche Definition der Entropie einer Information hinausgegangen (siehe Chaitinkette).

Literatur

• Rolf Johanneson, Informationstheorie Addison-Wesley 1992, ISBN 3893194657

Weblinks

• http://www.madeasy.de/2/zufallgz.htm
  • Einführung der Entropie als Gesamtzufallsmenge mit vielen Beispielen.
  • Für alle die mit der Shannonformel überfordert sind.

Siehe auch: Kolmogorov-Entropie, Kolmogorov-Sinai-Entropie, Maximum-Entropie-Methode, Metrische Entropie, Transinformation, Nat, Ornstein Theorem, Redundanz, Topologische Entropie, Markow-Kette, Renyi-Entropie, Entropierate, Transinformation, Kullback-Leiber-Entropie, Negentropie, Blockentropie