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]

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

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 $\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}}\;\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 {KL} }(P\|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 {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

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

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.

{\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é: $D_{\mathrm {KL} }(P\|Q)\geq 0$
Égalité presque sûre: $P\;{\stackrel {p.s.}{=}}\;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ù, en utilisant l' Inégalité de Jensen:

\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 ${\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 $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.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)$ ).^{[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 $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 $\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.

Notes et références

↑ Kullback et Leibler 1951.
↑ Kullback 1959.
↑ MacKay, David J.C., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, First éd. (ISBN 9780521642989, lire en ligne), p. 34
↑ S. Kullback, Information Theory and Statistics, John Wiley & Sons, 1959. Republished by Dover Publications in 1968; reprinted in 1978: (ISBN 0-8446-5625-9).
↑ Amari et Nagaoka 2000.
↑ Csiszár 1967.
↑ Ali et Silvey 1967.
↑ Amari 2010.
↑ Bregman 1967.

Annexes

Bibliographie

[Ali et Silvey 1967] (en) M. S. Ali et D. Silvey, « A general class of coefficients of divergence of one distribution from another », Journal of the Royal Statistical Society, Ser. B, vol. 28,‎ 1967, p. 131-140.
[Amari et Nagaoka 2000] (en) Sunichi Amari et Hiroshi Nagaoka, Methods of information geometry, vol. 191, American Mathematical Society, 2000.
[Amari 2010] (en) Sunichi Amari, « Information geometry in optimization, machine learning and statistical inference », Frontiers of Electrical and Electronic Engineering in China, SP Higher Education Press, vol. 5, n^o 3,‎ septembre 2010, p. 241–260 (DOI 10.1007/s11460-010-0101-3).
[Bregman 1967] (en) L. Bregman, « The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming », USSR Computational Mathematics and Mathematical Physics, vol. 7, n^o 3,‎ 1967, p. 200–217 (DOI 10.1016/0041-5553(67)90040-7).
[Csiszár] (en) I. Csiszár, « Information-type measures of difference of probability distributions and indirect observation », Studia Sci. Math. Hungar., vol. 2,‎ 1967, p. 229-318.
[Kullback et Leibler 1951] (en) S. Kullback et R. Leibler, « On information and sufficiency », Annals of Mathematical Statistics, vol. 22,‎ 1951, p. 79-86.
[Kullback 1959] (en) S. Kullback, Information theory and statistics, New York, John Wiley and Sons, 1959.

Voir aussi

[KullbackLeibler1951-1] Kullback et Leibler 1951.

[Kullback1959-2] Kullback 1959.

[MacKey2003-3] MacKay, David J.C., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, First éd. (ISBN 9780521642989, lire en ligne), p. 34

[Kullback-4] S. Kullback, Information Theory and Statistics, John Wiley & Sons, 1959. Republished by Dover Publications in 1968; reprinted in 1978: (ISBN 0-8446-5625-9).

[AmariNagaoka2000-5] Amari et Nagaoka 2000.

[Csiszár1967-6] Csiszár 1967.

[AliSilvey1967-7] Ali et Silvey 1967.

[Amari2010-8] Amari 2010.

[Bregman1967-9] Bregman 1967.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]