Divergence de Kullback-Leibler

En théorie des probabilités et en théorie de l'information, la divergence de Kullback-LeiblerModèle:SfnModèle:,Modèle:Sfn (ou divergence K-L ou encore entropie relative) est une mesure de dissimilarité entre deux distributions de probabilités. Elle doit son nom à Solomon Kullback et Richard Leibler, deux cryptanalystes américains. Selon la NSAModèle:Refnec, c'est durant les années 1950, 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.

Introduction et contexte

On considère deux distributions de probabilités, notées P et Q. Typiquement, P représente les données, les observations, ou une distribution de probabilités calculée avec précision, tandis que la distribution Q représente typiquement une théorie, un modèle, une description ou une approximation de P. La divergence de Kullback-Leibler s'interprète comme la différence moyenne du nombre de bits nécessaires au codage d'échantillons de P en utilisant un code optimisé pour Q plutôt que le code optimisé pour P.

Définition

Il existe plusieurs définitions selon les hypothèses sur les distributions de probabilités.

Premières définitions

Pour deux distributions de probabilités discrètes P et Q sur un ensemble X. La divergence de Kullback–Leibler de P par rapport à Q est définie par

$D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=\sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)}$

où P(x) et Q(x) sont les valeurs respectives en x des fonctions de masse pour P et Q. En d'autres termes, la divergence de Kullback-Leibler est l'espérance de la différence des logarithmes de P et Q, en prenant la probabilité P pour calculer l'espérance.

Pour des distributions P et Q continues de densités respectives p et q, on utilise une intégrale

$D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}p(x)\log \frac{p(x)}{q(x)}\mathrm{d}x$.

Définitions générales

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 $\mu$ : le théorème de Radon-Nikodym-Lebesgue assure l'existence des densités p et q avec $dP=pd\mu$ et $dQ=qd\mu$, on pose alors

$D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=\underset{X}{\int }p\log \frac{p}{q}\mathrm{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{K}\mathrm{L}}(P\Vert Q)$ est finie) alors $\frac{p}{q}=\frac{\mathrm{d}P}{\mathrm{d}Q}$ est la dérivée de Radon-Nikodym de P par rapport à Q et on obtient

$D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=\underset{X}{\int }\log \frac{\mathrm{d}P}{\mathrm{d}Q}\mathrm{d}P=\underset{X}{\int }\frac{\mathrm{d}P}{\mathrm{d}Q}\log \frac{\mathrm{d}P}{\mathrm{d}Q}\mathrm{d}Q$,

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{K}\mathrm{L}}(P\Vert Q)=-\underset{X}{\int }\log \frac{dQ}{dP}dP$

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

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

Exemple

Two distributions to illustrate Kullback–Leibler divergence

Kullback donne l'exemple suivant (Table 2.1, Example 2.1). Soit P et Q les distributions données dans la table et la figure. P est la distribution sur la partie gauche de la figure, il s'agit d'une distribution binomiale avec Modèle:Nobr et Modèle:Nobr. Q est la distribution de la partie droite de la figure, une distribution uniforme discrète avec trois valeurs Modèle:Nobr, chacune de probabilité Modèle:Nobr.

Le tableau suivant donne les fonctions de masse des distributions P et Q. Par exemple, pour la distribution P, la probabilité d'avoir la valeur 1 est 0,48.

	0	1	2
Distribution P	0,36	0,48	0,16
Distribution Q	0,333	0,333	0,333

La divergence KL est calculée comme suit. On utilise le logarithme naturel.

$\begin{array}{cc}{D}_{\text{KL}}(Q\parallel P)& =\sum _{x\in X}Q(x)\ln \left(\frac{Q(x)}{P(x)}\right)\\ & =0,333\ln \left(\frac{0,333}{0,36}\right)+0,333\ln \left(\frac{0,333}{0,48}\right)+0,333\ln \left(\frac{0,333}{0,16}\right)\\ & =-0,02596+(-0,12176)+0,24408\\ & =0,09637\end{array}$

Propriétés

Positivité

$D_{\mathrm{K}\mathrm{L}}(P\Vert Q)\ge 0$

Égalité presque sûre

$P\stackrel{p.s.}{=}Q$ ssi $D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=0$

Additivité

Soit deux distributions séparables $P_{12}(x_1,x_2)=P_1(x_1).P_2(x_2)$ et $Q_{12}(x_1,x_2)=Q_1(x_1).Q_2(x_2)$

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

• Dans le formalisme de la géométrie de l'information développé par S.AmariModèle:Sfn, 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\Vert Q)$ ou $D(Q\Vert P)$).Modèle:Cn
• 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\Vert Q)=2\sum _i{(\sqrt{P_i}-\sqrt{Q_i})}^2.$

Discussion

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.

La divergence de Kullback-Leibler entre dans la catégorie plus large des f-divergences, introduite indépendamment par CsiszárModèle:Sfn en 1967 et par Ali et SilveyModèle:Sfn en 1966. Par son appartenance à cette famille, elle respecte des propriétés de conservation de l'information : invariance, monotonicitéModèle:Sfn.

De manière complémentaire, la divergence de Kullback-Leibler est également une divergence de BregmanModèle:Sfn, associée à la fonction potentiel $\psi (x)=x\log x-x$. La conséquence est que cette divergence, par transformation de Legendre de $\psi$ est associée à un couple dual de système de coordonnées $(x,\log x)$ permettant de représenter les distributions de la famille exponentielle.

Annexes

Bibliographie

• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.

Voir aussi

• Distance en variation totale (probabilités)
• Distance de Hellinger
• Distance de Bhattacharyya