Entropie

Wenn du ein Passwort erstellst, sind manche Passwörter leicht zu erraten und andere kaum. Auch bei einem Münzwurf weißt du vorher nicht sicher, was kommt. In der Informatik gibt es ein Maß dafür, wie viel Unsicherheit in solchen Zeichen, Zahlen oder Nachrichten steckt.

Deine Lernziele

• Du verstehst Entropie als Maß für Unsicherheit und durchschnittliche Information.
• Du erkennst den Zusammenhang zwischen Wahrscheinlichkeit und Informationsgehalt.
• Du berechnest einfache Entropie-Werte in Bit.
• Du erklärst, warum Entropie für Codes, Speicherplatz und Passwörter wichtig ist.

Von Unsicherheit zu Information

Stell dir vor, deine Lehrkraft wirft eine faire Münze. Vor dem Wurf sind Kopf und Zahl gleich möglich. Du bist unsicher. Nach dem Wurf ist die Unsicherheit weg.

Unsicherheit bedeutet hier: Du weißt noch nicht, welches Ergebnis eintreten wird. Information bedeutet: Eine Nachricht nimmt dir Unsicherheit weg. Wenn dir jemand sagt „Kopf“, weißt du mehr als vorher.

Definition

Information ist in der Informationstheorie nicht die Bedeutung eines Satzes, sondern die Verringerung von Unsicherheit durch eine Nachricht.

Wenn etwas sicher ist, bringt die Nachricht kaum neue Information. Wenn deine App jeden Tag dieselbe Meldung zeigt, überrascht dich die Meldung nicht. Wenn aber viele Ergebnisse möglich sind, bringt das tatsächliche Ergebnis mehr Information.

Beispiel

Eine Münze hat zwei mögliche Ergebnisse: Kopf oder Zahl. Die Nachricht „Kopf“ klärt eine von zwei gleich wahrscheinlichen Möglichkeiten.

Ein Würfel hat sechs mögliche Ergebnisse. Die Nachricht „Es ist eine 5“ klärt eine von sechs gleich wahrscheinlichen Möglichkeiten. Das ist mehr Unsicherheit als bei der Münze.

Merke

Je mehr echte Möglichkeiten offen sind, desto mehr Unsicherheit kann eine Nachricht beseitigen.

Entropie als Durchschnitt

Nun brauchst du ein Maß für die Unsicherheit einer ganzen Quelle. Eine Quelle ist in der Informatik ein Erzeuger von Zeichen oder Nachrichten. Das kann eine Münze, ein Würfel, ein Textgenerator oder ein Sensor sein.

Entropie ist der durchschnittliche Informationsgehalt einer Quelle. Durchschnittlich heißt: Du betrachtest alle möglichen Ergebnisse und berücksichtigst, wie wahrscheinlich sie sind.

Definition

Entropie ist ein Maß dafür, wie viel Information eine Quelle im Durchschnitt pro Ergebnis liefert. Sie wird oft mit \(H\) bezeichnet.

Die Einheit ist Bit. Ein Bit entspricht der Information einer fairen Ja-Nein-Entscheidung. Eine faire Münze hat deshalb eine Entropie von 1 Bit pro Wurf.

Beispiel

Quelle A sendet immer das Zeichen A. Du weißt vorher sicher, was kommt. Die Entropie ist 0 Bit.

Quelle B sendet zufällig 0 oder 1, beide gleich oft. Du musst eine echte Ja-Nein-Entscheidung klären. Die Entropie ist 1 Bit.

Quelle C würfelt fair mit 8 gleich wahrscheinlichen Seiten. Weil \(2^3 = 8\) gilt, brauchst du 3 Bit, um ein Ergebnis zu unterscheiden.

Merke

Entropie ist nicht die Information eines einzelnen Ergebnisses, sondern der Durchschnitt über die ganze Quelle.

Wahrscheinlichkeit und Informationsgehalt

Nicht jedes Ergebnis ist gleich überraschend. Ein seltenes Ergebnis liefert mehr Information als ein häufiges Ergebnis.

Der Informationsgehalt eines einzelnen Ergebnisses misst, wie überraschend dieses Ergebnis ist. Er hängt von der Wahrscheinlichkeit ab. Eine Wahrscheinlichkeit ist eine Zahl zwischen 0 und 1. Sie beschreibt, wie oft ein Ergebnis langfristig zu erwarten ist.

Definition

Der Informationsgehalt eines Ergebnisses mit Wahrscheinlichkeit \(p\) ist

$$ I = -\log_2(p) $$

Dabei bedeutet \(\log_2\): Logarithmus zur Basis 2.

Du musst den Logarithmus nicht sofort perfekt beherrschen. Für wichtige Werte kannst du dir merken: Wenn ein Ergebnis die Wahrscheinlichkeit \(1/2\) hat, hat es 1 Bit Informationsgehalt. Bei \(1/4\) sind es 2 Bit. Bei \(1/8\) sind es 3 Bit.

Beispiel

Bei einer fairen Münze ist die Wahrscheinlichkeit für Kopf \(p = 1/2\).

$$ I = -\log_2(1/2) = 1 $$

Die Nachricht „Kopf“ hat also 1 Bit Informationsgehalt.

Bei einem fairen 8-seitigen Würfel ist jedes Ergebnis mit \(p = 1/8\) wahrscheinlich.

$$ I = -\log_2(1/8) = 3 $$

Ein bestimmtes Ergebnis liefert 3 Bit Information.

Merke

Seltene Ergebnisse sind informativer, weil sie mehr Möglichkeiten ausschließen.

Entropie berechnen

Für Entropie reicht ein einzelnes Ergebnis nicht. Du brauchst alle möglichen Ergebnisse und ihre Wahrscheinlichkeiten.

Wenn eine Quelle die Ergebnisse \(x_1, x_2, ..., x_n\) mit Wahrscheinlichkeiten \(p_1, p_2, ..., p_n\) hat, lautet die Shannon-Entropie:

Das Summenzeichen \(\sum\) bedeutet: Rechne den Ausdruck für alle Ergebnisse aus und addiere alles.

Beispiel

Eine faire Münze hat zwei Ergebnisse.

Kopf: \(p = 0{,}5\)

Zahl: \(p = 0{,}5\)

$$ H = -(0{,}5 \cdot \log_2(0{,}5) + 0{,}5 \cdot \log_2(0{,}5)) $$

Weil \(\log_2(0{,}5) = -1\) ist:

$$ H = -(0{,}5 \cdot -1 + 0{,}5 \cdot -1) = 1 $$

Die Entropie beträgt 1 Bit.

Beispiel

Eine gezinkte Münze zeigt Kopf mit \(0{,}75\) und Zahl mit \(0{,}25\).

$$ H = -(0{,}75 \cdot \log_2(0{,}75) + 0{,}25 \cdot \log_2(0{,}25)) $$

Das ergibt ungefähr \(0{,}81\) Bit.

Die Entropie ist kleiner als 1 Bit, weil Kopf wahrscheinlicher ist und du weniger unsicher bist.

Merke

Die Entropie ist am größten, wenn alle möglichen Ergebnisse gleich wahrscheinlich sind.

Entropie bei Zeichen und Codes

Computer speichern Zeichen als Folgen von 0 und 1. Ein Code ordnet jedem Zeichen eine Bitfolge zu. Ein guter Code nutzt kurze Bitfolgen für häufige Zeichen und längere Bitfolgen für seltene Zeichen.

Redundanz bedeutet: Ein Code enthält mehr Bits, als im Durchschnitt unbedingt nötig wären. Redundanz kann Platz verschwenden. Manchmal ist sie aber nützlich, zum Beispiel zur Fehlererkennung.

Definition

Ein Code ist eine Regel, die Zeichen in andere Zeichenfolgen übersetzt, zum Beispiel Buchstaben in Bits. Redundanz ist der zusätzliche Anteil eines Codes über der theoretisch nötigen durchschnittlichen Länge.

Entropie sagt dir eine untere Grenze: Im Durchschnitt kannst du eine Quelle nicht mit weniger Bits pro Zeichen speichern als ihre Entropie. Für einzelne Zeichen kann ein Code länger oder kürzer sein. Entscheidend ist der Durchschnitt.

Beispiel

Eine Quelle sendet vier Zeichen:

A mit Wahrscheinlichkeit \(1/2\)

B mit Wahrscheinlichkeit \(1/4\)

C mit Wahrscheinlichkeit \(1/8\)

D mit Wahrscheinlichkeit \(1/8\)

Häufiges A bekommt einen kurzen Code, zum Beispiel 1. Seltene Zeichen bekommen längere Codes, zum Beispiel 010 oder 011. So kann die mittlere Codelänge nahe an der Entropie liegen.

Gut zu wissen

Komprimierung nutzt solche Muster. Wenn Zeichen oder Wörter ungleich häufig vorkommen, kann man häufige Teile kürzer speichern. Wenn alles völlig gleichmäßig und unvorhersagbar ist, ist starke Komprimierung schwer.

Grenzen und typische Fehler

Entropie ist ein starkes Werkzeug, aber sie misst nicht alles. Sie betrachtet Wahrscheinlichkeiten. Sie versteht nicht automatisch Bedeutung, Grammatik oder Absicht.

Wenn du nur einzelne Zeichen zählst, können zwei Zeichenketten gleich aussehen, obwohl sie unterschiedlich geordnet sind. Die Folge 0101010101 und eine zufällig wirkende Folge mit gleich vielen Nullen und Einsen können bei einfacher Zeichenzählung dieselbe Entropie haben. Trotzdem ist die erste Folge leichter beschreibbar.

Definition

Bedingte Entropie betrachtet, wie viel Unsicherheit bleibt, wenn du schon etwas weißt. Zum Beispiel: Wie unsicher ist der nächste Buchstabe, wenn du die vorherigen Buchstaben kennst?

Bei Sprache ist das wichtig. Nach dem Buchstaben q kommt im Deutschen sehr oft u. Wenn du das q kennst, bist du über den nächsten Buchstaben weniger unsicher.

Beispiel

Ohne Vorwissen könnte der nächste Buchstabe fast jeder Buchstabe sein.

Nach „Schu“ sind in einem Schulwort bestimmte Fortsetzungen wahrscheinlicher als andere, zum Beispiel „l“. Dein Vorwissen senkt die Unsicherheit.

Merke

Einfache Entropie zählt Wahrscheinlichkeiten einzelner Ergebnisse. Für Muster in Reihenfolgen brauchst du oft bedingte Entropie oder weitere Modelle.

Zusammenfassung

Entropie misst, wie viel Unsicherheit eine Quelle im Durchschnitt hat. In der Informatik wird sie meist in Bit angegeben. Ein sicheres Ergebnis hat 0 Bit, eine faire Münze hat 1 Bit, und ein fairer 8-seitiger Würfel hat 3 Bit.

Der Informationsgehalt eines einzelnen Ergebnisses hängt von seiner Wahrscheinlichkeit ab: Seltene Ergebnisse überraschen stärker. Die Formel dafür ist \(I = -\log_2(p)\). Die Entropie bildet daraus den gewichteten Durchschnitt über alle möglichen Ergebnisse.