Mengapa divergensi KL adalah non-negatif?

18

Mengapa divergensi KL non-negatif?

Dari perspektif teori informasi, saya memiliki pemahaman yang intuitif:

Katakanlah ada dua ansambel A dan B yang terdiri dari himpunan elemen yang sama dengan label x . p(x) dan q(x) adalah distribusi probabilitas yang berbeda atas masing-masing ensemble A dan B

Dari perspektif teori informasi, adalah sedikitnya jumlah bit yang diperlukan untuk merekam elemen x untuk ensemble A . Sehingga harapan Σ x e n s e m b l e - p ( x ) ln ( p ( x ) ) dapat diartikan sebagai setidaknya berapa banyak bit yang kita butuhkan untuk merekam elemen di A rata-rata.log2(P(x))xA

xensemblep(x)ln(p(x))
A

Karena rumus ini menempatkan batas bawah pada bit yang kita butuhkan rata-rata, sehingga untuk ansambel yang berbeda yang menghasilkan distribusi probabilitas q yang berbeda ( x ) , batasan yang diberikannya untuk setiap elemen x pasti tidak akan menggigit yang diberikan oleh p ( x ) , yang berarti mengambil ekspektasi, x e n s e m b l e - p ( x ) ln ( q ( x ) )Bq(x)xp(x)

xensemblep(x)ln(q(x))
Rata-rata lama ini pasti akan lebih besar dari yang pertama satu, yang mengarah ke
Saya tidak menaruh≥ disini karenap(x)danq(x)berbeda.
xensemblep(x)ln(p(x))ln(q(x))>0
p(x)q(x)

Ini adalah pemahaman intuitif saya, apakah ada cara yang murni matematis untuk membuktikan perbedaan KL adalah non-negatif? Masalahnya dapat dinyatakan sebagai:

Diberikan dan q ( x ) keduanya positif atas garis nyata, dan + - p ( x ) d x = 1 , + - q ( x ) d x = 1 . Buktikan + - p ( x ) ln p ( x )p(x)q(x)+p(x)dx=1+q(x)dx=1 adalah non-negatif.

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

Bagaimana ini bisa dibuktikan? Atau dapatkah ini dibuktikan tanpa syarat tambahan?

meTchaikovsky
sumber
1
Jika Anda memahami bukti ketidaksamaan Fano, mudah untuk mendapatkan nonnegativitas dari entropi relatif.
Lerner Zhang

Jawaban:

30

Bukti 1:

dalamSebuahSebuah-1Sebuah>0

-DKL.(hal||q)0DKL.(hal||q)0

-D(hal||q)=-xhal(x)dalamhal(x)q(x)=xhal(x)dalamq(x)hal(x)(Sebuah)xhal(x)(q(x)hal(x)-1)=xq(x)-xhal(x)=1-1=0

Untuk ketidaksetaraan (a) kami menggunakan dalam ketimpangan dijelaskan di awal.

Alternatively you can start with Gibbs' inequality which states:

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

Then if we bring the left term to the right we get:

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

The reason I am not including this as a separate proof is because if you were to ask me to prove Gibbs' inequality, I would have to start from the non-negativity of KL divergence and do the same proof from the top.


Proof 2: We use the Log sum inequality:

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.
sumber