Estimar la divergencia de Kullback Leibler (KL) con Monte Carlo

Question

Quiero estimar la divergencia de KL entre dos distribuciones continuas f y g. Sin embargo, no puedo anotar la densidad para f o g. Puedo tomar muestras de ambas f y g a través de algún método (por ejemplo, la cadena de Markov Monte Carlo).

La divergencia de KL de f a g se define así

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

Esta es la expectativa de $ \log\left ( \frac {f(x)}{g(x)} \right )$ con respecto a la f, así que podrías imaginar alguna estimación de Monte Carlo

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

Donde i indexa N muestras que se extraen de f (es decir $x_i \sim f()$ para i = 1, ..., N)

Sin embargo, como no sé f() y g(), ni siquiera puedo usar esta estimación de Monte Carlo. ¿Cuál es la forma estándar de estimar el KL en esta situación?

EDITAR: NO conozco la densidad no normalizada de f() o g()

Answer 1

Asumo que puedes evaluar $f$ y $g$ hasta una constante normalizadora. Denota $f(x) = f_u(x)/c_f$ y $g(x) = g_u(x)/c_g$ .

Puede utilizar la estimación $$ \widehat {D_{KL}}(f || g) = \frac {1}{N} \sum_i ^N \log\left ( \frac {f_u(x_i)}{g_u(x_i)} \right ) + \log ( \hat {r}) $$ donde $ \hat {r}$ es un estimador de muestreo importante para la proporción $c_g/c_f$ . Podrías usar $ \pi_f $ y $ \pi_g $ como densidades instrumentales para $f$ y $g$ respectivamente. $$ \hat {r} = \frac {1/n}{1/n} \frac { \sum_j f_u(x_j)/ \pi_f (x_j)}{ \sum_j g_u(x_j)/ \pi_g (x_j)}. $$ El numerador converge en $1/c_f$ . El denominador converge en $1/c_g$ . La proporción es consistente con el teorema de la cartografía continua. El registro de la proporción es consistente por el teorema de mapeo continuo de nuevo.

Mi motivación es la siguiente:

\begin {alineado*} 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 ]. \end {alineado*}

Para más ideas sobre cómo simular la proporción de probabilidad, este artículo tiene algunas: https://projecteuclid.org/download/pdf_1/euclid.aos/1031594732

Answer 2

Aquí asumo que sólo puede tomar muestras de los modelos; una función de densidad no normalizada no está disponible.

Escribes eso

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

donde he definido la proporción de probabilidades de ser $r$ . Alex Smola escribe, aunque en un contexto diferente que puedes estimar estos ratios "fácilmente" con sólo entrenar un clasificador. Supongamos que ha obtenido un clasificador $p(f|x)$ que puede decirte la probabilidad de que una observación $x$ ha sido generado por $f$ . Tenga en cuenta que $p(g|x) = 1 - p(f|x)$ . Entonces..:

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

donde el primer paso se debe a Bayes y el último se debe a la suposición de que $p(g) = p(f)$ .

Conseguir tal clasificador puede ser bastante fácil por dos razones.

Primero, puedes hacer actualizaciones estocásticas. Eso significa que si estás usando un optimizador basado en gradientes, como es típico para la regresión logística o las redes neuronales, puedes simplemente sacar una muestra de cada $f$ y $g$ y hacer una actualización.

En segundo lugar, como tienes datos virtualmente ilimitados puedes simplemente tomar muestras $f$ y $g$ a la muerte no tienes que preocuparte por la sobrecarga o algo así.