Dlaczego rozbieżność KL jest nieujemna?

18

Dlaczego dywergencja KL nie jest ujemna?

Z punktu widzenia teorii informacji rozumiem tak intuicyjnie:

Powiedzmy, że istnieją dwa zespoły A i B które składają się z tego samego zestawu elementów oznaczonych x . p(x) i q(x) są różne rozkłady prawdopodobieństwa ponad zespołem A i B , odpowiednio.

Z punktu widzenia teorii informacji log2(P(x)) jest najmniejsza ilość bitów wymaganych dla nagrywania elementu x na zespół A . Tak więc oczekiwanie

xensemblep(x)ln(p(x))
może być interpretowane jako co najmniej ile bitów potrzebujemy średnio do zarejestrowania elementu w A

Ponieważ ta formuła nakłada dolną granicę na potrzebne bity średnio, tak że dla innego zbioru który powoduje inny rozkład prawdopodobieństwa q ( x ) , granica, którą daje dla każdego elementu x , z pewnością nie będzie go bitować podane przez p ( x ) , co oznacza przyjęcie oczekiwań, x e n s e m b l e - p ( x ) ln ( q ( x ) )Bq(x)xp(x)

xensemblep(x)ln(q(x))
ta średnia długość z pewnością będzie większa niż poprzednia, co prowadzi do
Nie umieszczamtutaj, ponieważp(x)iq(x)są różne.
xensemblep(x)ln(p(x))ln(q(x))>0
p(x)q(x)

Takie jest moje intuicyjne rozumienie, czy istnieje czysto matematyczny sposób wykazania, że ​​rozbieżność KL jest nieujemna? Problem można określić jako:

Biorąc pod uwagę, że i q ( x ) są dodatnie w stosunku do linii rzeczywistej, a + - p ( x ) d x = 1 , + - q ( x ) d x = 1 . Wykazać + - p ( x ) ln p ( x )p(x)q(x)+p(x)dx=1+q(x)dx=1 jest nieujemne.

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

Jak można to udowodnić? Czy można to udowodnić bez dodatkowych warunków?

meTchaikovsky
źródło
1
Jeśli rozumiesz dowód nierówności Fano, łatwo jest wywnioskować nieegatywność względnej entropii.
Lerner Zhang

Odpowiedzi:

30

Dowód 1:

lnaa1a>0

DKL(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

Nie uwzględniam tego jako osobnego dowodu, ponieważ jeśli poprosisz mnie o udowodnienie nierówności Gibbsa, musiałbym zacząć od braku negatywności rozbieżności KL i zrobić ten sam dowód od góry.


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

Then we can show that 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.
źródło