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

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,‎ , p. 79-86
  2. (en) S. Kullback, Information theory and statistics, John Wiley and Sons, NY,‎
  3. (en) I. Csiszár, « Information-type measures of difference of probability distributions and indirect observation », Studia Sci. Math. Hungar., vol. 2,‎ , 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,‎ , 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,‎ .