Divergence de Kullback-Leibler

Un article de Wikipédia, l'encyclopédie libre.

En théorie des probabilités et en théorie de l'information, la divergence de Kullback-Leibler^[1] (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 ^[2]^[3].

Cette mesure s'interprète comme la difference moyenne le nombre de bits nécessaire 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épendament par Csiszár^[4] en 1967 et par Ali et Silvey ^[5] en 1966. Bien que souvent considérée comme une distance, elle n'en remplit pas tout les axiomes, notamment elle n'est pas symétrique.

[modifier] 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 $d P = p d μ$ et $d Q = q d μ$ , on pose alors

$D_{\mathrm{KL}}(P\|Q) = \int_X p \log \frac{p}{q} \;d\mu \!$

sous reserve que la quantité de droite existe. Si P est absolument continue par rapport à Q, (ce qui est nécéssaire si $D_{\mathrm{KL}}(P\|Q)$ est finie) alors $\frac{p}{q} = \frac{dP}{dQ}$ est la dérivé 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é en bits; lorsque la base est e, l'unités est le nats.

[modifier] Réferences

↑ S. Kullback and R. Leiber, « On information and sufficiency », dans Annals of Mathematical Statistics, 22, p. 79-86
↑ Dr. Solomon Kullback sur www.nsa.gov
↑ Dr. Richard Leiber sur www.nsa.gov
↑ I. Csiszár, « Information-type measures of difference of probability distributions and indirect observation », dans Studia Sci. Math. Hungar., 2, p. pp. 229-318
↑ 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, 28, p. 131-140