Entropie (Informationstheorie)

Entropie ist ein Maß für die Menge an Zufallsinformation, die in einem System oder einer Informationsfolge steckt. Der 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.

Definition

Claude Elwood Shannon (1916-2001) definierte die Entropie H einer gegebenen Information I über einem Alphabet Z durch

(1)

H(I) = - \sum_{j=1}^{|Z|}{p_j} \cdot  log_{|Z|}({p_j})

wobei p_j die Wahrscheinlichkeit ist, mit der das j-te Symbol z_j des Alphabets Z im Informationtext I auftritt. Zur Berechnung wählt man oft eine andere Basis als Z, z.B. e oder 10. Für die Basis 2 lautet (1):

(2)

H(I) = - \frac{1}{log_2(|Z|)} \cdot  \sum_{j=1}^{|Z|}{p_j} \cdot  log_2({p_j})

H multipliziert mit der Anzahl der Zeichen im Informationstext ergibt dann die mindestens notwendige Anzahl von Symbolen, die zur Darstellung der Information notwendig sind.

Der Begriff Alphabet wird hier in einem verallgemeinerten Sinne gebraucht. Die 26 Groß- und Kleinbuchstaben, das Leerzeichen und einige Satzzeichen bilden z.B. ein Alphabet zur Darstellung von Texten. Zur Darstellung der natürlichen Zahlen bilden die Ziffern 0 bis 9 ein häufig benutztes Alphabet. Zahlen können auch mit 8 Ziffern im Oktalsystem, 16 "Ziffern" 0-9A-F im Hexadezimalsystem oder nur durch 2 Ziffern im Binärssystem dargestellt werden. Im Binärsystem wird der Logarithmus zur Basis 2 gebildet.

Eine Information lässt sich mit jedem Alphabet mit mindestens 2 Symbolen darstellen. Weniger übersichtlich auch mit einem Symbol (Unärdarstellung).

Interpretation

Entropie ist grob gesagt ein Maß für die Menge an Zufallsinformation, die in einem System oder einer Informationsfolge steckt. Dabei ist die Einheit der Zufallsinformation (1 Shannon) definiert als die Informationsmenge, die in einer Zufallsentscheidung eines idealen Münzwurfes enthalten ist. Ein idealer Münzwurf hat nur zwei Möglichkeiten – Kopf oder Zahl –, die beide mit der gleichen Wahrscheinlichkeit p = 0,5 auftreten.

Shannons ursprüngliche Absicht, die 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.

Nochmal einfacher Formuliert ist die Entropie die durchschnittliche Anzahl von Entscheidungen (bits) die benötigt werden um ein Zeichen aus einer Zeichenmenge zu Identifizieren bzw. zu isolieren.

Beispiel: Alphabet

Bei gleichmäßiger Verteilung kann bei einem Alphabet auf kein Zeichen verzichtet werden. Dagegen ist die Buchstabenhäufigkeit in der deutschen Sprache ungleichmäßig. Beispielsweise ist der Buchstabe E 7 Mal häufiger als M oder O. Setzt man die Wahrscheinlichkeiten in (1) ein und multipliziert mit N = 26, d.i. die Anzahl der Zeichen , erhält man:

H(I) \cdot N = 22{,}5

Ohne Informationsverlust könnte das Alphabet um 3 Buchstaben reduziert werden. Diese Überlegung berücksichtigt nur die statistische Verteilung der Buchstaben. Häufige Buchstabenkombinationen wie SCH oder ST bleiben genauso unberücksichtigt wie gleich klingende Buchstaben (Q, K).

Beispiel: Münzwurf

Bei einem Münzwurf sind idealerweise „Kopf“ oder „Zahl“ gleichwahrscheinlich. Wenn man die Entropie als Maß für die Ungewissheit auffasst, wird sie hier 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.

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älle „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.

Die Summe der Wahrscheinlichkeiten ist immer 1.

p + q = 1

Die Entropie lässt sich in diesem Fall mit folgender Formel berechnen:

H = - ( p \cdot \log_2 p + q \cdot \log_2 q)

Ersetzt man $q$ durch den Ausdruck $1-p$ , so erhält man die Formel

H = - ( p \cdot \log_2 p + ( 1 - p ) \cdot \log_2 (1 - p))

Dies kann man grafisch folgendermaßen darstellen:

Entropq.gif

Für jedes $p$ kann man daraus die Entropie direkt ablesen. Die Funktion ist symmetrisch zur Geraden $p = 0{,}5$ . Sie fällt bei $p = 0$ sehr steil zu einem Entropie-Wert von 0 ab. Auch bei Werten, die sich dem sicheren Ereignis von $p = 1$ nähern, fällt die Entropie auf 0 ab.

Dieser Zusammenhang gilt jeweils für ein Zufallsereignis. Bei mehreren Zufallsereignissen muss man die einzelnen Entropien zusammenzählen und man kann so leicht Entropiewerte über 1 erreichen. Die Wahrscheinlichkeit $p$ dagegen bleibt auch bei Wiederholungen definitionsgemäß immer zwischen 0 und 1!

Wiederholt man den Münzwurf zweimal, wächst die Zahl der Möglichkeiten auf vier. Die Wahrscheinlichkeit jeder einzelnen Möglichkeit liegt bei 0,25. Die Entropie des zweimaligen Münzwurfes ist dann 2 Sh. Wenn man einen idealen Münzwurf mehrfach wiederholt, dann addiert sich die Entropie einfach. Die Entropie einer Reihe von 20 idealen Münzwürfen berechnet sich einfach: $H = 20 \cdot 1\ \mbox{bit} = 20\ \mbox{bit}$ . Dies wird im folgenden Bild dargestellt.

Entrosum.gif

Man kann nicht einfach aus einem Wert der Wahrscheinlichkeit die Entropie ausrechnen. Die Entropie betrifft den gesamten Zufallsprozess. Jede Teilwahrscheinlichkeit eines möglichen Ergebnisses geht in die Berechnung der Entropie des Gesamtprozesses ein. Die Angabe einer Teilentropie für jedes mögliche Ergebnis macht dabei wenig Sinn. In der Shannonschen Entropieformel sollte also die Summe der Wahrscheinlichkeiten 1 ergeben, sonst kann es ein missverständliches Ergebnis geben.

Speichert man eine Folge von Münzwürfen als Bitfolge, dann bietet es sich an, „Kopf“ stets durch 0 und „Zahl“ stets durch 1 zu repräsentieren (oder umgekehrt). Bei der gezinkten Münze sind kompaktere Kodierungen möglich. Diese erhält man beispielsweise durch den Huffman-Kode.

Beispiel: Idealer Würfel

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

H = \log_2(Zahl\ der\ gleichberechtigten\ Elemente\ im\ Ergebnisraum)

Beim idealen Würfel sind sechs Möglichkeiten im Ergebnisraum. Daraus folgt die Entropie für einmaliges Werfen:

H = \log_2 6 = \log_2 (2 \cdot 3) = \log_2 2 + \log_2 3 = 1 + \log_2 3 \approx 1 + 1{,}585 = 2{,}585\ \mbox{Sh}

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

H = \log_2 8 = 3\ \mbox{Sh}

Die Entropie eines Wurfes mit dem idealen Achterwürfel entspricht der Entropie von drei Würfen mit der idealen Münze.

Die folgende Abbildung stellt den Zusammenhang zwischen der Entropie und der Zahl der gleichberechtigten Möglichkeiten eines Zufallsexperimentes dar.

Entrurne.gif

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:

\frac{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 ${H_{\mathrm{max}}}$ .

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 (siehe dort).

Entropietests

Um zu testen, wie gut Daten komprimierbar sind, oder um Zufallszahlen zu testen, werden Entropietests verwendet. Als Zufallszahltest wird die Entropie einer bestimmen Anzahl von Zufallszahlen bestimmt und ab einem Mindestwert, beispielsweise 7 Bit je Byte, gilt er als bestanden. Allerdings gibt es viele solcher Tests, da die Entropie nicht eindeutig ist; sie kann beispielsweise bitbasiert oder bytebasiert definiert sein.

Ein einfaches Beispiel:

Eine Quelle, z. B. ein Spielwürfel oder eine Münze, gebe nur die Werte 0xAA (dezimal 170) und 0x55 (dezimal 85) aus, beide mit gleicher Wahrscheinlichkeit. Bitweise ist der output zu 50 % 0 oder 1, byteweise ist er zu 50 % 0xAA oder 0xFF. Die bitweise Entropie ist (mit log = ln)

$H = 1/log(2) (1/2 \cdot log(1/2) +1/2 \cdot log(1/2)) = 1$

während die byteweise Entropie mit $H = 1/log(8) *(1/2 *log(1/2) +1/2 *log(1/2)) = 1/3$

deutlich kleiner ist.

Der Hersteller dieses Zufallszahlengenerator wird natürlich als Entropie des Geräts die bitweise Entropie, also 1, angeben. Analog wird ein Programmierer eines Kompressionsprogramms möglichst diejenige Basis wählen, bei der die Entropie minimal ist (hier Bytes), sich also die Daten am besten komprimieren lassen.

Dieses Beispiel ist wenig realistisch, da nur zwei von 256 möglichen Werten verwendet werden, aber wenn auch die anderen Bytes mit einer kleinen Wahrscheinlichkeit von z. B. 1/123456789 ausgegeben, so ändert dies an der bitweisen Entropie nichts und die byteweise wird kaum größer; sie bleibt unter 1/2. Erst mit Annäherung der Byte-Wahrscheinlichkeiten an 1/256 erreicht die byteweise Entropie den Wert 1, aber dann kann es noch Korrelationen der Bytes geben, also z. B. die Folge 0xaaaa viel häufiger sein als die Folge 0x5555. Dies ist der Hauptgrund, weshalb es viele verschiedene Zufallszahlentests gibt.

Diese Mehrdeutigkeit ist nicht möglich beim Entropiebelag, da dort nicht nur über Wahrscheinlichkeiten summiert wird, sondern über ergodische Wahrscheinlichkeiten von Zuständen, Zustandsübergangswahrscheinlichkeiten und bedingte Wahrscheinlichkeiten. Berechnet wird er mit der Theorie der Markov-Kette. Allerdings ist der Rechenaufwand dafür bei realen Zufallszahlengeneratoren sehr hoch.

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ß für die durch eine schlechte Kodierung ausgelösten Verschwendungen von Bits eine Rolle.

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$
$H = - (0{,}5\cdot\log_2{0{,}5} + 0{,}25\cdot\log_2{0{,}25} + 2\cdot(0{,}125\cdot \log_2{0{,}125})) = 1{,}75$
Maximalentropie ( $p_A = p_B = p_C = p_D = 0{,}25$ ):
$H_{max} = -4\cdot(0{,}25\cdot\log_2{0{,}25})= -\log_2{4^{-1}}= \log_2{4} = 2$

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 angegeben wird. Ä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
Claude Elwood Shannon 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.)
Sven P. Thoms: Ursprung des Lebens. Frankfurt: Fischer 2005 ISBN 3-5961-6128-2 (Das Buch ist aus biologischer und chemischer Perspektive geschrieben. Ein Kapitel behandelt den Zusammenhang von Leben und Entropie.)

Siehe auch

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

Entropie

Weblinks

http://www.madeasy.de/2/zufallgz.htm
- Einführung der Entropie als Gesamtzufallsmenge mit vielen Beispielen und hilfreichen Erklärungen zur Formel von Shannon.
http://www.techfak.uni-kiel.de/matwis/amat/mw1_ge/kap_5/advanced/t5_3_2.html
- Entropie und Information, gut erklärt

Kybernetik | Theoretische Informatik | Informationstheorie

Gourt Home::Gourt :: Entropie (Informationstheorie)