Entropie (Informationstheorie)

[[Bild:Shannon 2.jpeg|thumb|]]

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 Begriffes Entropie geht auf Claude E. Shannon zurück und existiert seit etwa 1948. In diesem Jahr veröffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prägte damit die moderne Informationstheorie.

Inhaltsverzeichnis

1 Definition

2 Interpretation

3 Beispiel: Münzwurf

4 Beispiel: Idealer 6er Würfel

5 Maximaler Entropiewert und Normierung

6 Datenkompression und Entropie

7 Beispiel: Entropiekodierung

8 Alternative Möglichkeiten der Informationsquantifizierung

9 Literatur

10 Siehe auch

11 Weblinks

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 Entropie erhält die Pseudoeinheit bit. 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 sich die Berechnung der Entropie auch auf andere Zahlensysteme (etwa Oktalsystem, Hexadezimalsystem) als das Binärssystem (Basis 2) übertragen. In diesem Fall wird der Logarithmus nicht zur Basis 2, sondern zur entsprechenden informationstheoretischen Basis des Zahlensystems gebildet.

Die Verallgemeinerung der Entropie für eine multivariate Zufallsvariable wird Blockentropie beziehungsweise Verbundentropie genannt.

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 Zahl $H (I)$ gibt intuitiv die durchschnittliche Information an, die in einem Symbol der Quelle enthalten ist.

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, die beide auf Verbundwahrscheinlichkeiten aufbauen.

In engem Zusammenhang zur bedingten Entropie steht auch die Transinformation, die die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen angibt.

Beispiel: Münzwurf

Bei einem Münzwurf sind idealerweise „Kopf“ oder „Zahl“ gleichwahrscheinlich. Indem man die Entropie als Maß für die Ungewissheit auffasst, wird sie hier daher einen maximalen Wert aufweisen. Es ist völlig ungewiss, ob beim nächsten Wurf „Kopf“ oder aber „Zahl“ geworfen wird. Die Entropie wird hier als 1 bit definiert.

Wiederholt man den Münzwurf 2 mal wächst die Zahl der Möglichkeiten auf 4. Die Wahrscheinlichkeit jeder einzelnen Möglichkeit liegt bei 0,25. Die Entropie des zweimaligen Münzwurfes ist dann 2 bit.

Anders bei einer gezinkten Münze, etwa einer Münze, die im Mittel in 60 % der Fälle „Kopf“ und nur in 40 % der Fällen „Zahl“ anzeigt. Die Ungewissheit ist hier geringer als bei der normalen Münze, da man eine gewisse Präferenz für „Kopf“ hat. Gemessen als Entropie liegt die Ungewissheit bei nur noch etwa 0,971 .

Sei nun eine Folge von Münzwürfen als Bitfolge zu speichern. Während es sich bei der normalen Münze anbietet, „Kopf“ stets durch 0 und „Zahl“ stets durch 1 zu repräsentieren (oder umgekehrt), so sind bei der gezinkten Münze kompaktere Kodierungen möglich. Diese erhält man beispielsweise durch den Huffman-Kode. Im Mittel benötigt man hier pro Münzwurf nur etwa 0,971 Bit. Dies ist genau der Wert der Entropie.

Beispiel: Idealer 6er Würfel

Bei einem Wurf eines idealen Würfels mit 6 Möglichkeiten ist die Entropie größer als 1. Allgemein ist sie größer als eins für ein Zufallsereignis aus einem Zufallsexperiment mit mehr als 2 gleichberechtigten Möglichkeiten im Ergebnisraum. Ihr Wert wird bei gleichwahrscheinlichen Möglichkeiten im Ergebnisraum folgendermaßen berechnet:

H =  log₂(Zahl der gleichberechtigten Elemente im Ergebnisraum ).

Beim idealen Würfel sind 6 Möglichkeiten im Ergebnisraum. Daraus folgt die Entropie für einmal werfen:

H = log₂ 6 = log₂ 2*3 = log₂ 2 + log₂ 3 = 1 + log₂ 3  1 + 1.585 = 2.585 bit

Einfach zu berechnen ist die Entropie eines Wurfes eines idealen Achterwürfels: Er hat 8 gleichberechtigte Möglichkeiten.

H = log₂ 8 = 3 bit

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_{\mathrm{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_{\mathrm{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.

Um die Entropien von Nachrichten unterschiedlicher Länge vergleichen zu können, hat man die Entropierate eingeführt, die die Entropie auf das einzelne Zeichen bezieht (s. dort).

Datenkompression und Entropie

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

In diesem Zusammenhang spielen die Kreuzentropie sowie die Kullback-Leibler-Divergenz als Maße für die durch eine schlechte Kodierung ausgelösten Verschwendungen von Bits eine Rolle.

Beispiel: Entropiekodierung

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$

$\mbox{Entropie}=-(0.5*\log_2{0.5} + 0.25*\log_2{0.25} + 2*(0.125*\log_2{0.125}))= 1.75 \, \mbox{Bit}/\mbox{Zeichen}$
Maximalentropie ( $p a = p b = p c = p d = 0.25$ ):
$\mbox{Entropie}_{\mbox{max}}= -4*(0.25*log_2{0.25})= -log_2{4^{-1}}= log_2{4} = 2\, \mbox{Bit}/\mbox{Zeichen}$

Alternative Möglichkeiten der Informationsquantifizierung

Ein anderer Zugang, den Informationsgehalt einer Nachricht zu messen, ist durch die Kolmogorow-Komplexität gegeben, worin der kürzestmögliche Algorithmus zur Darstellung einer gegebenen Zeichenkette die Komplexität der Nachricht angibt. Ähnlich ist die Logische Tiefe definiert, die sich aber auf die Laufzeit bzw. Zeitkomplexität eines Algorithmus zur Erzeugung der Daten bezieht. Gregory Chaitin ist ebenfalls über die Shannonsche Definition der Entropie einer Information hinausgegangen (siehe Algorithmische Informationstheorie).

Literatur

Johanneson, Rolf: Informationstheorie, Addison-Wesley 1992, ISBN 3893194657
Shannon, Claude E. und Warren Weaver: The Mathematical Theory of Communication, University of Illinois Press 1963, ISBN 0252725484 (Softcover) und ISBN 0252725468 (Hardcover)
Norbert Bischof: Struktur und Bedeutung, 1998, ISBN 3456830807 (Das Buch ist für Sozialwissenschaftler geschrieben und erklärt mathematische Zusammenhänge Nicht-Mathematikern in sehr verständlicher Weise. Das Kapitel 2 widmet sich der informationstheorie.)

Siehe auch

Kolmogorov-Entropie, Kolmogorov-Sinai-Entropie, Maximum-Entropie-Methode, Metrische Entropie, Nat, Ornstein Theorem, Redundanz, Topologische Entropie, Markow-Kette, Renyi-Entropie, Negentropie, Entropiekodierung

Entropie, Entropie (Physik)

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.