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

Considérons deux distributions de probabilités P et 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 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 la divergence de Kullback–Leibler de P par rapport à Q 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.

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.

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 {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 {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 e, l'unité est le nat.

Exemple

Kullback donne l'exemple suivant (Table 2.1, Example 2.1). Soit P et Q les distributions donnés 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 N = 2 et p = 0.4. Q est la distribution de la partie droite de la figure, une distribution uniforme discrète avec trois valeurs x = 0, 1, or 2, chacune de probabilité p = 1/3.

	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{aligned}D_{\text{KL}}(Q\parallel P)&=\sum _{i}Q(i)\ln \left({\frac {Q(i)}{P(i)}}\right)\\[6pt]&=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)\\[6pt]&=-0.02596+(-0.12176)+0.24408\\[6pt]&=0.09637\end{aligned}}$

Propriétés

• $D_{\mathrm {KL} }(P\|Q)\geq 0$
• $P\;{\stackrel {p.s.}{=}}\;Q$ ssi $D_{\mathrm {KL} }(P\|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}\|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.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\|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}.$

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. Grâce à cette appartenance à cette famille, elle respecte d'importantes 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.