Unterschied zwischen "Information" und "Nutzinformation" in der algorithmischen Informationstheorie

16

Laut Wikipedia :

Informellerweise entspricht aus der Sicht der algorithmischen Informationstheorie der Informationsgehalt einer Zeichenkette der Länge der kürzest möglichen in sich geschlossenen Darstellung dieser Zeichenkette.

Was ist die analoge informelle rigorose Definition von "nützlichen Informationen"? Warum werden "nützliche Informationen" nicht als das natürlichere oder grundlegendere Konzept angesehen? naiv scheint es, dass eine rein zufällige Zeichenfolge per definitionem null Informationen enthalten muss, daher versuche ich, mir darüber klar zu werden, dass die Standarddefinition davon ausgeht, dass sie maximale Informationen enthält.

user1247
quelle
2
Herzlich willkommen! Bitte beachten Sie, dass Sie Ihren Benutzernamen so ändern können, dass andere Benutzer ihn eher erkennen, wenn Sie ein regelmäßiger Besucher werden.
Raphael

Antworten:

12

Das zentrale Konzept hierbei ist die Kolmogorov-Komplexität und insbesondere die Kompressibilität . Um ein intuitives Gefühl der Kompressibilität zu erhalten, sollten Sie zwei Strings AB und BB , wobei B={0,1} . Lassen

A=1010 1010 1010 1010 und

B=1011 0110 0111 1001 .

Beachten Sie, dass|A|=|B|=16 . Wie können wir quantifizieren, wie viele Informationen oder B haben? Wenn wir über die klassische Informationstheorie nachdenken, dauert die Übertragung einer Kette mit der Länge n im Durchschnitt n Bits. Wir können jedoch nicht sagen, wie viele Bits wir benötigen, um eine bestimmte Zeichenfolge mit der Länge n zu übertragen .ABnnn

Warum ist der Informationsgehalt einer zufälligen Zeichenfolge nicht Null?

Bei näherer Betrachtung können wir sehen, dass tatsächlich . Allerdings ist es sehr viel schwieriger zu sagen , wenn B offensichtliche Muster in seiner Struktur hat, zumindest es scheint und fühlt sich mehr zufällig als A . Weil wir ein Muster in finden A , können wir leicht komprimieren A und stellen es mit weniger als 16 Bits. Ebenso können wir Muster in B nicht so stark komprimieren , da es nicht einfach ist, sie zu erkennen . Daher können wir sagen, dass B mehr Informationen als A hat . Darüber hinaus ist eine zufällige Zeichenfolge der Länge nA=108BAAA16BBAnhat maximale Informationen, da es keine Möglichkeit gibt, diese zu komprimieren und daher mit weniger als Bits darzustellen .n

Was sind dann nützliche Informationen?

Für nützliche Informationen , ja, es ist eine Definition , eine Turing - Maschine mit . Die nützliche Information in x B istTxB

minT { l(T)+C(x|T):T{T0,T1,...}},

wobei bezeichnet die Länge eines selbstbegrenzenden Codierung für eine Turing Maschine T . Die Notation ist normalerweise so, dass C ( x ) die Kolmogorov-Komplexität von x und C ( x | y ) die bedingte Kolmogorov-Komplexität von x bei gegebenem y bezeichnet .l(T)TC(x)xC(x|y)xy

Hier verkörpert die Menge nützlicher Informationen, die in x enthalten sind . Was wir fragen könnten, ist, welches solche T unter denjenigen auszuwählen ist, die die Anforderung erfüllen. Das Problem ist , ein kürzestes Programm zu trennen x * in Teile x * = p q st p für ein geeigneten T . Dies ist eigentlich genau die Idee, aus der die minimale Beschreibungslänge (MDL) hervorgegangen ist .TxTxx=pqpT

Juho
quelle
4

Es könnte sein, dass "nützlich" schwer zu definieren ist. Angenommen, wir haben eine hochstrukturierte, informationsreiche Nachricht die höchstens um den Faktor α zur Nachricht y komprimiert werden kann . Intuitiv enthalten x und y dieselbe Menge nützlicher Informationen. in der Tat enthalten sie die gleiche Menge an Informationen gemäß der üblichen Definition. Stellen Sie sich nun ein Präfix z von x vor, das dieselbe Länge hat wie y ; es sollte nicht mehr nützliche Informationen als x enthalten , daher nicht mehr als y . Jedoch y ist mehr "random" als z , da zxαyxyzxyxyyzzkann komprimiert werden und kann nicht. Wenn wir also versuchen, "nützliche" Informationen mit Komprimierbarkeit zu verknüpfen, könnten wir auf folgendes Paradox stoßen: Ein Präfix einer Nachricht könnte höhere "nützliche" Informationen enthalten als die gesamte Nachricht, was anscheinend ein Widerspruch ist.y

Patrick87
quelle
Es mag schwer zu definieren sein und es mag sein, dass es sich nicht trivial auf die Komprimierbarkeit verlassen kann, wie es "Informationen" tun, aber es scheint wie die wichtigere Definition! So wie es aussieht, scheint "Information" ein Alias ​​für "Kolmogorov-Komplexität" zu sein, und nicht ein ernsthafter Versuch, Informationen im üblichen Sinne zu definieren, was in anderen Kontexten per Definition nützlich sein muss! Ist das ein aktives Forschungsgebiet? Gibt es vorgeschlagene Definitionen?
user1247
@ user1247 Warum ist die Komplexität von Kolmogorov Ihrer Meinung nach nicht ernst gemeint ?
Juho
@mrm Ich betrachte es als ein sehr ernstes und interessantes Konzept, aber es ist mir unangenehm, dieses Konzept als "Information" zu bezeichnen. Was bedeutet es für eine völlig zufällige Zeichenfolge, Informationen zu enthalten? "Nützliche Informationen" scheinen geeigneter und interessanter zu sein, wenn es darum geht, Informationen (wo "nützlich" impliziert ist) in der realen Welt zu diskutieren, beispielsweise in philosophischen oder quantenmechanischen Diskussionen über gesendete oder empfangene Informationen.
user1247
1
@ user1247 Eine möglicherweise interessante Möglichkeit, meine Antwort zu interpretieren, ist folgende: Informationen sind nur dann nützlich oder nutzlos, wenn sie interpretiert werden. Bei einer festen Interpretation kann eine Nachricht mehr oder weniger nützliche Informationen enthalten als eine andere. Jede Theorie nützlicher Informationen muss meiner Meinung nach solche Interpretationen berücksichtigen (regelmäßige Maßnahmen wie Entropie tun dies auch, wenn auch implizit).
Patrick87
@ Patrick87 Ich bin absolut einverstanden, dass jede gute Theorie von "nützlichen Informationen" den Entschlüsselungsmechanismus berücksichtigen sollte. Das macht es zu einem interessanten Problem! Wenn Sie mir eine Bit-Zeichenfolge senden und ich sie im Prinzip nicht entschlüsseln kann, sollte festgelegt werden, dass sie keine nützlichen Informationen enthält.
user1247
4

Aus einer weniger formalen Sicht denke ich, dass es hilfreich sein kann, wenn Sie sich vom Wort "zufällig" lösen, da Sie richtig sind, dass eine Reihe von wirklich zufälligen Bits keine Informationen im praktischen Sinne speichern. (Wenn ich eine Reihe von Namen verschlüssele und die verschlüsselten Werte an Sie sende, haben sie möglicherweise eine sehr hohe Kolmogorov-Komplexität, aber es hilft Ihnen nicht, die Namen herauszufinden.)

Aber denken Sie so darüber nach. Wenn Sie eine Website in einer Fremdsprache sehen (sagen Sie Schwedisch, vorausgesetzt, Sie sprechen sie nicht), sieht sie mehr oder weniger zufällig aus. Die Worte werden eine gewisse Ordnung haben, aber nicht viel. Wenn Sie sich jedoch eine Webseite ansehen, deren Text so aussieht: 123456123456123456123456 ... und so weiter, können Sie ihn schneller verstehen. Wenn Sie kein Schwedisch sprechen, können Sie wahrscheinlich noch viel mehr daraus machen, auch wenn auf der schwedischen Webseite das Äquivalent zu "den ersten sechs Zahlen, die nacheinander wiederholt werden" stand. Die Webseiten enthalten die gleichen Informationen, von denen jedoch eine für Sie zufällig aussieht. Und für die Menge an Speicherplatz ist diejenige, die Sie verstehen, viel weniger effizient als die schwedische Webseite, obwohl sie dieselben Informationen speichert. Möglicherweise finden Sie diese Informationen nicht "nützlich", weil es '

Der Begriff "Information" ist universell zu verstehen. Was für Sie also wie zufällige - und daher unbrauchbare - Bits aussieht, kann eine große Menge an Informationen für andere Personen speichern. Das Maß der Information soll eine intrinsische Eigenschaft der Zeichenfolge sein und kann nicht davon abhängen, was für Sie Sinn macht und was Sie nicht interpretieren können.

Ein weiterer (eher technischer) Punkt, der helfen könnte, ist, dass ich hier etwas unaufrichtig bin. Wie Juho weist darauf hin, Informationen sinddefiniert im Verhältnis zu der Person, die es interpretiert. Möglicherweise ist die schwedische Webseite als Informationsmedium völlig nutzlos, aber jemand, der schwedisch spricht, kann feststellen, dass sie viele Informationen enthält. Die Definition spiegelt dies wider. Aus der Mathematik können wir jedoch lernen, dass sich der Unterschied zwischen der kürzesten (für den Raum informativsten) Webseite, auf der diese Website an Sie kommuniziert wird, und der kürzesten Webseite, auf der sie an jemanden kommuniziert wird, der Schwedisch spricht, nur durch eine additive Konstante unterscheiden kann. Warum? Für Sie als nicht schwedischer Sprecher ist der kürzeste Weg, die Seite zu speichern, die Sie verstehen können, "die ersten sechs Ganzzahlen, die nacheinander wiederholt werden". Dies kann etwas länger dauern als die schwedischen.

(Most efficient representation of information in English)(Most efficient representation in Swedish)+(Length of Swedish-English dictionary)
. Dies wird von Ihrer ursprünglichen Frage etwas unangebracht, aber der Punkt, den ich versuche, ist, dass es nicht allzu wichtig ist, wer die Informationen liest. Die zufällig aussehende schwedische Webseite war für Sie nicht "nützlich", aber für andere "nützlich", und Sie sind nur eine konstante Menge an Informationen, die Sie nicht selbst nutzen können.
SamM
quelle