L'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 préfixes et au contenu informationnel n’est pas évident. Ici, je souhaite explorer quelques méthodes pour arriver indépendamment à cette notion.

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 cette approche, 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 apporte peu d’information.
$I$ doit être continue et monotoniquement décroissante sur $[0, 1]$ . Un événement plus courant est moins informatif.
Deux événements indépendants de probabilités $p$ et $q$ doivent 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 n’est vrai 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égative. Comme $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 que $c^{'}$ encode la base du logarithme. Par commodité, nous posons $c^{'} = 1$ et utilisons $lo g$ pour désigner le logarithme en base 2.

L’entropie est simplement l’espérance 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

# Function to calculate the entropy of a Bernoulli variable
def bernoulli_entropy(p):
    return -p * np.log2(p) - (1 - p) * np.log2(1 - p)

# Generate values for p from 0 to 1
p_values = np.linspace(0.01, 0.99, 100)
entropy_values = bernoulli_entropy(p_values)

# Create the plot
fig = go.Figure()

# Add the entropy trace
fig.add_trace(go.Scatter(x=p_values, y=entropy_values, mode='lines', name='Entropy', line=dict(color='red')))

# Update layout for dark mode
fig.update_layout(
    title='Entropy of a Bernoulli Random Variable',
    xaxis_title='p',
    yaxis_title='Entropy',
    template='plotly_dark'
)

# Save the plot to an HTML file
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 préfixes

Supposons que nous ayons un ensemble de symboles $X = {X_{1}, \dots, X_{M}}$ que nous souhaitons transmettre via un canal binaire. Nous construisons le canal de manière à pouvoir envoyer soit un $1$ , soit un $0$ à la fois. Nous voulons trouver un schéma d’encodage optimal pour $X$ , avec une condition : il doit être préfixe.

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

Un code préfixe implique que le code est uniquement décodable sans délimiteurs supplémentaires entre les symboles, ce qui est une propriété souhaitable.

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

Arbre binaire d’un code 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. Assurez-vous qu’une telle construction donne toujours un code préfixe.

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

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

où $X$ est une variable aléatoire prenant 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 le degré de compression d’une distribution, ou de manière équivalente, la quantité d’information qu’elle contient.

L’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. On remarque 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 le descendant d’aucun mot de code (considérez l’arbre du code ${10, 11}$ ) !

Borne inférieure pour L

Considérons maintenant la longueur attendue d’un mot de code

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

Nous allons montrer que l’entropie est une borne inférieure pour $L$ , c’est-à-dire

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

Démonstration :

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ù l’inégalité finale est due à 1) la divergence 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}$ , alors $L = H (X)$ , le minimum théorique. La raison pour laquelle nous ne pouvons pas toujours l’atteindre est que $- lo g p_{i}$ n’est pas nécessairement un entier, ce qui est évidemment requis.

Une borne supérieure pour L

Remarquez qu’il est possible de construire un code 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 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$ , on obtient

- \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 sous forme de code préfixe.

Références

Cours Alon Orlitsky ECE 255A, UCSD
Cover, T. M., & Thomas, J. A. (2006). Éléments de théorie de l’information. Wiley-Interscience.

←

Modèles de Mélange Gaussien Interactifs