Shannons Entropieformel.Hilf meiner Verwirrung

Question

Ich verstehe die Entropieformel so, dass sie zur Berechnung der Mindestanzahl von Bits verwendet wird, die zur Darstellung einiger Daten erforderlich sind.Bei der Definition wird es normalerweise anders formuliert, aber ich habe mich bisher auf das bisherige Verständnis verlassen.

Hier ist mein Problem.Angenommen, ich habe eine Folge von 100 „1“, gefolgt von 100 „0“ = 200 Bits.Das Alphabet ist {0,1}, die Basis der Entropie ist 2.Die Wahrscheinlichkeit des Symbols „0“ beträgt 0,5 und „1“ beträgt 0,5.Die Entropie beträgt also 1 oder 1 Bit, um 1 Bit darzustellen.

Sie können es jedoch in der Lauflänge mit etwa 100/1/100/0 kodieren, wobei die Anzahl der auszugebenden Bits gefolgt vom Bit angegeben wird.Es scheint, als hätte ich eine Darstellung, die kleiner als die Daten ist.Vor allem, wenn Sie die Zahl 100 auf eine viel größere Zahl erhöhen.

Ich benutze: http://en.wikipedia.org/wiki/Information_entropy als Referenz im Moment.Was habe ich falsch gemacht?Ist es die den Symbolen zugeordnete Wahrscheinlichkeit?Ich denke nicht, dass es falsch ist.Oder habe ich den Zusammenhang zwischen Komprimierung und Entropie falsch verstanden?Irgendetwas anderes?

Danke.

Bearbeiten

Im Anschluss an einige der Antworten lautet mein Follow-up:Würden Sie die Entropieformel auf eine bestimmte Instanz einer Nachricht anwenden, um deren Informationsgehalt herauszufinden?Wäre es gültig, die Nachricht „aaab“ zu nehmen und zu sagen, dass die Entropie ~0,811 beträgt?Wenn ja, wie groß ist dann die Entropie von 1...10...0, wobei Einsen und Nullen unter Verwendung der Entropieformel n-mal wiederholt werden?Ist die Antwort 1?

Ja, ich verstehe, dass Sie eine Zufallsvariable Ihrer Eingabesymbole erstellen und die Wahrscheinlichkeitsmassenfunktion basierend auf Ihrer Nachricht erraten.Ich versuche zu bestätigen, dass die Entropieformel die Position der Symbole in der Nachricht nicht berücksichtigt.

Answer 1

Oder habe ich den Zusammenhang zwischen Komprimierung und Entropie falsch verstanden?

Sie sind ziemlich nah dran, aber diese letzte Frage ist, wo der Fehler lag.Wenn Sie etwas in eine Form komprimieren können, die kleiner als seine ursprüngliche Darstellung ist, bedeutet das, dass die ursprüngliche Darstellung zumindest eine gewisse Redundanz aufwies. Jedes Bit in der Nachricht übermittelte wirklich nicht ein Bit an Information.

Da redundante Daten nicht zum Informationsgehalt einer Nachricht beitragen, erhöhen sie auch nicht deren Entropie.Stellen Sie sich zum Beispiel einen „Zufallsbitgenerator“ vor, der nur den Wert „0“ zurückgibt.Das vermittelt überhaupt keine Informationen!(Eigentlich vermittelt es eine nicht definiert Informationsmenge, da jede binäre Nachricht, die nur aus einer Symbolart besteht, in der Entropieformel eine Division durch Null erfordert.)

Hätten Sie hingegen eine große Anzahl zufälliger Münzwürfe simuliert, wäre es sehr schwierig, die Größe dieser Nachricht wesentlich zu reduzieren.Jedes Bit würde nahezu 1 Bit Entropie beitragen.

Wenn Sie Daten komprimieren, extrahieren Sie diese Redundanz.Im Gegenzug zahlen Sie einen einmaligen Entropiepreis, indem Sie ein Schema entwickeln müssen, das weiß, wie diese Daten komprimiert und dekomprimiert werden;Das selbst erfordert einige Informationen.

Sie können es jedoch in der Lauflänge mit etwa 100/1/100/0 kodieren, wobei die Anzahl der auszugebenden Bits gefolgt vom Bit angegeben wird.Es scheint, als hätte ich eine Darstellung, die kleiner als die Daten ist.Vor allem, wenn Sie die Zahl 100 auf eine viel größere Zahl erhöhen.

Zusammenfassend lässt sich sagen, dass Sie einen Plan entwickeln könnten, um das zu erreichen Kodierung der Daten kleiner als die Originale Daten sagt dir etwas Wichtiges.Das heißt nämlich Ihre Originaldaten enthielten nur sehr wenige Informationen.

---

Weiterführende Literatur

Eine ausführlichere Behandlung hierzu, einschließlich der genauen Berechnung der Entropie für eine beliebige Ziffernfolge anhand einiger Beispiele, finden Sie hier dieses kurze Whitepaper.

Answer 2

Hier finden Sie aktuelle Kolmogorov Komplexität

  

Die minimale Anzahl von Bits in die eine Zeichenfolge, ohne dabei Informationen komprimiert werden. Dies ist definiert in Bezug auf ein festes, aber universelles Dekompression Schema, gegeben durch eine universelle Turing-Maschine.

Und in Ihrem speziellen Fall, beschränkt sich nicht auf Alphabet {0,1}. Für Ihr Beispiel Verwendung {0 ... 0, 1 ... 1} (hundert von 0'en und hundert von 1en)

Answer 3

Ihre Codierung arbeitet in diesem Beispiel, aber es ist möglich, ein gleichwertiger Fall zu begreifen: 010101010101 ..., die als 1/0/1/1 / ...

codiert werden würden

Entropy wird über alle möglichen Nachrichten gemessen, die im gegebenen Alphabet konstruiert werden können, und nicht nur pathologische Beispiele!

Answer 4

John Feminella es richtig gemacht, aber ich glaube, es gibt mehr zu sagen ist.

Shannon-Entropie basiert auf Wahrscheinlichkeit und Wahrscheinlichkeit ist immer im Auge des Betrachters.

Sie haben gesagt, 1 und 0 gleich wahrscheinlich sind (0,5). Wenn das so ist, dann folgte die Zeichenfolge von 100 1s mit 100 0en hat eine Wahrscheinlichkeit von 0,5 ^ 200, von denen -log (Basis 2) beträgt 200 Bits, wie erwartet. Allerdings ist die Entropie dieser Zeichenfolge (in Shannon Bedingungen) sein Informationsgehalt mal seine Wahrscheinlichkeit oder 200 * 0,5 ^ 200, immer noch eine wirklich kleine Zahl.

Dies ist wichtig, denn wenn Sie das tun Lauflängencodierung die Zeichenfolge im Fall dieser Zeichenfolge zu komprimieren, wird es eine kleine Länge, aber alle 2 ^ 200 Strings gemittelt über, es wird nicht gut tun. Mit etwas Glück wird der Durchschnitt aus bis etwa 200, aber nicht weniger.

Auf der anderen Seite, wenn Sie in Ihrem ursprünglichen Zeichenfolge aussehen und sagen, dass es so fällt auf, dass wer auch immer erzeugt es wahrscheinlich ist, mehr wie es zu erzeugen, dann sind Sie wirklich sagen, seine Wahrscheinlichkeit ist größer als 0,5 ^ 200, so dass Sie eine andere Annahmen über die ursprüngliche Wahrscheinlichkeitsstruktur des Generators des Strings zu machen, nämlich, dass sie niedriger Entropie als 200 Bits haben.

Ich persönlich finde dieses Thema sehr interessant, vor allem, wenn man sich in Kolmogorov (Algorithmic) Informationen. In diesem Fall legen Sie den Informationsgehalt einer Zeichenfolge als die Länge des kleinsten Programms, das es erzeugen könnte. Dies führt zu allen möglichen Einblicke in Software-Engineering und Design-Sprache.

Ich hoffe, das hilft, und vielen Dank für Ihre Frage.