Entropie à partir des premiers principes

1 janvier 2025

Je trouve l’entropie extrêmement fascinante. Cependant, faire correspondre la formule $\sum p_{i} lo g \frac{1}{p _{i}}$ à ses explications “intuitives” liées aux codes sans préfixe et au contenu informationnel n’est pas évident. Ici, je veux explorer quelques façons d’arriver indépendamment à cette idée.

Propriétés de l’information

Supposons que nous voulions définir une fonction $I$ , qui représente le contenu informationnel d’un événement. En faisant abstraction des spécificités de l’événement, une mesure que nous pourrions utiliser pour comparer un événement à un autre est leur probabilité d’occurrence. Ainsi, $I$ pourrait être une application d’une probabilité $p \in [0, 1]$ vers $R$ . Avec ce cadre, les exigences suivantes sont raisonnables :

$I (1) = 0$ . Si un événement se produit certainement, il n’est pas très intéressant et nous donne peu d’information.
$I$ doit être continue et monotoniquement décroissante sur $[0, 1]$ . Un événement plus commun est moins informatif.
Deux événements indépendants avec des probabilités $p$ et $q$ devraient avoir une information $I (p) + I (q)$

La dernière exigence est la plus révélatrice. Par définition, la probabilité que deux événements indépendants se produisent est $pq$ . Donc

I (pq) = I (p) + I (q) .

Puisque la fonction doit être continue, cela ne tient que pour

I (p) = c lo g p .

Si nous voulons que $I$ soit monotoniquement décroissante,

\frac{d I}{d p} = c / p

doit être négatif. Puisque $p$ est positif, $c$ doit être négatif. En posant $c^{'} = ∣ c ∣$

I (p) = c^{'} lo g \frac{1}{p}

Puisque $lo g_{a} b = \frac{l o g b}{l o g a}$ , où le dénominateur est une constante, nous pouvons considérer $c^{'}$ comme encodant la base du logarithme. Pour plus de commodité, nous laissons $c^{'}$ être 1, et nous laissons $lo g$ désigner le logarithme en base 2.

L’entropie est simplement la valeur attendue de $I$ , sur une distribution $p = (p_{1}, p_{2}, \dots, p_{n})$

H (p) = i = 1 \sum n p_{i} lo g \frac{1}{p _{i}}

Nous supposons également que $H (0) = 0 lo g \frac{1}{0} = 0$ , motivé par la continuité.

Par exemple, considérons la variable aléatoire de Bernoulli $B_{p}$ , qui prend la valeur $1$ avec probabilité $p$ , et $0$ avec probabilité $1 - p$ . Si nous traçons son entropie

Code de tracé

import numpy as np
import plotly.graph_objects as go

# Fonction pour calculer l'entropie d'une variable de Bernoulli
def bernoulli_entropy(p):
    return -p * np.log2(p) - (1 - p) * np.log2(1 - p)

# Générer des valeurs pour p de 0 à 1
p_values = np.linspace(0.01, 0.99, 100)
entropy_values = bernoulli_entropy(p_values)

# Créer le tracé
fig = go.Figure()

# Ajouter la trace de l'entropie
fig.add_trace(go.Scatter(x=p_values, y=entropy_values, mode='lines', name='Entropie', line=dict(color='red')))

# Mettre à jour la mise en page pour le mode sombre
fig.update_layout(
    title='Entropie d\'une variable aléatoire de Bernoulli',
    xaxis_title='p',
    yaxis_title='Entropie',
    template='plotly_dark'
)

# Sauvegarder le tracé dans un fichier HTML
fig.write_html("bernoulli_entropy_plot.html")

nous voyons qu’elle est maximisée lorsque la distribution est uniforme, et minimisée lorsqu’elle est presque déterministe.

Codes sans préfixe

Supposons que nous ayons un ensemble de symboles $X = {X_{1}, \dots, X_{M}}$ que nous voulons transmettre sur un canal binaire. Nous construisons le canal de telle sorte que nous puissions envoyer soit un $1$ soit un $0$ à la fois. Nous voulons trouver un schéma de codage optimal pour $X$ , avec une exigence : il doit être sans préfixe.

Définissons une fonction de codage $f : X \to {0, 1}^{+}$ , qui mappe des symboles à des chaînes binaires de longueur $\geq 1$ . Nous disons qu’un codage est sans préfixe si aucun mot de code n’est un préfixe d’un autre. Par exemple, ${0, 01}$ n’est pas sans préfixe car $0$ est un préfixe de $01$ . Cependant, ${0, 10}$ l’est.

Un code sans préfixe implique que le code est décomposable de manière unique sans délimiteurs supplémentaires entre les symboles, ce qui est une propriété souhaitable.

Nous remarquons également qu’un code binaire sans préfixe est uniquement défini par un arbre binaire :

Arbre binaire d’un code sans préfixe — Source : https://leimao.github.io/blog/Huffman-Coding

où le chemin de la racine au symbole détermine le mot de code, et les symboles sont toujours des feuilles. Convainquez-vous que toute construction de ce type résulte en un code sans préfixe.

Nous allons maintenant montrer que la longueur moyenne des mots de code $L$ de tout code sans préfixe sur $X$ est bornée par

H (X) \leq L < H (X) + 1.

où $X$ est une variable aléatoire qui prend des valeurs dans l’ensemble $X$ avec des probabilités $(p_{1}, \dots, p_{n})$ . Plus important encore, nous voyons que l’entropie de $X$ est une borne inférieure pour la compression d’une distribution, ou de manière équivalente, pour la quantité d’information qu’elle contient.

Inégalité de Kraft

Supposons que $l_{i}$ soit la longueur du $i$ ème mot de code. Si le code est sans préfixe :

i = 1 \sum M 2^{- l_{i}} \leq 1

Preuve :

Soit $l_{max}$ la longueur du mot de code le plus long. Nous remarquons que :

Il y a au plus $2^{l_{max}}$ nœuds au niveau $l_{max}$
Pour tout mot de code de longueur $l_{i}$ , il y a $2^{l_{max} - l_{i}}$ descendants au niveau $l_{max}$ .
Les ensembles de descendants de chaque mot de code sont disjoints (puisqu’un mot de code n’est jamais un descendant d’un autre)

Cela implique

⟹ i \sum 2^{l_{max} - l_{i}} \leq 2^{l_{max}} i \sum 2^{- l_{i}} \leq 1.

Pourquoi $\leq$ au lieu de l’égalité ? Parce qu’il est possible qu’un nœud au niveau $l_{max}$ ne soit pas un descendant d’aucun mot de code (considérez l’arbre du code ${10, 11}$ ) !

Borne inférieure pour L

Considérons maintenant la longueur moyenne des mots de code

L = i \sum p_{i} l_{i}

Nous allons montrer que l’entropie est une borne inférieure pour $L$ , ou

H (X) \leq L ⟺ L - H (X) \geq 0

Preuve :

L - H (X) = i \sum p_{i} l_{i} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} + i \sum p_{i} lo g (j \sum 2^{- l_{j}}) - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = i \sum p_{i} lo g \frac{p _{i}}{2 ^{- l_{i}} / \sum _{j} 2 ^{- l_{j}}} - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = D_{K L} [p ∣∣ q] + lo g \frac{1}{c} \geq 0

Où la dernière inégalité est due à 1) la divergence de KL étant non négative et 2) à $c \leq 1$ en raison de l’inégalité de Kraft. Une chose à noter est que si $l_{i} = - lo g p_{i}$ , $L = H (X)$ , le minimum théorique. La raison pour laquelle nous ne pouvons pas toujours atteindre ce minimum est que $- lo g p_{i}$ n’a pas besoin d’être un entier, ce qui est évidemment requis.

Une borne supérieure pour L

Remarquons qu’il est possible de construire un code sans préfixe avec des longueurs

l_{i} = ⌈ - lo g p_{i} ⌉

puisqu’elles satisfont l’inégalité de Kraft :

i \sum 2^{- l_{i}} \leq i \sum 2^{l o g p_{i}} = 1

Par la définition de la fonction plafond

- lo g p_{i} \leq l_{i} < - lo g p_{i} + 1

En prenant l’espérance sur $p$ , nous obtenons

- \sum p_{i} lo g p_{i} \leq \sum p_{i} l_{i} < - \sum p_{i} lo g p_{i} + 1 ⟹ H (X) \leq L < H (X) + 1

Cela montre que $H (X) + 1$ est une bonne borne supérieure pour L !

En résumé, l’entropie est une borne inférieure, et une estimation raisonnable, pour le nombre moyen de bits nécessaires pour encoder une distribution en tant que code sans préfixe.

Références

Alon Orlitsky’s ECE 255A Lectures, UCSD
Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory. Wiley-Interscience.

←

Modèles de Mélange Gaussien Interactifs