Entropie (Informationstheorie)

Begriff und Grundidee

Die informationstheoretische Entropie H ist ein Maß für den mittleren Informationsgehalt der Nachrichten einer Quelle. Anschaulich gibt sie die durchschnittliche Anzahl binärer Entscheidungen beziehungsweise Bits an, die nötig sind, um ein Zeichen aus einer Zeichenmenge zu identifizieren. Information kann dabei als beseitigte Unsicherheit verstanden werden: Ein seltenes Zeichen besitzt einen hohen, ein häufiges Zeichen einen niedrigen Informationsgehalt. Kleine Entropie weist auf Redundanzen oder statistische Regelmäßigkeiten hin.

Für ein Ereignis z mit der Wahrscheinlichkeit p_z ist der Informationsgehalt I(z) = −log₂ p_z. Der Wert entsteht daraus, dass zur Unterscheidung von 1/p_z gleich wahrscheinlichen Möglichkeiten log₂(1/p_z) Bits benötigt werden. Ein Shannon ist der Informationsgehalt eines Ereignisses mit p = 0,5. Die Basis 2 führt zur Einheit Bit; bei Basis 3 erhält man Trits. Die Wahl der Basis ändert nur die Einheit.

Ein Alphabet sollte mindestens zwei Zeichen enthalten. Bei nur einem möglichen Zeichen entstehen weder neue Information noch Unsicherheit. Die Entropie wurde von Claude E. Shannon um 1948 eingeführt und ursprünglich zur Bestimmung der benötigten Bandbreite eines Übertragungskanals verwendet.

Mathematische Definition

Für eine diskrete, gedächtnislose Quelle X über dem endlichen Alphabet Z = {z₁, z₂, …, zₘ} mit p_i = P(X = z_i) ist die Entropie eines Zeichens der Erwartungswert seines Informationsgehalts:

H₁ = E[I] = −∑{z∈Z} p_z log₂ p_z = −∑{i=1}^m p_i log₂ p_i.

Dabei setzt man 0 · log₂ 0 = 0, entsprechend dem Grenzwert lim_{x→0} x log₂ x. Ereignisse mit Wahrscheinlichkeit 0 tragen daher nichts zur Summe bei.

Für Wörter w der Länge n gilt Hₙ = −∑_{w∈Zⁿ} p_w log₂ p_w, wobei p_w = P(X = w). Die Entropie pro Zeichen einer Quelle ist

H = lim_{n→∞} Hₙ/n.

Sind alle Zeichen stochastisch unabhängig, gilt Hₙ = nH₁ und damit H = H₁. Bei abhängigen Zeichen genügt H₁ dagegen nicht. So besitzen die Folgen 101010… und eine Folge unabhängiger Münzwürfe dieselbe Einzelzeichenentropie, weil 0 und 1 jeweils gleich häufig sind. Für Zweierblöcke gilt jedoch H₂ = 1 bei der regelmäßigen Folge und H₂ = 2 bei unabhängigen Würfen. Abhängigkeiten werden unter anderem durch bedingte Entropie und Quellentropie beschrieben. Die Transinformation misst die Stärke des statistischen Zusammenhangs zweier Zufallsgrößen.

Maximum und Normierung

Bei N = |Z| möglichen Zeichen erreicht die Entropie ihr Maximum, wenn alle Zeichen gleich wahrscheinlich sind, also p_i = 1/N. Dann gilt

H_max = −∑_{i=1}^N (1/N) log₂(1/N) = log₂ N.

Für ein binäres Alphabet Z = {0,1} ist H_max = 1 Bit pro Zeichen. Dieser Wert wird erreicht, wenn Nullen und Einsen gleich häufig auftreten. Eine normierte Entropie erhält man durch Division durch das Maximum:

H/H_max = −∑_{i=1}^{|Z|} p_i log_N p_i ≤ 1.

Sie kann höchstens den Wert 1 annehmen. Zum Vergleich von Nachrichten unterschiedlicher Länge verwendet man außerdem die Entropierate, also die auf ein einzelnes Zeichen bezogene Entropie.

Bei gleich verteilten Zeichen beträgt der durchschnittliche Informationsgehalt I(X) = log₂|Z| = log₂N. Für einen Text aus n Zeichen werden damit mindestens n log₂N Bits zur Darstellung benötigt.

Typische Zufallsexperimente

Bei einer idealen Münze sind Kopf und Zahl jeweils mit p = 0,5 wahrscheinlich. Ihre Entropie beträgt H = 1 Bit. Allgemein gilt für eine Münze mit q = 1 − p:

H = −p log₂p − q log₂q = −p log₂p − (1−p) log₂(1−p).

Die Funktion ist symmetrisch zu p = 0,5. Dort liegt ihr Maximum; bei p = 0 oder p = 1 ist H = 0, weil das Ergebnis sicher ist. Bei einer gezinkten Münze mit 60 % Kopf und 40 % Zahl beträgt die Entropie etwa 0,971. Unabhängige Wiederholungen addieren sich: Zwei ideale Würfe besitzen 2 Sh Entropie, 20 Würfe 20 Bit. Die Entropie bezieht sich auf den gesamten Zufallsprozess; alle Ergebniswahrscheinlichkeiten müssen berücksichtigt werden und ihre Summe muss 1 sein.

Für n gleich wahrscheinliche Ergebnisse gilt H = log₂n. Ein idealer sechsseitiger Würfel besitzt daher H = log₂6 = 1 + log₂3 ≈ 2,585 Sh. Für einen idealen Achterwürfel gilt H = log₂8 = 3 Sh; dies entspricht der Entropie dreier idealer Münzwürfe.

Auch natürliche Alphabete sind ungleich verteilt. Für 26 deutsche Buchstaben beträgt H = 4,0629 bit/Zeichen, während H_max = log₂26 = 4,7004 bit/Zeichen ist. Die Redundanz R = H_max − H beträgt somit 0,6375 bit/Zeichen. Hochgerechnet entspricht dies etwa 3,53 beziehungsweise drei Zeichen. Diese Rechnung berücksichtigt allerdings weder häufige Buchstabenfolgen wie SCH oder ST noch gleich klingende Buchstaben wie Q und K.

Entropietests und Datenkompression

Entropietests dienen dazu, die Komprimierbarkeit von Daten oder die Verteilung von Zufallszahlen zu untersuchen. Das Ergebnis hängt davon ab, ob beispielsweise Bits oder Bytes als Zeichen betrachtet werden. Gibt eine Quelle nur 0xAA und 0x55 mit gleicher Wahrscheinlichkeit aus, sind ihre Bits jeweils zu 50 % 0 oder 1; die normierte bitweise Entropie ist deshalb 1. Auf Byteebene treten jedoch nur zwei von 256 Werten auf, sodass die normierte byteweise Entropie 1/8 beträgt. Selbst eine hohe Einzelzeichenentropie kann außerdem verborgene Korrelationen zwischen aufeinanderfolgenden Werten übersehen.

Entropietests messen daher vor allem Gleichwahrscheinlichkeit, nicht echte Unvorhersehbarkeit. Der Unterschied zwischen echten Zufallszahlengeneratoren und Pseudozufallszahlengeneratoren ist auf diese Weise nicht messbar. Der Entropiebelag berücksichtigt zusätzlich ergodische Zustandswahrscheinlichkeiten, Zustandsübergänge und bedingte Wahrscheinlichkeiten mithilfe der Theorie der Markow-Ketten, ist bei realen Generatoren aber aufwendig zu berechnen.

Bei der verlustfreien Datenkompression nutzt die Entropiekodierung ungleiche Zeichenwahrscheinlichkeiten für kompaktere Codes, etwa mittels Huffman-Kodierung. Für ABBCAADA gelten p_A = 0,5, p_B = 0,25 und p_C = p_D = 0,125. Daraus folgen H = 1,75 und bei vier gleich wahrscheinlichen Zeichen H_max = log₂4 = 2. Kreuzentropie und Kullback-Leibler-Divergenz beschreiben in diesem Zusammenhang die Verschwendung von Bits durch eine ungeeignete Kodierung.

Andere Informationsmaße und physikalischer Bezug

Neben Shannons Entropie gibt es weitere Maße. Die Kolmogorow-Komplexität bestimmt die Komplexität einer Zeichenkette durch den kürzestmöglichen Algorithmus, der sie darstellt. Die Logische Tiefe bezieht sich dagegen auf die Zeitkomplexität eines Algorithmus zur Erzeugung der Daten. Gregory Chaitins Arbeiten gehören zur algorithmischen Informationstheorie. Die differentielle Entropie dient dem Vergleich kontinuierlicher Zufallsvariablen.

Die Entropie der Thermodynamik und statistischen Mechanik ist eng mit der Informationsentropie verwandt. Die physikalische Größe verwendet zusätzlich die Boltzmannsche Konstante k_B als Normierungsfaktor und den natürlichen statt des dualen Logarithmus. Physikalische und mathematische Entropie unterscheiden sich dadurch um den Umrechnungsfaktor −k_B ln 2. Ein Zusammenhang wird durch das Gedankenexperiment des Maxwellschen Dämons hergestellt.