Introduction à la divergence de Kullback-Leibler

Définition

Cette divergence est une mesure de la dissimilarité entre deux lois de probabilités. Elle est classiquement définie pour deux distributions de probabilité P et Q (telles que P est absolument continue par rapport à Q)

Formula : $$KL(P,Q)= \int \log\left(\frac{dP}{dQ}\right) dP$$

L'intuition derrière est de quantifier l'espérance du nombre de bits supplémentaires nécessaires pour encoder (au sens de Huffman) un message provenant de la distribution Q sachant que l'on dispose d'un système de codage établi à partir de la distribution P.

Évidemment dans le cas discret l'écriture devient (avec la convention 0.log(0) = 0) et sous condition que Q(i)=0 => P(i)=0

Formula : $$KL(P,Q)= \sum_i P(i) \log\left( \frac{P(i)}{Q(i)} \right) $$

Ou encore dans le cas de lois de Bernouilli de paramètres p et q :

Formula : $$KL(P,Q)= p \log\left( \frac{p}{q}\right) + (1-p) \log\left( \frac{1-p}{1-q} \right) $$

Quelques propriétés

  • Toujours positive
  • P = Q si et seulement si KL(P,Q) = 0 (à condition que KL puisse être défini)
  • Pinsker : pour tout ensemble mesurable A :
    Formula : $$|P(A)-Q(A)| \leq \sqrt{\frac12 KL(P,Q)} $$
  • D'où il vient pour tous réels p, q dans [0,1] (pioché dans la thèse de S. Bubeck) :
    Formula : $$ 2(p-q)^2 \leq KL(p,q) \leq \frac{ (p-q)^2 }{q(1-q) } $$

Calcul

On peut essayer d'évaluer cette divergence en R pour la famille de lois suivantes partageant le même support. 

 
x <- seq(-5, 5, length=300)
y <- cbind(u=dunif(x,0,2), n1=dnorm(x), n2=dnorm(x,1), t=dt(x, df=10))
matplot(x,y,type="l")

R plot

KL <- function(p, q, seuil=1e-10 ) {
	step = 1/sum(p) 
	use <- (p>seuil) & (q>seuil) #pour éviter des pbms numériques 
	k <- sum( p[use] * log(p[use]/q[use]) )
	return( k * step )
	}

> KL(y[,"n1"] , y[,"n1"] )
[1] 0
> KL(y[,"n1"] , y[,"n2"] )
[1] 0.5
> KL(y[,"n1"] , y[,"t"] )
[1] 0.01119959

#Notons que KL(P,Q) != KL(Q,P)
> KL(y[,"t"] , y[,"n1"])
[1] 0.01805289

#Attention, les cas suivants ne sont pas corrects si on inverse P et Q (pourquoi ?)
> KL(y[,"u"] , y[,"n1"] )  
[1] 0.8968782
> KL(y[,"u"] , y[,"n2"] )
[1] 0.3935337

Exos

  • Tracer le graphe de l'aire utilisée dans le calcul.
  • Trouvez deux mesures telles que la fonction implémentée KL renvoie 0 mais avec P différent de Q.
  • Faites un graphique (ou une série de graphiques) illustrant l'encadrement de KL(P,Q) dans le cas des lois de bernouilli.
Design selector