If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Informationsentropie

Schließlich erreichen wir unser Quantifizierung für Entropie. Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Stelle dir zwei Maschinen vor. Sie geben beide Nachrichten aus einem Alphabet von A, B, C oder D aus. Maschine Eins generiert jedes Symbol zufällig, sie treten alle in 25% der Fälle auf, während Maschine Zwei Symbole gemäß den folgenden Wahrscheinlichkeiten generiert. Welche Maschine produziert mehr Informationen? Claude Shannon hat die Frage clever umformuliert. Wenn du das nächste Symbol von jeder Maschine vorhersagen müsstest, wie viele Ja- oder Nein-Fragen würdest du im Durchschnitt stellen? Schauen wir uns Maschine 1 an. Der effizienteste Weg ist, eine Frage zu stellen, die die Möglichkeiten halbiert. Zum Beispiel könnte unsere erste Frage sein, ob es eines von zwei Symbolen ist, "A oder B?", da es eine 50% Chance auf A oder B und eine 50% Chance auf C oder D gibt. Nachdem wir die Antwort erhalten haben, können wir die Hälfte der Möglichkeiten ausschließen, und uns bleiben zwei Symbole, beide gleich wahrscheinlich. Also wählen wir einfach eines aus, wie "Ist es A?". und nach dieser zweiten Frage, haben wir das Symbol korrekt identifiziert. Wir können sagen, die Unsicherheit von Maschine Eins beträgt zwei Fragen pro Symbol. Und wie sieht es mit Maschine Zwei aus? Wie bei Maschine Eins könnten wir zwei Fragen stellen, um das nächste Symbol zu bestimmen. Dieses Mal ist jedoch die Wahrscheinlichkeit jedes Symbols unterschiedlich, sodass wir unsere Fragen anders stellen können. Hier hat A eine 50% Chance aufzutreten, und alle anderen Buchstaben addieren sich zu 50%. Wir könnten damit beginnen zu fragen "Ist es A?". Und wenn es A ist, sind wir fertig. Nur eine Frage in diesem Fall. Andernfalls bleiben uns zwei gleichwertige Ergebnisse übrig, D oder B und C. Wir könnten fragen, "Ist es D?". Wenn ja, sind wir mit zwei Fragen fertig. Andernfalls müssen wir eine dritte Frage stellen, um festzustellen, welches der beiden letzten Symbole es ist. Im Durchschnitt, wie viele Fragen erwartest du zu stellen, um ein Symbol von Maschine Zwei zu bestimmen? Das lässt sich gut mit einer Analogie erklären. Nehmen wir an, wir wollen stattdessen Maschine Eins und Maschine Zwei bauen. Wir können Symbole erzeugen, indem wir eine Scheibe in eine von zwei gleich wahrscheinlichen Richtungen von einem Zapfen abprallen lassen. Je nachdem, in welche Richtung sie fällt, können wir ein Symbol generieren. Bei Maschine Eins müssen wir eine zweite Ebene oder einen zweiten Sprung hinzufügen, sodass wir zwei Sprünge haben, die zu vier gleich wahrscheinlichen Ergebnissen führen. Je nachdem, wo die Scheibe landet, geben wir A, B, C oder D aus. Jetzt Maschine Zwei. In diesem Fall führt der erste Sprung entweder zu einem A, das 50% der Zeit auftritt, oder wir gelangen zu einem zweiten Sprung, der dann entweder ein D ausgibt, was in 25% der Fälle passiert, oder es führt zu einem dritten Sprung, der dann entweder zu B oder C führt, 12,5% der Zeit. Jetzt nehmen wir einfach ein gewichtetes Durchschnittsmaß wie folgt. Die erwartete Anzahl von Sprüngen ist die Wahrscheinlichkeit des Symbols A multipliziert mit einem Sprung, plus die Wahrscheinlichkeit von B multipliziert mit drei Sprüngen, plus die Wahrscheinlichkeit von C multipliziert mit drei Sprüngen, plus die Wahrscheinlichkeit von D multipliziert mit zwei Sprüngen. Das ergibt 1,75 Sprünge. Beachte die Verbindung zwischen Ja- oder Nein-Fragen und fairen Sprüngen. Die erwartete Anzahl der Fragen entspricht der erwarteten Anzahl der Sprünge. So benötigt Maschine Eins zwei Sprünge, um ein Symbol zu erzeugen, während das Erraten eines unbekannten Symbols zwei Fragen erfordert. Maschine Zwei benötigt 1,75 Sprünge. Wir müssen durchschnittlich 1,75 Fragen stellen. Wenn wir hundert Symbole von beiden Maschinen erraten müssen, ewarten wir, dass wir für Maschine eins 200 Fragen stellen müssen und für Maschine zwei 175. Das bedeutet, dass Maschine Zwei weniger Informationen produziert, weil es weniger Unsicherheit oder Überraschung über ihre Ausgabe gibt. Und das war's. Claude Shannon nennt dieses Maß für durchschnittliche Unsicherheit "Entropie" und er verwendet den Buchstaben H, um es darzustellen. Die Einheit der Entropie, die Shannon wählt, basiert auf der Unsicherheit eines fairen Münzwurfs. Und er nennt das "Bit", was einem fairen Wurf gleichkommt. Wir können zu demselben Ergebnis kommen, indem wir unsere Sprunganalogie verwenden. Entropie oder H ist die Summe für jedes Symbol der Wahrscheinlichkeit dieses Symbols multipliziert mit der Anzahl der Sprünge. Der Unterschied liegt darin, wie wir die Anzahl der Sprünge auf eine allgemeinere Weise ausdrücken. Wie wir gesehen haben, hängt die Anzahl der Sprünge davon ab, wie weit wir in der Baumstruktur sind. Wir können dies vereinfachen, indem wir sagen, dass die Anzahl der Sprünge dem Logarithmus zur Basis zwei der Anzahl der Ergebnisse auf dieser Ebene entspricht. Die Anzahl der Ergebnisse auf einer Ebene basiert auch auf der Wahrscheinlichkeit, wobei die Anzahl der Ergebnisse auf einer Ebene gleich eins geteilt durch die Wahrscheinlichkeit dieses Ergebnisses ist. Die Anzahl der Sprünge entspricht tatsächlich dem Logarithmus zur Basis zwei von eins geteilt durch die Wahrscheinlichkeit dieses Symbols, was uns unsere endgültige Gleichung gibt. Entropie oder H ist die Summe für jedes Symbol der Wahrscheinlichkeit dieses Symbols multipliziert mit dem Logarithmus zur Basis zwei von eins geteilt durch die Wahrscheinlichkeit dieses Symbols. Shannon schreibt dies ein wenig anders, indem er den Ausdruck innerhalb des Logarithmus umkehrt, was dazu führt, dass wir ein negatives Zeichen hinzufügen. Beide Formeln liefern dasselbe Ergebnis. Zusammenfassend lässt sich sagen, dass die Entropie maximal ist, wenn alle Ergebnisse gleich wahrscheinlich sind. Jedes Mal, wenn man sich von gleich wahrscheinlichen Ergebnissen entfernt oder Vorhersagbarkeit einführt, muss die Entropie sinken. Die grundlegende Idee ist, dass wenn die Entropie einer Informationsquelle sinkt, wir weniger Fragen stellen müssen, um das Ergebnis zu erraten. Dank Shannon wurde das Bit, die Einheit der Entropie, als quantitative Messung von Informationen oder Messung von Überraschung übernnommen.