Unterschied zwischen „Informationen“ und „nützlichen Informationen“ in der algorithmischen Informationstheorie

Question

Entsprechend Wikipedia:

Aus der Sicht der algorithmischen Informationstheorie entspricht der Informationsgehalt einer Zeichenfolge die Länge der kürzestmöglichen, in sich geschlossenen Darstellung dieser Zeichenfolge.

Was ist die analoge informelle strenge Definition von "nützlichen Informationen"? Warum wird "nützliche Informationen" nicht als natürlicheres oder grundlegenderes Konzept angesehen? Naiv es scheint, dass eine rein zufällige Zeichenfolge per Definition keine Informationen enthalten muss. Ich versuche, mich durch die Standarddefinition zu maximaler Informationen zu haben.

Answer 1

Das zentrale Konzept hier ist Kolmogorov -Komplexität, und genauer gesagt Kompressibilität. Um ein intuitives Gefühl der Kompressibilität zu erhalten, betrachten Sie zwei Zeichenfolgen $ a in mathbb {b}^*$ und $ b in mathbb {b}^*$, wobei $ mathbb {b} = {0,1 } $. Lassen

$ A = 1010 $ 1010 $ 1010 $ 1010 $ 1010 $ und

$ B = 1011 $ $ 0110 $ 0111 $ $ 1001 $.

Beachten Sie, dass $ | a | = | B | = 16 $. Wie könnten wir quantifizieren, wie viele Informationen $ a $ oder $ B $ haben? Wenn wir über die klassische Informationstheorie nachdenken, übernimmt die Übertragung einer Länge von $ n $ im Allgemeinen im Durchschnitt $ n $ Bits. Wir können jedoch nicht sagen, wie viele Teile wir brauchen, um a zu übertragen Spezifisch Länge $ n $.

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

Auf näherer Blick können wir sehen, dass $ a = 10^8 $. Es ist jedoch viel schwieriger zu sagen, ob $ B $ offensichtliche Muster in seiner Struktur hat, zumindest scheint und fühlt sich mehr zufällig als $ a $. Da wir ein Muster in $ a $ finden können, können wir leicht $ a $ komprimieren und es mit weniger als 16 $ $ Bit repräsentieren. Da es nicht einfach ist, Muster in $ B $ zu erkennen, können wir es nicht so stark komprimieren. Daher können wir sagen, dass $ B $ mehr Informationen als $ A $ hat. Darüber hinaus enthält eine zufällige Länge $ n $ maximale Informationen, da wir sie auf keinen Fall komprimieren können und daher mit weniger als $ n $ Bits darstellen können.

Was sind dann nützliche Informationen?

Zum nützliche Informationen, Ja, es gibt eine Definition mit einer Turing -Maschine $ t $. Die nützlichen Informationen in $ x in mathbb {b}^*$ ist

$$ min_t space { space l (t) + c (x | t): t in {t_0, t_1, ... } }, $$

wobei $ l (t) $ die Länge einer selbstlimitierenden Kodierung für eine Turing-Maschine $ T $ bezeichnet. 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 $ bezeichnet $ y $.

Hier verkörpert $ t $ die Menge an nützlichen Informationen, die in $ x $ enthalten sind. Was wir fragen könnten, ist, welche solche $ t $ unter denjenigen auswählen können, die die Anforderungen erfüllen. Das Problem besteht darin, ein kürzestes Programm $ x^* $ in Teile $ x^* = pq $ st $ p $ zu trennen. Dies ist eigentlich die Idee, die hervorgebracht wurde Mindestbeschreibungslänge (MDL).

Answer 2

Es könnte daran liegen, dass "nützlich" schwer zu definieren ist. Angenommen, wir haben eine hochstrukturierte, Informationsreiche Nachricht $ x $, die höchstens um einen Faktor von $ alpha $ an die Nachricht $ y $ komprimiert werden kann. Intuitiv enthalten $ x $ und $ y $ die gleiche 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 $ in der gleichen Länge wie $ y $ vor; Es sollte nicht mehr nützliche Informationen als $ x $ enthalten, daher nicht mehr als $ y $. $ Y $ ist jedoch "zufälliger" als $ z $, da $ z $ komprimiert werden kann und $ y $ kann nicht. Wenn wir also versuchen, "nützliche" Informationen mit Kompressibilität zu verknüpfen, könnten wir das folgende Paradoxon treffen: Ein Präfix einer Nachricht könnte höhere "nützliche" Informationen als die gesamte Nachricht haben, scheinbar ein Widerspruch.

Answer 3

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

Aber denken Sie auf diese Weise darüber nach. Wenn Sie eine Website in einer Fremdsprache sehen (sagen wir schwedisch, vorausgesetzt, Sie sprechen sie nicht), wird sie mehr oder weniger zufällig aussehen. Es wird einige Ordnung zu den Worten geben, aber nicht viel. Wenn Sie sich jedoch eine Webseite mit Text ansehen, die wie folgt aussieht: 123456123456123456123456 ... und so weiter können Sie sie schneller verstehen. Wenn Sie nicht schwedisch sprechen, können Sie wahrscheinlich viel mehr daraus machen, auch wenn die schwedische Webseite das Äquivalent der "ersten sechs Zahlen nacheinander wiederholt" besagt. Die Websites enthalten die gleichen Informationen, aber man sieht für Sie zufällig aus. Und für die Menge an Platz ist die, die Sie verstehen, weniger effizient als die schwedische Webseite, obwohl sie dieselben Informationen speichert. Möglicherweise finden Sie diese Informationen nicht "nützlich", weil sie schwedisch ist, aber die Informationen sind immer noch da.

Der Begriff der "Information" soll universell sein. Was zufällig aussieht-und damit nutzlos-, können Sie für Sie viel Informationen an eine andere Person speichern. Das Maß an Informationen soll eine intrinsische Eigenschaft der Saite sein und kann nicht davon abhängen, was für Sie zu tun hat und was Sie nicht interpretieren können und was Sie nicht interpretieren können.

Ein weiterer (technischerer) Punkt, der helfen kann, ist, dass ich hier etwas unaufrichtig bin. Wie Juho betont, Informationen ist definiert relativ zu wer interpretiert es. Möglicherweise finden Sie die schwedische Webseite als Informationsmittel völlig nutzlos, aber jemand, der schwedisch spricht, kann es sein, dass sie viel Informationen hat. Die Definition spiegelt dies wider. Aus der Mathematik können wir jedoch erfahren, dass der Unterschied zwischen der kürzesten (am informativsten) Webseite, um diese Website mit Ihnen mitzuteilen, und der kürzesten Webseite, die sie an jemanden mitteilt, der schwedisch spricht, nur durch eine additive Konstante unterscheiden kann. Wieso den? Denn für Sie als nicht schwingender Sprecher ist der kürzeste Weg, um die Seite zu speichern, die Sie verstehen können, "die ersten sechs Ganzzahlen, die nacheinander wiederholt werden". Dies kann viel länger sein als die Schwedisch. (Nehmen Sie hier mit mir und nehmen Sie an, dass Schwedisch super kurz und effizient ist, während Englisch sehr lang und verschwenderisch ist).

Aber selbst wenn Sie Schwedisch sprechen konnten, können Sie nur eine Additivkonstante aus der Länge schneiden! Wieso den? Weil Sie immer ein schwedisch-englisches Wörterbuch kaufen können. Dann würde die superschreien schwedischen Webseiten für Sie Sinn machen. Sicher, sie machen nur Sinn, wenn Sie das Wörterbuch haben, aber das Wörterbuch hat eine konstante Länge. Also $$ ( mbox {effizienteste Darstellung von Informationen in Englisch}) leq ( mbox {effizienteste Darstellung in schwedisch}) + ( mbox {Länge des schwedisch-englischen Wörterbuchs}) $$. Dies wird von Ihrer ursprünglichen Frage etwas abseits des Topics, aber der Punkt, den ich versuche, ist, dass es nicht zu sehr spielt, wer die Informationen liest. Die zufällig aussehende schwedische Webseite war für Sie nicht "nützlich", aber es ist "nützlich" für eine andere Person, und Sie sind nur eine ständige Menge an Informationen davon entfernt, es selbst zu verwenden.