La théorie de l'information : l'origine de l'entropie

La théorie de l'information est due à Shannon (vers 1948), avec bien sûr l'influence des grands théoriciens de l'informatique (Turing, von Neumann, Wiener). À noter des convergences avec les travaux de Fisher.

Le problème est celui de la communication entre une source et un récepteur : la source émet un message que le récepteur lit. On voudrait quantifier l'« information » que contient chaque message émis. Par exemple, il est clair que si l'émetteur dit toujours la même chose, la quantité d'information apportée par une répétition supplémentaire est nulle.

Le cas le plus simple est le suivant : le récepteur attend une information de type oui/non, le oui et le non étant a priori aussi vraisemblables l'un que l'autre. Lorsque la source transmet soit un oui soit un non, on considère que le récepteur reçoit une unité d'information (un bit). Autrement dit : une unité d'information, c'est quand on a a priori un ensemble de deux possibilités, et que l'une d'elles se réalise.

L'entropie existe en version combinatoire, en version de probabilités discrètes ou encore en probabilités continues (ce dernier thème étant très proche de problématiques d'analyse). On commence par la première.

Information combinatoire

Que se passe-t-il si on a plus de possibilités ? Supposons d'abord qu'on a un ensemble de possibilités $\Omega$ , et que le message consiste à spécifier un élément de $\Omega$ . Si tous les éléments de $\Omega$ sont aussi vraisemblables a priori (on verra ci-dessous ce qui se passe si on dote $\Omega$ d'une probabilité), quelle est l'information transmise par le message « telle possibilité s'est réalisée » ?

Si $\Omega$ a deux éléments, on transmet une information d'une unité. Si $\Omega$ comporte $2^n$

éléments, on peut spécifier un élément de $\Omega$ en donnant n informations élémentaires (par exemple par dichotomie de type « moitié de droite / moitié de gauche » ou bien en numérotant les éléments de $\Omega$ et en donnant la décomposition en base $2$

). On a donc envie de dire que spécifier un élément parmi un ensemble $\Omega$ de possibilités revient à transmettre $\log_2 \abs{\Omega}$ unités d'information. (Désormais dans cette partie, tous les logarithmes seront implicitement pris en base $2$

À noter que la quantité d'information n'est pas une propriété intrinsèque d'un certain objet, mais une propriété de cet objet en relation avec un ensemble de possibilités dans lequel on considère qu'il se trouve : comme l'entropie en physique, la quantité d'information est une notion relative à la connaissance préalable de l'observateur du système, du récepteur du message.

À ce stade, en notant $I_\Omega(x)$ la quantité d'information de l'événement x appartenant à l'ensemble $\Omega$ , on a donc

Avant d'en venir à un cadre probabilisé, regardons quelle est l'information d'une phrase telle que « l'événement réalisé appartient à un sous-ensemble A de l'ensemble $\Omega$ des possibilités ». On applique le principe intuitif suivant : si on dit que l'événement réalisé appartient à une partie A, puis qu'on spécifie ensuite de quel événement de A il s'agit, on a totalement spécifié l'événement, comme si on l'avait donné directement dès le début. Spécifier directement l'événement réalisé, c'est transmettre $\log\abs{\Omega}$ unités d'information. Spécifier un événement en sachant déjà qu'il appartient à un sous-ensemble A, peut se faire en transmettant $\log\abs{A}$ unités d'information. On en déduit qu'en précisant que l'événement appartient à A, on avait déjà transmis $\log\abs{\Omega}-\log\abs{A}$ unités d'information d'où

Cadre probabiliste

Supposons maintenant que toutes les possibilités ne sont pas équiprobables mais qu'on sait que certaines, a priori, apparaîtront plus souvent que d'autres. L'idée est que les événements plus rares contiennent plus d'information (exemple : complétez les mots français de cinq lettres Z___E et E___E).

On peut s'inspirer de la version combinatoire ci-dessus : on sait que l'appartenance à une partie A dans un ensemble $\Omega$ est un événement de $\log\abs{\Omega}/\abs{A}$ unités d'information. Si on suppose qu' $\Omega$ est un ensemble probabilisé où tous les événements sont équiprobables, la probabilité de la partie A est $\abs{A}/\abs{\Omega}$ ; l'information apportée par la réalisation d'un événement de A est donc $-\log p(A)$ .

Si désormais $(\Omega, p)$ est un espace probabilisé, et $A\subset \Omega$ un événement, on pose donc

Cette définition a bien la propriété qu'on attendait, à savoir que la survenue d'un événement rare contient plus d'information. Inversement, la survenue d'un événement certain (de probabilité $1$

) n'apporte aucune information.

La quantité d'information dépend plus de la distribution de probabilité que d'un événement x particulier. On va donc définir l'entropie d'une distribution de probabilité : c'est l'information moyenne qu'on obtient si on tire un élément de $\Omega$ suivant la probabilité p :

Revenons au modèle de l'émetteur et du récepteur : on suppose qu'à chaque instant, l'émetteur envoie une lettre a de l'alphabet avec la probabilité $p(a)$

; l'entropie est alors la quantité moyenne d'information apportée par chaque nouvelle lettre transmise, ou encore, l'incertitude moyenne sur la prochaine lettre qui va arriver.

L'entropie est maximale quand toutes les possibilités sont a priori équiprobables ; s'il y a n possibilités, l'entropie est alors $\log n$ . Inversement, si la mesure est concentrée en un point de probabilité $1$

, alors un tirage sous cette loi n'apporte aucune information car le résultat est connu d'avance, l'entropie est nulle.

La formule ci-dessus est celle obtenue par Boltzmann (à un facteur k près, la constante de Boltzmann, qui est un changement de l'unité d'information) pour la thermodynamique : Boltzmann suppose qu'on a un système composé de N particules indiscernables, et on sait que la proportion de particules se trouvant dans l'état i est $p_i$

. Quelle est la quantité d'information apportée par la spécification complète de l'état microscopique des particules, autrement dit, la liste qui pour chaque particules dit dans quel état elle se trouve ? Le nombre de possibilités de répartir les N particules en respectant les proportions est

Si toutes les probabilités sont égales à $1/\abs{\Omega}$ , on trouve en particulier la formule célèbre $S=\log\abs{\Omega}$ qui (avec la constante de proportionnalité k) est gravée sur la tombe de Boltzmann. Dans ce cas, l'entropie de la distribution de probabilité est bien sûr égale à la quantité d'information apportée par chaque événement particulier. (Ce qui est à l'origine d'un certain nombre de confusions, du fait que l'entropie est une notion globale définie pour une mesure de probabilité, et que parler de l'entropie d'un état particulier n'a pas de sens. En physique, l'entropie d'un état macroscopique donné est en fait l'entropie de la mesure uniforme sur tous les états microscopiques donnant cet état macroscopique.)

Tous ces raisonnements intuitifs sont justifiés par le théorème suivant, dû à Shannon, sans doute le premier théorème de théorie de l'information :

Théorème.

La famille de fonctions $S_n(p_1,p_2,\ldots,p_n)=-\sum p_i\log p_i$ est la seule vérifiant :

est symétrique en ses arguments, positive, continue
$S_n(p_1,\ldots,p_n)=S_{n-1}(p_1+p_2,p_3,\ldots,p_n)+(p_1+p_2)S_2(\frac{p_1}{p_1+p_2},\frac{p_2}{p_1+p_2})$

Le dernier axiome est un axiome de regroupement, qu'on avait déjà utilisé ci-dessus pour calculer la quantité d'information apportée par une partie $A\subset \Omega$ . Supposons par exemple que le message soit constitué de lettres, mais qu'on confonde les lettres E et F. Alors la quantité d'information reçue à la transmission est seulement $S_{25}(p(E)+p(F), p(A), \ldots p(Z))$ et pour reconstituer le message, il faut, dans une proportion $p(E)+p(F)$

des cas, demander une information supplémentaire qui départage entre E et F, ce qui transmet exactement $S_2(\frac{p(E)}{p(E)+p(F)},\frac{p(F)}{p(E)+p(F)})$ unités d'information.

Entropie d'une suite de variables

Si X et Y sont deux variables aléatoires, on peut définir l'entropie du couple $X,Y$

: $S=-\sum p_{ij}\log p_{ij}$ . On peut bien sûr généraliser à un nombre quelconque de variables.

Il résulte de la définition que si X et Y sont deux variables aléatoires indépendantes, on a

Ceci n'est pas toujours vrai : il se peut que la variable X contienne de l'information sur ce que va être Y. Par exemple, si on répète toujours deux fois de suite la même chose, l'information de la deuxième répétition est nulle : $S(X,X)=S(X)$

. En fait on a toujours

Revenons à une source qui émet régulièrement des signaux. Soit $X_t$

le signal émis au temps t, c'est une variable aléatoire à valeurs dans un certain alphabet. Ces variables ne sont pas forcément indépendantes (cas d'un texte en français : chaque lettre dépend des précédentes). L'entropie de la suite infinie $X=(X_1,\ldots,X_n,\ldots)$ est définie par

Si les lettres successives du message sont toutes indépendantes et équidistribuées (la loi de $X_n$

est égale à la loi de $X_1$

pour tout n), alors on a bien sûr

Autrement dit, dans le cas d'une source qui émet des lettres successives et indépendantes toujours avec la même loi, la quantité d'information moyenne pour chaque nouvelle lettre, est égale à l'entropie de la loi.

Entropie et codages

Codage sans bruit

La base des définitions ci-dessus était la constatation qu'un élément d'un ensemble de taille $2^n$

peut être codé par n unités d'information. C'est le premier lien entre théorie de l'information et codage.

Un codage sur un alphabet A est une application injective de A vers l'ensemble des mots sur un alphabet B (souvent $B=\{0,1\}$ ). On dit que le codage est instantanément décodable s'il n'existe pas deux lettres $a, a'$

de A telles que le code de a soit un préfixe du code de $a'$

. Tous les codages ci-dessous seront supposés instantanément décodables.

On étend le codage aux mots sur A par concaténation des codes des lettres. La propriété d'être instantanément décodable garantit alors que le codage des mots est non ambigu.

Le problème est le plus souvent de trouver les codages les plus courts possibles. La stratégie de base consiste à attribuer des codes courts aux lettres fréquentes, et des codes longs aux lettres moins fréquentes.

Soient $X_1,\ldots,X_n,\ldots$ des variables aléatoires identiquement distribuées à valeurs dans un ensemble A. Soit C un codage de A utilisant un alphabet B. On définit la longueur moyenne du codage :

Théorème.

Soit C un codage instantanément décodable pour la suite de variables $X_1,\ldots,X_n,\ldots$ . Alors

$L(C)\geq \frac{S(X_1,\ldots,X_n,\ldots)}{\log \abs{B}}$

De plus, on peut construire des codages ayant des longueurs arbitrairement proches de cette valeur.

La preuve qu'aucun code ne fait mieux que cette valeur est simple : c'est essentiellement le fait que si $\sum p_i=\sum q_i=1$ , alors $\sum p_i\log q_i$ est maximal quand $p_i=q_i$

, et la remarque que si les $\ell_i$ sont les longueurs des codes d'un codage instantanément déchiffrable, on a $\sum 2^{-\ell_i}\leq 1$ .

L'idée de la preuve que l'optimum peut être approché est la suivante : les mots de longueur n obtenus par tirage des $X_i$

peuvent être décomposés en deux classes, une classe de mots « typiques » et une classe de mots « rares ». Les mots typiques sont environ au nombre de $2^{nS}$ , chacun d'entre eux étant de probabilité environ $2^{-nS}$ ; les mots rares ont une probabilité totale négligeable. Pour coder dans $\{0,1\}$ un mot typique, on met un « 0 » suivi du code en base $2$

du numéro du mot typique parmi les $2^{nS}$ mots typiques (ce qui prend nS chiffres en base $2$

) ; pour un mot rare, on met un « 1 » suivi simplement du code en base $2$

du numéro du mot rare parmi l'ensemble des mots possibles sur l'alphabet de départ.

Un codage plus simple, proche du codage optimal, est le codage de Shannon-Fano : il consiste à attribuer à la lettre a un code en base $2$

de longueur $-\log p(a)$ (arrondi à l'entier supérieur), ce qui est toujours possible : par exemple, arranger les probabilités de manière croissante sur l'intervalle $[0;1]$

, ce qui donne une partition en sous-intervalles, si un intervalle est de longueur $p_i$

on peut trouver un nombre binaire à $-\log p_i$ chiffres qu'on lui associe, de manière à former un codage sans préfixes. Autrement dit on code les lettres plus fréquentes par des mots plus courts.

Codage avec bruit

On s'intéresse désormais au codage par des canaux de communication qui peuvent introduire des erreurs. Soit X le message à la source, Z le message codé transmis dans un canal (qui est une fonction aléatoire de X). Soit $\phi$ une fonction de décodage, on veut que $\phi(Z)=X$ le plus souvent possible, mais le passage de X vers Z n'est pas forcément injectif. Le théorème suivant, dû à Fano, affirme que la probabilité minimale d'erreur est liée à l'entropie :

Théorème.

Pour toute fonction de décodage $\phi$ , la probabilité que $\phi(Z)$ soit différent de X est supérieure ou égale à

$\frac{S(X|Z)-1}{\log\abs{X}}$

où $\abs{X}$ est la taille de l'alphabet de X.

Un canal de communication binaire étant donné, avec des probabilités d'erreur, il y a un arbitrage à faire entre concision du codage et probabilité de décodage correct : si on prend un codage sans aucune redondance, le décodage est très sensible à toute erreur ; si on répète trois fois chaque mot, on a de meilleures chances d'être compris.

Supposons donc qu'un émetteur fait transiter une lettre X d'un alphabet A au travers d'un canal binaire $\mathcal{C}$ . Auparavant, il code X par une suite binaire Y de longueur $\ell$ . Le récepteur, lui, reçoit à la sortie du canal une suite binaire Z qui est une fonction aléatoire de la suite binaire Y donnée à l'entrée du canal.

On définit la capacité d'un canal $\mathcal{C}$ par $Cap(\mathcal{C})=\sup I\!M(Y,Z)/S(Y)$ , le sup étant pris sur toutes les lois de probabilité possibles pour le mot binaire Y. Cette quantité ne dépend que du canal.

Par exemple, imaginons que le canal transmette des $0$

et des

, mais, avec une faible probabilité p, change un $0$

ou un

. La capacité est alors $1+p\log p +(1-p)\log (1-p)\leq 1$ . Dans le cas où $p=\frac12$ , aucune information ne peut être tirée, la capacité est nulle.

Un canal étant donné, on peut se demander quel codage adopter. Soit A l'alphabet de départ, un codage binaire est une application $C:A\rightarrow \{0,1\}^\ell$ pour une certaine longueur $\ell$ (pour simplifier, on considère des codages à longueur constante). On définit la probabilité d'erreur $P_e$

d'un codage C (avec fonction de décodage D) par $P_e(C)=\sup_{X\in A} P(D(Z)\neq X|Y=C(X))$ . On définit aussi le taux de compression du codage par $R(C)=(\log\abs{A})/\ell$ .

Shannon montre alors le théorème suivant, qui identifie la capacité du canal avec le taux de compression optimal :

Théorème.

La capacité $Cap(\mathcal{C})$ d'un canal $\mathcal{C}$ est égale au sup des nombres R tels que, pour tout $\eps>0$ , il existe un alphabet A, une longueur $\ell$ , un codage $C:A\rightarrow \{0,1\}^\ell$ tels que $R=R(C)$

et $P_e(C)\leq \eps$ .

La preuve de ce théorème est hautement non constructive (on choisit le codage au hasard!), et comme ci-dessus elle utilise des mots « typiques ». Ce domaine de recherche est encore très ouvert.

Codage continu

On s'intéresse désormais à la situation où on cherche à transmettre une quantité continue (intensité, voltage...). Cette fois-ci on a donc des lois de probabilité sur $\R$ . Par analogie avec le cas discret, l'entropie d'une distribution de probabilité f sur $\R$ est égale à $-\int_{x\in\R} f(x)\log f(x) dx$ .

On remarque que, si on multiplie par c la variable transmise par le canal, on ajoute $\log c$ à l'entropie de l'information transmise (ce qui est naturel : en multipliant par $2$

on a une précision deux fois plus grande, ce qui donne un bit d'information en plus). Pour obtenir des résultats pertinents, on suppose en général que les canaux utilisés sont limités en puissance, par exemple qu'ils ne peuvent pas transmettre une variable dont la variance est supérieure à un certain seuil (sans cette hypothèse, on peut facilement transmettre une quantité infinie d'information).

Un simple calcul variationnel montre que, parmi les distributions de probabilité de variance fixée, les gaussiennes sont celles d'entropie maximale. En effet, soit f une fonction maximisant $-\int f\log f$ , et calculons l'entropie d'une fonction voisine $f+\delta f$ de même variance. Comme $f $

et $f+\delta f$ sont des mesures de probabilité, donc d'intégrale $1$

, on a $\int \delta f=0$ . On peut supposer que f et $\delta f$ sont de moyenne nulle (par translation), et donc $\int t \delta f(t)=0$ . Alors le fait que $f+\delta f$ ait même variance que f s'écrit $\int t^2 \delta f(t)=0$ . Maintenant, la variation d'entropie est $-\delta \int f\log f=-\int \delta f \log f-\int f \delta \log f=-\int \delta f \log f-\int f \delta f/f=-\int \delta f \log f$ . Pour tout $\delta f$ vérifiant $\int \delta f=\int t \delta f(t)=\int t^2 \delta f(t)=0$ , on doit donc avoir $\int \delta f \log f=0$ si f est un extrémum d'entropie. Cela implique $\log f(t)=A+Bt+Ct^2$ , d'où la gaussienne.

Intéressons-nous au cas où on cherche à transmettre une information X à travers un canal limité en puissance, la limite étant p (autrement dit l'espérance de $X^2$

doit être inférieure à p). Mais ce canal est bruité ; plus exactement, on a un ennemi qui a accès à ce canal et qui peut transmettre du bruit Y (indépendant de X), la puissance du bruit transmis étant inférieure à $p'$

. Le récepteur reçoit $X+Y$

, qui fait perdre de l'information par rapport à X. Ce qui intéresse le transmetteur est de maximiser $I\!M(X+Y,X)$ à Y donné, tandis que l'ennemi cherche à minimiser cette quantité à X donné (si chacun connaît la stratégie appliquée par l'autre).

Théorème.

Il y a un équilibre de Nash à ce jeu, qui vérifie :

$\inf_Y\sup_X I\!M(X+Y,X)=\sup_X\inf_Y I\!M(X+Y,X)=\frac12\log(1+\frac{p}{p'})$

et cet équilibre consiste pour chacun à utiliser des variables gaussiennes de variances p et $p'$

La preuve utilise des inégalités fines. Par analogie avec le fait que les variances de variables indépendantes s'ajoutent, on définit la puissance-entropie $N(X)$

d'une variable X comme la variance qu'aurait une gaussienne de même entropie que X. (On vérifie qu'en dimension d, on a $N=\exp(2S/d)/2\pi e$ .)

On a alors l'inégalité de puissance-entropie de Shannon pour des variables indépendantes : $N(X+Y)\geq N(X)+N(Y)$ . Pour conserver l'information on doit monter en puissance... Autre forme équivalente : pour $0<\lambda<1$ , si X et Y sont des variables aléatoires indépendantes, alors $S(\sqrt{\lambda}\,X+\sqrt{1-\lambda}\,Y)\geq \lambda S(X)+(1-\lambda)S(Y)$ . Ceci peut servir à montrer par exemple que si $X_1,\ldots,X_n$ sont des variables aléatoires indépendantes identiquement distribuées, alors $(X_1+\cdots+X_n)/\sqrt{n}$ ressemble à une gaussienne (au moins si n est une puissance de $2$

)...

Ces inégalités n'ont pas été rigoureusement démontrées par Shannon (elles le sont désormais). Elles sont à rapprocher, par exemple, de l'inégalité de Brunn-Minkowski, ou encore à des problèmes de constantes optimales dans l'inégalité de convolution de Young $\norm{f\ast g}_{L^r}\leq C_{pqr}\norm{f}_{L^p}\norm{g}_{L^q}$ pour $1+1/r=1/p+1/q$

...