Intuición sobre la divergencia Kullback-Leibler (KL)

Question

He aprendido sobre la intuición detrás de la Divergencia KL como cuánto difiere una función de distribución del modelo de la distribución teórica/verdadera de los datos. La fuente que estoy leyendo continúa diciendo que la comprensión intuitiva de la "distancia" entre estas dos distribuciones es útil, pero no debe tomarse literalmente porque para dos distribuciones $P$ y $Q$ la divergencia KL no es simétrica en $P$ y $Q$ .

No sé cómo entender la última afirmación, ¿o es aquí donde se rompe la intuición de la "distancia"?

Agradecería un ejemplo sencillo, pero perspicaz.

Answer 1

Sumándose a las otras excelentes respuestas, una respuesta con otro punto de vista que quizás pueda añadir algo más de intuición, lo que se pedía.

La divergencia de Kullback-Leibler es $$ \DeclareMathOperator{\KL}{KL} \KL(P || Q) = \int_{-\infty}^\infty p(x) \log \frac{p(x)}{q(x)} \; dx $$ Si tienes dos hipótesis sobre qué distribución está generando los datos $X$ , $P$ y $Q$ entonces $\frac{p(x)}{q(x)}$ es el cociente de probabilidades para probar $H_0 \colon Q$ contra $H_1 \colon P$ . Vemos que la divergencia de Kullback-Leibler anterior es entonces el valor esperado de la razón de loglabilidad bajo la hipótesis alternativa. Por lo tanto, $\KL(P || Q)$ es una medida de la dificultad de este problema de prueba, cuando $Q$ es la hipótesis nula. Así que la asimetría $\KL(P || Q) \not= \KL(Q || P)$ simplemente refleja la asimetría entre la hipótesis nula y la alternativa.

Veamos esto en un ejemplo concreto. Sea $P$ sea el $t_\nu$ -distribución y $Q$ la distribución normal estándar (en el ejemplo numérico siguiente $\nu=1$ ). La integral que define la divergencia parece complicada, así que vamos a utilizar simplemente la integración numérica en R:

    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

En el primer caso la integral parece divergir numéricamente, indicando que la divergencia es muy grande o infinita, en el segundo caso es pequeña, resumiendo: $$ \KL(P || Q) \approx \infty \\ \KL(Q || P) \approx 0.26 $$ El primer caso se verifica mediante integración simbólica analítica en respuesta por @Xi'an aquí: ¿Cuál es el valor máximo de la divergencia Kullback-Leibler (KL) .

¿Qué nos dice esto, en términos prácticos? Si el modelo nulo es una distribución normal estándar pero los datos se generan a partir de una $t_1$ -entonces es bastante fácil rechazar la nulidad. Los datos de una $t_1$ -no parecen datos con distribución normal. En el otro caso, los papeles se intercambian. El nulo es el $t_1$ pero los datos son normales. Pero los datos normales distribuidos podrían tener el siguiente aspecto $t_1$ datos, por lo que este problema es mucho más difícil.

Aquí tenemos el tamaño de la muestra $n=1$ y todos los datos que podrían provenir de una distribución normal también podrían provenir de una $t_1$ ¡! Cambiando los papeles, no, la diferencia viene sobre todo del papel de los valores atípicos.

Con la distribución alternativa $t_1$ hay una probabilidad bastante grande de obtener una muestra que tenga una probabilidad muy pequeña bajo el modelo nulo (normal), dando una divergencia enorme. Pero cuando la distribución alternativa es normal, prácticamente todos los datos que podamos obtener tendrán una probabilidad moderada (realmente, densidad...) bajo el modelo nulo $t_1$ modelo, por lo que la divergencia es pequeña.

Esto está relacionado con mi respuesta aquí: ¿Por qué debemos utilizar los errores t en lugar de los errores normales?

Answer 2

Una distancia (métrica) $D$ debe ser simétrica, es decir $D(P,Q) = D(Q,P)$ . Pero, por definición, $KL$ no lo es.

Ejemplo: $\Omega = \{A,B\}$ , $P(A) = 0.2, P(B) = 0.8$ , $Q(A) = Q(B) = 0.5$ .

Lo tenemos:

$$KL(P,Q) = P(A)\log \frac{P(A)}{Q(A)} + P(B) \log \frac{P(B)}{Q(B)} \approx 0.19$$

y

$$KL(Q,P) = Q(A)\log \frac{Q(A)}{P(A)} + Q(B) \log \frac{Q(B)}{P(B)} \approx 0.22$$

así $KL(P,Q) \neq KL(Q,P)$ y por lo tanto $KL$ no es una distancia (métrica).

Answer 3

En primer lugar, la violación de la condición de simetría es el menor problema de la divergencia de Kullback-Leibler. $D(P||Q)$ también viola la desigualdad del triángulo. Se puede introducir simplemente la versión simétrica como $$ SKL(P, Q) = D(P||Q) + D(Q||P) $$ pero eso no es una métrica, porque ambos $D(P||Q)$ y $SKL(P, Q)$ viola la desigualdad del triángulo. Para demostrar que simplemente tomar tres monedas sesgadas A, B y C que produce mucho menos caras que colas, por ejemplo, las monedas con probabilidad de cara de: A = 0,1, B = 0,2 y C = 0,3. En ambos casos, la divergencia KL regular D o su versión simétrica SKL, comprueba que no cumplen la desigualdad del triángulo $$D(A||B) + D(B||C) \ngeqslant D(A||C)$$ $$SKL(A, B) + SKL(B, C) \ngeqslant SKL(A, C)$$ Basta con utilizar estas fórmulas: $$ D(P||Q) = \sum\limits_{i}p_i \cdot \log(\frac{p_i}{q_i})$$ $$ SKL(P, Q) = \sum\limits_{i}(p_i - q_i) \cdot \log(\frac{p_i}{q_i})$$

$$D(A||B) = 0.1 \cdot \log(\frac{0.1}{0.2}) + 0.9 \cdot \log(\frac{0.9}{0.8}) \approx 0.0159$$ $$D(B||C) \approx 0.0112$$ $$D(A||C) \approx 0.0505$$ $$0.0159 + 0.0112 \ngeqslant 0.0505$$ $$SKL(A, B) \approx 0.0352$$ $$SKL(B, C) \approx 0.0234$$ $$SKL(A, C) \approx 0.1173$$ $$ 0.0352 + 0.0234 \ngeqslant 0.1173$$

Introduje este ejemplo a propósito. Imaginemos que se lanzan unas monedas, por ejemplo, 100 veces. Mientras estas monedas sean imparciales, simplemente codificarías los resultados de los lanzamientos con una secuencia de bits 0-1, (1-cabeza, 0-cola). En esta situación, cuando la probabilidad de la cabeza es la misma que la de la cola e igual a 0,5, es una codificación bastante eficaz. Ahora bien, tenemos algunas monedas sesgadas, por lo que preferimos codificar los resultados más probables con un código más corto, por ejemplo, fusionar grupos de caras y colas y representar secuencias de k caras con un código más largo que la secuencia de k colas (son más probables). Y aquí la divergencia de Kullback-Leibler $D(P||Q)$ ocurre. Si P representa la verdadera distribución de resultados, y Q es sólo una aproximación de P, entonces $D(P||Q)$ denota la penalización que se paga cuando se codifican los resultados que realmente provienen de P distrib con la codificación prevista para Q (penalización en el sentido de los bits adicionales que hay que utilizar).

Si sólo necesita el sistema métrico, utilice Distancia de Bhattacharyya (por supuesto la versión modificada $\sqrt{1 - [\sum\limits_{x} \sqrt{p(x)q(x)}]}$ )

Answer 4

Me siento tentado a dar una respuesta puramente intuitiva a su pregunta. Reformulando lo que dices, la divergencia KL es una forma de medir la distancia entre dos distribuciones como se calcularía la distancia entre dos conjuntos de datos en un espacio de Hilbert, pero hay que tener cierta precaución.

¿Por qué? La divergencia KL no es una distancia como la que se suele utilizar, como por ejemplo la $L_2$ norma. En efecto, es positiva e igual a cero si y sólo si las dos distribuciones son iguales (como en los axiomas para definir una distancia). Pero, como se ha dicho, no es simétrica. Hay formas de evitarlo, pero tiene sentido que no sea simétrica.

En efecto, la divergencia KL define la distancia entre una distribución modelo $Q$ (que realmente conoces) y una teórica $P$ como para que tenga sentido manejarse de forma diferente $KL(P, Q)$ (la distancia "teórica" de $P$ a $Q$ asumiendo el modelo $P$ ) y $KL(Q, P)$ (la distancia "empírica" de $P$ a $Q$ asumiendo los datos $Q$ ) ya que significan medidas muy diferentes.

Answer 5

El libro de texto Elementos de la teoría de la información nos da un ejemplo:

Por ejemplo, si conociéramos la verdadera distribución p del azar variable aleatoria, podríamos construir un código con una longitud de descripción media H(p). Si, en cambio, utilizamos el código de una distribución q, necesitaríamos necesitaríamos H(p) + D(p||q) bits de media para describir la variable aleatoria variable aleatoria.

Parafraseando la afirmación anterior, podemos decir que si cambiamos la distribución de la información (de q a p) necesitamos D(p||q) bits extra de media para codificar la nueva distribución.

Una ilustración

Permítanme ilustrar esto utilizando una aplicación de la misma en el procesamiento del lenguaje natural.

Considere que un gran grupo de personas, etiquetado como B, son mediadores y a cada uno de ellos se le asigna la tarea de elegir un sustantivo de turkey , animal y book y transmitirlo a C. Hay un tipo llamado A que puede enviar a cada uno de ellos un correo electrónico para darles algunas pistas. Si nadie del grupo ha recibido el correo electrónico, es posible que levanten las cejas y duden durante un rato sobre lo que necesita C. Y la probabilidad de que cada opción sea elegida es de 1/3. En principio, la distribución es uniforme (si no es así, puede estar relacionada con sus propias preferencias y simplemente ignoramos estos casos).

Pero si se les da un verbo, como baste 3/4 de ellos pueden elegir turkey y 3/16 elegir animal y 1/16 elija book . Entonces, ¿cuánta información en bits ha obtenido de media cada uno de los mediadores una vez que conocen el verbo? Así es:

\begin{align*} D(p(nouns|baste)||p(nouns)) &= \sum_{x\in\{turkey, animal, book\}} p(x|baste) \log_2 \frac{p(x|baste)}{p(x)} \\ &= \frac{3}{4} * \log_2 \frac{\frac{3}{4}}{\frac{1}{3}} + \frac{3}{16} * \log_2\frac{\frac{3}{16}}{\frac{1}{3}} + \frac{1}{16} * \log_2\frac{\frac{1}{16}}{\frac{1}{3}}\\ &= 0.5709 \space \space bits\\ \end{align*}

Pero ¿qué pasa si el verbo dado es read ? Podemos imaginar que todos ellos elegirían book sin vacilación, entonces la ganancia media de información para cada mediador del verbo read es:

\begin{align*} D(p(nouns|read)||p(nouns)) &= \sum_{x\in\{book\}} p(x|read) \log_2 \frac{p(x|read)}{p(x)} \\ &= 1 * \log_2 \frac{1}{\frac{1}{3}} \\ & =1.5849 \space \space bits \\ \end{align*} Podemos ver que el verbo read puede dar a los mediadores más información. Y eso es lo que la entropía relativa puede medir.

Continuemos nuestra historia. Si C sospecha que el sustantivo puede ser erróneo porque A le ha dicho que podría haberse equivocado al enviar el verbo equivocado a los mediadores. Entonces, ¿cuánta información en bits puede dar a C esa mala noticia?

1) si el verbo dado por A era baste :
\begin{align*} D(p(nouns)||p(nouns|baste)) &= \sum_{x\in\{turkey, animal, book\}} p(x) \log_2 \frac{p(x)}{p(x|baste)} \\ &= \frac{1}{3} * \log_2 \frac{\frac{1}{3}}{\frac{3}{4}} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{\frac{3}{16}} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{\frac{1}{16}}\\ &= 0.69172 \space \space bits\\ \end{align*}

2) pero ¿qué pasaría si el verbo fuera read ? \begin{align*} D(p(nouns)||p(nouns|baste)) &= \sum_{x\in\{book, *, *\}} p(x) \log_2 \frac{p(x)}{p(x|baste)} \\ &= \frac{1}{3} * \log_2 \frac{\frac{1}{3}}{1} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{0} + \frac{1}{3} * \log_2\frac{\frac{1}{3}}{0}\\ &= \infty \space \space bits\\ \end{align*}

Como C nunca se sabe cuáles serían los otros dos sustantivos y cualquier palabra del vocabulario sería posible.

Podemos ver que la divergencia KL es asimétrica.

Espero estar en lo cierto, y si no es así por favor comenten y ayuden a corregirme. Gracias de antemano.