16 Entropie 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 ?
16.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 d’observation 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 16.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 16.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.
16.2 Le théorème de Shannon
Quel 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 16.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)\).
Le théorème de codage suivant ne s’applique qu’aux variables discrètes.
Théorème 16.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 en 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 meilleurs 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\).
16.3 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 le code \(S\). À une constante près1, la divergence de Kullback-Leibler \[ \dkl(P\mid Q) = - \int P \ln Q - \left( - \int P \ln P \right)\] indique donc à 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é.
16.4 Retour sur l’information de Fisher
Dans un modèle exponentiel, nous avons vu que l’information de Fisher est la courbure de l’entropie (Proposition 15.1). 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)\).↩︎