Entropie de Shannon

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

L'entropie de Shannon, due à Claude Shannon, est une fonction mathématique qui, intuitivement, 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.

Sommaire

[modifier] 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 [\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. L'entropie ainsi définie vérifie les propriétés suivantes :

  • elle est maximale pour une distribution uniforme, c’est-à-dire quand tous les états ont la même probabilité ;
  • toutes choses égales par ailleurs, elle 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) ;
  • elle est continue : une faible modification des probabilités la modifie faiblement.

[modifier] Utilité pratique

L'entropie de Shannon est utilisée en électronique numérique pour numériser une source en utilisant le minimum possible de bits sans perte d'information. Elle permet aussi de quantifier le nombre minimum de bits sur lesquels on peut coder un fichier, mesurant ainsi les limites que peuvent espérer atteindre les algorithmes de compression sans perte. Il existe de tels algorithmes dits optimaux, c'est-à-dire qui compressent le fichier en un fichier d'entropie maximale (et donc de taille minimale).[réf. nécessaire] Elle est également utilisée dans d'autres domaines, comme, par exemple, pour la sélection du meilleur point de vue d'un objet en trois dimensions[1].

[modifier] Exemples simples

Considérons 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 : 'w'), 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, ce que cherche à quantifier la notion d'entropie de Shannon.

[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, fondamental dans la théorie de l'information[2].

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. Le terme entropie a été suggéré par le mathématicien John Von Neumann pour la raison que cette notion ressemblait à celle déjà connue sous le nom d'entropie en physique statistique, et il aurait de plus ajouté que ce terme était de plus assez mal compris pour pouvoir triompher dans tout débat[3].

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 Myron Tribus de "révolution passée inaperçue" dans ce document (PDF).

[modifier] Voir aussi

[modifier] Bibliographie

  1. ↑ (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.
  2. ↑ Claude E.Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July and October, 1948
  3. ↑ M. Tribus, E.C. McIrvine, “Energy and information”, Scientific American, 224 (September 1971).