La formule d'entropie de Shannon. Aide ma confusion

Question

D'après ma compréhension de la formule d'entropie, elle est utilisée pour calculer le nombre minimal de bits requis pour représenter certaines données. Il est généralement libellé différemment lorsqu'il est défini, mais la compréhension précédente est celle sur laquelle je m'appuyais jusqu'à présent.

Voici mon problème. Supposons que j'ai une séquence de 100 '1' suivie de 100 '0' = 200 bits. L'alphabet est {0,1}, la base d'entropie est 2. Probabilité du symbole "0" est égal à 0,5 et "1" est 0.5. Donc, l'entropie est 1 ou 1 bit pour représenter 1 bit.

Cependant, vous pouvez le coder en longueur avec quelque chose comme 100/1 1/100/0 où son nombre de bits à sortir suivi du bit. Il semble que j'ai une représentation plus petite que les données. Surtout si vous augmentez le nombre 100 à beaucoup plus grand.

J'utilise: http://en.wikipedia.org/wiki/Information_entropy comme référence pour le moment. Où me suis-je trompé? Est-ce la probabilité assignée aux symboles? Je ne pense pas que c'est faux. Ou ai-je mal compris le lien entre compression et entropie? Quelque chose d'autre?

Merci.

Modifier

Voici certaines des réponses suivantes: appliqueriez-vous la formule d'entropie à une instance particulière d'un message afin de déterminer son contenu en informations? Serait-il valide de prendre le message " aaab " et dire que l'entropie est ~ 0.811. Si oui, quelle est l'entropie de 1 ... 10 ... 0 où 0 et 1 sont répétés n fois en utilisant la formule d'entropie. La réponse est-elle 1?

Oui, je comprends que vous créez une variable aléatoire de vos symboles de saisie et que vous deviniez la fonction de masse de probabilité en fonction de votre message. Ce que j'essaie de confirmer, c'est que la formule d'entropie ne prend pas en compte la position des symboles dans le message.

Answer 1

  

Ou ai-je mal compris le lien entre compression et entropie?

Vous êtes assez proches, mais cette dernière question est où l'erreur était. Si vous êtes capable de compresser quelque chose dans une forme qui était plus petite que sa représentation originale, cela signifie que la représentation originale avait au moins une certaine redondance. Chaque élément du message ne contenait pas réellement un élément d'information.

Comme les données redondantes ne contribuent pas au contenu informationnel d'un message, elles n'augmentent pas non plus son entropie. Imaginez, par exemple, un "générateur de bits aléatoires". qui ne renvoie que la valeur "0". Cela ne donne aucune information du tout! (En réalité, il transmet une quantité d'informations non définie , car tout message binaire composé d'un seul type de symbole nécessite une division par zéro dans la formule d'entropie.)

En revanche, si vous aviez simulé un grand nombre de lancers aléatoires, il serait très difficile de réduire considérablement la taille de ce message. Chaque bit contribuerait à près de 1 bit d'entropie.

Lorsque vous compressez des données, vous extrayez cette redondance. En échange, vous payez un prix d'entropie unique en ayant à concevoir un schéma qui sache compresser et décompresser ces données; cela prend quelques informations.

  

Cependant, vous pouvez le coder en longueur avec quelque chose comme 100/1 1/100/0 où son nombre de bits à sortir suivi du bit. Il semble que j'ai une représentation plus petite que les données. Surtout si vous augmentez le nombre 100 à beaucoup plus grand.

Pour résumer, le fait que vous puissiez concevoir un schéma pour rendre l'encodage des données inférieur à celui des données d'origine vous indique quelque chose d'important. En particulier, il est indiqué que vos données d'origine contenaient très peu d'informations .

Lectures supplémentaires

Pour un traitement plus approfondi de ce problème, y compris comment calculer l’entropie pour toute séquence de chiffres arbitraire avec quelques exemples, consultez ce court livre blanc .

Answer 2

Consultez la complexité de Kolmogorov

.

  

Le nombre minimum de bits dans lesquels une chaîne peut être compressée sans perdre d'informations. Ceci est défini par rapport à un schéma de décompression fixe mais universel, donné par une machine de Turing universelle.

Et dans votre cas particulier, ne vous limitez pas à l'alphabet {0,1}. Pour votre exemple, utilisez {0 ... 0, 1 ... 1} (centaines de 0 et centaines de 1)

Answer 3

Votre codage fonctionne dans cet exemple, mais il est possible de concevoir un cas tout aussi valide: 010101010101 ... qui serait codé au format 1/0/1/1 / ...

L'entropie est mesurée dans tous les messages possibles pouvant être construits dans l'alphabet donné, et pas seulement dans les exemples pathologiques!

Answer 4

John Feminella a eu raison, mais je pense qu'il y a plus à dire.

L'entropie de Shannon est basée sur la probabilité, et la probabilité est toujours dans l'oeil du spectateur.

Vous avez dit que 1 et 0 étaient également probables (0,5). Si tel est le cas, la chaîne de 100 1 suivie de 100 0 a une probabilité de 0,5 à 200, dont -log (base 2) vaut 200 bits, comme vous le souhaitez. Toutefois, l’entropie de cette chaîne (en termes de Shannon) correspond au contenu de l’information multiplié par sa probabilité, ou 200 * 0.5 ^ 200, un nombre encore très petit.

Cela est important car si vous codez la longueur d’exécution pour compresser la chaîne, sa longueur ne sera pas très grande, mais sa moyenne sera moyenne pour toutes les 2 ^ 200 chaînes. Avec un peu de chance, le nombre moyen sera d'environ 200, mais pas moins.

D'autre part, si vous regardez votre chaîne d'origine et dites qu'elle est si frappante que celui qui l'a générée est susceptible de générer davantage de contenu similaire, vous dites en réalité que sa probabilité est supérieure à 0,5 ^ 200, faire des hypothèses différentes sur la structure de probabilité d'origine du générateur de la chaîne, à savoir qu'il a une entropie inférieure à 200 bits.

Personnellement, je trouve ce sujet très intéressant, en particulier lorsque vous examinez les informations de Kolmogorov (algorithmique). Dans ce cas, vous définissez le contenu informationnel d'une chaîne comme longueur du plus petit programme susceptible de la générer. Cela donne lieu à toutes sortes d’informations sur le génie logiciel et la conception de langage.

J'espère que cela vous aide et merci pour votre question.