Quantité d'information, entropie de Shannon, entropie conjointe et conditionnelle, information mutuelle et redondance d'une source.
Objectifs du chapitre
À la fin de ce chapitre, vous serez capable de:
expliquer pourquoi la quantité d'information d'un événement ne dépend que de sa probabilité, et justifier la forme −log2p par l'additivité sur des événements indépendants;
calculer l'entropie de Shannon H(X) d'une source discrète en bits par symbole, y compris lorsque certaines probabilités sont nulles;
démontrer les bornes 0≤H(X)≤log2n et caractériser les deux cas d'égalité;
reconnaître la fonction d'entropie binaire, son maximum en 1/2 et sa pente infinie au voisinage de 0 et de 1;
calculer une entropie conjointe, une entropie conditionnelle et une information mutuelle sur une table de probabilités complète, et vérifier numériquement la règle de chaînage;
mesurer la redondance d'une source et dire à quoi elle sert: le chapitre 7 la supprimera pour comprimer, le chapitre 8 la rajoutera pour corriger.
La question que Shannon a posée
Les cinq premiers chapitres ont demandé combien d'opérations coûte un calcul et ce qu'une machine peut calculer. Les cinq suivants posent la troisième question du cours: combien de bits? Combien faut-il de bits pour stocker un texte, transmettre une photographie, décrire l'état d'un capteur? Et surtout: existe-t-il une limite en dessous de laquelle aucun procédé, si ingénieux soit-il, ne pourra descendre?
Avant 1948, cette question n'avait pas de réponse parce qu'elle n'avait pas de formulation. On savait compter les caractères d'un télégramme et les impulsions d'une ligne, mais on ne savait pas dire ce qu'était la quantité d'information d'un message, et encore moins la comparer d'un message à l'autre. En 1948, dans A Mathematical Theory of Communication, Claude Shannon propose une définition, en tire un théorème sur le codage de source (notre chapitre 7) et un théorème sur le codage de canal (notre chapitre 8), et fonde d'un seul geste une discipline entière.
Le point de départ est un renversement. Notre intuition associe l'information au sens: «la Terre tourne autour du Soleil» nous paraît porter plus d'information que «ojrvkq zlmpt». Shannon écarte délibérément cette intuition. Pour lui, une source d'information est un mécanisme aléatoire qui produit des symboles, et l'information d'un message se mesure à ce que ce message lève d'incertitude sur ce que la source allait produire. Une phrase n'est pas informative parce qu'elle est vraie, belle ou utile: elle est informative parce qu'elle était improbable.
Pourquoi la probabilité et non le sens
Trois arguments justifient ce choix, et il vaut la peine de les distinguer.
Le premier est opératoire. L'ingénieur qui conçoit une ligne, un disque ou un format de fichier ne connaît pas le sens des messages qu'il transportera; il ne connaît que leurs statistiques. Un standard de compression d'images ne sait rien des visages ni des paysages, mais il sait qu'un pixel ressemble à son voisin. Une théorie utilisable doit donc se contenter de ce que l'ingénieur possède: des probabilités.
Le deuxième est mathématique. Le sens n'a pas, à ce jour, de mesure quantitative sur laquelle on puisse démontrer des théorèmes. La probabilité, si. Shannon ne prétend pas que le sens n'existe pas; il constate que son problème — transmettre exactement une suite de symboles — ne le requiert pas. Sa phrase, en 1948, est explicite: les aspects sémantiques de la communication sont sans rapport avec le problème d'ingénierie.
Le troisième est empirique, et c'est le plus fort: la théorie fonctionne. Les bornes qu'elle établit sont atteintes en pratique, à quelques pourcents près, par les algorithmes du chapitre 7; les codes correcteurs du chapitre 8 s'approchent de la capacité qu'elle prédit. Une théorie qui ignore le sens et qui prédit correctement la taille des fichiers a gagné le droit d'ignorer le sens.
La quantité d'information d'un événement
Trois exigences
Commençons par un événement unique. Un capteur vient de signaler quelque chose; l'événement observé avait la probabilité p. Quelle quantité d'information I(p) lui attribuer? Plutôt que de deviner une formule, imposons trois exigences raisonnables et regardons ce qu'elles laissent subsister.
I ne dépend que de p. Deux événements de même probabilité apportent la même information, quel que soit leur contenu. C'est exactement le renoncement au sens décrit plus haut.
I est décroissante et continue. Un événement plus improbable est plus informatif; un événement certain (p=1) n'apprend rien, donc I(1)=0. Une petite variation de probabilité ne doit pas produire un saut d'information.
I est additive sur des événements indépendants. Si A et B sont indépendants, apprendre «A et B» doit coûter autant qu'apprendre A puis apprendre B. Comme P(A∩B)=P(A)P(B)=pq, cela s'écrit
I(pq)=I(p)+I(q)pour tous p,q∈]0,1].(6.1)
L'exigence 3 est la plus contraignante, et c'est elle qui fait apparaître le logarithme. Elle est aussi la plus naturelle: si vous recevez le résultat de deux lancers de pièce indépendants, vous voulez que l'information reçue soit le double de celle d'un lancer.
Démonstration. Posons f(x)=I(e−x) pour x≥0. La fonction f est continue, croissante (car x↦e−x décroît et I décroît), et f(0)=I(1)=0. La relation (6.1) devient, avec p=e−x et q=e−y,
f(x+y)=f(x)+f(y)pour tous x,y≥0.
C'est l'équation fonctionnelle de Cauchy. Par récurrence, f(nx)=nf(x) pour tout entier n≥1; en appliquant cela à x=m/n on obtient nf(m/n)=f(m)=mf(1), donc f(r)=rf(1) pour tout rationnel positif r. Les rationnels sont denses dans R+ et f est continue, donc f(x)=Cx pour tout x≥0, avec C=f(1)≥0. En revenant à I: I(p)=f(−lnp)=−Clnp. La constante est strictement positive, sinon I serait identiquement nulle et l'exigence de décroissance stricte tomberait. □
La démonstration montre bien d'où vient le logarithme: il est la seule façon continue de transformer un produit de probabilités en une somme d'informations. Ce n'est pas un choix de commodité, c'est une conséquence.
Le choix de la base 2
Reste à fixer C, c'est-à-dire l'unité. La convention de Shannon est de donner un à l'événement le plus simple qui ne soit pas certain: le résultat d'un tirage équiprobable entre deux possibilités. On impose donc I(1/2)=1, ce qui donne C=1 en base 2 et
I(p)=−log2p=log2p1bits.(6.2)
Le mot «bit» porte ici deux sens qu'il faut tenir séparés, et le cours les distinguera systématiquement: le bit physique, qui est une case mémoire valant 0 ou 1, et le bit d'information, qui est une unité de mesure comme le mètre ou le joule et qui peut parfaitement valoir 2,0404. Un symbole d'ABRACADABRA occupe 3 bits physiques dans un codage à longueur fixe mais ne porte que 2,0404 bits d'information: tout le chapitre 7 vit dans cet écart.
D'autres bases sont en usage: la base e donne le nat (1 nat =1/ln2≈1,4427 bits), commode en analyse parce que la dérivée de ln est simple; la base 10 donne le dit ou hartley. Dans tout ce cours, la base est 2 et elle est écrite explicitement: log2.
Question 6.1
Un tirage donne un événement de probabilité 1/8. Quelle est sa quantité d'information?
L'entropie de Shannon
Une source ne produit pas un événement isolé: elle produit des symboles, encore et encore. Ce qui intéresse l'ingénieur est le coût moyen par symbole, donc l'espérance de la quantité d'information.
Trois remarques sur cette définition, chacune importante.
L'unité.H s'exprime en bits par symbole. Multipliée par le nombre de symboles d'un message, elle donne un nombre de bits. Si la source émet à 1000 symboles par seconde, 1000H est un débit en bits par seconde. Ne confondez jamais l'entropie d'une source (par symbole) avec l'information totale d'un message (le produit des deux).
La convention 0log20=0. Elle n'est pas arbitraire: c'est la seule valeur qui rende la fonction x↦xlog2x continue en 0. En effet, en posant x=2−t,
x→0+limxlog2x=t→+∞lim−t2−t=0,
car l'exponentielle l'emporte sur toute puissance. La lecture est limpide: un symbole qui n'arrive jamais a une surprise infinie, mais il contribue à l'entropie avec un poids nul, et le produit 0×∞ se tranche par la limite, qui vaut zéro. Conséquence pratique: ajouter à un alphabet des symboles de probabilité nulle ne change pas l'entropie. C'est indispensable pour comparer deux sources sur des alphabets de tailles différentes.
Le signe. Chaque pi est dans [0,1], donc log2pi≤0, donc chaque terme −pilog2pi est positif ou nul: H≥0 toujours. L'entropie est une moyenne de surprises, et les surprises sont positives.
Question 6.2
Une source émet quatre symboles avec les probabilités 0,4, 0,3, 0,2 et 0,1. Quelle est son entropie, en bits par symbole?
Les propriétés fondamentales de l'entropie
Toutes les propriétés qui suivent découlent d'une seule inégalité, qu'il vaut donc la peine d'isoler.
Démonstration. L'ingrédient est l'inégalité élémentaire lnt≤t−1 pour tout t>0, avec égalité si et seulement si t=1: la fonction g(t)=t−1−lnt vérifie g′(t)=1−1/t, donc g décroît sur ]0,1], croît sur [1,+∞[ et atteint son minimum g(1)=0.
Notons S={i:pi>0} le support de p. La différence des deux membres de (6.4) s'écrit
puisque ∑i∈Sqi≤∑iqi=1. L'égalité exige simultanément qi/pi=1 pour tout i∈S et ∑i∈Sqi=1, c'est-à-dire p=q. □
La quantité ∑ipilog2(pi/qi), positive d'après (6.4), s'appelle la divergence de Kullback-LeiblerD(p∥q); elle mesure ce que l'on perd à coder une source de loi p avec un code optimisé pour la loi q. Le chapitre 7 en donnera l'interprétation exacte en bits gaspillés. Retenez qu'elle n'est pas symétrique en p et q, et n'est donc pas une distance.
Démonstration.Borne inférieure. Chaque terme −pilog2pi est positif ou nul, donc H≥0. Une somme de termes positifs est nulle si et seulement si tous les termes le sont; or −plog2p=0 n'a lieu que pour p=0 ou p=1. Toutes les probabilités sont donc dans {0,1}, et comme elles somment à 1, exactement une vaut 1: la source est déterministe. Réciproquement, une source déterministe a bien H=0 par la convention 0log20=0.
Borne supérieure. Appliquons l'inégalité de Gibbs (6.4) avec la distribution uniforme qi=1/n:
H(X)≤−i=1∑npilog2n1=log2ni=1∑npi=log2n.
Le cas d'égalité de (6.4) donne immédiatement pi=1/n pour tout i. □
La lecture de (6.5) est celle qu'il faut garder: l'incertitude est maximale quand rien ne permet de parier, et nulle quand tout est prévisible. Entre les deux, log2n borne ce que l'on peut espérer: une source sur cinq symboles ne dépassera jamais log25=2,3219 bits par symbole, quelles que soient ses probabilités.
Regrouper ou scinder des symboles
Que devient l'entropie quand on cesse de distinguer deux symboles, par exemple parce qu'un capteur ne sait plus les séparer? La réponse est exacte et très utile.
Démonstration. Seuls les deux premiers termes diffèrent. Écrivons p1=pα et p2=p(1−α) avec α=p1/p. Alors
En développant log2(pα)=log2p+log2α et de même pour l'autre terme, la partie en log2p se regroupe en −plog2p (puisque α+(1−α)=1) et la partie restante vaut p(−αlog2α−(1−α)log2(1−α))=pH(α,1−α). □
Deux conséquences immédiates. Fusionner deux symboles fait toujours baisser l'entropie (le terme ajouté est positif): perdre la capacité de distinguer, c'est perdre de l'information. Et scinder un symbole en deux fait toujours monter l'entropie, d'une quantité qui vaut au plus p bit (le maximum de l'entropie binaire est 1), atteinte quand la scission est équitable.
Question 6.3
Classez ces quatre sources de la plus petite à la plus grande entropie.
Glissez les éléments pour les mettre dans le bon ordre
1.
une source à quatre symboles de probabilités (0,97;0,01;0,01;0,01)
2.
un dé équilibré à six faces
3.
une source à deux symboles de probabilités (0,99;0,01)
4.
une source binaire équiprobable
Explorateur 6.1 · Explorateur d'entropie d'une source à quatre symboles
Les quatre curseurs fixent des poids relatifs; ils sont renormalisés pour que les probabilités somment toujours à 1. L'entropie H est recalculée à chaque mouvement, ainsi que la redondance 1 − H/log₂4. Rendez les quatre poids égaux: H atteint son maximum log₂ 4 = 2 bits/symbole et la redondance s'annule. Mettez au contraire tout le poids sur un seul symbole: H tombe à 0 et la redondance vaut 1.
Poids du symbole a4,0
Poids du symbole b3,0
Poids du symbole c2,0
Poids du symbole d1,0
Entropie H
1,8464bits/symbole
Maximum log₂ 4
2,0000bits/symbole
Redondance 1 − H/log₂ 4
0,0768
État
non équiprobable
Figure 6.1. Explorateur interactif: l'entropie d'une source à quatre symboles. Les poids des curseurs sont renormalisés pour que les probabilités somment toujours à 1; la jauge du bas compare H au maximum log₂ 4 = 2 bits/symbole.
Prenez le temps de manipuler l'explorateur de la figure 6.1, car il rend visibles les deux théorèmes qui précèdent. Amenez les quatre curseurs à la même valeur: la jauge se remplit exactement jusqu'à 2 et la redondance tombe à 0 — c'est le cas d'égalité du théorème 6.3. Poussez au contraire tout le poids sur un seul symbole: H tombe à 0 et la redondance vaut 1. Essayez enfin de faire monter H au-dessus de 2: c'est impossible, la borne tient. Une dernière expérience, plus subtile: partez de (4;3;2;1), notez H=1,8464, puis transférez du poids du symbole a vers le symbole d. L'entropie monte tant que la distribution s'égalise et redescend dès qu'on la déséquilibre dans l'autre sens.
L'entropie binaire
Le cas de deux symboles mérite un traitement séparé: il apparaît dans tous les problèmes de canal du chapitre 8, et sa courbe est l'une des plus utiles du cours.
Figure 6.2. La fonction d'entropie binaire, échantillonnée en 601 points à partir de sa formule. Le maximum vaut exactement 1 bit en p = 1/2; la courbe s'annule aux deux extrémités, avec une tangente verticale. Le point bleu marque la valeur H(0,1) = 0,4690 utilisée plus loin pour le canal bruité.
Quatre propriétés se lisent sur la figure 6.2 et se démontrent en deux lignes.
Symétrie.H(p)=H(1−p): la définition est symétrique en échangeant les deux symboles. Rien ne distingue «pile avec probabilité 0,9» de «face avec probabilité 0,1».
Maximum. Par le théorème 6.3 avec n=2, H(p)≤log22=1 avec égalité si et seulement si p=1/2. C'est le point le plus haut de la courbe.
Concavité. En dérivant (6.7),
H′(p)=log2p1−p,H′′(p)=−p(1−p)ln21<0sur ]0,1[,
donc H est strictement concave: la courbe est en cloche, sans plateau ni point d'inflexion. La dérivée s'annule en p=1/2, ce qui redonne le maximum.
Pente infinie aux bords.H′(p)→+∞ quand p→0+ et H′(p)→−∞ quand p→1−. La courbe quitte 0 à la verticale. La conséquence est contre-intuitive et importante: une source presque certaine porte plus d'information qu'on ne le croit. Un canal qui se trompe une fois sur cent a une entropie d'erreur H(0,01)=0,0808 bit par bit transmis — huit fois plus que la probabilité d'erreur elle-même. Quelques valeurs, toutes calculées:
p
0,001
0,01
0,05
0,10
0,11
0,25
0,50
H(p)
0,0114
0,0808
0,2864
0,4690
0,4999
0,8113
1,0000
Retenez le repère H(0,11)≈0,5: il faut déjà onze pour cent d'erreurs pour détruire la moitié d'un bit. Cette lenteur est ce qui rend possibles les codes correcteurs du chapitre 8.
Entropie conjointe, entropie conditionnelle, information mutuelle
Jusqu'ici une seule source. Mais toute la communication met en jeu deux variables: ce qui a été émis et ce qui a été reçu, l'état d'un système et la mesure qu'on en fait, le passé d'un texte et sa lettre suivante. Il faut donc mesurer ce que l'une dit de l'autre.
Attention à la dissymétrie de la notation: H(X∣Y) est bien un nombre unique, pas une fonction de y. C'est l'incertitude qui reste sur X une fois Y connu, en moyenne sur les valeurs possibles de Y. Et H(X∣Y)=H(Y∣X) en général: savoir la date de naissance de quelqu'un vous dit son âge, l'inverse est faux.
Démonstration. Partons de la définition de H(X,Y) et utilisons p(x,y)=p(x)p(y∣x), donc log2p(x,y)=log2p(x)+log2p(y∣x) (les termes où p(x,y)=0 ne contribuent pas, par la convention 0log20=0):
Dans la première somme, ∑yp(x,y)=p(x), donc elle vaut −∑xp(x)log2p(x)=H(X). La seconde est exactement H(Y∣X) par (6.8). La seconde égalité de (6.9) s'obtient en échangeant les rôles de X et de Y. □
La lecture est celle du bon sens: décrire le couple coûte le prix de X, plus ce qu'il reste à dire de Y une fois X connu. Et l'on peut commencer par l'un ou par l'autre, le total est le même.
Démonstration. En développant (6.10) avec les définitions,
C'est la divergence de la loi conjointe par rapport au produit des marginales: appliquons l'inégalité de Gibbs (6.4) sur l'alphabet des couples (x,y), avec pi=p(x,y) et qi=p(x)p(y) — ce dernier est bien une loi de probabilité, car ∑x,yp(x)p(y)=1. Le théorème 6.2 donne I(X;Y)≥0 et l'égalité si et seulement si p(x,y)=p(x)p(y) pour tout couple, c'est-à-dire l'indépendance. □
Une table conjointe entièrement travaillée
Le modèle qui servira de fil au chapitre 8: une station émet un bit X, le canal binaire symétrique le retourne avec la probabilité p=0,10 indépendamment de la valeur émise, et Y est le bit reçu. La source n'est pas équiprobable: P(X=0)=0,30 et P(X=1)=0,70 (c'est un capteur qui signale une anomalie trois fois sur dix). La loi conjointe s'obtient par p(x,y)=p(x)p(y∣x).
p(x,y)
Y=0
Y=1
marge p(x)
X=0
0,27
0,03
0,30
X=1
0,07
0,63
0,70
marge p(y)
0,34
0,66
1,00
Contrôle des marges.0,27+0,03=0,30 et 0,07+0,63=0,70: les lignes redonnent bien la loi de X. 0,27+0,07=0,34 et 0,03+0,63=0,66: les colonnes redonnent bien la loi de Y. Le total des quatre cases vaut 1,00. Ce contrôle n'est pas une formalité: une table conjointe dont les marges ne se recollent pas rend faux tout ce qui suit.
Figure 6.3. Diagramme de Venn des six entropies du canal de l'exemple 6.4. La lentille centrale est l'information mutuelle; les deux croissants sont les incertitudes résiduelles; l'union entière est l'entropie conjointe. Les aires du dessin sont approximativement, mais non exactement, proportionnelles aux valeurs.
Le diagramme de la figure 6.3 est un aide-mémoire remarquablement fidèle: chaque identité du chapitre s'y lit comme une addition d'aires.
H(X)=H(X∣Y)+I(X;Y), soit 0,4255+0,4558=0,8813: le disque de gauche est la somme de son croissant et de la lentille.
H(Y)=H(Y∣X)+I(X;Y), soit 0,4690+0,4558=0,9248.
H(X,Y)=H(X∣Y)+I(X;Y)+H(Y∣X), soit 0,4255+0,4558+0,4690=1,3503: l'union est la somme des trois régions disjointes.
H(X,Y)≤H(X)+H(Y) toujours, avec égalité si et seulement si les disques sont disjoints, c'est-à-dire si X et Y sont indépendantes.
Question 6.4
Dans la table conjointe de l'exemple 6.4, supposons que le récepteur observe Y=1. Quelle entropie conditionnelle H(X∣Y=1) reste-t-il sur le bit émis, en bits?
La redondance d'une source
Nous disposons maintenant des deux nombres qu'il faut comparer: ce qu'une source coûte au maximum, et ce qu'elle porte réellement.
Lorsqu'un codage à longueur fixe est déjà imposé, avec ℓ bits par symbole, on compare plutôt à ℓ: la redondance du codage est 1−H(X)/ℓ. Les deux notions se confondent quand n est une puissance de 2 et que le codage est optimal en longueur fixe; elles diffèrent sinon, et il faut dire laquelle on utilise. Nous le ferons chaque fois.
La redondance est le concept qui articule toute la seconde moitié du cours, et il vaut la peine de l'écrire en toutes lettres:
le chapitre 7 (compression) supprime la redondance. Un texte français a une redondance élevée: certaines lettres sont fréquentes, certaines suites sont impossibles. Coder chaque lettre sur le même nombre de bits gaspille cette structure. Huffman, le codage arithmétique et Lempel-Ziv la récupèrent, et le théorème du codage de source dira exactement jusqu'où: pas en dessous de H;
le chapitre 8 (codes correcteurs) réintroduit de la redondance, délibérément. Un code de Hamming (7,4) ajoute trois bits de parité à quatre bits utiles: sa redondance est de 3/7, et c'est elle qui permet de localiser une erreur. Rien n'est gratuit — le canal doit transporter 7 bits pour 4 bits utiles;
entre les deux, la même grandeur change de signe pédagogique: ce que la compression tient pour du gaspillage, la correction d'erreurs le paie volontairement. La chaîne complète d'une transmission moderne comprime d'abord puis recode ensuite, et ce n'est pas absurde: la redondance retirée était celle du langage, non maîtrisée; celle qui est ajoutée est construite pour que le décodeur sache exactement quoi en faire.
Question 6.5
Une source de quatre symboles a pour probabilités (1/2,1/4,1/8,1/8). Quelle est sa redondance relative?
La source du cours: ABRACADABRA
Le fil rouge des chapitres 6 et 7 est le message ABRACADABRA, onze symboles sur l'alphabet {A,B,C,D,R}. Comptons: A apparaît cinq fois (positions 1, 4, 6, 8, 11), B deux fois, R deux fois, C une fois, D une fois. Total 5+2+2+1+1=11: le compte est bon.
Nous adoptons le modèle d'ordre 0: la source est supposée émettre chaque symbole indépendamment des précédents, avec les probabilités égales aux fréquences observées. C'est une hypothèse, et la section suivante montrera à quel point elle est fausse pour ce message précis; elle est néanmoins le point de départ de tout codeur simple.
Symbole
Occurrences
p
−log2p (bits)
p×(−log2p)
A
5
5/11=0,4545
1,1375
0,5170
B
2
2/11=0,1818
2,4594
0,4472
R
2
2/11=0,1818
2,4594
0,4472
C
1
1/11=0,0909
3,4594
0,3145
D
1
1/11=0,0909
3,4594
0,3145
Total
11
1,0000
—
2,0404
La colonne des probabilités somme à 1 exactement (5+2+2+1+1=11 sur 11), et la dernière colonne donne l'entropie:
Figure 6.4. Les cinq symboles d'ABRACADABRA. La largeur de chaque barre est proportionnelle à sa fréquence, sa hauteur est son information moins log2 de p en bits, et son aire est donc sa contribution à l'entropie. La ligne horizontale en tirets est la hauteur moyenne pondérée par les largeurs: H = 2,0404 bits par symbole.
La figure 6.4 rend visible le compromis de l'entropie. Le A est large et bas: fréquent, donc peu surprenant, mais sa fréquence lui donne quand même la plus grosse aire (0,5170 bit de contribution). Les C et D sont étroits et hauts: chacun vaut 3,4594 bits de surprise, mais ils n'arrivent qu'une fois sur onze et ne contribuent que 0,3145 bit chacun. La ligne horizontale à 2,0404 est la hauteur moyenne pondérée: c'est exactement l'entropie, et l'aire totale sous les barres vaut H.
Ce que l'entropie n'est pas
Il vaut la peine de fermer explicitement quatre portes, parce que chacune a été franchie par erreur dans des textes sérieux.
L'entropie n'est pas une mesure de sens. «Le chat dort» et «Lej lhbu qsvy» peuvent avoir la même entropie d'ordre 0. La théorie mesure l'imprévisibilité de la source, pas l'intelligibilité du message. Un générateur de caractères aléatoires produit l'entropie maximale et ne dit rien.
L'entropie n'est pas une mesure de valeur ni d'utilité. Le message «votre vol est annulé» a une valeur considérable pour vous et une entropie dérisoire s'il était probable. Inversement, le résultat d'un tirage au sort auquel vous ne participez pas a une entropie maximale et une utilité nulle. Toute phrase qui traite l'entropie comme une richesse est une confusion.
L'entropie n'est pas une mesure de vérité. Une affirmation fausse et une affirmation vraie de même probabilité a priori portent la même quantité d'information. La théorie suppose le canal fidèle à une source; elle ne certifie pas la source.
L'entropie n'est pas la complexité d'un objet individuel. Les mille premières décimales de π ont une entropie d'ordre 0 proche de log210=3,3219 bits par chiffre, mais un programme de quelques lignes les engendre. La grandeur qui capture cela est la complexité de Kolmogorov, la longueur du plus court programme produisant l'objet — et le chapitre 5 nous a appris qu'elle n'est pas calculable, par un argument voisin de celui du problème de l'arrêt. L'entropie de Shannon est calculable parce qu'elle est une propriété de la loi, pas de l'objet.
Et la thermodynamique?
La formule de Shannon a la même forme que l'entropie statistique de Boltzmann et Gibbs, S=−kB∑ipilnpi, à la constante kB et à la base du logarithme près. Que faut-il en penser?
Il faut le dire aussi précisément que possible, parce que ce point est le lieu de beaucoup de littérature vague. Ce n'est pas une simple métaphore: la parenté est mathématique et réelle. Les deux grandeurs mesurent la même chose formelle — le logarithme du nombre d'états compatibles avec ce que l'on sait — et la mécanique statistique est, lue ainsi, un exercice d'inférence sur des états microscopiques. Le lien a aussi une conséquence physique mesurable: le principe de Landauer affirme qu'effacer irréversiblement un bit d'information dissipe au moins kBTln2 joules, soit environ 3⋅10−21 J à température ambiante — une quantité minuscule, très inférieure à ce que consomme un transistor réel, mais non nulle et expérimentalement approchée depuis les années 2010 par plusieurs équipes.
Mais ce n'est pas une identité non plus. L'entropie de Shannon se mesure en bits et porte sur une loi de probabilité choisie par le modélisateur; l'entropie thermodynamique se mesure en joules par kelvin et porte sur l'état macroscopique d'un système physique. La première change si vous changez de modèle; la seconde est une fonction d'état. Confondre les deux conduit à des énoncés qui sonnent profonds et ne prédisent rien. La formulation honnête: une analogie formelle avec une parenté mathématique réelle et une conséquence physique vérifiée, mais deux grandeurs distinctes. Nous nous en tiendrons là; ce cours n'a pas besoin de plus.
Synthèse
La quantité d'information d'un événement de probabilité p vaut −log2p bits. Le logarithme n'est pas un choix de commodité: c'est la seule fonction continue et décroissante qui rende l'information additive sur des événements indépendants, et la base 2 fixe l'unité en donnant 1 bit au tirage équiprobable entre deux possibilités.
L'entropieH(X)=−∑ipilog2pi est l'information moyenne par symbole, en bits/symbole, avec la convention 0log20=0 qui est la seule limite continue. Elle vérifie 0≤H(X)≤log2n, la borne basse caractérisant les sources déterministes et la borne haute les sources équiprobables; les deux se déduisent de l'inégalité de Gibbs.
L'entropie binaireH(p) est en cloche, maximale et égale à 1 en p=1/2, nulle en 0 et en 1, avec une tangente verticale aux bords: un canal qui se trompe une fois sur cent porte déjà 0,0808 bit d'incertitude par bit transmis.
La règle de chaînageH(X,Y)=H(X)+H(Y∣X) et l'information mutuelleI(X;Y)=H(X)−H(X∣Y)≥0 mesurent ce qu'une variable dit d'une autre. Sur le canal binaire symétrique de l'exemple 6.4, , , , , et bit, toutes les identités étant vérifiées numériquement.
La redondanceR=1−H/log2n est le fil de la seconde moitié du cours: le chapitre 7 la supprimera pour comprimer, le chapitre 8 en rajoutera délibérément pour corriger les erreurs.
Pour ABRACADABRA, H=2,0404 bits/symbole, soit 22,44 bits pour les onze symboles contre 33 bits en longueur fixe. Ces 22,44 bits sont un plancher que le chapitre 7 approchera sans l'atteindre: le codage de Huffman donnera 23 bits — un total forcé, même si plusieurs jeux de longueurs l'atteignent —, l'écart venant de ce qu'une longueur de mot est un entier.
Enfin, l'entropie est une propriété du modèle probabiliste, jamais de la chaîne: ABABABABAB vaut 1 bit/symbole à l'ordre 0 et 0 à l'ordre 1. Améliorer le modèle abaisse la borne, sans jamais contredire le théorème.
Série d'exercices du chapitre 6Exercice 1 sur 5
Question 6.6
Laquelle de ces affirmations sur l'entropie est vraie?
Problème guidé 6.1 · Un capteur industriel, de la mesure au plancher de compression
Un capteur de surveillance transmet toutes les secondes son état parmi trois valeurs: «normal» avec la probabilité 0,70, «alerte» avec 0,20 et «panne» avec 0,10. Les états successifs sont supposés indépendants (modèle d'ordre 0). On vous demande de dimensionner la liaison.
1
L'entropie de la source
Vérifiez que les probabilités somment à 1, puis calculez l'entropie de ce capteur en bits par mesure.
Question
Quelle est l'entropie de la source, en bits par mesure?
La redondance
Le plancher pour une heure d'enregistrement
Le capteur redevient bavard
Exercices
Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.
Exercice 6.1 · Quatre entropies et leurs redondances
Calculez l'entropie, en bits par symbole, de chacune des sources suivantes, puis sa redondance relative par rapport à log2n.
(1/2,1/4,1/4);
(0,4;0,3;0,2;0,1);
cinq symboles équiprobables;
(0,97;0,01;0,01;0,01).
Classez les quatre sources par entropie croissante et commentez le rôle de la taille de l'alphabet.
Solution
1.H=21⋅1+41⋅2+41⋅2=1,5000 bit/symbole. Le maximum est , donc , soit .
Exercice 6.2 · La fonction d'entropie binaire
Démontrez que H(p)=H(1−p) pour tout p∈[0,1].
Calculez H′(p) et H′′(p) sur ]0,1[; déduisez-en la concavité et la position du maximum.
Montrez que H′(p)→+∞ quand p→0+ et interprétez.
Le premier terme du développement de H au voisinage de 0: montrez que H(p)≈plog2(1/p)+plog2e pour p petit, et comparez la valeur approchée à la valeur exacte pour .
Solution
1. Échanger p et 1−p dans −plog2p−(1−p)log2(1−p) échange les deux termes de la somme sans la modifier. Interprétation: l'entropie ne dépend pas de la façon dont on nomme les deux symboles.
Exercice 6.3 · Une table conjointe complète
Une station météo enregistre chaque soir l'état du ciel Y (couvert ou dégagé) et note le lendemain s'il a plu, variable X (pluie ou sec). Sur un long historique, la loi conjointe est estimée à:
p(x,y)
couvert
dégagé
pluie
0,35
0,05
sec
0,10
0,50
Calculez les deux lois marginales et vérifiez que le total vaut 1.
Calculez H(X), H(Y) et H(X,Y).
Déduisez-en H(X∣Y), H(Y∣X) et I(X;Y), et vérifiez les trois expressions de (6.10).
Le ciel du soir est-il un bon prédicteur de la pluie du lendemain? Chiffrez votre réponse en pourcentage d'incertitude levée.
Solution
1. Marges de X: 0,35+0,05=0,40 pour «pluie», 0,10+0,50=0,60 pour «sec». Marges de Y: 0,35+0,10=0,45 pour «couvert», pour «dégagé». Le total des quatre cases vaut , et les deux jeux de marges somment chacun à .
Exercice 6.4 · Le plancher d'ABRACADABRA, et ce qui le déplace
Recalculez H pour la source ABRACADABRA et retrouvez 22,44 bits pour les onze symboles.
Un codage à longueur fixe coûte 33 bits. Quelle est la redondance de ce codage? Quelle est celle de la source par rapport à log25?
On ajoute au message un douzième symbole E, de fréquence 0. L'entropie change-t-elle? Justifiez par la convention et par l'intuition.
On modifie le message pour qu'il compte six A au lieu de cinq, en remplaçant le D par un A (le message devient ABRACAAABRA, toujours onze symboles). Recalculez H et commentez le sens de la variation.
Solution
1. Avec pA=5/11, pB=pR=2/11 et (somme ), les surprises valent , et bits. Les contributions sont pour A, pour B et pour R, pour C et pour D. Leur somme est bits/symbole, et bits.
Exercice 6.5 · Positivité, indépendance et une fausse évidence
Démontrez que H(X∣Y)≤H(X), avec égalité si et seulement si X et Y sont indépendantes.
Démontrez que H(X,Y)≥max(H(X),H(Y)) et interprétez.
Soit Y=f(X) une fonction déterministe de X. Montrez que H(Y∣X)=0 et que I(X;Y)=H(Y). Que vaut H(X,Y)?
Une fausse évidence. Soient X et Y deux bits indépendants et équiprobables, et Z=X⊕Y (ou exclusif). Calculez H(Z), I(X;Z) et I(X;Z∣Y)=H(X∣Y)−H(X∣Y,Z). Que conclure sur l'idée que «conditionner réduit toujours l'information»?
Solution
1. Par (6.10), H(X)−H(X∣Y)=I(X;Y), et le théorème 6.6 donne I(X;Y)≥0 avec égalité si et seulement si p(x,y)=p(x)p(y) pour tout couple, c'est-à-dire l'indépendance. La démonstration passe par l'inégalité de Gibbs appliquée à la loi conjointe et au produit des marginales.
Références
Shannon, C. E., A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, 1948 — l'article fondateur; les sections 1 à 7 sont lisibles avec ce chapitre en main.
Cover, T. M. et Thomas, J. A., Elements of Information Theory, 2e éd., Wiley, Hoboken, chap. 2 (entropie, entropie relative et information mutuelle).
MacKay, D. J. C., Information Theory, Inference and Learning Algorithms, Cambridge University Press, chap. 2 et 4 (librement disponible en ligne).
Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, Boston, chap. 3 (ce que les bits n'expriment pas).
Landauer, R., Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, vol. 5, 1961 — pour le lien avec la thermodynamique.
Polycopiés du cours ICC de l'EPFL, partie «Information et codage».
H(p1,…,pn)
i
H2(p)
H(X)
12,1%
(1,3,3,3,3)
(1,2,4,4,3)
(1,3,4,4,2)
23
5×1+2×3+2×3+1×3+1×3=23
23, et non 22,44.
0,56
−log2(5/11)=1,1375
Attention toutefois
H(X)=0,8813
H(Y)=0,9248
H(X,Y)=1,3503
H(X∣Y)=0,4255
H(Y∣X)=0,4690
I=0,4558
log23=1,5850
R=1−1,5000/1,5850=0,0536
5,4%
2. Les termes valent 0,5288, 0,5211, 0,4644 et 0,3322: H=1,8464 bit/symbole. Le maximum est log24=2, donc R=0,0768, soit 7,7%.
3. Source uniforme: H=log25=2,3219 bits/symbole et R=0 par le cas d'égalité du théorème 6.3. C'est la source la plus «chère» des quatre bien qu'elle n'ait que cinq symboles.
4.H=0,97×0,0439+3×0,01×6,6439=0,0426+0,1993=0,2419 bit/symbole, et R=1−0,2419/2=0,8790, soit 87,9%. Presque tout est gaspillé: cette source se comprime très bien.
Classement croissant:0,2419<1,5000<1,8464<2,3219, donc 4, 1, 2, 3.
Commentaire. La source 4 a quatre symboles et la plus petite entropie; la source 1 en a trois et bat la source 4. La taille de l'alphabet ne fixe qu'une borne supérieurelog2n; c'est la forme de la distribution qui décide de l'entropie effective. Un alphabet immense mais très déséquilibré porte peu d'information.
p=0,01
2. Avec log2u=lnu/ln2,
H′(p)=ln21(−lnp−1+ln(1−p)+1)=log2p1−p.
Puis
H′′(p)=ln21(1−p−1−p1)=−p(1−p)ln21<0sur ]0,1[,
donc H est strictement concave. La dérivée s'annule pour p1−p=1, soit p=1/2, où H(1/2)=1: c'est bien le maximum, conformément au théorème 6.3 avec n=2.
3. Quand p→0+, (1−p)/p→+∞, donc H′(p)=log2p1−p→+∞. La courbe part de l'origine avec une tangente verticale. Interprétation: près de la certitude, un tout petit peu de doute coûte beaucoup. Passer de p=0 à p=0,01 fait gagner 0,0808 bit, soit huit fois la variation de p; alors qu'au voisinage de 1/2, une variation de 0,01 sur p ne change H que de 0,00029 bit (la dérivée y est nulle, et l'on mesure alors la courbure).
4. Écrivons H(p)=−plog2p−(1−p)log2(1−p). Pour le second terme, ln(1−p)=−p−p2/2−…, donc
D'où H(p)≈plog2(1/p)+plog2e. Pour p=0,01: 0,01×6,6439=0,0664 pour le premier terme, 0,01×1,4427=0,0144 pour le second, soit 0,0809, contre une valeur exacte de 0,0808: l'écart est de 10−4, c'est-à-dire du même ordre que le O(p2) négligé. L'approximation est excellente dès que p est petit, et elle montre que le terme dominant est plog2(1/p), c'est-à-dire la contribution de l'événement rare.
0,05+0,50=0,55
0,35+0,05+0,10+0,50=1,00
1
2. Les deux marginales sont binaires:
H(X)=H(0,40)=0,9710 bit,H(Y)=H(0,45)=0,9928 bit.
Pour l'entropie conjointe, −log20,35=1,5146, −log20,05=4,3219, −log20,10=3,3219 et −log20,50=1:
Les trois expressions de l'information mutuelle donnent la même valeur:
H(X)−H(X∣Y)=0,9710−0,5856=0,3853;
H(Y)−H(Y∣X)=0,9928−0,6074=0,3853;
H(X)+H(Y)−H(X,Y)=0,9710+0,9928−1,5784=0,3853.
Les deux décompositions de H(X,Y) se recoupent aussi: 0,9710+0,6074=1,5784 et 0,9928+0,5856=1,5784.
4. Le ciel du soir lève I/H(X)=0,3853/0,9710=0,3968, soit environ 40 % de l'incertitude sur la pluie du lendemain. C'est loin d'être négligeable mais loin d'être décisif: il reste 0,5856 bit d'incertitude sur 0,9710. On peut le voir autrement: P(pluie∣couvert)=0,35/0,45=0,7778, alors que la probabilité a priori était 0,40. Un ciel couvert fait donc presque doubler la probabilité de pluie, sans la rendre certaine.
pC=pD=1/11
=11/11=1
1,1375
2,4594
3,4594
pI
0,5170
0,4472
0,3145
H=2,0404
11×2,0404=22,44
2. Redondance du codage à longueur fixe: 1−2,0404/3=0,3199, soit 32,0%. Redondance de la source par rapport au maximum d'un alphabet à cinq symboles: 1−2,0404/2,3219=0,1213, soit 12,1%. Les deux nombres ne mesurent pas la même chose: le premier inclut le gaspillage dû au fait que 5 n'est pas une puissance de 2 (⌈log25⌉=3 alors que log25=2,32), le second ne mesure que le déséquilibre de la source.
3. L'entropie ne change pas. Formellement, le terme ajouté est −0×log20=0 par la convention, qui est la limite continue de xlog2x en 0. Intuitivement, un symbole qui n'apparaît jamais n'apporte aucune surprise à moyenner: il ne coûte rien à décrire puisqu'il ne survient pas. C'est cette propriété qui permet de comparer des sources définies sur des alphabets différents.
4. Le nouveau message ABRACAAABRA a les fréquences A =6, B =2, R =2, C =1, D =0, donc les probabilités (6/11,2/11,2/11,1/11), dont la somme vaut bien 1. Les surprises sont −log2(6/11)=0,8745, 2,4594 (deux fois) et 3,4594, d'où
soit 18,54 bits pour le message. L'entropie baisse de 2,0404 à 1,6858: la distribution est devenue plus déséquilibrée (un symbole a disparu, un autre s'est renforcé), donc la source est plus prévisible. C'est cohérent avec le théorème 6.3: on s'éloigne de l'équiprobabilité, donc de la borne log25.
2. Par la règle de chaînage, H(X,Y)=H(X)+H(Y∣X)≥H(X) car une entropie conditionnelle est une moyenne d'entropies, donc positive. Symétriquement H(X,Y)≥H(Y), d'où le maximum. Interprétation: décrire un couple ne peut pas coûter moins cher que de décrire l'une de ses composantes. Sur le diagramme de Venn, l'union contient chaque disque.
3. Si Y=f(X), alors pour chaque x la loi conditionnelle de Y sachant X=x est concentrée sur la seule valeur f(x): son entropie est nulle, donc H(Y∣X)=∑xp(x)×0=0. Par (6.10), I(X;Y)=H(Y)−H(Y∣X)=H(Y): la fonction ne peut pas révéler plus que sa propre entropie. Et par la règle de chaînage, H(X,Y)=H(X)+H(Y∣X)=H(X): le couple (X,f(X)) ne coûte pas plus cher que X seul, ce qui est évident puisque Y se recalcule.
4.Z=X⊕Y vaut 0 si X=Y et 1 sinon; comme X et Y sont indépendants et équiprobables, les quatre couples (0,0),(0,1),(1,0),(1,1) ont chacun la probabilité 1/4, donc P(Z=0)=P(Z=1)=1/2 et H(Z)=1 bit.
X et Z sont indépendants: P(Z=0∣X=0)=P(Y=0)=1/2, et de même dans les trois autres cas. Donc I(X;Z)=0: connaître Z seul n'apprend rien sur X.
Mais si l'on connaît déjà Y, alors X=Z⊕Y est entièrement déterminé par Z. Donc H(X∣Y)=H(X)=1 (indépendance) et H(X∣Y,Z)=0, d'où
I(X;Z∣Y)=1−0=1 bit>I(X;Z)=0.
Conclusion. Conditionner peut augmenter l'information mutuelle. Le théorème 6.6 dit seulement que I(X;Y)≥0 et que conditionner ne fait pas monter l'entropie marginale en moyenne; il ne dit rien de la comparaison entre I(X;Z) et I(X;Z∣Y), qui peut aller dans les deux sens. Cet exemple est aussi celui qui fait échouer le diagramme de Venn à trois variables: l'«intersection triple» I(X;Y;Z)=I(X;Z)−I(X;Z∣Y)=−1 bit y serait une aire négative. L'image est un aide-mémoire, jamais une démonstration.