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

Eine mathematische Theorie der Kommunikation

Claude Shannon zeigte, wie ein "Englisch aussehender" Text mit Hilfe von Markov-Ketten generiert werden kann. 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

Shannon hatte gerade die Entwicklung seiner Theorien zur Kryptographie entwickelt. Ihm war bewusst, dass die menschliche Kommunikation eine Mischung war aus Zufälligkeit und statistischen Abhängigkeiten. Die Buchstaben in unseren Nachrichten waren offensichtlich abhängig von vorherigen Buchstaben. Im Jahr 1949 veröffentlichte er einen bahnbrechenden Artikel: "Eine mathematische Theorie der Kommunikation". Darin verwendet er Markov-Modelle als Grundlage dafür, wie wir über Kommunikation denken können. Er beginnt mit einem kleinen Beispiel: Stell dir vor, du siehst einen Haufen Text, geschrieben in einem Alphabet aus A, B und C. Vielleicht weißt du nichts über diese Sprache, aber du bemerkst, dass As aneinander zu klumpen scheinen, während Bs und Cs das nicht tun. Er zeigt dann, dass man eine Maschine entwerfen kann, die ähnlich aussehenden Text erzeugt. Mit Hilfe einer Markov-Kette. Er beginnt mit einer Annäherung der nullten Ordnung. Das heißt, wir wählen einfach unabhängig jedes Symbol A, B oder C zufällig aus und bilden eine Abfolge. Beachte jedoch, dass diese Folge nicht wie das Original aussieht. Er zeigt, dass man es besser machen kann mit einer Approximation erster Ordnung. Hier werden die Buchstaben unabhängig voneinander gewählt, aber nach der Wahrscheinlichkeit der einzelnen Buchstaben in der ursprünglichen Reihenfolge. Das ist etwas besser, da As nun wahrscheinlicher sind, aber es hat immer noch nicht die gleiche Struktur. Der nächste Schritt ist entscheidend. Eine Approximation zweiter Ordnung berücksichtigt alle Buchstabenpaare, die vorkommen können. In diesem Fall brauchen wir drei Zustände. Der erste Zustand steht für alle Paare, die mit A beginnen. Der zweite alle Paare, die mit B beginnen und der dritte Zustand alle Paare, die mit C beginnen. Beachte nun, dass der A-Becher viele AA-Paare hat. Das macht Sinn, denn die bedingte Wahrscheinlichkeit für ein A nach einem A höher ist in unserer ursprünglichen Nachricht. Wir können eine Sequenz mit diesem Modell zweiter Ordnung relativ einfach erzeugen. Wir beginnen irgendwo und wählen ein Plättchen. Wir notieren uns davon den ersten Buchstaben. und bewegen uns zu dem Becher, der durch durch den zweiten Buchstaben definiert ist. Dann wählen wir ein neues Plättchen und wiederholen diesen Vorgang unendlich oft. Beachte, dass diese Abfolge nun langsam der ursprünglichen Nachricht ähnlich sieht. Denn dieses Modell erfasst die bedingten Abhängigkeiten zwischen Buchstaben. Wenn wir es noch besser machen wollen, gibt es die Approximation dritter Ordnung. Sie berücksichtigt Folgendes: Gruppen von drei Buchstaben, sogenannte "Trigramme". In diesem Fall würden wir neun Zustände benötigen. Aber als nächstes wendet Shannon genau dieselbe Logik auf einen tatsächlichen englischen Text an, indem er Statistiken verwendet, die für Buchstaben, Paare und Trigramme etc. bekannt waren. Er zeigt das gleiche Fortschreiten von der nullten Ordnung (zufällige Buchstaben) zur ersten Ordnung, zweiter Ordnung und Sequenzen der dritten Ordnung. Anschließend versucht er das Gleiche mit Wörtern anstelle von Buchstaben, und er schreibt: "Die Ähnlichkeit mit gewöhnlichem englischen Text nimmt mit der Tiefe immer weiter zu." In der Tat produzierten diese Maschinen nichtssagenden Text, obwohl sie ungefähr die gleiche statistische Struktur beinhalten, die man auch in der englischen Sprache findet. Shannon definiert dann ein quantitatives Maß für Information, als er feststellt, dass die Menge an Information einer Nachricht im Design der Maschine gebunden sein muss, welche die ähnlich aussehenden Sequenzen erzeugt. Das bringt uns zu seinem Konzept der Entropie.