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. Elle doit son nom à Solomon Kullback et Richard Leibler, deux cryptanalystes américains. Selon la NSA^{[réf. nécessaire]}, 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^[3]

${\displaystyle D_{\mathrm {KL} }(P\|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

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{-\infty }^{\infty }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 ${\displaystyle \mu }$ : le théorème de Radon-Nikodym-Lebesgue assure l'existence des densités p et q avec ${\displaystyle dP=pd\mu }$ et ${\displaystyle dQ=qd\mu }$, on pose alors

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{X}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 ${\displaystyle D_{\mathrm {KL} }(P\|Q)}$ est finie) alors ${\displaystyle {\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

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{X}\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\;\mathrm {d} P=\int _{X}{\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

${\displaystyle 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 ${\displaystyle \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

Two distributions to illustrate Kullback–Leibler divergence

Kullback^[4] 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 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 ou 2, chacune de probabilité p = 1/3.

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.

${\displaystyle {\begin{aligned}D_{\text{KL}}(Q\parallel P)&=\sum _{x\in X}Q(x)\ln \left({\frac {Q(x)}{P(x)}}\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

Positivité

${\displaystyle D_{\mathrm {KL} }(P\|Q)\geq 0}$

Égalité presque sûre

${\displaystyle P\;{\stackrel {p.s.}{=}}\;Q}$ ssi ${\displaystyle D_{\mathrm {KL} }(P\|Q)=0}$

Démonstration (cas discret)

${\displaystyle 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ù, en utilisant l' Inégalité de Jensen:

${\displaystyle \sum _{i}P(i)\log {\frac {Q(i)}{P(i)}}\leq \log \left(\sum _{i}P(i){\frac {Q(i)}{P(i)}}\right)=\log \sum _{i}Q(i)=\log(1)=0\!}$

Avec égalité ssi ${\displaystyle {\frac {Q(i)}{P(i)}}}$ est constant presque partout. (à 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 ${\displaystyle P_{12}(x_{1},x_{2})=P_{1}(x_{1}).P_{2}(x_{2})}$ et ${\displaystyle Q_{12}(x_{1},x_{2})=Q_{1}(x_{1}).Q_{2}(x_{2})}$

${\displaystyle 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 : ${\displaystyle D(P\|Q)}$ ou ${\displaystyle D(Q\|P)}$).^{[citation nécessaire]}
• La distance symétrique (induite par la connexion de Levi-Civita, autoduale) associée à la métrique de Fisher est la distance de Hellinger ${\displaystyle 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ár^[6] en 1967 et par Ali et Silvey^[7] en 1966. Par son appartenance à cette famille, elle respecte des propriétés de conservation de l'information : invariance, monotonicité^[8].

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