Estoy tratando de entender la intuición detrás de los SVM del kernel. Ahora, entiendo cómo funciona el SVM lineal, mediante el cual se toma una línea de decisión que divide los datos lo mejor que puede. También entiendo el principio detrás de la transferencia de datos a un espacio de dimensiones superiores, y cómo esto puede facilitar la búsqueda de una línea de decisión lineal en este nuevo espacio. Lo que no entiendo es cómo se usa un núcleo para proyectar puntos de datos a este nuevo espacio.

Lo que sé sobre un núcleo es que representa efectivamente la "similitud" entre dos puntos de datos. Pero, ¿cómo se relaciona esto con la proyección?

Deje la proyección a alta espacio dimensión F . Básicamente, la función del núcleo K ( x 1 , x 2 ) = $h(x)$$\mathcal{F}$ , que es el producto interior. Por lo tanto, no se usa para proyectar puntos de datos, sino más bien un resultado de la proyección. Puede considerarse una medida de similitud, pero en un SVM, es más que eso.$K(x_1,x_2)=\langle h(x_1),h(x_2)\rangle$

La optimización para encontrar el mejor hiperplano de separación en implica h ( x ) solo a través de la forma interna del producto. Es decir, si conoce K ( ⋅ , ⋅ ) , no necesita conocer la forma exacta de h ( x ) , lo que facilita la optimización.$\mathcal{F}$$h(x)$$K(\cdot,\cdot)$$h(x)$

Cada kernel tiene su correspondiente h ( x ) . Entonces, si está usando un SVM con ese núcleo, entonces está encontrando implícitamente la línea de decisión lineal en el espacio en el que h ( x ) se asigna.$K(\cdot,\cdot)$$h(x)$$h(x)$

El Capítulo 12 de Elementos del aprendizaje estadístico ofrece una breve introducción a SVM. Esto proporciona más detalles sobre la conexión entre el núcleo y la asignación de características: http://statweb.stanford.edu/~tibs/ElemStatLearn/

Las propiedades útiles de kernel SVM no son universales; dependen de la elección del kernel. Para tener intuición, es útil observar uno de los núcleos más utilizados, el núcleo gaussiano. Sorprendentemente, este núcleo convierte SVM en algo muy parecido a un clasificador vecino k-más cercano.

Esta respuesta explica lo siguiente:

1. ¿Por qué la separación perfecta de datos de entrenamiento positivos y negativos siempre es posible con un núcleo gaussiano de ancho de banda suficientemente pequeño (a costa de un sobreajuste)?
2. Cómo esta separación puede interpretarse como lineal en un espacio de características.
3. Cómo se usa el núcleo para construir la asignación del espacio de datos al espacio de características. Spoiler: el espacio de características es un objeto matemáticamente abstracto, con un producto interno abstracto inusual basado en el núcleo.

1. Lograr una separación perfecta

La separación perfecta siempre es posible con un núcleo gaussiano debido a las propiedades de localidad del núcleo, que conducen a un límite de decisión arbitrariamente flexible. Para un ancho de banda de kernel suficientemente pequeño, el límite de decisión se verá como si dibujara pequeños círculos alrededor de los puntos cuando sea necesario para separar los ejemplos positivos y negativos:

(Crédito: curso de aprendizaje automático en línea de Andrew Ng ).

Entonces, ¿por qué ocurre esto desde una perspectiva matemática?

Considere la configuración estándar: tiene un núcleo gaussiano y datos de entrenamiento ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , … , ( x ( n $K(\mathbf{x},\mathbf{z}) = \exp(- ||\mathbf{x}-\mathbf{z}||^2 / \sigma^2)$donde losvalores de y ( i ) son±1. Queremos aprender una función clasificadora$(\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \ldots, (\mathbf{x}^{(n)},y^{(n)})$$y^{(i)}$$\pm 1$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x})$$

Ahora, ¿cómo asignaremos los pesos ? ¿Necesitamos espacios de dimensiones infinitas y un algoritmo de programación cuadrática? No, porque solo quiero mostrar que puedo separar los puntos perfectamente. Entonces hago σ mil millones de veces más pequeño que la separación más pequeña | El | x ( i ) - x ( j ) | El | entre dos ejemplos de entrenamiento, y acabo de establecer w i = 1 . Esto significa que todos los puntos de entrenamiento son de mil millones sigmas aparte En lo que concierne al núcleo, y cada punto controla por completo el signo de $w_i$$\sigma$$||\mathbf{x}^{(i)} - \mathbf{x}^{(j)}||$$w_i = 1$$\hat{y}$en su barrio Formalmente tenemos

$$\hat{y}(\mathbf{x}^{(k)}) = \sum_{i=1}^n y^{(k)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} K(\mathbf{x}^{(k)},\mathbf{x}^{(k)}) + \sum_{i \neq k} y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} + \epsilon$$

donde es un valor arbitrariamente pequeño. Sabemos que ϵ es pequeño porque x ( k ) está a mil millones de sigmas de distancia de cualquier otro punto, por lo que para todo i ≠ k tenemos$\epsilon$$\epsilon$$\mathbf{x}^{(k)}$$i \neq k$

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = \exp(- ||\mathbf{x}^{(i)} - \mathbf{x}^{(k)}||^2 / \sigma^2) \approx 0.$$

Desde es tan pequeña, y ( x ( k ) ) sin duda tiene el mismo signo que Y ( k $\epsilon$$\hat{y}(\mathbf{x}^{(k)})$$y^{(k)}$ , y el clasificador alcanza una precisión perfecta en los datos de entrenamiento. En la práctica, esto sería terriblemente sobreajustado, pero muestra la tremenda flexibilidad del kernel gaussiano SVM y cómo puede actuar de manera muy similar al clasificador vecino más cercano.

2. Kernel SVM aprendiendo como separación lineal

El hecho de que esto puede interpretarse como "separación lineal perfecta en un espacio de características de dimensiones infinitas" proviene del truco del núcleo, que le permite interpretar el núcleo como un producto interno abstracto y un espacio de características nuevo:

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(j)}) = \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x}^{(j)})\rangle$$

donde es la asignación del espacio de datos al espacio de características. De ello se deduce inmediatamente que la Y ( x ) la función como una función lineal en el espacio de características:$\Phi(\mathbf{x})$$\hat{y}(\mathbf{x})$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x})\rangle = L(\Phi(\mathbf{x}))$$

donde la función lineal se define en los vectores de espacio de características v como$L(\mathbf{v})$$\mathbf{v}$

$$L(\mathbf{v}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\mathbf{v}\rangle$$

Esta función es lineal en porque es solo una combinación lineal de productos internos con vectores fijos. En el espacio de características, la frontera de decisión y ( x ) = 0 es sólo L ( v ) = 0 , el conjunto de nivel de una función lineal. Esta es la definición misma de un hiperplano en el espacio de características.$\mathbf{v}$$\hat{y}(\mathbf{x}) = 0$$L(\mathbf{v}) = 0$

3. Cómo se usa el núcleo para construir el espacio de características

Kernel methods never actually "find" or "compute" the feature space or the mapping $\Phi$ explicitly. Kernel learning methods such as SVM do not need them to work; they only need the kernel function $K$. It is possible to write down a formula for $\Phi$ but the feature space it maps to is quite abstract and is only really used for proving theoretical results about SVM. If you're still interested, here's how it works.

Basically we define an abstract vector space $V$ where each vector is a function from $\mathcal{X}$ to $\mathbb{R}$. A vector $f$ in $V$ is a function formed from a finite linear combination of kernel slices:

$$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$ (Here the $\mathbf{x}^{(i)}$ are just an arbitrary set of points and need not be the same as the training set.) It is convenient to write $f$ more compactly as $$f = \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}$$ where $K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y})$ is a function giving a "slice" of the kernel at $\mathbf{x}$.

The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:

$$\langle \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}, \sum_{j=1}^n \beta_j K_{\mathbf{x}^{(j)}} \rangle = \sum_{i,j} \alpha_i \beta_j K(\mathbf{x}^{(i)},\mathbf{x}^{(j)})$$

This definition is very deliberate: its construction ensures the identity we need for linear separation, $\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \rangle = K(\mathbf{x},\mathbf{y})$.

With the feature space defined in this way, $\Phi$ is a mapping $\mathcal{X} \rightarrow V$, taking each point $\mathbf{x}$ to the "kernel slice" at that point:

$$\Phi(\mathbf{x}) = K_\mathbf{x}, \quad \text{where} \quad K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y}).$$

You can prove that $V$ is an inner product space when $K$ is a positive definite kernel. See this paper for details.

For the background and the notations I refer to How to calculate decision boundary from support vectors?.

So the features in the 'original' space are the vectors $x_i$, the binary outcome $y_i \in \{-1, +1\}$ and the Lagrange multipliers are $\alpha_i$.

As said by @Lii (+1) the Kernel can be written as $K(x,y)=h(x) \cdot h(y)$ ('$\cdot$' represents the inner product.

I will try to give some 'intuitive' explanation of what this $h$ looks like, so this answer is no formal proof, it just wants to give some feeling of how I think that this works. Do not hesitate to correct me if I am wrong.

I have to 'transform' my feature space (so my $x_i$) into some 'new' feature space in which the linear separation will be solved.

For each observation $x_i$, I define functions $\phi_i(x)=K(x_i,x)$, so I have a function $\phi_i$ for each element of my training sample. These functions $\phi_i$ span a vector space. The vector space spanned by the $\phi_i$, note it $V=span(\phi_{i, i=1,2,\dots N})$.

I will try to argue that is the vector space in which linear separation will be possible. By definition of the span, each vector in the vector space $V$ can be written as as a linear combination of the $\phi_i$, i.e.: $\sum_{i=1}^N \gamma_i \phi_i$, where $\gamma_i$ are real numbers.

$N$ is the size of the training sample and therefore the dimension of the vector space $V$ can go up to $N$, depending on whether the $\phi_i$ are linear independent. As $\phi_i(x)=K(x_i,x)$ (see supra, we defined $\phi$ in this way), this means that the dimension of $V$ depends on the kernel used and can go up to the size of the training sample.

The transformation, that maps my original feature space to $V$ is defined as

$\Phi: x_i \to \phi(x)=K(x_i, x)$.

This map $\Phi$ maps my original feature space onto a vector space that can have a dimension that goed up to the size of my training sample.

Obviously, this transformation (a) depends on the kernel, (b) depends on the values $x_i$ in the training sample and (c) can, depending on my kernel, have a dimension that goes up to the size of my training sample and (d) the vectors of $V$ look like $\sum_{i=1}^N \gamma_i \phi_i$, where $\gamma_i$, $\gamma_i$ are real numbers.

Looking at the function $f(x)$ in How to calculate decision boundary from support vectors? it can be seen that $f(x)=\sum_i y_i \alpha_i \phi_i(x)+b$.

In other words, $f(x)$ is a linear combination of the $\phi_i$ and this is a linear separator in the V-space : it is a particular choice of the $\gamma_i$ namely $\gamma_i=\alpha_i y_i$ !

The $y_i$ are known from our observations, the $\alpha_i$ are the Lagrange multipliers that the SVM has found. In other words SVM find, through the use of a kernel and by solving a quadratic programming problem, a linear separation in the $V$-spave.

This is my intuitive understanding of how the 'kernel trick' allows one to 'implicitly' transform the original feature space into a new feature space $V$, with a different dimension. This dimension depends on the kernel you use and for the RBF kernel this dimension can go up to the size of the training sample.

So kernels are a technique that allows SVM to transform your feature space , see also What makes the Gaussian kernel so magical for PCA, and also in general?

Transform predictors (input data) to a high-dimensional feature space. It is sufficient to just specify the kernel for this step and the data is never explicitly transformed to the feature space. This process is commonly known as the kernel trick.

Let me explain it. The kernel trick is the key here. Consider the case of a Radial Basis Function (RBF) Kernel here. It transforms the input to infinite dimensional space. The transformation of input $x$ to $\phi(x)$ can be represented as shown below (taken from http://www.csie.ntu.edu.tw/~cjlin/talks/kuleuven_svm.pdf)

The input space is finite dimensional but the transformed space is infinite dimensional. Transforming the input to an infinite dimensional space is something that happens as a result of the kernel trick. Here $x$ which is the input and $\phi$ is the transformed input. But $\phi$ is not computed as it is, instead the product $\phi(x_i)^T\phi(x)$ is computed which is just the exponential of the norm between $x_i$ and $x$.

There is a related question Feature map for the Gaussian kernel to which there is a nice answer /stats//a/69767/86202.

The output or decision function is a function of the kernel matrix $K(x_i,x)=\phi(x_i)^T\phi(x)$ and not of the input $x$ or transformed input $\phi$ directly.

Mapping to a higher dimension is merely a trick to solve a problem that is defined in the original dimension; so concerns such as overfitting your data by going into a dimension with too many degrees of freedom are not a byproduct of the mapping process, but are inherent in your problem definition.

Basically, all that mapping does is converting conditional classification in the original dimension to a plane definition in the higher dimension, and because there is a 1 to 1 relationship between the plane in the higher dimension and your conditions in the lower dimension, you can always move between the two.

Taking the problem of overfitting, clearly, you can overfit any set of observations by defining enough conditions to isolate each observation into its own class, which is equivalent of mapping your data to (n-1)D where n is the number of your observations.

Taking the simplest problem, where your observations are [[1,-1], [0,0], [1,1]] [[feature, value]], by moving into the 2D dimension and separating your data with a line, your are simply turning the conditional classification of feature < 1 && feature > -1 : 0 to defining a line that passes through (-1 + epsilon, 1 - epsilon). If you had more data points and needed more condition, you just needed to add one more degree of freedom to your higher dimension by each new condition that your define.

You can replace the process of mapping to a higher dimension with any process that provides you with a 1 to 1 relationship between the conditions and the degrees of freedom of your new problem. Kernel tricks simply do that.