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

48

Aprendí acerca de la intuición detrás de la divergencia de KL sobre 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 pasa a decir que la comprensión intuitiva de 'distancia' entre estas dos distribuciones es útil, pero no debe tomarse literalmente, porque para dos distribuciones P y Q , el KL divergencia no es simétrica en P y Q .

No estoy seguro de cómo entender la última declaración, ¿o es aquí donde se rompe la intuición de 'distancia'?

Agradecería un ejemplo simple pero perspicaz.

cgo
fuente
3
Creo que tiene que dar un paso atrás y comprender que normalmente tiene una asimetría en las estadísticas entre la distribución de la población real y la muestra (o verdadero y modelo), etc., y esto es lo que refleja KL Divergence ... En la teoría de probabilidad general no hay Por lo general, esa distinción y una métrica simétrica tienen más sentido
seanv507
1
¿Qué "fuente" estabas leyendo?
nbro

Respuestas:

34

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: , P ( A ) = 0.2 , P ( B ) = 0.8 , Q ( A ) = Q ( B ) = 0.5 .Ω={A,B}P(A)=0.2,P(B)=0.8Q(A)=Q(B)=0.5

Tenemos:

KL(P,Q)=P(A)logP(A)Q(A)+P(B)logP(B)Q(B)0.19

y

KL(Q,P)=Q(A)logQ(A)P(A)+Q(B)logQ(B)P(B)0.22

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

mic
fuente
51

Agregando a las otras excelentes respuestas, una respuesta con otro punto de vista que tal vez pueda agregar algo más de intuición, que se solicitó.

La divergencia Kullback-Leibler es Si tiene dos hipótesis sobre qué distribución está generando los datos X , P y Q , entonces p ( x )

KL(P||Q)=p(x)logp(x)q(x)dx
XPQ es la razón de verosimilitud para probarH0:QcontraH1:P. Vemos que la divergencia Kullback-Leibler anterior es entonces el valor esperado de la razón de verosimilitud bajo la hipótesis alternativa. Entonces,KL(P||Q)es una medida de la dificultad de este problema de prueba, cuandoQes la hipótesis nula. Entonces la asimetríaKL(P||Q)KL(Q||P)p(x)q(x)H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P) simplemente refleja la asimetría entre hipótesis nula y alternativa.

Veamos esto en un ejemplo particular. Sea la distribución t ν y Q la distribución normal estándar (en el examen numérico a continuación ν = 1 ). La integral que define la divergencia parece complicada, así que simplemente usemos la integración numérica en R:PtνQν=1

> 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, lo que indica que la divergencia es muy grande o infinita, en el segundo caso es pequeña, resumiendo: El primer caso se verifica por 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).

KL(P||Q)KL(Q||P)0.26

t1t1t1t1n=1t1! Cambiando los roles, no, la diferencia proviene principalmente de los roles de los valores atípicos.

t1t1

Esto está relacionado con mi respuesta aquí: ¿Por qué deberíamos usar errores t en lugar de errores normales?

kjetil b halvorsen
fuente
22

D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
D(P||Q)=ipilog(piqi)
SKL(P,Q)=i(piqi)log(piqi)

D(A||B)=0.1log(0.10.2)+0.9log(0.90.8)0.0159
D(B||C)0.0112
D(A||C)0.0505
0.0159+0.01120.0505
SKL(A,B)0.0352
SKL(B,C)0.0234
SKL(A,C)0.1173
0.0352+0.02340.1173

Introduje este ejemplo a propósito. Imaginemos que está lanzando algunas monedas, por ejemplo, 100 veces. Mientras estas monedas sean imparciales, simplemente codificaría los resultados de lanzamiento con una secuencia de 0-1 bits (1 cabeza, 0 cola). En tal situación, cuando la probabilidad de cabeza es igual a la probabilidad de cola e igual a 0.5, esa es una codificación bastante efectiva. Ahora, tenemos algunas monedas sesgadas, por lo que preferimos codificar 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 colas k (son más probables). Y aquí se produce la divergencia Kullback-Leibler . Si P representa la distribución real de los resultados, y Q es solo una aproximación de P, entoncesD(P||Q)D(P||Q) denota la penalización que paga cuando codifica resultados que en realidad provienen de P distrib con codificación destinada a Q (penalización en el sentido de los bits adicionales que necesita usar).

Si simplemente necesita métrica, use la distancia Bhattacharyya (por supuesto, la versión modificada )1[xp(x)q(x)]

Adam Przedniczek
fuente
77
Si a uno le preocupa tener una métrica con una conexión más cercana a la divergencia KL, podría considerar la raíz cuadrada de la divergencia Jensen-Shannon en lugar de Bhattacharyya.
cardenal
5

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

¿Por qué? La divergencia KL no es una distancia como la que puede usar habitualmente, como por ejemplo la norma . De hecho, es positivo e igual a cero si y solo si las dos distribuciones son iguales (como en los axiomas para definir una distancia). Pero como se mencionó, no es simétrico. Hay formas de eludir esto, pero tiene sentido que no sea simétrico.L2

De hecho, la divergencia KL define la distancia entre una distribución de modelo (que realmente conoce) y una teórica de tal manera que tenga sentido manejar de manera diferente (la distancia "teórica" ​​de a suponiendo que modelo ) y (la distancia "empírica" ​​de a asumiendo los datos ) ya que significan medidas bastante diferentes.QPKL(P,Q)PQPKL(Q,P)PQQ

Meduz
fuente
5

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

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

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

Una ilustración

Permítanme ilustrar esto usando una aplicación en el procesamiento del lenguaje natural.

Tenga en cuenta que un gran grupo de personas, con la etiqueta B, son mediadores y cada uno de ellos se le asigna una tarea de elegir un nombre de turkey, animaly booky transmitirlo a C. No es un nombre de tipo A, que puede enviar cada uno de ellos un correo electrónico para dar ellos algunas pistas. Si nadie en el grupo recibió el correo electrónico, pueden levantar las cejas y dudar por un momento considerando lo que C necesita. Y la probabilidad de que cada opción sea elegida es 1/3. Distribución uniformemente uniforme (si no, puede relacionarse con sus propias preferencias e ignoramos tales casos).

Pero si se les da un verbo, como baste, 3/4 de ellos pueden elegir turkeyy 3/16 elegir animaly 1/16 elegir book. Entonces, ¿cuánta información en bits ha obtenido en promedio cada uno de los mediadores una vez que conocen el verbo? Está:

D(p(nouns|baste)||p(nouns))=x{turkey,animal,book}p(x|baste)log2p(x|baste)p(x)=34log23413+316log231613+116log211613=0.5709  bits

Pero, ¿y si el verbo dado es read? Podemos imaginar que todos elegirían booksin dudarlo, entonces la ganancia promedio de información para cada mediador del verbo reades:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Podemos ver que el verbo readpuede dar más información a los mediadores. Y eso es lo que puede medir la entropía relativa.

Continuemos nuestra historia. Si C sospecha que el sustantivo puede estar equivocado porque A le dijo que podría haber cometido un error al enviar el verbo equivocado a los mediadores. Entonces, ¿cuánta información en bits puede dar una noticia tan mala a C?

1) si el verbo dado por A era baste:

D(p(nouns)||p(nouns|baste))=x{turkey,animal,book}p(x)log2p(x)p(x|baste)=13log21334+13log213316+13log213116=0.69172  bits

2) pero ¿qué pasa si el verbo era read?

D(p(nouns)||p(nouns|baste))=x{book,,}p(x)log2p(x)p(x|baste)=13log2131+13log2130+13log2130=  bits

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

Podemos ver que la divergencia KL es asimétrica.

Espero tener razón, y si no, por favor comente y ayude a corregirme. Gracias por adelantado.

Lerner Zhang
fuente