¿Qué función podría ser un núcleo?

En el contexto del aprendizaje automático y el reconocimiento de patrones, hay un concepto llamado Kernel Trick . Enfrentando problemas en los que se me pide que determine si una función podría ser una función del núcleo o no, ¿qué se debe hacer exactamente? ¿Debería comprobar primero si tienen la forma de las tres o cuatro funciones del núcleo, como polinomio, RBF y gaussiano? Entonces, ¿qué se supone que debo hacer? ¿Debo demostrar que es positivo definitivo? ¿Alguien podría resolver un ejemplo para mostrar una solución paso a paso para tales problemas? Como por ejemplo, ¿ es una función del núcleo$f(x)=e^{x^tx'}$ (supongamos que no sabemos que es un núcleo gaussiano)?

Generalmente, una función es una función válida del núcleo (en el sentido del truco del núcleo) si cumple dos propiedades clave:$k(x,y)$

• simetría: $k(x,y) = k(y,x)$

• semi-definición positiva.

Referencia: Página 4 de http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

La comprobación de la simetría suele ser sencilla mediante inspección. Verificar analíticamente la semi-definición positiva puede ser bastante difícil a veces. Se me ocurren dos estrategias para verificar este hecho:

• (1) Inspección de una representación de "producto interno"

Considere . ¿Podemos encontrar alguna tal que ? Un poco de matemática muestra que , así que dejemos que y terminemos. ϕ ( a ) k ( x , y ) = ϕ ( x ) T ϕ ( y ) e x + y = e x e y ϕ ( a ) = e $k(x,y) = e^{x+y}$$\phi(a)$$k(x,y) = \phi(x)^T \phi(y)$$e^{x+y} = e^x e^y$$\phi(a)=e^a$

Si tiene suerte, su será susceptible de este análisis. Si no, puede recurrir a la opción (2):$k()$

• (2) Verificación de la definición positiva por simulación aleatoria.

Considere la función en -dim vectores , donde cada vector debe ser no negativo y sumarse a uno. ¿Es este un núcleo válido?k ( → x , → y ) = ∑ D d = 1 min ( x d , y d ) → x , → $D$$k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$$\vec{x}, \vec{y}$

Podemos verificar esto por simulación. Dibuje un conjunto de vectores aleatorios y construya una matriz de Gram donde . Luego verifique si es positivo (semi) definido.{ → x i } N i = 1 K K i j = k ( → x i , → x j ) $N$$\{\vec{x}_i\}_{i=1}^N$$K$$K_{ij} = k( \vec{x}_i , \vec{x}_j )$$K$

La mejor manera de hacer esto numéricamente es encontrar los valores propios de la matriz (usando buenas bibliotecas numéricas existentes como scipy o matlab), y verificar que el valor propio más pequeño sea mayor o igual a 0 . En caso afirmativo, la matriz es psd. De lo contrario, no tiene un núcleo válido.$K$

Código de muestra MATLAB / Octave:

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, puede estar seguro de que el kernel no es válido, pero si pasa el kernel aún podría no ser válido.

Encuentro que no importa cuántas matrices aleatorias genere e independientemente de y , este núcleo pasa la prueba, por lo que probablemente sea positivo semi-definido (de hecho, este es el conocido núcleo de intersección de histograma , y ha sido probado válido).$N$$D$

Sin embargo, la misma prueba en falla en cada intento que le he dado (al menos 20) . Por lo tanto, es definitivamente inválido y bastante fácil de verificar.$k(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$

Realmente me gusta esta segunda opción porque es bastante rápida y mucho más fácil de depurar que las pruebas formales compiladas. Según la diapositiva 19 de Jitendra Malik , el núcleo de intersección se introdujo en 1991, pero no se demostró que era correcto hasta 2005. ¡Las pruebas formales pueden ser muy desafiantes!