Théorie de l'information et entropie

La théorie de l'information fournit un langage pour décrire l'incertitude et les limites de la communication. Développez cette branche dans l'ordre suivant :

1. auto-information et entropie ;
2. entropie conjointe et conditionnelle ;
3. information mutuelle et indépendance ;
4. entropie croisée et divergence de Kullback–Leibler ;
5. codage de source et limites de compression ;
6. canaux bruités et capacité du canal ;
7. liens avec la modélisation probabiliste et les objectifs d'apprentissage automatique.

Cette référence se limite aux distributions discrètes finies, au codage et à la prédiction. Commencez par les probabilités, probabilités conditionnelles et espérances. MIT OpenCourseWare 6.050J développe les sujets de communication et de physique du parcours ci-dessus.

Surprise et incertitude moyenne

Un résultat de probabilité $p>0$ porte une auto-information de $-\log_2 p$ bits. Les probabilités de résultats indépendants se multiplient, donc leurs informations s'additionnent. Un résultat certain porte zéro bit ; un résultat de probabilité $1/8$ porte 3 bits. Cela mesure la surprise sous un modèle, pas la vérité, l'utilité ou le sens.

Pour une variable aléatoire $X$ de probabilités $p(x)$, l'entropie est l'espérance de l'auto-information :

$$H(X)=-\sum_x p(x)\log_2 p(x),\qquad 0\log_2 0:=0.$$

Pour $k$ résultats possibles, $0\le H(X)\le\log_2 k$, avec un maximum pour la distribution uniforme. Une pièce équilibrée a une entropie de 1 bit ; une pièce de probabilités $(3/4,1/4)$ a une entropie d'environ $0.811$ bit. Le résultat rare porte 2 bits, mais l'entropie moyenne les deux résultats.

Conditionnement et information partagée

L'entropie conjointe mesure l'incertitude sur le couple $(X,Y)$. L'entropie conditionnelle moyenne l'incertitude restant sur $Y$ après observation de $X$ :

$$H(X,Y)=H(X)+H(Y\mid X),\qquad I(X;Y)=H(Y)-H(Y\mid X).$$

L'information mutuelle $I(X;Y)$ est non négative et nulle exactement lorsque $X$ et $Y$ sont indépendantes. Le conditionnement ne peut augmenter l'entropie en moyenne, mais une observation particulière peut accroître l'incertitude. Si $Y=X$ pour une pièce équilibrée, $H(Y\mid X)=0$ et $I(X;Y)=1$ bit. Pour deux pièces équilibrées indépendantes, $H(X,Y)=2$ et $I(X;Y)=0$. Une dépendance ne prouve pas une causalité.

Entropie croisée et erreur de modèle

Soient $p$ la distribution réelle et $q$ la distribution prédictive sur les mêmes résultats. Avec des logarithmes en base 2,

$$H(p,q)=-\sum_x p(x)\log_2 q(x) =H(p)+D_{\mathrm{KL}}(p\|q),$$ $$D_{\mathrm{KL}}(p\|q)=\sum_{x:p(x)>0}p(x)\log_2\frac{p(x)}{q(x)}.$$

Les termes avec $p(x)=0$ contribuent zéro et sont omis. Si $q(x)=0$ là où $p(x)>0$, ces quantités sont infinies. Sinon, la divergence KL est non négative et ne s'annule que si les distributions coïncident. Ce n'est pas une distance métrique : elle est généralement asymétrique et ne vérifie pas l'inégalité triangulaire.

Pour $p=(3/4,1/4)$ et $q=(1/2,1/2)$, l'entropie croisée vaut 1 bit et la divergence KL environ $0.189$ bit. Minimiser l'entropie croisée sur $q$ minimise KL puisque $H(p)$ est fixe. En classification, la moyenne de $-\log q(y_i\mid x_i)$ sur les étiquettes observées estime une perte logarithmique attendue ; les logarithmes naturels donnent des nats plutôt que des bits. Une faible perte d'entraînement ne suffit pas à établir la performance sur de nouvelles données.

Ce que l'entropie dit de la compression

Pour une distribution de source finie connue, le code préfixe binaire optimal a une longueur moyenne $L$ telle que $H(X)\le L<H(X)+1$. L'entropie est une borne moyenne, pas une promesse de longueur fractionnaire pour chaque symbole. La pièce biaisée exige encore un bit par symbole avec un code préfixe binaire symbole par symbole. Pour des symboles indépendants et identiquement distribués, coder des blocs de longueur $n$ ramène le surcoût possible par symbole sous $1/n$ bit. Les sources corrélées demandent une structure conditionnelle ou un taux d'entropie ; leur entropie par symbole isolé n'est pas forcément la meilleure limite.

Les variables continues demandent un traitement distinct : l'entropie différentielle dépend des coordonnées et peut être négative. Elle ne donne donc pas directement le nombre de bits pour stocker une valeur réelle. Il faut d'abord préciser la résolution souhaitée.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.