L’entropie et le code le plus court

La plupart des bornes de ce domaine sont lâches. On démontre qu’une erreur vaut au plus quelque chose, ce quelque chose est énorme, et l’intérêt du résultat tient à sa forme plus qu’à son chiffre.

L’entropie n’est pas de cette espèce. C’est la longueur moyenne la plus courte qu’un code puisse atteindre, et il existe un code qui l’atteint.

L’affirmation, sur une source vérifiable à la main

Prenez quatre symboles de probabilités $\tfrac12$, $\tfrac14$, $\tfrac18$, $\tfrac18$. L’entropie vaut

$$H = \sum_x p(x)\log_2\frac{1}{p(x)} = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1{,}75 \text{ bits}$$

Construisez maintenant le meilleur code préfixe, c’est-à-dire un code où aucun mot n’est le début d’un autre, de sorte que le flux se lit sans séparateurs. En fusionnant à plusieurs reprises les deux symboles les moins probables, on obtient des longueurs de 1, 2, 3 et 3 bits, soit une moyenne de

$$0{,}5(1) + 0{,}25(2) + 0{,}125(3) + 0{,}125(3) = 1{,}75 \text{ bits}$$

Exactement l’entropie, à toutes les décimales. Un code de longueur fixe demanderait 2 bits par symbole : l’économie est de 0,25 bit, soit 12,5 %.

La raison de cette égalité exacte se lit dans le calcul : chaque longueur idéale $\log_2(1/p)$ est ici un entier, parce que toutes les probabilités sont des puissances de deux. Le code peut donner à chaque symbole précisément la longueur qu’il mérite.

Ce que dit vraiment la borne

$$L \ge H \quad \text{pour tout code uniquement déchiffrable}$$

Deux moitiés méritent d’être séparées. La réciproque dit qu’aucun code ne peut faire mieux : ni un arbre plus astucieux, ni un autre alphabet, ni un procédé que personne n’a encore inventé. L’atteignabilité dit qu’il existe un code à moins d’un bit de la borne, et qui s’en approche autant qu’on veut grâce à l’astuce ci-dessous.

Cette combinaison fait de l’entropie un outil de modélisation plutôt qu’une statistique descriptive. Si un compresseur bat l’entropie que vous avez calculée, le théorème n’est pas en difficulté : votre distribution était fausse. Le plus souvent elle supposait une indépendance qui n’existe pas, et le compresseur a trouvé la structure que vous n’avez pas modélisée.

Là où les bits entiers sont trop grossiers

Changez la source en $(0{,}6,\ 0{,}25,\ 0{,}1,\ 0{,}05)$. L’entropie vaut 1,4905 bit et le meilleur code préfixe en moyenne 1,5500. Un écart de 0,0595 bit par symbole est apparu.

Le code n’a rien de fautif : il est prouvé optimal parmi les codes préfixes pour cette source. Le problème est la granularité. La longueur idéale d’un symbole de probabilité 0,6 est $\log_2(1/0{,}6) = 0{,}737$ bit, et aucun mot de code ne dure 0,737 bit. Le mieux possible est 1, et vous surpayez de 0,263 bit chaque fois que ce symbole apparaît.

La figure ci-dessous construit le code plutôt que de le recopier, pour la distribution que vous réglez. Partez de la source dyadique : l’écart est exactement nul. Écartez n’importe quelle probabilité d’une puissance de deux et un écart apparaît aussitôt ; la colonne de droite montre pourquoi, en donnant la longueur méritée par chaque symbole à côté de l’entier qu’il a bien fallu lui donner. Augmentez ensuite la taille de bloc et regardez l’écart se refermer par le haut, sans que l’entropie par symbole bouge d’un cheveu.

L’astuce qui referme l’écart

Cessez de coder un symbole à la fois. Codez des blocs, et l’erreur d’arrondi se partage sur le bloc :

On s’en approche par le haut, sans jamais la franchir.

Il vaut la peine de préciser pourquoi cela fonctionne, car l’explication évidente est fausse. Les symboles sont ici indépendants : il n’y a donc aucune redondance entre eux qu’un bloc plus long pourrait exploiter, et l’entropie par symbole ne change pas. Ce qui change, c’est qu’un bloc de quatre possède 256 valeurs, dont les longueurs idéales s’approchent bien plus finement par des nombres entiers de bits. Le gaspillage est la même fraction de bit, répartie sur quatre fois plus de symboles.

Ce que mesure l’entropie

Il est tentant de lire l’entropie comme un désordre, et cette lecture est sans danger jusqu’au moment où elle ne l’est plus. L’énoncé précis est : le nombre moyen de questions par oui ou non nécessaires pour identifier le résultat, lorsque vous avez le droit de choisir les questions au mieux.

Ce cadrage explique la forme de la formule. Un symbole de probabilité $p$ porte $\log_2(1/p)$ bits : une certitude porte zéro, un événement à une chance sur un million porte environ 20 bits. Les événements rares informent précisément parce qu’ils étaient inattendus, et l’entropie est la moyenne de cette surprise sur tout ce que la source peut produire.

Cela explique aussi ce que l’entropie n’est pas : une propriété d’une chaîne de caractères. Un fichier n’a pas d’entropie. Une source en a une, et votre estimation est un énoncé sur le modèle que vous avez apporté.

Ce que cela prépare

Tout ce qui précède suppose que vous connaissez $p$. Ce n’est jamais le cas. La leçon suivante demande ce qu’il advient lorsqu’on code une source avec le meilleur code d’une distribution erronée, et la réponse se révèle être la fonction de perte que chaque classifieur que vous avez entraîné minimisait déjà.