La borne qui est vraiment atteinte

La plupart des bornes de l’apprentissage automatique 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.

La théorie de l’information fait exception, et c’est ce qui lui vaut quelques heures d’attention. Trois de ses quantités centrales sont des bornes atteintes, et chacune se révèle être une chose que vous utilisez déjà sans lui donner ce nom.

Un : la longueur minimale d’un code

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

$$H = \sum_x p(x)\log_2\frac{1}{p(x)} = 1{,}75 \text{ bits}$$

Construisez maintenant le meilleur code préfixe en fusionnant à plusieurs reprises les deux symboles les moins probables. Les longueurs sortent à 1, 2, 3 et 3 bits, soit une moyenne de 1,7500 bit : l’entropie, à toutes les décimales. Un code de longueur fixe demanderait 2 bits, d’où une économie de 12,5 %.

L’égalité est exacte parce que chaque longueur idéale $\log_2(1/p)$ se trouve être ici un entier. Passez à la source $(0{,}6,\ 0{,}25,\ 0{,}1,\ 0{,}05)$ et elle cesse de l’être : entropie 1,4905, meilleur code 1,5500. La longueur idéale d’un symbole de probabilité 0,6 est 0,737 bit, et aucun mot de code ne dure 0,737 bit.

La parade consiste à coder plusieurs symboles à la fois, pour partager l’erreur d’arrondi :

On s’en approche par le haut, sans jamais la franchir. Notez ce qui ne se produit pas : les symboles sont indépendants, il n’y a donc aucune redondance entre eux à exploiter et l’entropie par symbole ne change jamais. Seule la granularité s’améliore.

La lecture pratique est celle qu’il faut garder. Si un compresseur bat l’entropie que vous avez calculée, le théorème n’est pas en difficulté : votre distribution était fausse. L’entropie est un énoncé sur un modèle, ce qui en fait un outil de modélisation plutôt qu’une propriété d’un fichier.

Deux : ce que coûte la mauvaise distribution

Vous ne connaissez jamais $p$. Codez donc cette même source avec le code optimal d’une autre distribution $q$, disons l’uniforme, et mesurez la facture :

$$\underbrace{2{,}0000}_{H(p,q)} = \underbrace{1{,}4905}_{H(p)} + \underbrace{0{,}5095}_{\mathrm{KL}(p\|q)}$$

Exactement deux bits par symbole, se scindant exactement en l’entropie de la source plus un supplément. Ce supplément est la divergence de Kullback-Leibler.

Regardez de quoi dépend chaque terme. $H(p)$ est une propriété du monde : aucun modèle ne la change, et c’est le jumeau informationnel de l’erreur irréductible de la décomposition biais-variance. $\mathrm{KL}(p\|q)$ est entièrement votre modèle.

Minimiser l’entropie croisée sur des modèles revient donc à minimiser exactement la divergence à la vérité. Deux choses en découlent aussitôt : la perte ne peut jamais atteindre zéro sur une source bruitée, donc une perte d’entraînement qui tend vers zéro signale une mémorisation plutôt qu’un apprentissage ; et minimiser l’entropie croisée, c’est faire du maximum de vraisemblance dans d’autres unités.

Ce n’est pas une distance

Prenez une source qui émet un symbole 98 % du temps.

Les deux mêmes distributions, et une direction coûte un peu plus du double de l’autre.

$\mathrm{KL}(p\|q)$ est dominée par les issues que $p$ produit et que $q$ juge improbables : la minimiser étale le modèle pour couvrir ce qui arrive. $\mathrm{KL}(q\|p)$ punit l’inverse, donc la minimiser fait s’engager le modèle sur une région. Le choix est une décision de modélisation, et c’est pourquoi les approches variationnelles qui prennent la seconde direction cherchent les modes.

Et elle n’est pas bornée

La perte sur un exemple vaut $\log_2(1/q(\text{vérité}))$ :

Un modèle juste 95 % du temps mais certain sur les 5 % qu’il rate est bien plus mal noté qu’un modèle aussi souvent juste qui nuance. La justesse ne voit pas cette différence ; l’entropie croisée en est faite. Cela explique aussi une courbe de perte qui fait un pic sans que la justesse bouge : quelques exemples confidemment faux dominent le gradient.

Trois : ce qu’une variable dit d’une autre

La même machinerie, appliquée à une paire, répond du même chiffre à une question d’ingénierie et à une question de modélisation.

Pour un canal qui inverse chaque bit avec probabilité $f$, la capacité vaut $1 - H(f)$ :

À $f = 0{,}1$ le canal a raison neuf fois sur dix et transporte à peine plus d’un demi-bit : justesse et information ne sont pas la même monnaie. À $f = 0{,}5$ il ne transporte rien du tout, car la distribution de sortie est alors identique quoi que l’on envoie. À $f = 0{,}9$ il revient à 0,5310 : un menteur constant vaut un témoin fiable.

La dépendance que la corrélation annonce nulle

Engendrez deux bits indépendants et prenez leur ou exclusif comme cible. Sur 200 000 tirages :

Toutes les lectures sont justes. Aucune entrée seule ne dit quoi que ce soit, et l’information mutuelle, qui attraperait une dépendance de n’importe quelle forme et non seulement linéaire, le confirme. La paire détermine exactement la cible.

Donc tout filtrage de variables qui les classe une à une écarte les deux, sur un rapport parfaitement propre. Le cas n’a rien d’exotique : un médicament qui n’agit qu’en présence d’un gène, une panne qui ne survient que lorsque deux réglages divergent. La parade est de noter des sous-ensembles, ou de laisser un modèle qui représente les interactions les voir ensemble.

Une précaution : l’information mutuelle est plus difficile à estimer qu’une corrélation. Sur des variables continues elle dépend d’un découpage, et elle est biaisée vers le haut sur de petits échantillons, si bien qu’une valeur élevée sur peu de points peut n’être que l’estimateur qui parle.

Le plafond que rien ne relève

Mesurez le canal à 10 % et vous obtenez 0,5329 bit sur ce qui a été émis, ce qui rejoint la valeur théorique 0,5310. Effacez trois bits reçus sur dix en les mettant à 0 et mesurez de nouveau : 0,2763 bit.

C’est descendu, et aucun traitement ne peut le faire remonter. Pour toute chaîne $X \to Y \to Z$,

$$I(X;Z) \le I(X;Y)$$

car $Z$ est calculé à partir de $Y$ et ne voit de $X$ que ce que $Y$ a transmis. Les conséquences sont franches :

• les codes fonctionnent en ajoutant de la redondance avant la transmission ; aucun décodeur ne récupère ce que le canal a détruit
• aucun modèle, si profond soit-il, n’extrait sur l’étiquette plus que ses variables n’en portent : les couches sont des fonctions de couches et le plafond est fixé à l’entrée
• toute étape de prétraitement, de la quantification à la suppression d’une colonne, ne peut que perdre de l’information, ce qui peut être le bon compromis mais devrait être une décision et non une habitude de ménage

Le texte ci-dessus efface des bits ; la figure emploie plutôt un second canal à 10 % placé en série. Avec les deux probabilités d’inversion à 0,10, sa case Après traitement affiche 0,3199 bit plutôt que le 0,2763 ci-dessus, et les deux restent sous ce que le canal transportait. L’inégalité tient pour chaque choix ; le nombre dépend de celui que vous faites.

Pourquoi cela revient sans cesse

La compression, les communications et les fonctions de perte de l’apprentissage automatique sont les trois mêmes quantités habillées différemment. L’entropie est le plancher. L’entropie croisée est ce que vous payez quand votre distribution est fausse, et son excédent sur le plancher est ce que votre optimiseur réduisait depuis le début. L’information mutuelle est ce qu’une variable dit d’une autre, et elle borne tout ce qui suit.

Aucune des trois n’est une heuristique, ce qui est assez rare dans ce domaine pour valoir l’après-midi nécessaire à les apprendre correctement.