上篇讲了线性可分支持向量机的对偶形式，这节课我们将引入核技巧(Kernel Trick)。

前面我们学的叫做“线性可分“支持训练集，既然叫做线性可分支持向量机，当然必须要求样本点线性可分了，但现实中大多是线性不可分的，就像下面这张图。所以要让SVM解决线性不可分问题。

想要让SVM解决线性不可分的问题，可以将其转换到高维空间，也就是将$x_i$转换为$\Phi(x_i)$。比如下面这张图，将特征转换到了3维，就可以用支持向量机解决了。

而转换到高维空间，并计算内积的时候$\Phi(x_i)\Phi(x_j)$的计算量会随着变换的复杂度，指数级地增加，假设共$n$个特征，做了二维特征转换，那么内积的计算复杂度就等于$O(n^2)$，那么怎么才能让计算量变小呢？

假设对$x$进行二维转换(polynomial transform)，

$$ \Phi(x)=(1,x_1,x_2,...,x_d,x_1^2,x_1x_2,...,x_2x_d,...,x_d^2) $$

那么，可以推出，两个转换后的特征的内积为：

$$ \Phi_2(x)^T\Phi_2(x\prime)=1+\sum\limits_{i=1}^d x_ix_i\prime + \sum\limits_{i=1}^d\sum\limits_{j=1}^d x_ix_jx_i\prime x_j\prime $$

将第二个$\sum​$后面的公式拆开，可以得到

$$ \Phi_2(x)^T\Phi_2(x\prime)=1+\sum\limits_{i=1}^d x_ix_i\prime + \sum\limits_{i=1}^d x_i x_i\prime \sum\limits_{j=1}^d x_j x_j\prime $$

那么，可以得出，三个$\sum​$里面都是内积，于是就得出

$$ \Phi_2(x)^T\Phi_2(x\prime)=1+\langle x_i,x_i\prime\rangle + \langle x_i,x_i\prime\rangle\langle x_i,x_i\prime\rangle $$

这样，将转换->做内积的步骤，变成 内积->转换，计算复杂度与原始的特征数量有关，仍为$O(n)$极大地节省了计算量。

这就是核函数(Kernel Function)的思想。

$\Phi_2=K_\Phi(x,x\prime)=1+\langle x_i,x_i\prime\rangle + \langle x_i,x_i\prime\rangle\langle x_i,x_i\prime\rangle​$

上面的核函数叫做多项式核函数，上面是二维的，所以叫二维多项式核(Poly-2 Kernel)。可以动态调整自由度来调整边界的复杂程度。下面是不同自由度时边界曲线的样子，可以看出来，自由度越低，边界曲线越简单，反之边界曲线则更复杂。

当然，可以将函数更加“复杂化”，一遍更细致地调参，比如加入两个自由度

$$ K_2(x,x\prime)=(\zeta+\gamma \langle x_i,x_i\prime\rangle)^2 $$

其中，$\gamma>0​$，$\zeta\ge0​$。

当然，也可以将特征转换到更高维度，而不仅仅是二维：

$$ \begin{aligned} K_2(x,x\prime)&=(\zeta+\gamma \langle x_i,x_i\prime\rangle)^2\\ K_3(x,x\prime)&=(\zeta+\gamma \langle x_i,x_i\prime\rangle)^3\\ &...\\ K_Q(x,x\prime)&=(\zeta+\gamma \langle x_i,x_i\prime\rangle)^Q\\ \end{aligned} $$

线性支持向量机，是多项式核的一个特例，$\zeta=0,\gamma=1,Q=1$

$$ K_1(x,x\prime)=(0+1\cdot \langle x_i,x_i\prime\rangle)^1 =\langle x_i,x_i\prime\rangle $$

Gaussian Kernel

既然将转换到高维空间，可以得到更多的特征，获得更多特征间的关系，如果能将其转换到无限维(也就是无限维的$\Phi_{\infty}(x)$ )，效果岂不是很牛逼？

话虽如此，但是如果特征转换为无限维，计算量不是也无限大了吧？核函数将其变为有限次计算吗？这就引入了高斯核函数(Gaussian Kernel)：

假设有这么一个核函数：

$$ K(x,x\prime)=exp(-(x-x\prime)^2) $$

可以将他们拆开：

$$ K(x,x\prime)=exp(-x^2)exp(-(x\prime)^2)exp(2xx\prime) $$

对最后一个exp中的值，从0点进行泰勒展开：

$$ K(x,x\prime)=exp(-x^2)exp(-(x\prime)^2)\Big(\sum\limits_{i=0}^\infty \frac{(2xx\prime)^i}{i!} \Big) $$

将有$x$的项放在一起，有$x\prime$项放在另外一边，那么可以得出

$$ K(x,x\prime)=\sum\limits_{i=0}^\infty \bigg(exp(-x^2)\frac{\sqrt{2^i}}{\sqrt{i!}}{x^i} \bigg)\bigg(exp(-(x\prime)^2)\frac{\sqrt{2^i}}{\sqrt{i!}}{(x\prime)^i}\bigg) $$

设核函数

$$ K(x,x\prime)=\Phi(x)^T\Phi(x\prime) $$

那么就可以得到一个拥有无限维的$\Phi(x)=exp(-x^2)\cdot (1,\sqrt{\frac{2}{1!}}x,\sqrt{\frac{2^2}{2!}}x^2,...)$ ！

还可以加上一个自由度，可以让我们进行调参：

$$ K(x,x\prime)=exp(-\gamma||x-x\prime||) $$

基于高斯核函数的算法，最终的判别式是这样的：

$$ \begin{aligned} g_{SVM}(x)&=sgn\bigg(\sum\limits_{SV}\alpha_ny_nK(x_n,x)+b\bigg)\\ &=sgn\Bigg(\sum\limits_{SV}\alpha_ny_nexp\bigg(\gamma||x-x_n||^2\bigg)+b\Bigg) \end{aligned} $$

上一篇中说了，$\alpha_i​$不等于0时，$(x_i,y_i)​$是支持向量。可以看出，最终的判别公式，是以支持向量为中心建立的。也就是支持向量的线性组合。所以，高速核通常也被称为径向基函数(radial based function，RBF)。

不同自由度($\gamma$)的高斯核，最终的效果有很大差异，可以看下面这张图：

可以看出来，$\gamma$越高，对边界宽度的要求就越高，所以$\gamma$太高就变成这个吊样，所以高斯核的$\gamma$太大，还是会overfit的。

两个核函数的比较