Divergence de Kullback-Leibler

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 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.

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.

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[3] en 1967 et par Ali et Silvey [4] en 1966. Grâce à cette appartenance à cette famille, elle respecte d'importantes propriétés de conservation de l'information : invariance, monotonicité [5].

De manière complémentaire, la divergence de Kullback-Leibler est également une divergence de Bregman [6], 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.

Définition[modifier | modifier le code]

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 \!

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 \mu : le théorème de Radon-Nikodym-Lebesgue assure l'existence des densités p et q avec dP =  p d\mu et dQ = q d\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{d Q}{d P} \; 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.

Propriétés[modifier | modifier le code]

  • D_{\mathrm{KL}}(P\|Q) \ge 0
  • P=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.Amari[7], 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[modifier | modifier le code]

  1. (en) S. Kullback, R. Leibler, « On information and sufficiency », Annals of Mathematical Statistics, 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 », 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 », Journal of the Royal Statistical Society, Ser. B, vol. 28,‎ 1967, p. 131-140
  5. S.I Amari, Information geometry in optimization, machine learning and statistical inference, Front. Electr. Electon. Eng. China, Vol. 5(3): 241--260, 2010.
  6. 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(3): 200--217, 1967.
  7. (en) Sunichi Amari et Hiroshi Nagaoka, Methods of information geometry, vol. 191, American Mathematical Society,‎ 2000.