¿Es innecesario el truco del kernel para la SVM no lineal?

Question

Estoy aprendiendo sobre los núcleos de Mercer, y me ha surgido una pregunta. Desde que usamos el teorema de Mercer, sabemos que una matriz de kernel definida positiva puede ser representada por una producción interna del vector de entrada mapeado al nuevo espacio de características implicado por el kernel.

Una matriz Gram de $X$ se define un $K(X;k)\in \mathbb{R}^{m\times m}$ tal que $K_{i,j}=k(\hat{x}_i,\hat{x}_j)$ . Si la matriz $K$ es positiva definida, entonces $k$ se denomina núcleo de Mercer. Por el Teorema de Mercer, si tenemos un núcleo de Mercer, entonces existe una función $\phi: X \to Y $ tal que $$k(\hat{x}_i,\hat{x}_j)=\langle \phi(\hat{x}_i),\phi(\hat{x}_j) \rangle $$ La pregunta es, si es así, ¿por qué necesitamos utilizar la función del núcleo? ¿Por qué no transformar los datos según $\phi$ y utilizar las características transformadas para entrenar la SVM. Aparentemente con este enfoque debería haber alguna dificultad al clasificar un nuevo punto de datos, pero no estoy encontrando el problema.

Gracias.

Answer 1

Digamos que nuestros datos viven en $\mathbb R$ y estamos usando el núcleo $$k(x, y) = 1 + 2 x y + x^2 y^2,$$ que corresponde a $$\phi(x) = \begin{bmatrix}1 \\ \sqrt 2 x \\ x^2\end{bmatrix}.$$

Si entrenamos una SVM lineal en el modelo unidimensional $\phi(x)$ datos, o un kernel SVM en los datos tridimensionales $x$ datos, sacaremos la misma regla de predicción para los nuevos datos. Así que, en este caso, el truco del núcleo es "innecesario".

Pero digamos que nuestros datos viven en $\mathbb R^d$ y queremos utilizar el núcleo $$k(x, y) = 1 + 2 x^T y + (x^T y)^2 = (x^T y + 1)^2.$$ A continuación, las características correspondientes terminan siendo de dimensión $\frac12 d^2 + \frac32 d + 1$ . De repente, se trata de un modelo mucho más grande, que requerirá más cálculos para resolverlo, más memoria para almacenarlo, etc.

Peor aún, digamos que queremos utilizar el núcleo $$ k(x, y) = \exp\left( - \frac{1}{2 \sigma^2} \lVert x - y \rVert^2 \right) .$$ El $\phi$ características aquí terminan siendo infinito -dimensional ( ver aquí ), lo que significa que se necesitará una cantidad infinita de tiempo y memoria para computar directamente. Pero utilizando el truco del núcleo, podemos hacerlo sin problemas.

También puede ser mucho más fácil elegir las funciones $k$ con determinadas propiedades que diseñar funciones de características $\phi$ . (Los kernels no son más difíciles de diseñar que las funciones de características - se pueden escribir como $\phi(x)^T \phi(y)$ directamente, después de todo - pero la dirección opuesta puede ser bastante difícil).