Intuisi pada Divergensi Kullback-Leibler (KL)

47

Saya telah belajar tentang intuisi di balik KL Divergence karena seberapa banyak fungsi distribusi model berbeda dari distribusi teoritis / benar data. Sumber saya membaca selanjutnya mengatakan bahwa pemahaman intuitif 'jarak' antara dua distribusi ini sangat membantu, tetapi tidak harus diambil secara harfiah karena selama dua distribusi P dan Q , KL Divergence tidak simetris di P dan Q .

Saya tidak yakin bagaimana memahami pernyataan terakhir, atau inikah intuisi 'jarak' rusak?

Saya akan menghargai contoh sederhana, tetapi berwawasan luas.

cgo
sumber
3
Saya pikir Anda harus melangkah mundur dan memahami bahwa Anda biasanya memiliki asimetri dalam statistik antara distribusi populasi yang benar dan sampel (atau true dan model) dll, dan inilah yang dicerminkan oleh KL Divergence ... Dalam teori probabilitas umum, tidak ada perbedaan itu biasanya dan metrik simetris lebih masuk akal
seanv507
1
"Sumber" mana yang Anda baca?
1818

Jawaban:

34

Jarak (metrik) D harus simetris, yaitu D(P,Q)=D(Q,P) . Tapi, dari definisi, KL tidak.

Contoh: Ω={A,B} , P(A)=0.2,P(B)=0.8 , Q(A)=Q(B)=0.5 .

Kita punya:

KL(P,Q)=P(A)logP(A)Q(A)+P(B)logP(B)Q(B)0.19

dan

KL(Q,P)=Q(A)logQ(A)P(A)+Q(B)logQ(B)P(B)0.22

sehingga dan oleh karena itu K L bukan (metrik) jarak.KL(P,Q)KL(Q,P)KL

mik
sumber
50

Menambah jawaban luar biasa lainnya, jawaban dengan sudut pandang lain yang mungkin dapat menambahkan lebih banyak intuisi, yang diminta.

Divergensi Kullback-Leibler adalah Jika Anda memiliki dua hipotesis mengenai distribusi mana yang menghasilkan data X , P dan Q , maka p ( x )

KL(P||Q)=p(x)logp(x)q(x)dx
XPQ adalah rasio kemungkinan untuk mengujiH0:QmelawanH1:P. Kita melihat bahwa divergensi Kullback-Leibler di atas adalah nilai yang diharapkan dari rasio loglikelihood di bawah hipotesis alternatif. Jadi,KL(P||Q)adalah ukuran dari kesulitan masalah tes ini, ketikaQadalah hipotesis nol. Jadi asimetriKL(P||Q)KL(Q||P)p(x)q(x)H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P) hanya mencerminkan asimetri antara hipotesis nol dan alternatif.

Mari kita lihat ini dalam contoh khusus. Misalkan adalah distribusi t ν dan Q distribusi normal standar (dalam contoh numerik di bawah ν = 1 ). Integral mendefinisikan divergensi terlihat rumit, jadi mari kita gunakan integrasi numerik di R:PtνQν=1

> lLR_1  <-  function(x) {dt(x, 1, log=TRUE)-dnorm(x, log=TRUE)}  
> integrate(function(x) dt(x, 1)*lLR_1(x), lower=-Inf, upper=Inf)
Error in integrate(function(x) dt(x, 1) * lLR_1(x), lower = -Inf, upper = Inf) : 
  the integral is probably divergent

> lLR_2  <-  function(x) {-dt(x, 1, log=TRUE)+dnorm(x, log=TRUE)}  
> integrate(function(x) dnorm(x)*lLR_2(x), lower=-Inf, upper=Inf)
0.2592445 with absolute error < 1e-07

Dalam kasus pertama integral tampaknya berbeda secara numerik, menunjukkan divergensi sangat besar atau tidak terbatas, dalam kasus kedua itu kecil, meringkas:

KL(P||Q)KL(Q||P)0.26

t1t1t1t1n=1t1! Beralih peran, bukan, perbedaannya sebagian besar berasal dari peran outlier.

t1t1

Ini terkait dengan jawaban saya di sini: Mengapa kita harus menggunakan kesalahan alih-alih kesalahan normal?

kjetil b halvorsen
sumber
22

D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
D(P||Q)=ipilog(piqi)
SKL(P,Q)=i(piqi)log(piqi)

D(A||B)=0.1log(0.10.2)+0.9log(0.90.8)0.0159
D(B||C)0.0112
D(A||C)0.0505
0.0159+0.01120.0505
SKL(A,B)0.0352
SKL(B,C)0.0234
SKL(A,C)0.1173
0.0352+0.02340.1173

Saya memperkenalkan contoh ini dengan sengaja. Bayangkan Anda melempar koin, misalnya 100 kali. Selama koin ini tidak bias, Anda cukup menyandikan hasil lemparan dengan urutan 0-1 bit, (1-kepala, 0-ekor). Dalam situasi seperti itu ketika probabilitas kepala sama dengan probabilitas ekor dan sama dengan 0,5, itu adalah pengkodean yang cukup efektif. Sekarang, kami memiliki beberapa koin bias, jadi kami lebih suka mengkodekan hasil yang lebih mungkin dengan kode lebih pendek, misalnya menggabungkan kelompok kepala dan ekor dan mewakili urutan kepala k dengan kode yang lebih panjang daripada urutan ekor k (mereka lebih mungkin). Dan di sini terjadi Kullback-Leibler divergence . Jika P mewakili distribusi hasil yang benar, dan Q hanya merupakan perkiraan dari P, makaD(P||Q)D(P||Q) menunjukkan penalti yang Anda bayar ketika Anda menyandikan hasil yang sebenarnya berasal dari P distrib dengan pengkodean yang ditujukan untuk Q (penalti dalam arti bit tambahan yang perlu Anda gunakan).

Jika Anda hanya membutuhkan metrik, gunakan jarak Bhattacharyya (tentu saja versi yang dimodifikasi )1[xp(x)q(x)]

Adam Przedniczek
sumber
7
Jika seseorang khawatir benar-benar memiliki metrik dengan koneksi yang lebih dekat ke divergensi KL, mereka mungkin mempertimbangkan akar kuadrat dari divergensi Jensen-Shannon sebagai ganti Bhattacharyya.
kardinal
5

Saya tergoda di sini untuk memberikan jawaban yang murni intuitif untuk pertanyaan Anda. Mengulangi apa yang Anda katakan, divergensi KL adalah cara untuk mengukur jarak antara dua distribusi karena Anda akan menghitung jarak antara dua set data dalam ruang Hilbert, tetapi harus berhati-hati.

Mengapa? Divergensi KL bukan jarak seperti yang biasanya Anda gunakan, seperti misalnya norma . Memang, itu positif dan sama dengan nol jika dan hanya jika dua distribusi itu sama (seperti dalam aksioma untuk mendefinisikan jarak). Tetapi seperti yang disebutkan, itu tidak simetris. Ada cara untuk menghindari ini, tetapi masuk akal untuk tidak simetris.L2

Memang, divergensi KL menentukan jarak antara distribusi model (yang Anda benar-benar tahu) dan yang teoritis sehingga masuk akal untuk menangani berbeda (jarak "teoritis" dari ke dengan asumsi model ) dan ("empiris" jarak ke dengan asumsi data ) karena mereka berarti ukuran yang sangat berbeda.QPKL(P,Q)PQPKL(Q,P)PQQ

meduz
sumber
4

Teori Informasi Elemen buku teks memberi kita contoh:

Sebagai contoh, jika kita tahu p distribusi sebenarnya dari variabel acak, kita bisa membuat kode dengan panjang deskripsi rata-rata H (p). Sebaliknya, jika kita menggunakan kode untuk distribusi q, kita akan membutuhkan rata-rata H (p) + D (p | | q) untuk menggambarkan variabel acak.

Untuk memparafrasekan pernyataan di atas, kita dapat mengatakan bahwa jika kita mengubah distribusi informasi (dari q ke p) kita memerlukan bit ekstra D (p || q) untuk mengkodekan distribusi yang baru.

Sebuah ilustrasi

Izinkan saya mengilustrasikan ini menggunakan satu aplikasi dalam pemrosesan bahasa alami.

Pertimbangkan bahwa sekelompok besar orang, berlabel B, adalah mediator dan masing-masing dari mereka diberi tugas untuk memilih kata benda dari turkey, animaldan bookdan mengirimkan ke C. Ada nama pria A yang dapat mengirimkan masing-masing email ke memberi mereka beberapa petunjuk. Jika tidak ada seorang pun di grup yang menerima email, mereka dapat mengangkat alis mereka dan ragu-ragu untuk sementara mempertimbangkan kebutuhan C. Dan probabilitas setiap opsi yang dipilih adalah 1/3. Distribusi yang benar-benar seragam (jika tidak, itu mungkin berhubungan dengan preferensi mereka sendiri dan kami mengabaikannya).

Tetapi jika mereka diberi kata kerja, seperti baste, 3/4 dari mereka dapat memilih turkeydan 3/16 memilih animaldan 1/16 memilih book. Lalu berapa banyak informasi dalam bit yang diperoleh masing-masing mediator setelah mereka tahu kata kerjanya? Ini:

D(p(nouns|baste)||p(nouns))=x{turkey,animal,book}p(x|baste)log2p(x|baste)p(x)=34log23413+316log231613+116log211613=0.5709  bits

Tapi bagaimana jika kata kerja yang diberikan adalah read? Kita dapat membayangkan bahwa mereka semua akan memilih booktanpa ragu-ragu , maka perolehan informasi rata-rata untuk setiap mediator dari kata kerja readadalah:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Kita dapat melihat bahwa kata kerjanya readdapat memberi lebih banyak informasi kepada para mediator. Dan itulah yang dapat diukur oleh entropi relatif.

Mari kita lanjutkan kisah kita. Jika C mencurigai bahwa kata benda itu mungkin salah karena A mengatakan kepadanya bahwa ia mungkin telah melakukan kesalahan dengan mengirimkan kata kerja yang salah ke mediator. Lalu berapa banyak informasi dalam bit yang dapat diberikan sepotong berita buruk seperti C?

1) jika kata kerja yang diberikan oleh A adalah baste:

D(p(nouns)||p(nouns|baste))=x{turkey,animal,book}p(x)log2p(x)p(x|baste)=13log21334+13log213316+13log213116=0.69172  bits

2) tetapi bagaimana jika kata kerjanya read?

D(p(nouns)||p(nouns|baste))=x{book,,}p(x)log2p(x)p(x|baste)=13log2131+13log2130+13log2130=  bits

Karena C tidak pernah tahu apa yang akan menjadi dua kata benda lainnya dan setiap kata dalam kosa kata akan mungkin.

Kita dapat melihat bahwa divergensi KL asimetris.

Saya harap saya benar, dan jika tidak tolong beri komentar dan bantu koreksi saya. Terima kasih sebelumnya.

Lerner Zhang
sumber