Entropie de Shannon

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

L'entropie de Shannon, due à Claude Shannon, est une fonction mathématique qui correspond à la quantité d'information contenue ou délivrée par une source d'information. Une langue, un signal électrique, un fichier informatique quelconque, constituent des sources d'informations. La définition de l'entropie d'une source selon Shannon est telle que plus la source est redondante, moins elle contient d'information au sens de Shannon. L'entropie est ainsi maximale pour une source dont tous les symboles sont équiprobables.

Cette définition est utilisée en électronique numérique pour numériser une source en utilisant le minimum possible de bits sans perte d'information.

Enfin, elle sert à connaître sur combien de bits au minimum on peut coder un fichier, ce qui est très utile pour savoir quelle limite peuvent espérer atteindre les algorithmes de compression qui ne perdent pas d'information (types Zip, LZW ou encore RLE, et non pas JPEG ou MP3). Il existe de tels algorithmes dits optimaux, c'est-à-dire qui compressent le fichier en un fichier d'entropie minimale.

Le terme entropie fut utilisé par Shannon dans sa théorie de l'information, par analogie à la notion d'entropie existante en thermodynamique et dans la théorie du chaos. L'entropie d'une source possède ainsi des propriétés similaires aux définitions en thermodynamique, notamment l'additivité.

[modifier] Introduction

Intuitivement, l'entropie de Shannon peut être vue comme mesurant la quantité d'incertitude liée à un évènement aléatoire, ou plus précisément à sa distribution. Une autre manière de voir est de parler de la quantité d'information portée par le signal: l'information fournie par chaque nouvel évènement est fonction de l'incertitude sur cet évènement.

Par exemple, imaginons une urne contenant plusieurs boules de différentes couleurs, dont on tire une boule au hasard (avec replacement). Si toutes les boules ont des couleurs différentes, alors notre incertitude sur le résultat d'un tirage est maximale. En particulier, si nous devions parier sur le résultat d'un tirage, nous ne pourrions pas privilégier un choix plutôt qu'un autre. Par contre, si une certaine couleur est plus représentée que les autres (par exemple si l'urne contient davantage de boules rouges), alors notre incertitude est légèrement réduite: la boule tirée a plus de chances d'être rouge. Si nous devions absolument parier sur le résultat d'un tirage, nous miserions sur une boule rouge. Ainsi, révéler le résultat d'un tirage fournit davantage d'information dans le premier cas que dans le second, parce que l'entropie du "signal" (calculable à partir de la distribution statistique) est plus élevée.

Prenons un autre exemple: considérons un texte en français codé comme une chaîne de lettres, d'espaces et de ponctuations (notre signal est donc une chaîne de caractères). Comme la fréquence de certains caractères n'est pas très importante (ex : 'z'), tandis que d'autres sont très communs (ex : 'e'), la chaîne de caractères n'est pas si aléatoire que ça. D'un autre côté, tant qu'on ne peut pas prédire quel est le caractère suivant, d'une certaine manière, cette chaîne est aléatoire. L'entropie est une mesure de cet aléatoire suggérée par Shannon dans son article de 1948^[1].

Shannon donne une définition de l'entropie qui vérifie les assertions suivantes :

La mesure doit être proportionnelle (continue) - c'est-à-dire qu'une faible modification d'une probabilité doit résulter en un faible changement de l'entropie.
Si tous les tirages (les lettres dans l'exemple précédent) sont équiprobables, alors augmenter leur quantité doit toujours augmenter l'entropie.
On doit pouvoir faire le choix (dans notre exemple des lettres) en deux étapes, auquel cas l'entropie du résultat final doit être la somme pondérée des entropies des deux étapes.

[modifier] Historique

En 1948, tandis qu'il travaillait aux Laboratoires Bell, l'ingénieur en génie électrique Claude Shannon formalisa mathématiquement la nature statistique de "l'information perdue" dans les signaux des lignes téléphoniques. Pour ce faire, il développa le concept général d'entropie de l'information, la pierre angulaire fondamentale à la théorie de l'information. Initialement, il ne semble pas que Shannon ait été particulièrement au courant de la relation étroite entre sa nouvelle mesure et les travaux précédents en thermodynamique. En 1949, tandis qu'il travaillait à ses équations depuis un moment, il rendit visite au mathématicien John von Neuman. Deux sources différentes rapportent leurs propos au sujet de ce que Shannon aurait appelé "mesure de l'incertitude" ou atténuation dans le signal d'une ligne de téléphone. Voici la première ^[2] :

« Mon plus gros soucis était comment l'appeler. J'ai pensé à l'appeler "information", mais le mot était trop utilisé, alors j'ai décidé de l'appeler "incertitude". Quand j'en discutai avec John von Neumann, il eut une meilleure idée. Von Neuman me dit, "Tu devrais l'appeler entropie, pour deux raisons. Premièrement, ta fonction d'incertitude a été utilisée en mécanique statistique sous un autre nom, donc ça a déjà un nom. Deuxièmement, et le plus important, personne ne sait ce qu'est vraiment l'entropie, donc dans un débat tu aurais toujours l'avantage." »

D'après l'autre source^[3], quand von Neumann lui demanda comment il allait avec sa théorie de l'information, Shannon répondit :

« La théorie était en excellente forme, sauf qu'elle avait besoin d'un bon nom pour "information perdue". "Pourquoi ne l'appelles-tu pas entropie ?", suggéra von Neumann. "Premièrement, un développement mathématique ressemblant fort au tien existe déjà dans la mécanique statistique de Boltzmann, et deuxièmement, personne ne comprend vraiment bien l'entropie, donc dans une discussion tu te trouverais dans une position avantageuse. »

L'entropie de l'information de Shannon est un concept plus général que l'entropie en thermodynamique. L'entropie de l'information est présente chaque fois qu'il y a des quantités inconnues pouvant seulement être décrites termes de probabilités de distribution. Donc en général, il n'y a pas de lien avec l'entropie en thermodynamique. Cependant, comme E. T. Jaynes l'a soutenu dans une série d'articles en 1957, l'entropie de thermodynamique statistique peut être vue comme une application particulière de l'entropie de l'information de Shannon.

[modifier] Définition formelle

L'entropie de Shannon d'une variable aléatoire discrète X, avec n états possibles 1..n, est définie comme :

$H(x)= -\mathbf E [\log_2 {p(i)}] = \sum_{i=1}^np(i)\log_2 \left(\frac{1}{p(i)}\right)=-\sum_{i=1}^np(i)\log_2 p(i).\,\!$

où $\mathbf E$ désigne l'espérance mathématique.

On peut remarquer certaines caractéristiques de cette formule:

La valeur de H est maximale pour une distribution uniforme, c'est à dire quand tous les états ont la même probabilité.
Toutes choses égales par ailleurs, H augmente avec le nombre d'états possible (ce qui traduit l'intuition que plus il y a de choix possibles, plus l'incertitude est grande).

[modifier] Exemples d'applications

Le caractère général de la formule d'entropie de l'information de Shannon permet de l'appliquer à différents domaines :

Pour la sélection du meilleur point de vue d'un objet en trois dimensions^[4] :

$I(S,p)= -\sum_{i=0}^N\frac{A_i}{4\pi}\log_2\left(\frac{A_i}{4\pi}\right)$

où

A i

est la surface projetée de la face

i

4π

l'angle solide de la sphère.

A i / 4π

est alors la visibilité de la face

i

du point de vue

p

A 0

représente la surface projetée de l'arrière-plan dans une scène ouverte.

[modifier] Voir aussi

[modifier] Bibliographie

↑ Claude E.Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948
↑ M. Tribus, E.C. McIrvine, “Energy and information”, Scientific American, 224 (September 1971).
↑ John Avery,"Information Theory and Evolution",World Scientific,2003,ISBN 9812384006
↑ (en) P.-P. Vàzquez, M. Feixas, M. Sbert, W. Heidrich, Viewpoint selection using viewpoint entropy, Proceedings of the Vision Modeling and Visualization Conference, 273-280, 2001.