20 Hasard et information

Soient \(X_i\) des variables aléatoires définies sur un même ensemble fini \(\mathcal{X} = (a_1, \dotsc, a_k)\). On note \(p_k = \mathbb{P}(X = a_k)\). On observe un échantillon de \(n\) réalisations des \(X_i\), disons \((x_1, \dotsc, x_n)\). Avant de s’intéresser à l’information que portent ces observations sur la loi \(\mathbb{P}\), qui est le problème statistique auquel nous nous sommes intéressé, on peut se demander quelle est la quantité d’information portée par les \(x_i\) tout court, sans avoir à faire d’hypothèses sur la loi de \(X\). Par exemple, si toutes les observations sont identiques, l’échantillon transporte peu d’information – en tout cas, moins que si les observations sont un peu plus variées. La question posée est la suivante : si l’on voulait coder les observations de sorte que deux observations différentes soient codées de deux façons différentes, et de sorte qu’en moyenne le codage des informations soit le plus compressé possible, quel code utiliserait-on ?

20.1 La notion de code

Il faut raisonner en termes de bits d’information : on veut coder chaque élément observé par une suite de 0 et de 1.

Par exemple, supposons que \(\mathcal{X}\) ne possède que deux éléments ; on peut coder \(x_i=0\) ou \(1\) et voir notre échantillon comme une suite binaire de longueur \(n\). On aura donc besoin de au plus \(n\) bits d’information pour encoder l’échantillon ; un « bit » est la donnée d’un 0 ou d’un 1.

Si maintenant \(\mathcal{X}\) contient 4 éléments, on peut coder ses élements par des suites de deux bits : \(00,01,10, 11\). Le codage d’une observation nécessitera toujours deux bits. Pour encoder notre échantillon, on aura besoin de \(n\) fois deux bits d’information au plus, donc \(2n\) bits. Par exemple, l’échantillon \((a,a,a,b,a,d,d,a,a,a)\) sera codé \(00000001001111000000\), donc 20 bits.

Plus généralement, si \(\mathcal{X}\) contient \(k\) éléments, on peut chacun les coder avec au plus \(\log_2\lceil k \rceil\) bits et il faudra \(n\log_2\lceil k \rceil\) pour encoder l’échantillon.

Dans ces exemples, chaque codage d’un échantillon nécessitait le même nombre de bits. Ce codage-là ne nécessite aucune information particulière sur les \(x_i\). Mais maintenant, dans le cas où \(\mathcal{X}\) comporte 4 éléments \(\{a,b,c,d\}\), supposons que le premier élément soit beaucoup plus fréquent que les autres ; autrement dit,

	a	b	c	d
\(\mathbb{P}(X = …)\)	97%	1%	1%	1%

Dans ce cas, la plupart des observations n’auront que des \(a\). Donc si j’assigne à l’observation \(a\) un code d’un seul bit, disons 0, et que j’assigne aux trois autres des codes plus longs comme \(10, 110, 111\), alors le coût moyen de codage d’une observation sera \[ 1\times 97\% + 2\times 1\% + 3 \times 1\% + 3\times 1\% = 1.05\] Autrement dit, en moyenne, je n’aurai pas besoin de beaucoup plus d’un bit par observation, alors que le codage élémentaire ci-dessus en nécessitait exactement deux. Avec ce code, l’échantillon \((a,a,a,b,a,d,d,a,a,a)\) devient codé par \(000100111111000\), donc 15 bits.

Définition 20.1 Un code binaire de \(\mathcal{X}\) assigne à chaque élément \(a\) de \(\mathcal{X}\) un mot binaire \(w(a)\). Le code d’un élément ne doit pas être le début du code d’un autre élément.

Par exemple, je n’ai pas le droit de coder l’ensemble à quatre éléments avec le code \(w(1)=1, w(2)=10, w(3)=11, w(4)=010\). En effet, dans ce cas je ne serai pas en mesure de discerner si \(1010\) veut dire \(w(1)w(4)\) ou bien \(w(2)w(2)\).

La longueur du \(k\)-ème élément \(w(k)\) est notée \(\ell_k\). Étant donné un code, le nombre moyen de bits d’information nécessaire pour coder une variable aléatoire \(X\) sur \(\mathcal{X}\) est donc \[\mathbb{E}[\ell_X] = \sum_{i=1}^k \ell_i \mathbb{P}(X = a_i).\]

Exemple 20.1 Un roman contient environ 80000 mots, donc environ 400000 signes (en comptant les espaces). Un signe peut être l’une des 26 lettres de l’alphabet (en majuscule ou minuscule), un signe de ponctuation, un chiffre, une lettre accentuée… La plupart des romans occidentaux ont besoin d’un alphabet de ~200 lettres. Le codage binaire basique lettre-par-lettre nécessiterait donc environ \(\lceil \log_2 200 \rceil \approx 8\) bits d’information par lettre, soit 3200000 bits. On compte plutôt en paquet de 8 bits, appelés bytes : le codage du roman nécessiterait donc environ 400000 bytes soit 400kB. On va voir plus loin qu’un encode entropique serait plus économique.

20.2 L’entropie des variables aléatoires

Quelle est la plus petite quantité moyenne d’informations nécessaire à coder une réalisation de \(X\) ? La réponse est l’entropie de la loi de \(P\).

Définition 20.2 (Entropie) Soit \(X\) une variable aléatoire de loi \(P\), possédant une densité \(f\) par rapport à une mesure de référence. L’entropie \(\ent(P)\) est \[ - \int_{\mathcal{X}}f(x)\log_2 f(x)\nu(dx).\]

Lorsque \(X\) est une variable discrète prenant la valeur \(a_k\) avec probabilité \(p_k\), l’entropie est donc égale à \[ -\sum_{k} p_k \log_2 p_k.\]

En théorie de l’information, on prend plutôt le logarithme en base 2 plutôt que le logarithme népérien. L’entropie ne diffère alors que d’une constante \(\ln(2)\). L’entropie des lois discrètes finies possède de nombreuses propriétés intéressantes.

Proposition 20.1 Soit \(X\) une variable aléatoire sur un ensemble fini à \(m\) éléments. Son entropie \(\mathrm{Ent}(X)\) vérifie \[0 \leqslant \mathrm{Ent}(X) \leqslant \log_2(m).\]

L’entropie est nulle si et seulement si \(X\) est constante, et elle vaut \(\log_2(m)\) si et seulement si \(X\) est la loi uniforme.

Preuve. La première inégalité est évidente puisque \(-\log_2(p_k)\) est un nombre positif. Pour la seconde, on peut utiliser l’inégalité de Jensen : en effet, la fonction \(\log_2\) est concave, donc \[\mathrm{Ent}(X) = \mathbb{E}[\log_2(1/p_X)] \geqslant \log_2\left(\mathbb{E}[1/p_X]\right).\] Le résultat vient immédiatement du fait que \(\mathbb{E}[1/p_X] = m\). Si l’un des \(p_k\) est nul, il suffit de restreindre \(X\) à l’ensemble des \(k\) tels que \(p_k > 0\), qui contient moins de \(m\) éléments, pour avoir le résultat.

Remarque. Pour les lois continues, tout ceci est entièrement faux. Les entropies des variables à densité peuvent valoir n’importe quelle valeur réelle (même pas forcément positive).

Le lemme précédent donne une bonne intuition sur l’entropie : il s’agit vraiment d’une mesure de la quantité de hasard contenue dans un phénomène aléatoire. La loi uniforme est la loi la plus aléatoire possible, et son entropie est maximale. La masse de Dirac est la loi la moins aléatoire possible, et son entropie est nulle.

Plus il y a de hasard, de désordre ou de désorganisation, plus l’entropie est grande. Plus il y a de certitude, d’ordre et de structure, plus l’entropie est petite. En physique, le second principe de la thermodynamique dit que l’entropie d’un système isolé ne peut que croître ; le système se dirige toujours vers un état où il y a plus de désordre.

20.3 Le théorème de Shannon

Le théorème de codage suivant ne s’applique qu’aux variables discrètes.

Théorème 20.1 (Théorème de codage de Shannon) Tout codage vérifie \(\mathbb{E}[\ell_X]\geqslant \ent(P)\).

Il existe un codage appelé codage entropique vérifiant \(\ell^\star(a)=\lceil \log_2(p_k)\rceil\), et donc \(\mathbb{E}[\ell^\star_X]\leqslant \ent(P)+1\).

En particulier, le codage optimal d’un échantillon iid de taille \(n\) vérifie \[ \lim \frac{\mathbb{E}[\ell^\star_n]}{n} = \ent(P).\]

L’entropie d’une loi est donc le nombre moyen de bits d’information nécessaire à son codage le plus économe : asymptotiquement, ce codage est le codage entropique qui assigne à chaque \(a \in \mathcal{X}\) un code de longueur proche de \(\log_2(\mathbb{P}(X=a))\). Cependant, il existe d’autres codages qui sont asymptotiquement aussi bons que le codage ci-dessus, et qui sont meilleurs même à distance finie : par exemple, le codage de Huffman.

Preuve. On énumère les \(n>2\) éléments de \(\mathcal{X}\) en \(a_1, \dotsc, a_n\), et on note \(p_i = P(X = a_i)\). Soit \(\ell\) un codage et soit \(\ell_i\) la longueur du code \(\ell(a_i)\). La longueur moyenne de ce code est \[ E[\ell_X] = \sum_{i=1}^n p_i\ell_i.\]

Ainsi, \(E[\ell_X] - \ent(P)\) vaut \[\sum_{i=1}^n p_i\left(\ell_i + \log_2(p_i)\right)\] c’est-à-dire, après une petite manipulation, \[-\sum_{i=1}^n p_i\log_2\left(\frac{1}{p_i2^{\ell_i}}\right).\] La fonction \(-\log_2\) étant convexe, l’inégalité de Jensen dit que la quantité ci-dessus est plus grande que \[ -\log_2 \left( \sum_{i=1}^n p_i\frac{1}{p_i 2^{\ell_i}} \right)\] qui se simplifie en \[ -\log_2 \left( \sum_{i=1}^n \frac{1}{2^{\ell_i}} \right).\] Il suffit alors de montrer que la somme \(s\) à l’intérieur du \(\log_2\) est plus petite que 1 : c’est cette inégalité qui est connue sous le nom de lemme de Kraft. Elle entraîne immédiatement que \(-\log_2(s) \geqslant 0\), et donc \(E[\ell_X] \geqslant \ent(P)\).

Démonstration du lemme de Kraft. Mettons la constante \(s\) à une puissance entière \(k\) : en écrivant \(s^k\) comme \[\left(\sum_{a \in \mathcal{X}}\frac{1}{2^{\ell(a)}} \right)^k\] et en développant, on trouve \[\sum_{a^1, \dotsc, a^k \in \mathcal{X}}\frac{1}{2^{\ell(a^1) + \dotsb + \ell(a^k)}}\] c’est-à-dire \[\sum_{A \in \mathcal{X}^k}\frac{1}{2^{\ell(A)}}.\] Notons \(c_i\) le nombre de mots de \(k\) lettres dont le code est lui-même de longueur \(i\). La quantité précédente vaut \[\sum_{i=1}^{+\infty} c_i \frac{1}{2^i}.\] Vu que le code est injectif, deux mots différents ont deux codes différents : or, il y a \(2^i\) codes possibles de longueur \(i\), donc \(c_i \leqslant 2^i\). De plus, si \(N\) est la longueur de la lettre la plus longue à coder, il est clair que le mot le plus long à coder aura une longueur de \(kN\). Ainsi, \(c_i\) devient nul dès que \(i>kN\). On en déduit que la somme ci-dessus est plus petite que \[\sum_{i=1}^{kN} 2^i \frac{1}{2^i} = kN.\] On vient de montrer que, pour n’importe quel nombre entier \(k\) non nul, \[s^k \leqslant kN.\] Si le nombre \(s\) était strictement plus grand que 1, le terme de droite aurait une croissance exponentielle en \(k\), tandis que le terme de gauche n’aurait qu’une croissance linéaire. C’est impossible, et on doit donc avoir \(s\leqslant 1\).

20.4 L’entropie relative

Soit \(P\) une loi de probabilité. Le codage optimal de \(P\) est \(\log_2 P\). On pourrait aussi utiliser le codage d’une autre loi de probabilité, disons \(Q\) : la quantité

\[\sum_{k=1}^n p_k \log_2\frac{p_k}{q_k}\] peut aussi se voir comme \[(-E[\log_2 q_X]) - E[\ell_X^\star].\] Il s’agit donc bien d’une « redondance d’information » : le terme de droite est la quantité minimale d’information dont on a besoin pour coder \(X\) en moyenne (via le codage entropique), et le terme de gauche est la quantité d’information dont on use pour coder \(X\) en moyenne par un code qui serait le codage optimal de \(Q\). À une constante près¹, la divergence de Kullback-Leibler de \(P\) vers \(Q\) vaut \[ \dkl(P\mid Q) = - \int P \ln Q - \left( - \int P \ln P \right)\] et elle indique à quel point il est optimal (ou pas) d’encoder les réalisations de la loi \(P\) grâce au « code » \(\log_2 Q\) : \(\dkl\) quantifie la redondance de \(Q\) par rapport à \(P\). Puisque le codage optimal est celui qui code \(x\) par \(\log_2 P(x)\), le codage utilisant \(\log_2 Q(x)\) n’a pas structuré au mieux l’information disponible dans \(P\) est pourrait être allégé.

Point mnémotechnique. Pour se souvenir le sens de la formule de la divergence KL, il suffit de se souvenir que le premier terme est le source des variables \(X\). \(-\mathbb{E}[\log p(X)]\) est l’entropie et \(-\mathbb{E}[\log q(X)]\) est le coût non-optimal, donc la différence des deux est la redondance d’information.

Exemple 20.2 La fréquence des lettres en français et en anglais n’est pas la même. On estime l’entropie des 26 lettres de l’alphabet à environ 4.2 bits pour le français, et 4.7 bits pour l’anglais (et pour simplifier, on ignore la ponctuation et les accents).

Supposons qu’un programme soit conçu pour encoder des textes en anglais (par exemple, sur une liseuse, dans laquelle la place est assez limitée). Chaque lettre \(k\) est encodée par un code de longueur proche de \(\log_2(p^{\mathrm{eng}}_k)\) bits. Un texte contenant 400000 lettres écrit en anglais sera donc encodé avec une taille d’environ \(400000 \times 4.7 = 1880000\) bits, soit 235kB.

Maintenant, supposons qu’on utilise cet ordinateur pour encoder un texte écrit en français. La divergence de KL de l’anglais vers le français peut se calculer, et elle est égale à 0.2 bits environ : cela signifie que si le texte original est en français mais encodé par l’encodage optimal de langue anglaise, son encodage prendra plutôt \(4.9 \times 400000\) bits, soit 245kB, une perte de \(0.2 \times 400000\) soit 10kB.

Dans ce cas précis, il serait intéressant de détecter la langue et de faire varier l’encodage en fonction de la langue.

20.5 Information de Fisher et entropie

Dans le cas général d’une loi de densité \(f\) par rapport à une mesure de référence \(\nu\), l’entropie est donnée par

Définition 20.3 (Entropie) L’entropie d’une loi de densité \(f\) par rapport à la mesure de référence \(\nu\) est donnée par \[\mathrm{Ent}(f) = -\int f(x)\ln f(x)\nu(dx). \]

Lorsque \(\nu\) est la mesure de comptage sur un ensemble fini ou discret \(\mathcal{X}\), on retrouve la formule de l’entropie discrète ci-dessus.

Dans le cas d’un modèle exponentiel, l’entropie est égale à \(E_\theta[\ln p_\theta(X)]\) par définition. On peut interpréter \(I(\theta)\) comme la courbure moyenne de l’entropie.

Proposition 20.2 \(I(\theta) = - \nabla^2_\theta~ \mathrm{Ent}(p_\theta).\)

Preuve. Il suffit de dériver deux fois sous l’intégrale et d’utiliser Équation 17.2.

Comme dans ce cadre, l’entropie est concave, la courbure en \(\theta\) est un indicateur de à quel point l’entropie forme un « pic » autour de \(\theta\).

À savoir \(\ln(2)\).↩︎