Divergence de Kullback-Leibler

En théorie des probabilités et en théorie de l'information, la divergence de Kullback-Leibler^{[1], [2]} (ou divergence K-L ou encore entropie relative) est une mesure de dissimilarité entre deux distributions de probabilités P et Q. Elle doit son nom à Solomon Kullback (en) et Richard Leibler (en), deux cryptanalystes américains. Selon la NSA, c'est durant les années 50, alors qu'ils travaillaient pour cette agence, que Kullback et Leibler ont inventé cette mesure. Elle aurait d'ailleurs servi à la NSA dans son effort de cryptanalyse pour le projet VENONA.

Cette mesure s'interprète comme la différence moyenne du nombre de bits nécessaires au codage d'échantillons de P selon que le codage est choisi optimal pour la distribution P ou Q. Typiquement, P représente les données, les observations, ou une distribution de probabilités calculée avec précision. La distribution Q représente typiquement une théorie, un modèle, une description ou une approximation de P.

La divergence de Kullback-Leibler entre dans la catégorie plus large des f-divergences, introduite indépendamment par Csiszár^[3] en 1967 et par Ali et Silvey ^[4] en 1966. Bien que perçue souvent comme une distance, elle n'en remplit pas les conditions : elle n'est pas symétrique et ne respecte pas l'inégalité triangulaire.

Définition

Pour deux distributions de probabilités discrètes P et Q la divergence de Kullback–Leibler de Q par rapport à P est définie par

$D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)} \!$

Pour des distributions P et Q continues on utilise une intégrale

$D_{\mathrm{KL}}(P\|Q) = \int_{-\infty}^{\infty} p(x) \log \frac{p(x)}{q(x)} \; dx \!$

où p et q sont les densités respectives de P et Q.

On peut généraliser les deux cas particuliers ci-dessus en considérant P et Q deux mesures définies sur un ensemble X, absolument continues par rapport à une mesure μ : le théorème de Radon-Nikodym-Lebesgue assure l'existence des densités p et q avec dP = pdμ et dQ = qdμ, on pose alors

$D_{\mathrm{KL}}(P\|Q) = \int_X p \log \frac{p}{q} \;d\mu \!$

sous réserve que la quantité de droite existe. Si P est absolument continue par rapport à Q, (ce qui est nécessaire si $D_{\mathrm{KL}}(P\|Q)$ est finie) alors $\frac{p}{q} = \frac{dP}{dQ}$ est la dérivée de Radon-Nikodym de P par rapport à Q et on obtient

$D_{\mathrm{KL}}(P\|Q) = \int_X \log \frac{dP}{dQ} \; dP = \int_X \frac{dP}{dQ} \log\frac{dP}{dQ}\; dQ\,\!$,

où l'on reconnait l'entropie de P par rapport à Q.

De même, si Q est absolument continue par rapport à P, on a

$D_{\mathrm{KL}}(P\|Q) = -\int_X \log \frac{d Q}{d P} \; dP \!$

Dans les deux cas, on constate que la divergence de Kullback-Leibler ne dépend pas de la mesure μ

Lorsque les logarithmes de ces formules sont pris en base 2 l'information est mesurée en bits; lorsque la base est e, l'unité est le nat.

Propriétés

• $D_{\mathrm{KL}}(P\|Q) \ge 0$

• P = Q ssi $D_{\mathrm{KL}}(P\|Q) = 0$

Démonstration (cas discret)

$D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)} = - \sum_i P(i) \log \frac{Q(i)}{P(i)} \!$

Or le logarithme est strictement concave, d'où :

$\sum_i P(i) \log \frac{Q(i)}{P(i)} \le \log \left( \sum_i P(i) \frac{Q(i)}{P(i)} \right) = \log \sum_i Q(i) = \log ( 1 ) = 0 \!$

Avec égalité ssi $\frac{Q(i)}{P(i)}$ est constant. (à cause de la stricte concavité) Dans ce cas-là, la constante ne peut qu'être égale à 1 puisque les deux fonctions P et Q sont des probabilités.

D'où les propriétés.

 

• Additivité. Soit deux distributions séparables P₁₂(x₁,x₂) = P₁(x₁).P₂(x₂) et Q₁₂(x₁,x₂) = Q₁(x₁).Q₂(x₂)

$D(P_{12}\|Q_{12})=D(P_1\|Q_1)+ D(P_2\|Q_2)$

• Dans le formalisme de la géométrie de l'information développé par S.Amari^[5], la divergence de Kullback-Leibler est la divergence associée à deux connexions affines duales fondamentales : la connexion m (mélange, combinaison additive des distributions) et la connexion e (exponentielle, combinaison multiplicative des distributions). La divergence de Kullback-Leibler obéit localement à la métrique de Fisher et correspond à l'intégration de la distance entre deux points (distributions) le long d'une géodésique de type e ou m (selon que l'on considère un sens ou l'autre : $D(P\|Q)$ ou $D(Q\|P)$).
• La distance symétrique (induite par la connexion de Levi-Civita, autoduale) associée à la métrique de Fisher est la distance de Hellinger.

$D_H(P\|Q)=2\sum_i\left( \sqrt{P_i} - \sqrt{Q_i} \right)^2.$

Références

1. ↑ (en) S. Kullback, R. Leibler, « On information and sufficiency », dans Annals of Mathematical Statistics (en), vol. 22, 1951, p. 79-86 
2. ↑ (en) S. Kullback, Information theory and statistics, John Wiley and Sons, NY, 1959 
3. ↑ (en) I. Csiszár, « Information-type measures of difference of probability distributions and indirect observation », dans Studia Sci. Math. Hungar., vol. 2, 1967, p. 229-318 
4. ↑ (en) M. S. Ali, D. Silvey, « A general class of coefficients of divergence of one distribution from another », dans Journal of the Royal Statistical Society (en), Ser. B, vol. 28, 1967, p. 131-140 
5. ↑ (en) Sunichi Amari et Hiroshi Nagaoka, Methods of information geometry, vol. 191, American Mathematical Society, 2000 .