Por que a divergência KL não é negativa?

18

Por que a divergência KL não é negativa?

Da perspectiva da teoria da informação, tenho uma compreensão tão intuitiva:

Digamos que existem dois conjuntos A e B que são compostos do mesmo conjunto de elementos rotulados por x . p(x) e q(x) são distribuições de probabilidade diferentes sobre o conjunto A e B respectivamente.

Do ponto de vista da teoria da informação, log2(P(x)) é a menor quantidade de bits requerida para que a gravação de um elemento x para ensemble A . De modo que a expectativa

xensemblep(x)ln(p(x))
pode ser interpretada como, pelo menos quantos bits que é necessário para a gravação de um elemento em A em média.

Como essa fórmula coloca um limite inferior nos bits de que precisamos, em média, de modo que, para um conjunto diferente B que gera uma distribuição de probabilidade diferente q(x) , o limite que ele fornece para cada elemento x certamente não irá morder. dada por p(x) , o que significa tomar a expectativa,

xensemblep(x)ln(q(x))
este comprimento médio será certamente maior do que o anterior, o que leva a
Eu não coloqueiaqui, poisp(x)eq(x)são diferentes.
xensemblep(x)ln(p(x))ln(q(x))>0
p(x)q(x)

Esta é a minha compreensão intuitiva, existe uma maneira puramente matemática de provar que a divergência de KL não é negativa? O problema pode ser afirmado como:

Dado que e q ( x ) são positivos acima da linha real, e + - p ( x ) d x = 1 , + - q ( x ) d x = 1 . Prove + - p ( x ) ln p ( x )p(x)q(x)+p(x)dx=1+q(x)dx=1 não é negativo.

+p(x)lnp(x)q(x)

Como isso pode ser provado? Ou isso pode ser provado sem condições extras?

meTchaikovsky
fonte
1
Se você entende a prova da desigualdade de Fano , é fácil derivar a não-negatividade da entropia relativa.
Lerner Zhang

Respostas:

29

Prova 1:

Primeira nota que para todos a > 0 .lnaa1a>0

Agora mostraremos que que significa que D K L ( p | | q ) 0DKL(p||q)0DKL(p||q)0

D(p||q)=xp(x)lnp(x)q(x)=xp(x)lnq(x)p(x)(a)xp(x)(q(x)p(x)1)=xq(x)xp(x)=11=0

ln

xp(x)log2p(x)xp(x)log2q(x)

xp(x)log2p(x)xp(x)log2q(x)0xp(x)log2p(x)q(x)0

A razão pela qual não incluo isso como uma prova separada é porque, se você me pedisse para provar a desigualdade de Gibbs, teria que começar pela não-negatividade da divergência de KL e fazer a mesma prova do topo.


i=1nailog2aibi(i=1nai)log2i=1naii=1nbi

DKL(p||q)0

D(p||q)=xp(x)log2p(x)q(x)(b)(xp(x))log2xp(x)xq(x)=1log211=0

where we have used the Log sum inequality at (b).


Proof 3:

(Taken from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas)

D(p||q)=xp(x)log2p(x)q(x)=xp(x)log2q(x)p(x)(c)log2xp(x)q(x)p(x)=log21=0

where at (c) we have used Jensen's inequality and the fact that log is a concave function.

Andreas G.
fonte