Oszacuj rozbieżność Kullback Leibler (KL) z Monte Carlo

10

Chcę oszacować rozbieżność KL między dwoma ciągłymi rozkładami f i g. Nie mogę jednak zapisać gęstości dla f lub g. Mogę próbkować zf i g za pomocą jakiejś metody (na przykład markov chain Monte Carlo).

Rozbieżność KL od f do g jest zdefiniowana w następujący sposób

D_{K L} (f | | g) = \int_{- \infty}^{\infty} f (x) \log (\frac{f (x)}{g (x)}) d x

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

To jest oczekiwanie na w odniesieniu do f, abyście mogli sobie wyobrazić jakieś oszacowanie Monte Carlo $\log\left(\frac{f(x)}{g(x)}\right)$

\frac{1}{N} \sum_{i}^{N} \log (\frac{f (x_{i})}{g (x_{i})})

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

Gdzie i indeksuje N próbek pobranych z f (tj. dla i = 1, ..., N) $x_i \sim f()$

Ponieważ jednak nie znam f () i g (), nie mogę nawet użyć tego oszacowania Monte Carlo. Jaki jest standardowy sposób oszacowania KL w tej sytuacji?

EDYCJA: NIE znam nietypowej gęstości dla f () lub g ()

kullback-leibler

— frelk
źródło

Czy zastanawiałeś się nad użyciem plików ecdfs?

— Toby

to zadziała, ale może być dowolnie wolne przy trudnym wyborze f i g (blisko lub blisko ogona). Jeśli zdecydujesz się zignorować próbki z dala od ogonów, możesz mieć więcej szczęścia z górną granicą roc.

— Christian Chapman

Zasadniczo duplikat: stats.stackexchange.com/questions/211175/…

— kjetil b halvorsen

7

Zakładam, że możesz to ocenić $f$ i $g$ aż do stałej normalizującej. Oznaczać $f(x) = f_u(x)/c_f$ i $g(x) = g_u(x)/c_g$ .

Spójnym estymatorem, który można zastosować, jest

\hat{D_{K L}} (f | | g) = {[n^{- 1} \sum_{j} f_{u} (x_{j}) / π_{f} (x_{j})]}^{- 1} \frac{1}{N} \sum_{i}^{N} [\log (\frac{f_{u} (z_{i})}{g_{u} (z_{i})}) \frac{f_{u} (z_{i})}{π_{r} (z_{i})}] - \log (\hat{r})

$\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})$ gdzie

\begin{matrix} (1) & \hat{r} = \frac{1 / n}{1 / n} \frac{\sum_{j} f_{u} (x_{j}) / π_{f} (x_{j})}{\sum_{j} g_{u} (y_{j}) / π_{g} (y_{j})} . \end{matrix}

$\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}.$ jest estymatorem próbkowania o istotnym znaczeniu dla stosunku

c_{f} / c_{g}

$c_f/c_g$ . Tutaj używasz

π_{f}

$\pi_f$ i

π_{g}

$\pi_g$ jako gęstości instrumentalne dla

f_{u}

$f_u$ i

g_{u}

$g_u$ odpowiednio i

π_{r}

$\pi_r$ aby celować w stosunek logarytmiczny nietypowych gęstości.

Więc pozwól $\{x_i\} \sim \pi_f$ , $\{y_i\} \sim \pi_g$ , i $\{z_i\} \sim \pi_r$ . Licznik (1) jest zbieżny z $c_f$ . Mianownik jest zbieżny z $c_g$ . Współczynnik jest spójny z twierdzeniem o ciągłym odwzorowaniu. Rejestr współczynnika jest spójny poprzez ponowne mapowanie ciągłe.

Jeśli chodzi o drugą część estymatora,

\frac{1}{N} \sum_{i}^{N} [\log (\frac{f_{u} (z_{i})}{g_{u} (z_{i})}) \frac{f_{u} (z_{i})}{π_{r} (z_{i})}] \overset{as}{\to} c_{f} E [\log (\frac{f_{u} (z_{i})}{g_{u} (z_{i})})]

$\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]$ według prawa wielkich liczb.

Moja motywacja jest następująca:

\begin{aligned} D_{K L} (f | | g) & = \int_{- \infty}^{\infty} f (x) \log (\frac{f (x)}{g (x)}) d x \\ = \int_{- \infty}^{\infty} f (x) {\log [\frac{f_{u} (x)}{g_{u} (x)}] + \log [\frac{c_{g}}{c_{f}}]} d x \\ = E_{f} [\log \frac{f_{u} (x)}{g_{u} (x)}] + \log [\frac{c_{g}}{c_{f}}] \\ = c_{f}^{- 1} E_{π_{r}} [\log \frac{f_{u} (x)}{g_{u} (x)} \frac{f_{u} (x)}{π_{r} (x)}] + \log [\frac{c_{g}}{c_{f}}] . \end{aligned}

$\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*}$ Więc po prostu rozbijam go na łatwe do ułożenia kawałki.

Aby uzyskać więcej pomysłów na temat symulacji współczynnika wiarygodności, znalazłem artykuł, który ma kilka: https://projecteuclid.org/download/pdf_1/euclid.aos/1031594732

— Taylor
źródło

(+1) Warto tutaj zauważyć, że ważność próbkowania może mieć bardzo wysoką wariancję (nawet wariancję nieskończoną), jeśli rozkład docelowy ma grubsze ogony niż rozkład, z którego próbkujesz i / lub liczba wymiarów jest w ogóle duża.

— David J. Harris

@ DavidJ.Harris bardzo bardzo prawda

— Taylor

6

Tutaj zakładam, że możesz próbkować tylko z modeli; nietypowa funkcja gęstości nie jest dostępna.

Ty to piszesz

D_{K L} (f | | g) = \int_{- \infty}^{\infty} f (x) \log (\underset{=: r}{\underset{⏟}{\frac{f (x)}{g (x)}}}) d x,

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

gdzie zdefiniowałem stosunek prawdopodobieństwa $r$ . Alex Smola pisze, choć w innym kontekście , że można oszacować te współczynniki „łatwo”, po prostu trenując klasyfikatora. Załóżmy, że uzyskałeś klasyfikator $p(f|x)$ , co może powiedzieć prawdopodobieństwo, że obserwacja $x$ został wygenerowany przez $f$ . Zauważ, że $p(g|x) = 1 - p(f|x)$ . Następnie:

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)},

$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)},$

gdzie pierwszy krok należy do Bayesa, a ostatni wynika z założenia, że $p(g) = p(f)$ .

Uzyskanie takiego klasyfikatora może być dość łatwe z dwóch powodów.

Po pierwsze, możesz wykonać aktualizacje stochastyczne. Oznacza to, że jeśli używasz optymalizatora opartego na gradiencie, co jest typowe dla regresji logistycznej lub sieci neuronowych, możesz po prostu pobrać próbki z każdego $f$ i $g$ i dokonaj aktualizacji.

Po drugie, ponieważ masz praktycznie nieograniczoną liczbę danych - możesz po prostu próbkować $f$ i $g$ na śmierć - nie musisz się martwić o nadmierne dopasowanie itp.

— bayerj
źródło

0

Oprócz metody klasyfikatora probabilistycznego wspomnianej przez @bayerj, możesz również użyć dolnej granicy dywergencji KL uzyskanej w [1-2]:

K L [f ‖ g] \geq sup_{T} {E_{x \sim f} [T (x)] - E_{x \sim g} [\exp (T (x) - 1)]},

$\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\},$ gdzie

T : X \to R

$T:\mathcal{X}\to\mathbb{R}$ jest funkcją arbitralną. W niektórych łagodnych warunkach granica jest ścisła dla:

T (x) = 1 + \ln [\frac{f (x)}{g (x)}]

$T(x) = 1 + \ln \left[ \frac{f(x)}{g(x)} \right]$

Aby oszacować rozbieżność KL pomiędzy $f$ i $g$ , maksymalizujemy dolną granicę wrt do funkcji $T(x)$ .

Bibliografia:

[1] Nguyen, X., Wainwright, MJ i Jordan, MI, 2010. Oszacowanie funkcjonałów dywergencji i współczynnika prawdopodobieństwa poprzez minimalizację ryzyka wypukłości. Transakcje IEEE dotyczące teorii informacji, 56 (11), s. 5847–5861.

[2] Nowozin, S., Cseke, B. and Tomioka, R., 2016. f-gan: Trening generatywnych próbników neuronowych z wykorzystaniem minimalizacji dywergencji wariacyjnej. W postępach w neuronowych systemach przetwarzania informacji (str. 271–279).

— Cuong
źródło