De Kullback-Leibler divergencia se basa en el kernel

Question

Yo estoy buscando para el papel ", Una de Kullback-Leibler Divergencia Kernel Basado en SVM para la Clasificación en las Aplicaciones Multimedia". Autor sugiere utilizar el kernel de la función para las dos distribuciones $p$ y $q$: $k(p,q)= \exp (-a (D_{KL}(p,q) + D_{KL}(q,p)))$, donde $a>0$ $D_{KL}$ es de Kullback-Leibler divergencia entre el$p$$q$. Pero no es obvio a partir de este papel que dicho núcleo es positiva definida. Cómo se puede justificar que el kernel es positiva definida?

También es bien sabido que el $\exp (-a (D_{KL}(p,q) + D_{KL}(q,p)))$ puede ser positiva definida si y sólo si $(D_{KL}(p,q) + D_{KL}(q,p))$ es negativo definitivo del núcleo. Cómo puede uno prueba de ese hecho?

Answer 1

Si usted tiene un núcleo de la forma: $K(x,y) = \exp^{-a(M(x,y))}$, todo lo que se necesita es $M(x,y)$ válido métrica. Así que todo lo que se requiere es demostrar que la Symmetrised K-L Divergencia ( $KLS(p,q)$ ) es una métrica válida.

Para todo x, y, z en X, esta función se requiere para satisfacer las siguientes condiciones:

1. $d(x, y) \geq 0$ (no negatividad)
2. $d(x, y) = 0 \iff x = y$ (identidad de los indiscernibles. Tenga en cuenta que la condición 1 y 2 en conjunto producen positivo de la definición)
3. $d(x, y) = d(y, x)$ (simetría).
4. $d(x, z) ≤ d(x, y) + d(y, z)$ (subadditivity / desigualdad de triángulo).

1 y 2 tienen para cada uno de $KL(p,q)$ $KL(q,p)$ y, por tanto, poseen para $KLS(p,q)$. 3 tiene trivialmente.

Sin embargo 4 no se sostiene:

Contador de ejemplo Considere la posibilidad de a=[0.3 0.3 0.4] b=[0.25 0.35 0.4] c=[0.16 0.33 0.51]

tenemos

$KL(a||b)+KL(b||a)+KL(b||c)+KL(c||b)-[KL(a||c)+KL(c||a)]\approx -0.0327<0$

Por lo $KLS(p,q)$ no es válido métrica.

A menos que me haya perdido de algo, no creo que sus granos son necesariamente positiva definida - supongo que no fue discutido en el proceso de revisión de lo contrario, me gustaría esperar a ver que se discute en el papel. En la práctica, esto puede no ser un problema, como por sus ejemplos del mundo real de las matrices puede haber sido (al menos cerca) SPSD, y con la correspondiente regularización (incluso la adición de una pequeña constante de la diagonal) de los algoritmos que se debe trabajar aún. También hay algo de trabajo en la solución de SVMs por tiempo indefinido, los granos, véase, por ejemplo, Entrenamiento de SVM con Indefinido Núcleos o Análisis de SVM con Indefinido Núcleos así que no todo está perdido, incluso si los granos son de carácter indefinido.

Es interesante que sus resultados son mucho mejores que el uso de Fisher núcleos - en mi experiencia, Fisher kernels no funcionan bien, así que esto es potencialmente una buena manera de combinar generativa y discriminativo de los métodos. Déjanos saber cómo te va en si dar la vuelta a usarlos!!