Obsolète : cet article a fait l’objet d’une nouvelle réécriture qui est plus claire et moins théorique que cette version.

À mi-chemin entre rêve, technique et mysticisme, l’entropie est un très bon buzzword à utiliser n’importe comment pour briller en société et impressionner les néophytes.

« Nobody knows what entropy really is. »

John von Neumann d’après « Information Theory and Evolution »

Cette aura est d’ailleurs pleinement justifiée tant le concept est fondamental. On le doit au physicien Rudolf Clausius en 1865 qui l’a inventé pour exprimer le désordre d’un système, permettant d’énoncer au passage le deuxième principe de la thermodynamique : l’entropie ne peut qu’augmenter.

Cette notion a été reprise et adaptée à l’informatique en 1948 par Claude Shannon pour mesurer mathématiquement la quantité d’information produite par un émetteur :

« Can we define a quantity whichwill measure, in some sense, how much information is produced […], or better, at what rate information is produced? »¹

A Mathematical Theory of Communication, 1948, C. E. Shannon, version PDF.

La notion est à ce point fondamentale qu’il jette les bases de la Théorie de l’Information et, entre autre, invente le bit comme unité pour cette mesure (dont il attribue l’idée du terme à John Tukey, un de ses collègues chez Bell Labs). Unité que nous utilisons tout le temps pour mesurer la taille des fichiers et la capacité de nos connexions réseaux.

En fait, c’est tout simple, $H = -\sum p_i \log p_i$. On peut aller jusqu’à $I(x) = -\log p_x$ si vous voulez des précisions 😁.

Quantité d’information possible

La mesure de la quantité d’information n’est pas un problème inconnu après la deuxième guerre mondiale quand Shannon publie sa Théorie. Il fait en fait suite à des travaux antérieurs de Ralph Hartley, un autre de ses collègues chez Bell Labs qui a publié en 1928 une méthode pour comparer la capacité des méthodes de communications.

« Transmission of Information », 1928, R. V. L. Hartley, version PDF.

Nombre de messages

Le point de départ est qu’une information est représentée par une suite de symboles dans un alphabet. C’est peut être évident pour vous qui êtes en train de me lire mais théoriquement, on aurait pu se prendre la tête avec l’information contenue dans une onde sonore… Heureusement, le problème a été posé par des ingénieurs 😉.

Exemple : les mots que vous lisez utilisent l’alphabet latin à 26 lettres. Puisqu’on a aussi besoin de majuscules et d’espaces, ils pourraient êtres codés dans l’alphabet ASCII qui comporte 256 caractères. Mais comme j’ai aussi besoin de caractères accentués et d’émojis, j’ai choisi UTF-8 (qui unifie ASCII et unicode), ce qui me fourni 143 859 caractères définis dans sa dernière version (sur les 1 112 064 caractères possibles).

Une fois un alphabet fixé (appelé $\Omega$ par tradition et disons qu’il contient $s$ lettres pour les calculs), on se fixe une longueur de mot (appelons la $n$, toujours par tradition). On peut alors calculer le nombre de mots possibles (qu’on appelle formellement des séquences). Mathématiquement, on peut l’exprimer comme suit :

$$Card(\Omega ^ n) = s^n$$

Exemple : les nom « trump » et « biden » font partie des mots de cinq lettres, comme $26^5 = 11\ 881\ 376$ autres noms de même longueur si on se restreint à 26 lettres.

Ce nombre, bien qu’intéressant, n’est pas pratique pour exprimer une quantité d’information. Le problème, c’est son côté exponentiel car chaque fois qu’on ajoute une nouvelle lettre (avec une nouvelle taille $n+1$), le nombre de mots possible est multiplié par $s$.

Exemple : Si on s’autorise une 6^ème lettre, on se retrouve avec 26 fois plus de mots, soit une « quantité » s’approchant des 309 millions de mots… Cette sixième lettre aurait-elle tant d’importance ?

Intuitivement, on se dit que chaque lettre devrait ajouter autant d’information que les autres (qu’importe sa position).

Taille des messages

L’idée suivante de Ralph Hartley est donc d’imposer que la quantité d’information soit proportionnelle au nombre de symboles et qu’à quantité d’information égale, deux systèmes (utilisant des lettres différentes) expriment le même nombre de mots possibles.

« […] we arbitrarily put the amount of information proportional to the number of selections and so choose the factor of proportionality as to make equal amounts of information correspond to equal numbers of possible sequences. »

Ralph Hartley dans Transmission of Information

Autrement dit, si on met des mots bout à bout, on doit pouvoir additionner leurs quantité d’informations respectives pour obtenir celle de l’ensemble. De même, changer le nombre de lettres possibles doit se ressentir par un simple changement d’échelle. Mathématiquement, je vous passe les détails, ça ne peut s’exprimer que comme suit :

$$H = n \log s$$

En fait, il y a bien un théorème en annexe de l’article de Shannon qui dit qu’il existe une, et une seule fonction qui satisfasse ces contraintes (à un facteur multiplicatif près).

La quantité d’information Η (lettre grecque Eta²) étant le produit de la taille des mots $n$ et du logarithme du nombre de lettres de l’alphabet. Le choix de la base utilisée pour le logarithme fixe d’une certaine manière la taille de l’unité utilisée.

Exemples : La base 26 donne une mesure en lettres, la base 10 une mesure en chiffres et la base 2 donne une mesure en bits (même si l’Unité ne sera formellement créée que 20 ans plus tard).

Pour nos noms de 5 lettres, on voit déjà que cette quantité d’information est plus intuitive. On peut également calculer sa conversion en « 23,5 bits » ($= 5 \log_2 26$). Ce qui signifie que le même nombre de noms pourrait être codés avec un système à 24 interrupteurs (on/off) dont le dernier n’est pas toujours utilisé.

Le but de Ralph Hartley étant surtout de mesurer la quantité d’information exprimable avec un système de communication, sa mesure rempli sa mission. Il peut ainsi comparer différents encodages télégraphiques et déterminer lequel exprime le plus d’information.

Information utilisée

C’est ici que Claude Shannon prend le relais 20 ans plus tard. Plutôt que la capacité théorique d’un canal de communication, il va chercher à calculer la quantité réellement émise par l’émetteur du message. Intégrant dans ses réflexions les redondances et la tolérance au bruit.

Messages interdits

Tout part du constat que même si toutes les suites de symboles sont techniquement possibles, seule une (petite) partie d’entre eux seront vraiment utilisés car les autres n’auront aucun sens pour l’émetteur ou le récepteur (voir les deux). Pour communiquer, il faut une convention commune.

Exemple : Si vous cherchez à identifier toutes les voitures en circulation avec un code le plus court possible, votre format devra prendre en compte le nombre de voitures. Et pour économiser les numéros utilisés vous pouvez vous restreindre au nombre de voitures réellement en circulation.

Pour rester sur des mots de 5 lettres. Si on se restreint au français, seuls 7980 d’entre eux ont un sens (cf. listedesmots.net). Pour l’anglais, ils sont 6308 (cf. yougowords.com).

La formule précédente est toujours valable mais au lieu du nombre de mots maximal, on se restreint au nombre de mots exprimés.

$$H = \log Card(mots)$$

Exemple : Pour les mots de 5 lettres, sur les 24 bits utilisés, seuls 13 sont utiles ($\log_2 7980 = 12,96$ pour le français et $\log_2 6308 = 12,62$ pour l’anglais).

Pour gonfler ces chiffres, on peut aussi considérer le nombre total de mots d’une langue. C’est difficile à évaluer mais on compte généralement autour de 130000 mots dans un dictionnaire (17 bits) et pour gonfler encore plus, il y a 1 866 079 entrées pour le français dans fr.wiktionnary.org (soit 20,83 bits).

À l’autre extrême, les mots « Trump » et « Biden », s’il s’agit du vainqueur de la 59^ème élection présidentielle américaine, ne nécessitent en fait qu’un seul bit d’information (puisque ce sont les deux seules possibilités).

Ce qu’elle nous dit, et c’est important car c’est fondamental, c’est qu’en restreignant le nombre de mots autorisés, la quantité d’information de l’ensemble diminue. En fait, cette restriction et une information en elle-même et on peut considérer qu’on l’a, en quelque sorte, enlevée de l’ensemble initial.

Exemple : Si vous êtes face à un générateur de mots à 5 lettres, et que je vous informe qu’il s’agira de mots en français, la quantité d’information que vous espériez de chaque mot passera de 24 à 13 bits. Mon information vaut en quelque sorte 11 bits d’information.

Distribution de probabilité

On va maintenant nuancer cette idée de base de « mots impossible » en la remplaçant par l’idée que des mots sont « plus ou moins probables ». Autrement dit, on considère que, parmi tous les messages possibles, l’émetteur va en favoriser certains au détriment des autres.

Exemple : C’est le cas des langues, comme le français où certains mots sont très courants (comme les articles ou les verbes auxiliaires). Et de manière générale, c’est aussi le cas de « tirages pas aléatoires » comme le résultat des élections ou de courses (dans les deux cas, certains partent avec un avantage).

Mathématiquement on parle alors de probabilité. Cette proportion de chance (valeur entre 0 et 1) qu’un événement se produise (proche de 1) ou non (proche de 0). Pour un message $x$ donné, sa probabilité sera notée $p_x$. C’est important car les prochaines formules l’utiliseront toutes.

On rencontre plein de manières d’écrire de probabilités exprimant « La variable aléatoire X prend pour valeur x », du style $P(X = x)$ pour les plus verbeux, à $p_x$ pour les minimaliste ou encore $p(x)$. Tout dépend généralement du contexte et de l’utilité qu’on aura de la notation. Dans notre cas, $p_x$ est largement suffisant.

En ajoutant cette distribution de probabilité, on introduit une nouvelle subtilité car on doit maintenant distinguer deux quantité d’informations (qui ne sont plus les mêmes) :

1. celle contenue dans un message particulier (l’information propre),
2. celle qu’on peut attendre d’un émetteur particulier (la fameuse entropie).

Information propre d’un message

On reprend alors l’idée de Ralph Hartley d’additionner l’information de chaque morceau (indépendant puisqu’on parle de probabilité) pour avoir celle de l’ensemble et on ajoute la nouvelle contrainte que les mots rares portent plus d’information que les mots courants qui, s’ils sont certains, n’en apporteront pas du tout.

Exemple : je choisi aléatoirement un mot de 5 lettres en français, vous avez donc le choix parmis 7980 mots (je fait mes comptages avec listesdemots.net). Ensuite, pour vous aider, je vais vous donner une information : une des lettre qui apparaît dans le mot choisi.

De la même manière que vous informer que les mots sont en français réduit la quantité d’information de 24 à 13 bits, vous dire une des lettres qui le compose vous fourni de l’information :

• Si c’est un e, il restera 4338 mots, soit $\log_2 4338 = 12,08\ bits$,
• Si c’est un z, il restera 427 mots, soit $\log_2 427 = 8,7\ bits$.

En généralisant, plus une lettre est fréquente parmi les mots possibles, moins elle élimite de mots de la liste et donc moins elle apporte d’information à votre quête. Inversément, plus une lettre est rare, plus la liste des possible se réduit et plus sa connaissance apporte d’information.

Mathématiquement, je vous passe les détails, une seule famille de fonction répond à ces contraintes. Sans trop de surprise, ça ressemble à tout à l’heure… La base du logarithme permettant un changement d’échelle :

$$I(x) = - \log p_x$$

Si la ressemblance ne vous saute pas aux yeux, faisons les calculs avec un ensemble de $s^n$ mots qui sont tous aussi probables les uns que les autres. Leur probabilité vaut alors $1/s^n$ et dans ce cas, leur information propre est calculée de la manière suivante :

$$I(x) = - \log 1/s^n = \log s^n = n \log s$$

Exemple : Une lettre alphabétique tirée au hasard parmi les 26 habituelles, a une probabilité de $1/26$ d’être choisie. Dans ce cas, elles portent toutes la même quantité d’information, $-\log_2 1/26=4,7$ bits d’information.

Mais si je veux refléter la fréquence habituellement constatée dans les textes en français, je pourrais tirer une lettre au hasard dans wikipedia francophone (et recommencer tant que ça n’est pas une des 26). Si je fais ça en 2008 (année pour laquelle on dispose de ces fréquences), voici ce que je pourrais calculer :

• Le e est présent 14,19 % du temps et porte ainsi $- \log_2 0,1419 = 2,81$ bits d’information,
• Le z est présent 0,18% du temps et porte, lui, $-\log_2 0,0018 = 9,14$ bits d’information.

Entropie d’un émetteur

Nous sommes maintenant équipés pour mettre au point une formule pour calculer la quantité d’information qu’un émetteur produit à chaque message. Et pour ça, vous pouvez prendre le problème de deux manières différentes…

1. Simplement, en cherchant la quantité d’information moyenne des messages émis, mathématiquement, vous cherchez l’espérance $E(I)$,
2. Comme Shannon en 1948, en cherchant une fonction continue, qui soit au maximum lorsque les probabilités sont égales (c’est dans ce cas qu’un émetteur est le plus surprenant) et permettant d’additionner l’entropie de plusieurs générateur s’ils sont utilisés indépendamment.

Truc chouette avec les maths, les deux façons aboutissent à la même formule 🎉 :

$$H = \sum_x p_x I(x) = - \sum_x p_x \log p_x$$

La première version est sous la forme de l’espérance mathématique (moyenne pondérée des valeurs), la deuxième est la forme classique qu’on utilise partout et qui a été définie par Shannon.

Exemple : Si on tire une lettre alphabétique au hasard, votre quantité moyenne d’information, votre entropie donc, vaut 4,7 bits. Si, par contre, vous le faites dans wikipedia francophone, votre entropie se réduira à 4,1 bits. La différence de 0,6 bit correspond à une forme de redondance.

Pour la petite histoire, la lettre H et le nom entropie ont bien été choisi pour leur lien avec la physique. On le voit tout de suite dans le « Célèbre Théorème H » de Boltzmann qui introduit une quantité, opposée à l’entropie :

$$H=\sum_i\int_{\mathbf{v}} f_i \log f_i \mathrm{d}\mathbf{v}_i$$

Cette fois la ressemblance saute au yeux ! non ? Enlevez l’intégrale, le dv et ajoutez un - devant, remplacez le $f$ par un $p$ et vous l’avez !? Comme quoi, tout se tient.

Et après ?

Le calcul de l’information propre d’un message, ou celui de l’entropie d’un générateur servent dans plein de domaines autour de la Théorie de l’Information. En linguistique pour savoir à quel point une langue utilise efficacement ses symboles ou ses mots (plus l’entropie diminue, plus il y a redondance). En cryptologie et donc en sécurité informatique pour mesurer l’efficacité d’un générateur d’aléa (plus il y a d’entropie, plus l’aléa est de qualité). En expertise judiciaire, parfois, car l’entropie d’un fichier peut renseigner sur le type de contenu (on vous racontera).