Divergence de Kullback-Leibler
En théorie des probabilités et en théorie de l'information, la divergence de Kullback-Leibler (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, 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. Considérons deux distributions de probabilités P et 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-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. Il existe plusieurs définitions selon les hypothèses sur les distributions de probabilités. 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 où P(x) est 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 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 et , on pose alors sous réserve que la quantité de droite existe. Si P est absolument continue par rapport à Q, (ce qui est nécessaire si est finie) alors est la dérivée de Radon-Nikodym de P par rapport à Q et on obtient où l'on reconnait l'entropie de P par rapport à Q.