En el contexto de aprendizaje automático y reconocimiento de patrones, hay un concepto llamado Núcleo Truco. Frente a los problemas donde se me pide para determinar si una función podría ser un kernel funcione o no, ¿qué es exactamente lo que debe hacer? Debo en primer lugar comprobar si son de la forma de tres o cuatro funciones de núcleo, tales como polinomio, RBF y Gaussiano? Entonces, ¿qué se supone que tengo que hacer? Debo mostrar es positiva definida? Podría alguien resolver un ejemplo para mostrar un paso a paso de la solución para estos problemas? Como por ejemplo, la es $f(x)=e^{x^tx'}$ un núcleo de la función (supongamos que no saben que es un núcleo Gaussiano)?
Respuesta
¿Demasiados anuncios?
En general, una función de $k(x,y)$ es válido núcleo de la función (en el sentido de que el núcleo truco) si satisface dos propiedades fundamentales:
simetría: $k(x,y) = k(y,x)$
positiva semi-definición.
Referencia: Página 4 de http://www.cs.berkeley.edu/~jordan/cursos/281B-spring04/conferencias/lec3.pdf
La comprobación de la simetría es generalmente directo por la inspección. La verificación positiva semi-determinación analítica puede ser bastante peludo a veces. Puedo pensar en dos estrategias para la comprobación de este hecho:
- (1) la Inspección para un interior "producto" de la representación
Considere la posibilidad de $k(x,y) = e^{x+y}$. Podemos encontrar algunos de los $\phi(a)$ tal que $k(x,y) = \phi(x)^T \phi(y)$? Un poco de matemáticas muestra que $e^{x+y} = e^x e^y$, así que vamos a $\phi(a)=e^a$ y hemos terminado.
Si tiene suerte, su $k()$ serán susceptibles de este análisis. Si no, usted puede recurrir a la opción (2):
- (2) la Comprobación positiva definida-ness al azar de la simulación.
Considere la función en $D$-dim vectores $k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$, donde cada vector $\vec{x}, \vec{y}$ debe ser no negativo y suma a uno. Es esto válido kernel?
Podemos comprobar esto mediante la simulación. Sorteo de un set de $N$ random vectores $\{\vec{x}_i\}_{i=1}^N$ y construir una matriz de Gram $K$ donde $K_{ij} = k( \vec{x}_i , \vec{x}_j )$. A continuación, compruebe si $K$ es positivo (semi-) definitiva.
La mejor manera de hacer esto numéricamente es encontrar los valores propios de la matriz (utilizando el buen existente librerías numéricas como scipy o matlab), y compruebe que el menor autovalor es mayor que o igual a 0. Si sí, la matriz $K$ es p.s.d. De lo contrario, ¿ no válida del núcleo.
Ejemplo de MATLAB/Octave código:
D=5;
N=100;
X = zeros(N,D);
for n = 1:N
xcur = rand(1,D);
X(n,:) = xcur/sum(xcur);
end
K = zeros(N,N);
for n = 1:N; for m = 1:N
K(n,m) = sum( min( X(n,:), X(m,:) ) );
end; end;
disp( min( eig(K) ) );
Esta es una prueba muy simple, pero tenga cuidado. Si la prueba falla, usted puede estar seguro de que el kernel es no válido, pero si se pasa el kernel todavía podría no ser válida.
Me parece que no importa cuántas matrices aleatorias puedo generar e independientemente de $N$$D$, este kernel pasa la prueba, así que probablemente es positiva semi-definida (de hecho, este es el conocido histograma intersección del núcleo, y se ha demostrado válido).
Sin embargo, la misma prueba en $k(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$ falla en cada intento me ha dado (al menos 20). Así que definitivamente es inválida, y muy fácil de comprobar.
Me gusta mucho esta segunda opción porque es muy rápido y mucho más fácil de depurar que compilcated formal de las pruebas. De acuerdo a Jitendra Malik diapositiva 19, la intersección del núcleo fue introducido en 1991, pero no se ha comprobado la correcta hasta el año 2005. Pruebas puede ser muy difícil!
