Différence entre «information» et «information utile» dans la théorie algorithmique de l'information

16

Selon Wikipedia :

Informellement, du point de vue de la théorie algorithmique de l'information, le contenu informationnel d'une chaîne équivaut à la longueur de la représentation autonome la plus courte possible de cette chaîne.

Quelle est la définition rigoureuse informelle analogue des "informations utiles"? Pourquoi les "informations utiles" ne sont-elles pas considérées comme le concept le plus naturel ou le plus fondamental; naïvement, il semble qu'une chaîne purement aléatoire doive par définition ne contenir aucune information, donc j'essaie de me faire une idée du fait qu'elle est considérée comme ayant une information maximale selon la définition standard.

user1247
la source
2
Bienvenue! Veuillez noter que vous pouvez changer votre nom d'utilisateur en quelque chose que les gens sont plus susceptibles de reconnaître lorsque vous devenez un visiteur régulier.
Raphael

Réponses:

12

Le concept central ici est la complexité de Kolmogorov , et plus spécifiquement la compressibilité . Pour obtenir une sensation intuitive de compressibilité, considérons deux chaînes et B B , où B = { 0 , 1 } . LaisserABBBB={0,1}

1010 1010 1010 , etA=1010 1010 1010 1010

0110 0111 1001 .B=1011 0110 0111 1001

Notez que . Comment pourrions-nous quantifier la quantité d'informations A ou B ? Si l'on pense à la théorie classique de l'information, en général, la transmission d'une chaîne de longueur n prend en moyenne n bits. Cependant, nous ne pouvons pas dire de combien de bits nous avons besoin pour transmettre une chaîne de longueur spécifique|A|=|B|=16ABnn .n

Pourquoi le contenu informationnel d'une chaîne aléatoire n'est-il pas nul?

En y regardant de plus près, nous pouvons voir qu'en fait . Cependant, il est beaucoup plus difficile de dire si B a des motifs évidents dans sa structure, au moins il semble et se sent plus aléatoire que A . Parce que nous pouvons trouver un modèle dans A , nous pouvons facilement compresser A et le représenter avec moins de 16 bits. De même, comme il n'est pas facile de détecter des motifs dans B , nous ne pouvons pas le compresser autant. On peut donc dire que B a plus d'informations que AA=108BAAA16BBA . De plus, une chaîne aléatoire de longueur na une information maximale car il n'y a aucun moyen de la compresser, et donc de la représenter avec moins de bits.n

Quelles sont donc les informations utiles?

Pour des informations utiles , oui, il y a une définition en utilisant une machine de Turing . Les informations utiles dans x B sontTxB

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

désigne la longueur d'un codage auto-limitation pour une machine de Turing T . La notation est généralement telle que C ( x ) dénote la complexité de Kolmogorov de x et C ( x | y ) la complexité de Kolmogorov conditionnelle de x étant donné yl(T)TC(x)xC(x|y)xy .

Ici, la quantité d'informations utiles contenues dans x . Ce que nous pourrions demander, c'est quel tel T sélectionner parmi ceux qui satisfont à l'exigence. Le problème est de séparer un programme le plus court x en parties x = p q st p représente un T approprié . C'est en fait l'idée même qui a engendré la longueur minimale de description (MDL) .TxTxx=pqpT

Juho
la source
4

Cela pourrait être dû au fait que «utile» est difficile à définir. Supposons que nous ayons un message hautement structuré et riche en informations qui peut être compressé au maximum par un facteur α au message y . Intuitivement, x et y contiennent la même quantité d'informations utiles; en effet, ils contiennent la même quantité d'informations selon la définition habituelle. Imaginez maintenant un préfixe z de x de la même longueur que y ; il ne doit pas contenir plus d'informations utiles que x , donc pas plus que y . Cependant, y est plus "aléatoire" que z , car zxαyxyzxyxyyzzpeut être comprimé et ne peuvent pas. Donc, si nous essayons d'associer des informations "utiles" à la compressibilité, nous pourrions rencontrer le paradoxe suivant: un préfixe d'un message pourrait avoir des informations "utiles" plus élevées que le message entier, ce qui semble être une contradiction.y

Patrick87
la source
Il peut être difficile à définir, et il se peut qu'il ne puisse pas dépendre trivialement de la compressibilité comme le font les "informations", mais cela semble être la définition la plus importante! À l'heure actuelle, "l'information" semble être un alias de la "complexité de Kolmogorov", plutôt qu'une tentative sérieuse de définir l'information au sens habituel, qui dans d'autres contextes doit, par définition, être utile! Est-ce un domaine de recherche actif? Y a-t-il des définitions proposées?
user1247
@ user1247 Pourquoi pensez-vous que la complexité de Kolmogorov n'est pas sérieuse?
Juho
@mrm Je le vois comme un concept très sérieux et intéressant, mais je suis mal à l'aise d'appeler ce concept «information». Qu'est-ce que cela signifie pour une chaîne complètement aléatoire de contenir des informations? Les «informations utiles» semblent plus applicables et intéressantes lorsqu'il s'agit de discuter des informations (où «utiles» est implicite) dans le monde réel, dans des discussions philosophiques ou mécaniques quantiques sur les informations transmises ou reçues, par exemple.
user1247
1
@ user1247 Une façon peut-être intéressante d'interpréter ma réponse est la suivante: les informations ne sont utiles ou inutiles que si elles sont interprétées. Pour une interprétation fixe, un message peut contenir des informations plus ou moins utiles qu'un autre. Toute théorie de l'information utile devra, à mon avis, prendre en compte de telles interprétations (des mesures régulières comme l'entropie le font aussi, bien qu'implicitement).
Patrick87
@ Patrick87 Je suis absolument d'accord que toute bonne théorie des "informations utiles" devrait prendre en compte le mécanisme de décryptage. C'est ce qui en fait un problème intéressant! Si vous m'envoyez une chaîne de bits, et en principe je ne peux pas la déchiffrer, alors elle devrait être définie pour ne contenir aucune information utile.
user1247
4

D'un point de vue moins formel, je pense que cela peut aider si vous vous détachez du mot "aléatoire", car vous avez raison de dire qu'un ensemble de bits vraiment aléatoires ne stocke aucune information dans un sens pratique. (Si je crypte un ensemble de noms et que je vous envoie les valeurs chiffrées, elles peuvent présenter une complexité de Kolmogorov très élevée, mais cela ne vous aidera pas à déterminer les noms).

Mais pensez-y de cette façon. Si vous voyez un site Web dans une langue étrangère (par exemple le suédois, en supposant que vous ne le parlez pas), il sera plus ou moins aléatoire. Il y aura un certain ordre dans les mots, mais pas beaucoup. Cependant, si vous regardez une page Web avec un texte qui ressemble à ceci: 123456123456123456123456 ... et ainsi de suite, vous pourrez le comprendre plus rapidement. Si vous ne parlez pas suédois, vous pourrez probablement en tirer beaucoup plus, même si la page suédoise dit l'équivalent des "six premiers chiffres répétés séquentiellement". Les sites Web contiennent les mêmes informations, mais l'un vous semble aléatoire. Et pour la quantité d'espace, celle que vous comprenez est beaucoup moins efficace que la page Web suédoise, même si elle stocke les mêmes informations. Vous ne trouverez peut-être pas ces informations "utiles" car elles "

La notion d '"information" est censée être universelle, donc ce qui ressemble à des bits aléatoires - et donc inutiles - pour vous peut stocker beaucoup d'informations à quelqu'un d'autre. La mesure de l'information est destinée à être une propriété intrinsèque de la chaîne et ne peut pas dépendre de ce qui vous semble ou non logique, ni de ce que vous pouvez et ne pouvez pas interpréter.

Un autre point (plus technique) qui peut aider est que je suis un peu malhonnête ici. Comme le souligne Juho, l'information estdéfini par rapport à qui l'interprète. Vous pouvez trouver la page Web suédoise complètement inutile comme véhicule d'information, mais quelqu'un qui parle suédois peut trouver qu'elle contient beaucoup d'informations. La définition reflète cela. Cependant, à partir des mathématiques, nous pouvons apprendre que la différence entre la page Web la plus courte (la plus informative pour l'espace) pour vous communiquer ce site Web et la page Web la plus courte qui peut le communiquer à quelqu'un qui parle suédois ne peut différer que par une constante additive. Pourquoi? Parce que pour vous, en tant que locuteur non suédois, le moyen le plus court de stocker la page que vous pouvez comprendre est "les six premiers entiers répétés séquentiellement". Cela peut être un peu plus long que le suédois.

(Most efficient representation of information in English)(Most efficient representation in Swedish)+(Length of Swedish-English dictionary)
. Cela devient un peu hors sujet de votre question d'origine, mais le point que j'essaie de faire est que peu importe qui lit les informations. La page Web suédoise à l'aspect aléatoire ne vous était pas "utile", mais elle était "utile" à quelqu'un d'autre, et vous n'êtes qu'à une quantité constante d'informations de pouvoir vous-même en faire usage.
SamM
la source