Entropie de Shannon

Infos
catégorie : Théorie de l'information 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. Cette source peut être une langue, un signal électrique, ou un fichier informatique quelconque. 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. En l'absence de
Entropie de Shannon

catégorie : Théorie de l'information 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. Cette source peut être une langue, un signal électrique, ou un fichier informatique quelconque. 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. En l'absence de contraintes particulières, 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, mais 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 suggéré à Shannon dès 1947 par le mathématicien John Von Neumann, sur une boutade, selon Myron Tribus : Your mathematical formula is similar to one used in statistical mechanics. People do not really understand entropy so if you use it in an argument, you will win every time, hands down ("Votre formule ressemble beaucoup à celle utilisée en mécanique statistique. L'entropie étant un concept mal maîtrisé par les auditoires, si vous utilisez ce terme comme argument, il sera décisif"). Une analogie avec la notion d'entropie existante en thermodynamique (et utilisée plus tard en théorie du chaos) existait d'ailleurs bien : l'entropie d'une source possède ainsi des propriétés similaires aux définitions en thermodynamique, notamment l'additivité. En 1957, Edwin Thompson Jaynes démontrera le lien formel existant entre l'entropie macroscopique introduite par Clausius en 1847, la microscopique introduite par Gibbs, et l'entropie mathématique de Shannon. Cette découverte fut qualifié par Tribus de "révolution passée inaperçue" (PDF).

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 en moyenne 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 1948Claude E.Shannon . 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.

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 M. Tribus, E.C. McIrvine, “Energy and information”, Scientific American, 224 (September 1971). : :Mon plus gros souci é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 sourceJohn Avery, "Information Theory and Evolution", World Scientific, 2003, ISBN 9812384006, 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 en 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.

Définition formelle

L'entropie de Shannon d'une variable aléatoire discrète X, avec n états possibles, 1..n, et définie comme suit : ::H(X)= -\mathbf E = \sum_^np(i)\log_2 \left(\frac\right)=-\sum_^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).

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 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. : :I(S, p)= -\sum_^N\frac4\pi\log_2\left(\frac4\pi\right) :où A_i est la surface projetée de la face i et 4\pi l'angle solide de la sphère. A_i/4\pi 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.

Voir aussi

- Théorie de l'information
- Entropie de Rényi
- Entropie métrique

Bibliographie

de:Entropie (Informationstheorie) el:Εντροπία πληροφοριών en:Information entropy es:Entropía (información) he:אנטרופיה (סטטיסטיקה) hu:Shannon-entrópiafüggvény it:Entropia (teoria dell'informazione) ko:정보 엔트로피 nl:Entropie (informatietheorie) pl:Entropia (teoria informacji) ru:Информационная энтропия simple:Information entropy sv:Entropi (informationsteori) th:เอนโทรปีของข้อมูล vi:Entropy thông tin zh:熵 (信息论)
Sujets connexes
Angle solide   Chaîne de caractères   Claude Shannon   Codage   Compression de données   Distribution   Edwin Thompson Jaynes   Entropie   Entropie de Rényi   Entropie métrique   Espérance mathématique   Information   John von Neumann   Laboratoires Bell   Lempel-Ziv-Welch   Ludwig Boltzmann   Myron Tribus   Physique statistique   Run-length encoding   Thermodynamique   Théorie de l'information   Théorie du chaos   Variable aléatoire   ZIP (format de fichier)  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^