Divergence De Kullback-Leibler

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 P et Q. Elle doit son nom à Solomon Kullback et Richard Leibler, deux cryptanalystes américains ^[3][4].

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.

La divergence de Kullback-Leiber entre dans la catégorie plus large des f-divergences, introduite indépendamment par Csiszár^[5] en 1967 et par Ali et Silvey ^[6] en 1966. Bien que souvent considérée comme une distance, elle n'en remplit pas tous les axiomes : elle n'est pas symétrique et ne respecte pas l'inégalité triangulaire.

Définition

Pour deux distributions de probabilités discrètes P et Q la divergence de Kullback–Leiber 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 \!$

où 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 μ : le Théorème de Radon-Nikodym-Lebesgue assure l'existence des densités p et q avec dP = pdμ et dQ = qdμ, 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 μ

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

Références

1. ↑ S. Kullback and R. Leiber, « On information and sufficiency », dans 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. ↑ Dr. Solomon Kullback sur www.nsa.gov
4. ↑ Dr. Richard Leiber sur www.nsa.gov
5. ↑ I. Csiszár, « Information-type measures of difference of probability distributions and indirect observation », dans Studia Sci. Math. Hungar., vol. 2, 1967, p. pp. 229-318 
6. ↑ M. S. Ali and D. Silvey, « A general class of coefficients of divergence of one distribution from another », dans Journal of the Royal Statistical Society, Ser. B, vol. 28, 1967, p. 131-140 

Ce document provient de « Divergence de Kullback-Leibler ».