主要思想

定理：
对于线性不可分的点，一定可以有一个维度使其线性可分。

基于此定理，我们可以使用支持向量机解决线性不可分的数据，即把数据集映射到一个高纬度，之后再进行线性分类。

升维

假设原先的样本点是 $\vec x_i$，用 $\phi(\vec x_i)$ 表示映射到新的特征空间后的新样本点。那么分割超平面可以表示为

$f(\vec x)=\vec w\phi(\vec x)+b$

于是非线性支持向量机的对偶问题就成了：

$\max\limits_\vec\alpha\sum\limits^N_{i=1}\alpha_i-\frac{1}{2}\sum\limits^N_{i=1}\sum\limits^N_{j=1}\alpha_i\alpha_jy_iy_j\phi(\vec x_i)^T\phi(\vec x_j)$ $s.t.\ \sum\limits^N_{i=1}\alpha_iy_i=0,\ 0\le\alpha_i\le C$

但是从低维空间映射到高维空间后的维度可能很高，这样会大大增加 $\phi(\vec x_i)^T\phi(\vec x_j)$ 的计算量，所以需要通过其它办法来简化运算。这就用到了核函数。

核函数

核函数的作用

由于目标函数和分类决策函数都只涉及样本之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。设 $K(x,z)$ 是一个核函数，或正定核，则存在一个从输入空间到特征空间的映射 $\phi(\vec x)$，对任意输入空间的 $\vec x,\vec z$ 有

$K(\vec x,\vec z)=\phi(\vec x)\cdot\phi(\vec z)$

假设我们的输入空间是 $m$ 维，特征空间是 $d$ 维，那么通过核函数就可以把 $d$ 维运算降到 $m$ 维运算。当 $d$ 非常大甚至是无穷时，核函数可以减少大量的运算。

常见的核函数

线性核函数：$K(\vec x_i,\vec x_j)=\vec x_i^T\vec x_j+c$
多项式核函数：$K(\vec x_i,\vec x_j)=(\alpha\vec x_i^T\vec x_j+c)^d$
径向基核函数（高斯核函数）：$K(\vec x_i,\vec x_j)=e^{-\gamma\parallel\vec x_i-\vec x_j\parallel^2}$
$sigmod$ 核函数：$K(\vec x_i,\vec x_j)=\tanh(\alpha\vec x_i^T\vec x_j+c)$