Perkirakan divergensi Kullback Leibler (KL) dengan monte carlo

Saya ingin memperkirakan perbedaan KL antara dua distribusi kontinu f dan g. Namun, saya tidak bisa menuliskan kepadatan untuk f atau g. Saya dapat mengambil sampel dari kedua f dan g melalui beberapa metode (misalnya, rantai markov monte carlo).

Perbedaan KL dari f ke g didefinisikan seperti ini

$$D_{KL}(f || g) = \int_{-\infty}^{\infty} f(x) \log\left(\frac{f(x)}{g(x)}\right) dx$$

Ini adalah harapan dari berkenaan dengan f sehingga Anda dapat membayangkan beberapa perkiraan monte carlo$\log\left(\frac{f(x)}{g(x)}\right)$

$$\frac{1}{N}\sum_i^N \log\left(\frac{f(x_i)}{g(x_i)}\right)$$

Di mana saya mengindeks N sampel yang diambil dari f (yaitu untuk i = 1, ..., N)$x_i \sim f()$

Namun, karena saya tidak tahu f () dan g (), saya bahkan tidak bisa menggunakan estimasi monte carlo ini. Apa cara standar memperkirakan KL dalam situasi ini?

Suntingan: Saya TIDAK tahu kepadatan tidak normal untuk f () atau g ()

Saya berasumsi Anda dapat mengevaluasi dan hingga konstan normalisasi. Nyatakan dan .g f ( x ) = f u ( x ) / c f g ( x ) = g u ( x ) / c $f$$g$$f(x) = f_u(x)/c_f$$g(x) = g_u(x)/c_g$

Pengukur yang konsisten yang dapat digunakan adalah mana adalah penaksir pengambilan sampel penting untuk rasio . Di sini Anda menggunakan dan masing-masing sebagai densitas instrumental untuk dan , dan untuk menargetkan rasio log dari kepadatan yang tidak dinormalisasi. r = 1 /

$$\widehat{D_{KL}}(f || g) = \left[n^{-1} \sum_j f_u(x_j)/\pi_f(x_j)\right]^{-1}\frac{1}{N}\sum_i^N \left[\log\left(\frac{f_u(z_i)}{g_u(z_i)}\right)\frac{f_u(z_i)}{\pi_r(z_i)}\right] - \log (\hat{r})$$ cf/cgπfπgfuguπ $$\hat{r} = \frac{1/n}{1/n}\frac{\sum_j f_u(x_j)/\pi_f(x_j)}{\sum_j g_u(y_j)/\pi_g(y_j)} \tag{1}.$$ $c_f/c_g$$\pi_f$$\pi_g$$f_u$$g_u$$\pi_r$

Jadi, biarkan , , dan . Pembilang (1) konvergen ke . Penyebut konvergen ke . Rasio ini konsisten dengan teorema pemetaan kontinu. Log rasio konsisten dengan pemetaan berkelanjutan lagi. { y i } ∼ π g { z i } ∼ π r c f c $\{x_i\} \sim \pi_f$$\{y_i\} \sim \pi_g$$\{z_i\} \sim \pi_r$$c_f$$c_g$

Mengenai bagian lain dari estimator, berdasarkan hukum angka besar.

$$\frac{1}{N}\sum_i^N \left[\log\left(\frac{f_u(z_i)}{g_u(z_i)}\right)\frac{f_u(z_i)}{\pi_r(z_i)}\right] \overset{\text{as}}{\to} c_f E\left[ \log\left(\frac{f_u(z_i)}{g_u(z_i)}\right) \right]$$

Motivasi saya adalah sebagai berikut:

$$\begin{align*} D_{KL}(f || g) &= \int_{-\infty}^{\infty} f(x) \log\left(\frac{f(x)}{g(x)}\right) dx \\ &= \int_{-\infty}^{\infty} f(x)\left\{ \log \left[\frac{f_u(x)}{g_u(x)} \right] + \log \left[\frac{c_g}{c_f} \right]\right\} dx \\ &= E_f\left[\log \frac{f_u(x)}{g_u(x)} \right] + \log \left[\frac{c_g}{c_f} \right] \\ &= c_f^{-1} E_{\pi_r}\left[\log \frac{f_u(x)}{g_u(x)}\frac{f_u(x)}{\pi_r(x)} \right] + \log \left[\frac{c_g}{c_f} \right]. \end{align*}$$ Jadi saya memecahnya menjadi potongan-potongan yang bisa ditelusuri.

Untuk ide-ide lebih lanjut tentang cara mensimulasikan rasio likelhood, saya menemukan sebuah makalah yang memiliki beberapa: https://projecteuclid.org/download/pdf_1/euclid.aos/1031594732

Di sini saya berasumsi bahwa Anda hanya dapat mencicipi dari model; fungsi kepadatan yang tidak normal tidak tersedia.

Anda menulis itu

$$D_{KL}(f || g) = \int_{-\infty}^{\infty} f(x) \log\left(\underbrace{\frac{f(x)}{g(x)}}_{=: r}\right) dx,$$

di mana saya telah menetapkan rasio probabilitas menjadi . Alex Smola menulis, meskipun dalam konteks yang berbeda Anda dapat memperkirakan rasio ini "dengan mudah" hanya dengan melatih classifier. Mari kita asumsikan Anda telah memperoleh classifier , yang dapat memberi tahu Anda probabilitas bahwa observasi telah dihasilkan oleh . Perhatikan bahwa . Kemudian:$r$$p(f|x)$$x$$f$$p(g|x) = 1 - p(f|x)$

$$r = \frac{p(x|f)}{p(x|g)} \\ = \frac{p(f|x) {p(x) p(g)}}{p(g|x)p(x) p(f)} \\ = \frac{p(f|x)}{p(g|x)},$$

di mana langkah pertama adalah karena Bayes dan yang terakhir mengikuti dari asumsi bahwa .$p(g) = p(f)$

Mendapatkan penggolong seperti itu bisa sangat mudah karena dua alasan.

Pertama, Anda dapat melakukan pembaruan stokastik. Itu berarti bahwa jika Anda menggunakan pengoptimal berbasis gradien, seperti tipikal untuk regresi logistik atau jaringan saraf, Anda bisa menggambar sampel dari masing-masing dan dan membuat pembaruan.$f$$g$

Kedua, karena Anda memiliki data yang hampir tidak terbatas - Anda dapat mengambil sampel dan sampai mati - Anda tidak perlu khawatir tentang overfitting atau sejenisnya.$f$$g$

Selain metode klasifikasi probabilistik yang disebutkan oleh @bayerj, Anda juga dapat menggunakan batas bawah dari perbedaan KL yang diturunkan dalam [1-2]:

$$\mathrm{KL}[f \Vert g] \ge \sup_{T} \left\{ \mathbb{E}_{x\sim f}\left[ T(x) \right] - \mathbb{E}_{x\sim g} \left[ \exp \left( T(x) - 1 \right)\right] \right\},$$ mana adalah arbitrer fungsi. Dalam beberapa kondisi ringan, batasnya ketat untuk: $T:\mathcal{X}\to\mathbb{R}$ $$T(x) = 1 + \ln \left[ \frac{f(x)}{g(x)} \right]$$

Untuk memperkirakan divergensi KL antara dan , kami memaksimalkan wrt batas bawah ke fungsi .$f$$g$$T(x)$

Referensi:

[1] Nguyen, X., Wainwright, MJ dan Jordan, MI, 2010. Memperkirakan fungsi divergensi dan rasio kemungkinan dengan minimalisasi risiko cembung. Transaksi IEEE tentang Teori Informasi, 56 (11), hlm.5847-5861.

[2] Nowozin, S., Cseke, B. dan Tomioka, R., 2016. f-gan: Melatih pengambil sampel saraf generatif menggunakan minimalisasi divergence variasional. Dalam Kemajuan dalam sistem pemrosesan informasi saraf (hal. 271-279).