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).\]
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)\).
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 meilleur codage, et le meilleur codage en question est le codage entropique qui assigne à chaque \(a \in \mathcal{X}\) un code de longueur proche de \(\log_2(\mathbb{P}(X=a))\). On a donc compressé au mieux la variable \(X\).
Preuve. J’écrirai plus tard la preuve via le lemme de Kraft.
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)\).↩︎