线性不可分问题

不少数据是线性不可分的，对于这种情况，Cover's Theorem 说：在高维空间中，几乎所有的分类问题都是线性可分的。因此，问题就变成了如何将低维数据映射到高维空间中。当然，想要找到这样一个巧妙的映射 $\phi$ 的难度不言而喻，但它至少提供了一种新的思路。核方法带来的另一个问题在于更高维的数据就更加难以训练，也更容易过拟合。

内积问题

支持向量机的核心思想是：最大化数据点与界限之间的距离 (margin) 。由于 margin 与权重 $\omega$ 的范数成反比，因此问题就转换为最小化权重的范数：

$$ \min \frac{1}{2}\|\boldsymbol{w}\|^2 \mid\left(\boldsymbol{w}^T \boldsymbol{x}\right) y \geq 1 $$

通过拉格朗日乘子法，可将上述最小化问题转换为它的对偶问题：

$$ \max \alpha\left[\sum_i \alpha_i-\frac{1}{2} \sum{i, j} \alpha_i \alpha_j y_i y_j \boldsymbol{x}_i^T \boldsymbol{x}_j\right] \mid \alpha_i \geq 0 ; \sum_i \alpha_i y_i=0 $$

经过观察可以发现：该优化问题已经与权重 $\omega$ **无关；也与单个输入数据 $x_i$ 无关，而是需要求解一对输入数据 $<x_i,x_j>$ **的内积 $<x_i, x_j>=x_i^T x_j$。

核方法

假设现在已经找到了映射 $\phi$，那么上式将改为：

$$ \max \alpha\left[\sum_i \alpha_i-\frac{1}{2} \sum{i, j} \alpha_i \alpha_j y_i y_j \phi\left(\boldsymbol{x}_i\right)^T \phi\left(\boldsymbol{x}_j\right)\right] \mid \alpha_i \geq 0 ; \sum_i \alpha_i y_i=0 $$

可见，最终需要求解的东西既不是映射函数 $\phi$ **本身，又不是原始数据的内积，而是映射后数据的内积 $<\phi(x_i),\phi(x_j)>$。

这就启发我们：能不能跳过对映射函数 $\phi$ **的求解，直接对 $<\phi(x_i),\phi(x_j)>$ 进行求解？

这种思路就是寻找核函数（kernel function）$K$：

$$ K\left(\boldsymbol{x}_i, \boldsymbol{x}_j\right)=\phi\left(\boldsymbol{x}_i\right)^T \phi\left(\boldsymbol{x}_j\right)=\left\langle\phi\left(\boldsymbol{x}_i\right), \phi\left(\boldsymbol{x}_j\right)\right\rangle $$

假设我们能随手拿来一个现成的、好用的核函数 $K$ ，那么优化问题就变得十分简单：用核函数 $K$ 代替原式中的内积 $\phi\left(\boldsymbol{x}_i\right)^T \phi\left(\boldsymbol{x}_j\right)$，再进行求解即可。