Entropie en théorie de l'information
Le problème de la compression de fichiers
Imaginons une liste de systèmes distincts élémentaires (disons,
molécules). L'état de chaque système est supposé être l'un d'une
liste finie connue d'états possibles (qui peut être la même liste ou
différentes listes d'un système à l'autre). Cherchons une méthode
pour préciser tous ces états par de l'information numérique stockée
dans une clé USB, au format le plus compressé possible (pour prendre
peu d'espace mémoire). (Le cas d'une liste infinie d'états possibles
de chaque système élémentaire n'est pas vraiment exclu car il peut
se comporter comme la limite du cas fini, avec des probabilités
convergeant vers zéro assez rapidement quand les états sont énumérés
des quelques-uns les plus fréquent à l'infinité des plus
exceptionnels).
Imaginez la méthode d'enregistrement suivante.
Les états de systèmes successifs sont enregistrés sous forme de
fichiers successifs dans la mémoire. Chaque état possible d'un
système élémentaire est codé comme «un fichier», qui est une
succession de bits, qui fait partie d'une liste donnée de «fichiers
possibles» (successions de bits), où les "fichiers possibles"
correspondent bijectivement aux états possibles d'un système. Par
souci de compression, ces fichiers seront simplement mis côte à
côte, sans espace inutilisé entre eux ni aucun répertoire de
fichiers pour distinguer leur séparation. Pour éviter toute
ambiguïté tandis que les longueurs des fichiers peuvent différer, la
séparation entre fichiers sera déterminée par la méthode suivante.
L'état du premier système élémentaire donné sera codé par le premier
fichier (les premiers bits) en mémoire, dont le contenu est l'un
d'une liste L de possibilités, en correspondance biunivoque
avec les états possibles i de ce système: notons Ai
ce fichier, de longueur li bits. Puis, tout ce
qui vient après ce fichier décrit les prochains systèmes
élémentaires (à partir du deuxième) de la même manière.
La condition pour éviter tout risque d'ambiguïté, est que pour tout
contenu possible de la mémoire, un seul élément Ai
de L (décrivant le premier système) peut être considéré
comme son début (coïncide avec la séquence de même longueur partant
du début). Le cas interdit, où 2 fichiers dans L sont chacun
identique au début du même contenu de la mémoire de différentes
longueurs, signifierait qu'un élément de L coïncide avec le
début d'un autre.
Ainsi, on déduit la taille du premier fichier d'un contenu de
mémoire donnée, en le lisant à partir de ses premiers bits jusqu'à
ce qu'ils se retrouvent former une séquence identique à l'un des
fichiers dans L. Alors on sait que le second fichier
commence juste après.
Réinterpréter tous les contenus de mémoire possibles comme
expansions binaires des nombres réels entre 0 et 1, chaque état
possible i du premier système correspond à l'intervalle
entre Ai 2-li et (Ai+1)2-li,
de longueur 2-li, inclus dans [0,1].
Alors, la condition de non-ambiguïté est exprimée par le
non-chevauchement de ces intervalles. Par conséquent, la somme de
toutes leurs longueurs ne peut pas dépasser 1:
∑i 2-li
≤ 1
Nous avons ici choisi chiffres binaires pour représenter les choses.
Pourquoi ne pas utiliser des chiffres dans une autre base au lieu de
2 ? Par exemple, un chiffre de 8 valeurs donne autant d'informations
que 3 chiffres binaires, de sorte que la taille des fichiers est
prise en compte par paquets de 3 = log2(8) bits. Alors,
pour être neutre par rapport au choix de la base et oublier le cas
particulier de la représentation binaire, utilisons ln(x) au
lieu de log2(x) pour compter la "taille objective"
que vaut un chiffre en base x (avec x valeurs
possibles).
Ainsi, la "taille objective" d'un fichier avec li
bits, dont le contenu est l'un des 2li
séquences possibles de li bits, est le nombre
réel
Si = ln(2li)
= ln(2).li
L'inégalité ci-dessus s'écrit maintenant
∑i e-Si
≤ 1.
Entropie reçue (taille moyenne du fichier)
Si chaque état i a la probabilité pi de
se produire (où ∑i pi
= 1), la taille moyenne du fichier est
S' = ∑ipiSi
La qualité d'une compression est sa capacité à réduire cette
quantité. Comment cela peut-il dépendre du choix de l'encodage ?
Pour chaque état probabiliste (pi), soit li
= ⌈-log2(pi)⌉ (fonction
plafond), ce qui est l'idée d'un fichier
"juste moins d'un bit plus long que -ln(pi)".
Soit p'i = 2-li
= e-Si, de sorte que Si
= ln(2).li = -ln p'i
On a ∑ip'i ≤ ∑i
pi = 1, ainsi on peut choisir un codage binaire où
chaque état i est codé par un fichier de longueur li,
formant intervalles disjoints dans [0,1] de longueurs respectives p'i.
Dans le cas particulier où tous les pi sont des
puissances de 2, l'encodage donné par la méthode ci-dessus semble
naturellement parfait: il définit une partition de [0,1] en
intervalles de longueurs respectives p'i = pi.
Ainsi, chaque pi coïncide avec la probabilité
qu'un contenu parfaitement aléatoire de la mémoire, vu comme un
nombre réel dans [0,1], va tomber dans cet intervalle. (Une telle
variable aléatoire réelle correspond à un long contenu aléatoire de
la mémoire, ce qui représente la limite pour une longue série de
systèmes tous satisfaisant cette condition de perfection).
Alors la formule de la taille moyenne du fichier, devient la
définition générale de l'entropie d'un état probabiliste (pi)
d'un système (où ∑i pi
= 1):
S = - ∑i pi
ln pi
Plus generalement, pour 2 lois de probabilités pi,
p'i sur une liste donnée d'états, la formule
ci-dessus de S' définit l'entropie reçue (*) de
l'état probabiliste (pi) relativement à (p'i)
:
S' = - ∑i
pi ln p'i
On peut regarder p'i comme une probabilité
attendue (à tort, celle correcte étant pi):
c'est la probabilité pour laquelle cet encodage serait parfait, donc
qui est «attendue» implicitement par l'encodage choisi. Il n'importe
pas si la condition sur (p'i) est définie comme ∑i
p'i ≤ 1 ou ∑i p'i
= 1 car le premier cas peut être ramené au dernier en ajoutant un
état j à la liste, avec pj = 0 et p'j
= 1−∑i p'i.
En particulier pour notre construction ci-dessus, -log2(pi)
≤ li < -log2(pi)
+ 1 gives S ≤ S' < S + ln 2.
Pourquoi l'entropie reçue est supérieure à l'entropie réelle
Montrons ce qui est (peut-être) évident: qu'un format de
stockage relative à de fausses attentes (p'≠p) est
sous-optimal, à savoir donne un S' > S.
Pour cela, fixons pi, et regardons les
variations de S' lorsque p'i varie
(gardant ∑ipi=∑ip'i
= 1, donc ∑i dp'i
=0):
dS'= - ∑i
(pi/p'i)dp'i
= ∑i (1−(pi/p'i))dp'i
La condition d'annulation de cette dérivée est que pi=p'i
pour tout i: sinon, il doit y avoir un i pour lequel
pi>p'i, et un j pour
lequel pj<p'j ;
alors on voit sur cette formule que dans le cas dp'j
= -dp'i > 0 (les autres variations de p'
étant nulles), qui signifie que p' s'éloigne de p,
la valeur de S' augmente (dS'>0).
En particulier, pour tout codage binaire d'un état probabiliste dont
les probabilités ne sont pas des puissances de 2, la taille moyenne
des fichiers sera toujours supérieure à l'entropie.
Additivité de l'entropie des systèmes indépendants
Si 2 systèmes sont indépendants (non corrélées), à savoir tout état
combiné (i,j) a une probabilité pi,j = aibj
(où (ai) et (bj) sont les
probabilités d'états de chaque sous-système, indépendamment de
l'autre sous-système), alors l'entropie est additive, car elle est
la moyenne de
-ln pi,j = (-ln ai)
+ (-ln bj)
On peut l'écrire complètement formellement, comme
∑i,j pi,j
ln pi,j = ∑i,j aibj
(ln ai+ln bj)
= ∑iai (ln ai)
(∑jbj)+
(∑iai)(∑jbj
ln bj)
=∑i ai ln ai+∑j
bj ln bj
Par conséquent, même la marge d'un bit d'entropie supplémentaire (+
ln(2)) dans le procédé de compression ci-dessus, peut être
pratiquement éliminée (approchant 0 par fichier), en rassemblant un
grand nombre de fichiers représentant des systèmes non corrélées,
ensemble en un grand: en cherchant une compression, non de l'état
d'un système, mais d'une large succession de systèmes indépendants.
En traitant le système global comme un tout comme ci-dessus, on peut
trouver une compression de taille moyenne inférieure à
(Entropie du système global + ln(2)) = (Σ entropie des
systèmes individuels) + ln (2)
Ainsi, la marge ln(2) ne vient qu'une fois pour toutes au lieu
d'être répétée pour chaque sous-système.
En conclusion, par ces méthodes, même si les probabilités ne sont
pas des puissances de 2, l'entropie continue à représentant
essentiellement la "taille de l'information dans sa forme la plus
comprimée".
Entropie des systèmes corrélés
Le cas des systèmes corrélés peut être analysé comme suit:
Soit ai = ∑j pi,j
et bi,j = pi,j/ai
(où les i tels que ai = 0 sont éliminés
de la liste) de sorte que pi,j = ai
bi,j et ∑j bi,j=1
pour tout i. Alors
S = - ∑i,j ai bi,j
(ln ai + ln bi,j) = SA
+ ∑i ai SBi
où SBi = - ∑j bi,j
ln bi,j est l'entropie de l'état probabiliste (bi,j)
de B (pour i fixé et j variable).
L'entropie est une fonction concave de l'état de probabilité (somme
de fonctions concaves -x ln (x)), donc une moyenne
d'entropies est inférieure à l'entropie de la moyenne des états de
probabilité avec les mêmes poids:
∑i ai SBi
≤ SB = -∑i,j bj
ln bj
où bj=∑i pi,j
= ∑i ai bi,j.
On conclut
S ≤ SA + SB
(*) J'ai dû inventer l'expression
"entropie reçue" faute de trouver cette quantité définie et nommée
ailleurs.
Partie suivante :
Entropie en physique statistique
En anglais : Entropy in information
theory
Sommaire des pages en francais : fondements
des mathématiques et de la physique