En théorie de l'information, l'entropie de Shannon, ou plus simplement entropie, est une fonction mathématique qui, intuitivement, correspond à la quantité d'information contenue ou fournie par une source d'information. Cette source peut être un texte écrit dans une langue donnée, un signal électrique ou encore un fichier informatique quelconque (suite d'octets). Elle a été introduite par Claude Shannon.
Du point de vue d'un récepteur, plus la source émet d'informations différentes, plus lentropie (ou incertitude sur ce que la source émet) est grande. Ainsi, si une source envoie toujours le même symbole, par exemple la lettre 'a', alors son entropie est nulle, c'est-à-dire minimale. En effet, un récepteur qui connaît seulement les statistiques de transmission de la source est assuré que le prochain symbole sera un 'a'. Par contre, si la source envoie un 'a' la moitié du temps et un 'b' l'autre moitié, le récepteur est incertain de la prochaine lettre à recevoir. L'entropie de la source dans ce cas est donc non nulle (positive) et représente quantitativement l'incertitude qui règne sur l'information émanant de la source. L'entropie indique alors la quantité d'information nécessaire pour que le récepteur puisse déterminer sans ambiguïté ce que la source a transmis. Plus le récepteur reçoit d'information sur le message transmis, plus l'entropie (incertitude) vis-à-vis de ce message croît. En particulier, plus la source est redondante, moins elle contient d'information. En l'absence de contraintes particulières, l'entropie est maximale pour une source dont tous les symboles sont équiprobables.
Historique Au début des années 1940, les télécommunications étaient dominées par le mode analogique. Les sons et les images étaient transformés en signaux électriques dont l'amplitude et/ou la fréquence sont des fonctions continues du signal d'entrée. Un bruit ajouté pendant la transmission résultait en une dégradation du signal reçu. L'archétype de ce type de bruit prend la forme de grésillement pour la radio et de neige pour la télévision. Aujourd'hui, les signaux sont également codés sous forme numérique. Un bruit ajouté pendant la transmission se traduira par une erreur sur les données numériques transmises, se manifestant par exemple par l'apparition de pixels aberrants sur une image de télévision. Dans les deux cas, on souhaite d'une part transmettre le maximum de données en un minimum de temps sur un canal de transmission donné, d'autre part, on souhaite pouvoir corriger les altérations dues au bruit dans une limite donnée.
En 1948, Claude Shannon, ingénieur en génie électrique aux Laboratoires Bell, 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, ce qui lui permit d'évaluer la quantité d'information maximale qu'on pouvait transmettre dans un canal donné. Il a également montré qu'en utilisant une stratégie de codage numérique adéquat, il était possible de transmettre les informations de façon que le récepteur soit en mesure de restaurer le message original bruité sans perte d'information, sous réserve de réduire la vitesse de transmission des informations.
Initialement, il ne semble pas que Shannon ait été 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. Il aurait ajouté que ce terme était de plus assez mal compris pour pouvoir triompher dans tout débatM. Tribus, E.C. McIrvine, “Energy and information”, Scientific American, 224 (September 1971)..
En 1957, Edwin Thompson Jaynes démontrera le lien formel existant entre l'entropie macroscopique introduite par Clausius en 1847, l'entropie microscopique introduite par Gibbs, et l'entropie mathématique de Shannon. Cette découverte fut qualifiée par Myron Tribus de « révolution passée inaperçue »La référence est dans .
Le calcul de l'entropie d'une source de messages donne une mesure de l'information minimale que l'on doit conserver afin de représenter ces données sans perte. En termes communs, dans le cas particulier de la compression de fichiers en informatique, l'entropie indique le nombre minimal de bits que peut atteindre un fichier compressé. En pratique, l'entropie de l'image ou du son se voit davantage abaissée en retirant des détails imperceptibles pour les humains, comme lors de la compression des sons par le format MP3, des images par JPEG ou des vidéos par MPEG.
Définition formelle Pour une source, qui est une variable aléatoire discrète comportant symboles, chaque symbole ayant une probabilité d'apparaître, l'entropie de la source est définie comme :
où désigne l'espérance mathématique, et le logarithme en base b. On utilise en général un logarithme à base 2 car l'entropie possède alors les unités de bit/symbole. Les symboles représentent les réalisations possibles de la variable aléatoire . Dans ce cas, on peut interpréter comme le nombre de questions à réponse oui/non que doit poser en moyenne le récepteur à la source, ou la quantité d'information en bits que la source doit fournir au récepteur pour que ce dernier puisse déterminer sans ambiguïté la valeur de .
Si on dispose de deux variables aléatoires et , on définit d'une façon analogue la quantité , appelée l'entropie conjointe, des variables et :
ainsi que l'entropie conditionnelleDidier Dacunha-Castelle, Marie Duflo, Probabilités et statistiques, t.I, Masson (1982), p.19 de relativement à :
Justification de la formule Dans le cas où l'on dispose de N symboles équiprobables avec , n entier, il suffit de n questions, en procédant par dichotomie, pour déterminer le symbole envoyé par la source. Dans ce cas, la quantité d'information contenue par le symbole est exactement (on doit diviser n fois par 2 l'ensemble des possibilités pour qu'il n'en reste plus qu'une). Il est naturel de conserver cette formule dans le cas où N n'est pas une puissance de 2. Par exemple, si les symboles sont les lettres de l'alphabet ainsi que le symbole espace (soit 27 symboles), l'information contenue par un symbole est , valeur intermédiaire entre 4 bits (permettant de coder 16 symboles) et 5 bits (qui permet d'en coder 32). Cette définition de l'entropie dans le cas équiprobable est comparable à celle donnée en thermodynamique par Boltzmann.
On suppose maintenant que les N symboles sont répartis en n sous-catégories, la i-ème catégorie étant constituée de Ni symboles (avec donc ). Par exemple, les 27 caractères considérés précédemment peuvent être répartis en trois catégories, les voyelles, les consonnes et le caractère espace. Soit X la variable aléatoire donnant la catégorie du symbole considéré. On pose la probabilité que le symbole considéré appartienne à la i-ème catégorie. La détermination du symbole peut être effectuée en deux temps, d'abord celui de sa catégorie X, exigeant une quantité d'information H(X), puis, au sein de sa catégorie, la détermination du symbole. Si la catégorie à laquelle appartient le symbole est la i-ème, cette dernière étape demande une quantité d'information égale à . Cette éventualité se produisant avec une probabilité Pi, la quantité moyenne d'information pour déterminer le symbole connaissant sa catégorie est . La quantité d'information totale pour déterminer le symbole est donc la somme de la quantité H(X) pour déterminer sa catégorie, et de la quantité moyenne pour déterminer le symbole au sein de sa catégorie. On a donc :
donc :
Par exemple, la quantité d'information de 4,75 bits pour déterminer un caractère parmi 27 se scinde en H(X) = 0,98 bits pour déterminer sa catégorie (voyelle, consonne, espace) auxquels s'ajoutent 3,77 bits en moyenne pour déterminer le caractère au sein de sa catégorie.
Cas de deux variables indépendantes
On peut vérifier a posteriori la cohérence de cette définition avec la propriété d'additivité de l'entropie. Soient deux variables aléatoires indépendantes et . On s'attend à ce que . Par exemple, si (X,Y) représente la position d'un objet dans un tableau (X étant le numéro de ligne et Y le numéro de colonne), H(X,Y) est la quantité d'information nécessaire pour déterminer cette position. C'est la somme de la quantité d'information H(X) pour déterminer son numéro de ligne et de la quantité d'information H(Y) pour déterminer son numéro de colonne. Or, la probabilité du produit cartésien de ces variables aléatoires est donnée par :
qui sera abrégé par la suite en . On a alors :
comme attendu.
Exemples simples Processus de Bernoulli
On lance une pièce à pile ou face en connaissant les probabilités des deux résultats ; le modèle classique est celui d'un processus de Bernoulli.
L'entropie du résultat du lancer à venir est maximale pour une pièce équilibrée. Il s'agit bien du cas d'incertitude maximale car c'est là qu'il est le plus difficile de prédire l'issue du lancer ; le résultat de chaque lancer de la pièce donne un bit complet d'information. En effet
Cependant, si on sait par avance que la pièce n'est pas équilibrée, mais que pile et face ont des probabilités et , avec , alors l'incertitude est moindre. À chaque tirage, un côté est plus susceptible de sortir que l'autre. L'incertitude réduite est quantifiée dans une entropie moindre : en moyenne, chaque lancer délivre moins d'un bit d'information. Par exemple, si , alors
L'équiprobabilité mène à une incertitude maximale et donc une entropie maximale. L'entropie ne peut donc que décroitre en s'éloignant la valeur correspondant à l'équiprobabilité. Les cas extrêmes correspondant à des pièces double-face ou double-pile, où l'incertitude, et donc l'entropie, est nulle, et chaque tirage donne 0 bit d'information puisque le résultat est connu et certain.
Tirage aléatoire dans une urne On considère une urne contenant une boule rouge, une boule bleue, une boule jaune et une boule verte. On tire une boule au hasard. Il s'agit de communiquer la couleur tirée. Aucun tirage n'étant privilégié, l'entropie est maximale, égale ici à . Si on convient que les couleurs sont codées respectivement 00, 01, 10, 11, l'information contenue dans le tirage correspond effectivement à 2 bits.
Mais si une certaine couleur est plus représentée que les autres, alors l'entropie est légèrement réduite. On suppose par exemple que l'urne contienne 4 boules rouges, 2 bleues, 1 jaune et 1 verte. L'entropie est alors de 7/4. En effet,
Si les couleurs sont codées respectivement 0 pour le rouge, 10 pour le bleu, 110 pour le jaune et 111 pour le vertLes codes sont tels qu'aucun d'eux n'est préfixe d'un autre, de sorte qu'une suite de tirages avec remise puisse être communiquée sans ambiguïté pour le récepteur., alors l'information sur la couleur tirée occupe 1 bit une fois sur deux, 2 bits une fois sur quatre et 3 bits une fois sur quatre, soit en moyenne 7/4 bits, correspondant à l'entropie calculée.
Entropie d'un texte On considère un texte constitué d'une chaîne de lettres et d'espaces, soit 27 caractères. Si ces caractères sont équiprobables, l'entropie associée à chaque caractère est , ce qui signifie qu'il faut entre 4 et 5 bits pour transmettre un caractère. Mais si le texte est exprimé dans un langage naturel tel que le français, 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'), l'entropie de chaque caractère n'est pas si élevée. Compte tenu de la fréquence de chaque caractère, une estimation effectuée sur la langue anglaise par Shannon donne comme valeur de l'entropie environ 4,03Léon Brillouin, La science et la théorie de l'information, Masson (1959), réédité par Gabay (1988), .