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

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.

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 $A \in \mathbb{B}^*$ und $B \in \mathbb{B}^*$ , wobei $\mathbb{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 .$A$$B$$n$$n$$n$

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 $A = 10^8$$B$$A$$A$$A$$16$$B$$B$$A$$n$hat 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 ∗ ist$T$$x \in \mathbb{B}^*$

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)$$T$$C(x)$$x$$C(x|y)$$x$$y$

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 .$T$$x$$T$$x^*$$x^* = pq$$p$$T$

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 $x$$\alpha$$y$$x$$y$$z$$x$$y$$x$$y$$y$$z$$z$kann 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$

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.