L’entropie et l’information

« À quel point suis-je incertain ? » sonne comme une question de ressenti. Ce n’en est pas une. Elle a une réponse numérique précise, mesurée en bits, et cette réponse se révèle être la quantité qui décide comment un arbre de décision se divise et contre quelle perte un classifieur est entraîné. Les deux découlent d’une seule définition.

A. Mesurer la surprise en bits

Commençons par l’intuition. Une pièce dont on sait qu’elle tombe toujours sur face ne porte aucune incertitude : l’observer ne vous apprend rien que vous ne sachiez déjà. Une pièce équilibrée est maximalement incertaine entre deux options. Une pièce qui tombe sur face 99 % du temps est bien plus proche du premier cas que du second - pariez face et vous n’avez tort que 1 % du temps.

Nous voulons une mesure valant $0$ pour la pièce certaine, maximale pour la pièce équilibrée, et petite pour la pièce à 99 %. D’après Russell et Norvig, l’entropie d’une variable aléatoire $V$ prenant les valeurs $v_k$ avec les probabilités $P(v_k)$ est

$$H(V) = \sum_{k} P(v_k) \log_2 \frac{1}{P(v_k)} = -\sum_{k} P(v_k) \log_2 P(v_k) .$$

La première forme est la plus parlante. La quantité $\log_2 \frac{1}{P(v_k)}$ est la surprise de l’issue $k$ : grande quand l’issue était improbable, nulle quand elle était certaine. L’entropie est simplement la surprise espérée - chaque surprise pondérée par sa fréquence réelle.

Pourquoi la base 2. L’unité est le bit, et la base 2 le rend littéral : l’entropie est le nombre moyen de questions oui/non nécessaires pour cerner l’issue. Un lancer de pièce équilibrée demande une question, il doit donc mesurer exactement $1$ bit. C’est le cas :

$$H(\text{Fair}) = -\big(0.5 \log_2 0.5 + 0.5 \log_2 0.5\big) = 1 .$$

Un dé équilibré à quatre faces a quatre issues également probables, ce qui demande deux questions : $H = 2$ bits. Et la pièce truquée se comporte comme l’intuition l’exigeait :

$$H(\text{Loaded}) = -\big(0.99 \log_2 0.99 + 0.01 \log_2 0.01\big) \approx 0.08 \text{ bits}.$$

Pour une variable booléenne il est commode d’écrire $B(q)$ pour l’entropie de quelque chose de vrai avec probabilité $q$ :

$$B(q) = -\big(q \log_2 q + (1-q) \log_2 (1-q)\big).$$

Symétrique autour de $q = 0.5$, maximale là, et nulle à la certitude - exactement la forme demandée. (Par convention $0 \log 0 = 0$, ce qui est aussi sa limite.)

B. Le gain d’information : ce qu’une question vous apprend

L’entropie devient utile dès que vous demandez ce qu’un test vous rapporte. Supposons qu’un ensemble d’entraînement compte $p$ exemples positifs et $n$ négatifs. Son entropie vaut $B\!\left(\frac{p}{p+n}\right)$.

Testons maintenant un attribut $A$ à $d$ valeurs, divisant l’ensemble en sous-ensembles $E_1, \dots, E_d$, où $E_k$ contient $p_k$ positifs et $n_k$ négatifs. Descendre la branche $k$ laisse $B\!\left(\frac{p_k}{p_k+n_k}\right)$ bits encore à résoudre, et un exemple aléatoire emprunte cette branche avec probabilité $\frac{p_k+n_k}{p+n}$. L’entropie espérée restant après le test est donc

$$\text{Remainder}(A) = \sum_{k=1}^{d} \frac{p_k + n_k}{p + n}\, B\!\left(\frac{p_k}{p_k + n_k}\right),$$

et le gain d’information est la réduction espérée d’entropie :

$$\text{Gain}(A) = B\!\left(\frac{p}{p+n}\right) - \text{Remainder}(A).$$

Exemple résolu. Douze exemples, six positifs et six négatifs : l’entropie de départ vaut donc exactement $B(0.5) = 1$ bit. Un attribut les divise en une branche de 5 (4 positifs, 1 négatif) et une branche de 7 (2 positifs, 5 négatifs).

Entropies des branches : $B(4/5) = B(0.8) = 0.7219$ et $B(2/7) = B(0.2857) = 0.8631$.

Poids : $5/12 = 0.4167$ et $7/12 = 0.5833$.

$$\text{Remainder} = 0.4167 \times 0.7219 + 0.5833 \times 0.8631 = 0.8043 ,$$ $$\text{Gain} = 1.0000 - 0.8043 = 0.1957 \text{ bits}.$$

Cet attribut résout donc environ un cinquième de bit sur le bit d’incertitude de départ - une amélioration réelle mais modeste.

Un gain proche de zéro signale un attribut hors sujet. Si un test divise les données en sous-ensembles dont les proportions de classes ressemblent toutes à celles du parent, il ne vous a rien appris, et l’arithmétique ci-dessus renvoie approximativement zéro. Cela fait du gain d’information un signal exploitable pour l’élagage autant que pour la division.

La figure ci-dessous applique le même calcul à une autre partition : les données du restaurant de Russell & Norvig, elles aussi douze exemples dont six positifs et six négatifs, et deux de leurs attributs. Patrons rapporte $0.5409$ bit ; Type rapporte exactement $0$, l'attribut non pertinent de la remarque ci-dessus. Chaque branche est dessinée en barre et chaque nombre recalculé plutôt que cité. La troisième commande déplace des exemples dans la seule branche de Patrons encore mixte, le seul endroit où le gain peut changer sans changer la question, et elle montre ce qu'une seule partition calculée à la main ne peut pas montrer : l'entropie attendue restante est maximale quand cette branche est équilibrée, tandis que le gain n'y est pas simplement minimal, car déplacer un exemple change aussi l'entropie de départ.

C. Un piège de terminologie qu’il faut nommer

Les arbres de décision et les ensembles introduit le critère de division

$$D = -\sum_{k=1}^{K} \hat p_{mk} \log \hat p_{mk}$$

et l’appelle entropie croisée, suivant la convention de l’apprentissage statistique. Lue à l’aune de cet article, c’est la formule de l’entropie - une distribution unique évaluée contre elle-même.

La théorie de l’information réserve entropie croisée à une quantité impliquant deux distributions. Les deux appellations sont standard dans leur propre littérature, et aucune n’est fausse, mais ce ne sont pas le même objet et la collision cause une confusion bien réelle. Quand vous rencontrez « entropie croisée » comme critère de division d’arbre, lisez-la comme l’entropie du nœud ; la section suivante parle de l’autre chose.

D. L’entropie croisée et la divergence de Kullback-Leibler

Supposons que la vérité soit $p$ mais que vous agissiez selon une croyance $q$. L’entropie croisée mesure la surprise moyenne que vous encourez réellement :

$$H(p, q) = -\sum_{i} p(x_i) \log_2 q(x_i) .$$

Les poids sont les vraies probabilités $p$ ; les surprises sont calculées à partir de votre croyance $q$. Si $q = p$, cela se réduit à $H(p)$. Sinon, c’est strictement plus grand - vous êtes systématiquement plus surpris que nécessaire.

L’excédent porte un nom. La divergence KL entre $P$ et $Q$ est

$$\text{KL}(P, Q) = \sum_{i} P(x_i) \log_2 \frac{P(x_i)}{Q(x_i)} ,$$

et les trois quantités sont reliées par

$$H(p, q) = H(p) + \text{KL}(p \,\|\, q).$$

Autrement dit : votre surprise totale est l’incertitude irréductible du monde, plus une pénalité pour vous être trompé à son sujet. Puisque $H(p)$ est fixé par la réalité, minimiser l’entropie croisée sur votre modèle revient exactement à minimiser la divergence KL par rapport à la vérité.

Vérifions numériquement. Que la vérité soit une pièce équilibrée, $p = (0.5, 0.5)$, tandis que vous croyez $q = (0.9, 0.1)$ :

$$H(p) = 1.0000, \qquad H(p, q) = 1.7370, \qquad \text{KL}(p \,\|\, q) = 0.7370 .$$

Et $1.0000 + 0.7370 = 1.7370$, comme annoncé.

La KL n’est pas une distance. Elle n’est pas symétrique - > $\text{KL}(P, Q) \neq \text{KL}(Q, P)$ en général - et elle ne vérifie pas l’inégalité triangulaire. L’appeler « divergence » plutôt que distance est délibéré. Notez aussi qu’elle explose si $q(x) = 0$ là où $p(x) > 0$ : attribuer une probabilité nulle à quelque chose qui se produit ensuite est infiniment surprenant.

Ci-dessous, la source est fixe et le modèle vous appartient. Observez lequel des deux affichages refuse de bouger : l’entropie est une propriété de la source, et aucun réglage des curseurs n’y touche. Tout ce qui dépasse ce plancher est la divergence, et c’est la seule chose que l’entraînement puisse réduire. Le second panneau détaille le coût symbole par symbole, et c’est là que l’arithmétique cesse d’être une moyenne pour devenir un diagnostic : les bits sont rarement gaspillés là où l’on croit.

E. Pourquoi les classifieurs sont entraînés sur l’entropie croisée

C’est ici que la théorie gagne sa place. Un classifieur produit une distribution de probabilité sur les étiquettes ; la vérité terrain est aussi une distribution - généralement toute la masse sur une étiquette. Entraîner le modèle, c’est faire coïncider sa distribution avec la vraie, et l’entropie croisée est précisément la quantité qui mesure l’écart. Chollet le dit directement : l’entropie croisée est une quantité issue de la théorie de l’information qui mesure la distance entre distributions de probabilité, ici entre la distribution de vérité terrain et les prédictions du modèle, et c’est en général le bon choix quand un modèle produit des probabilités.

Avec une vérité one-hot sur la classe $c$, tous les termes sauf un s’annulent et la perte pour cet exemple n’est que

$$-\log q(c),$$

la surprise attribuée à la bonne réponse. Être confiant et juste ne coûte presque rien ; être confiant et faux coûte très cher. Cette asymétrie - fournie par le logarithme, non ajoutée après coup - est ce qui fait de l’entropie croisée un meilleur signal d’entraînement que l’exactitude, laquelle est plate presque partout et ne donne rien à descendre à la descente de gradient.

C’est le même raisonnement qui motive l’objectif de log-perte dans La régression logistique et la classification : la perte n’est pas une fonction commode arbitraire, c’est la surprise espérée des croyances du modèle sous la vraie distribution.

La même entropie mesure aussi ce qu'un canal bruité peut transporter, et c'est là que la figure ci-dessous va un pas plus loin que cet article. C'est un canal binaire qui inverse chaque bit avec la probabilité $f$, et sa capacité vaut $1 - B(f)$ bit par usage. Mettez la probabilité d'inversion à 0,1 et lisez 0,5310 ; à 0,5 et lisez exactement zéro ; au-delà, et regardez la capacité remonter, car un canal qui ment toujours peut être inversé. Le second panneau est un exemple distinct : deux bits équilibrés et une cible qui est leur ou exclusif, où chaque entrée seule porte exactement 0 bit sur la cible et la paire en porte 1. Quant au curseur de traitement, il envoie la sortie dans un second canal en série : son inversion composée vaut $f(1-g) + g(1-f)$, jamais plus proche de la certitude que $f$, si bien que l'information ne peut jamais remonter.

À retenir

• L’entropie $H(V) = -\sum_k P(v_k)\log_2 P(v_k)$ est la surprise espérée, mesurée en bits ; la base 2 en fait le nombre moyen de questions oui/non.
• Une pièce équilibrée vaut exactement $1$ bit, un dé équilibré à quatre faces $2$ bits, une pièce à 99 % environ $0.08$ bit, et une issue certaine $0$.
• Le gain d’information est la réduction d’entropie espérée d’un test ; notre division a fait passer $1$ bit à $0.8043$, soit un gain de 0,1957 bit.
• L’apprentissage statistique appelle le critère d’arbre $-\sum \hat p \log \hat p$ « entropie croisée » ; la théorie de l’information appelle cela l’entropie. Même formule, noms différents, confusion réelle.
• L’entropie croisée $H(p,q) = -\sum p \log q$ évalue une croyance $q$ contre une vérité $p$, et se décompose en $H(p) + \text{KL}(p \| q)$ - incertitude irréductible plus pénalité d’erreur.
• La divergence KL est asymétrique et non bornée ; ce n’est pas une distance.
• Minimiser l’entropie croisée revient à minimiser la KL par rapport à la vérité, d’où son statut de perte standard en classification.

La suite

L’entropie quantifie l’incertitude à l’intérieur d’un modèle probabiliste. Une autre tradition représente la connaissance par des énoncés simplement vrais ou faux et raisonne sur ce qui doit en découler - La logique et la représentation des connaissances.