Estimar a divergência Kullback Leibler (KL) com monte carlo

Quero estimar a divergência KL entre duas distribuições contínuas feeg. No entanto, não posso anotar a densidade para f ou g. Eu posso amostrar a partir de feg através de algum método (por exemplo, cadeia de markov monte carlo).

A divergência KL de f para g é definida assim

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

Esta é a expectativa de em relação a f, para que você possa imaginar uma estimativa de 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)$$

Onde i indexa N amostras extraídas de f (ie para i = 1, ..., N)$x_i \sim f()$

No entanto, como não conheço f () e g (), não posso nem usar essa estimativa de monte carlo. Qual é a maneira padrão de estimar o KL nessa situação?

Edição: Eu não sei a densidade não normalizada para f () ou g ()

Aqui, suponho que você só pode provar a partir dos modelos; uma função de densidade não normalizada não está disponível.

Você escreve isso

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

onde defini a razão de probabilidades como . Alex Smola escreve, embora em um contexto diferente, você possa estimar essas proporções "facilmente" apenas treinando um classificador. Suponhamos que você tenha obtido um classificador p ( f | x ) , que pode lhe dizer a probabilidade de uma observação x ter sido gerada por f . Observe que p ( g | x ) = 1 - p ( f | x ) . Então:$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)},$$

onde o primeiro passo é devido a Bayes e o último segue da suposição de que .$p(g) = p(f)$

Obter esse classificador pode ser bastante fácil por dois motivos.

Primeiro, você pode fazer atualizações estocásticas. Isso significa que, se você estiver usando um otimizador baseado em gradiente, como é típico para regressão logística ou redes neurais, você pode simplesmente desenhar uma amostra de cada e ge fazer uma atualização.$f$$g$

Segundo, como você tem dados virtualmente ilimitados - você pode apenas provar e g até a morte - não precisa se preocupar com o ajuste excessivo ou algo parecido.$f$$g$

Eu suponho que você pode avaliar e g até um constante de normalização. Denotam f ( x ) = f u ( x ) / C f e g ( x ) = g u ( x ) / c g .$f$$g$$f(x) = f_u(x)/c_f$$g(x) = g_u(x)/c_g$

Um estimador consistente que pode ser usado é em que 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})$$ é um estimador de amostragem de importância para a razãocf/cg. Aqui você usaπfeπgcomo densidades instrumentais parafuegu, respectivamente, eπrpara atingir a razão de log de densidades não normalizadas. $$\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$

Então deixou , { y i } ~ π g , e { z i } ~ π r . O numerador de (1) converge para c f . O denominador converge para c g . A proporção é consistente pelo teorema do mapeamento contínuo. O log da proporção é consistente pelo mapeamento contínuo novamente.$\{x_i\} \sim \pi_f$$\{y_i\} \sim \pi_g$$\{z_i\} \sim \pi_r$$c_f$$c_g$

Em relação à outra parte do estimador, pela lei dos grandes números.

$$\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]$$

Minha motivação é a seguinte:

$$\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*}$$

Para obter mais idéias sobre como simular a razão likelhood, encontrei um artigo com alguns: https://projecteuclid.org/download/pdf_1/euclid.aos/1031594732

Além do método classificador probabilístico mencionado por @bayerj, você também pode usar o limite inferior da divergência KL derivada em [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\},$$ $T:\mathcal{X}\to\mathbb{R}$ $$T(x) = 1 + \ln \left[ \frac{f(x)}{g(x)} \right]$$

$f$$g$$T(x)$

Referências:

[1] Nguyen, X., Wainwright, MJ e Jordan, MI, 2010. Estimando funcionais de divergência e a razão de verossimilhança por minimização de risco convexa. IEEE Transactions on Information Theory, 56 (11), pp.5847-5861.

[2] Nowozin, S., Cseke, B. e Tomioka, R., 2016. f-gan: Treinamento de amostradores neurais generativos usando minimização de divergência variacional. In Advances in neural information processing systems (pp. 271-279).