支持向量机（二）

前言

总算要对稍微有点难度的地方动手了，前面介绍的线性可分或者线性不可分的情况，都是使用平面作为分割面的，现在我们采用另一种分割面的设计方法，也就是核方法。
核方法涉及的分割面不再是$wx+b=0$，而是$f(x)=0$了。

具体内容

核方法其实就是坐标映射方法，类似于我们进行回归的时候对于反函数曲线采用$y=\frac{w}{x}+b$的形式来对数据进行拟合。
我们常用的标准做法都是先将原始数据$x$映射为$\frac{1}{x}$，然后对于数据$(\frac{1}{x},y)$寻找线性函数$y=kt+b$来拟合。

在非线性支持向量机中，我们需要把原始特征x通过映射函数变换为$\varphi (x)$，对于这个映射函数没有什么要求，只不过什么样的映射函数映射以后分类效果最佳是未知的，是需要通过比较才能发现的。
映射函数一般都是把原始特征$x$变为另一个向量$[1,x_1,\cdots ,x_n,x_1^2,\cdots ,x_i{x}_j,\cdots ,x_n^2,\cdots ]$其中的一项或者几项，具体是几项视具体情况确定，这个的目标是保留原始信息同时要增加尽可能多的生成信息，所以一般往高维方向映射。
当然这个函数设计好以后，我们在支持向量机的对偶函数中其实计算的是$K(x_i,x_j)$，这个函数是上面映射函数的乘积，可能计算更加复杂，所以从方便对偶函数的计算角度出发，设计了专门的对偶核函数，不过对偶核函数是有要求的，需要对所有特征$x$所构成的gram矩阵是半正定的。
而这种情况下我们可以设计方便计算的核函数，比如：
多项式核函数：$K(x,z)=(x\cdot z+1{)}^p$，计算难度大大减小，而且这个多项式核函数对应的映射函数也比较好求：
$$\begin{array}{rl}K(x,z)& =(x\cdot z+1{)}^2\\ & =(x_1{z}_1+x_2{z}_2+1{)}^2\\ & =x_1^2{z}_1^2+2x_1{x}_2{z}_1{z}_2+2x_1{z}_1+x_2^2{z}_2^2+2x_2{z}_2+1\\ & =[x_1^2,\sqrt{2}{x}_1{x}_2,\sqrt{2}{x}_1,x_2^2,\sqrt{2}{x}_2,1]\ast [z_1^2,\sqrt{2}{z}_1{z}_2,\sqrt{2}{z}_1,z_2^2,\sqrt{2}{z}_2,1{]}^T\end{array}$$

相当于截取了泰勒展开式中的前几项。
换句话说，如果我们想将坐标映射为$[1,x_1,x_2,x_1^2,x_1{x}_2,x_2^2]$，然后利用映射后的坐标来计算$w[1,x_1,x_2,x_1^2,x_1{x}_2,x_2^2{]}^T+b$来作为判别函数，那么这个分界面问题的对偶函数中$\varphi (x_i)\varphi (x_j)$就是上面的$(x\cdot z+1{)}^p$的形式，也就是我们不用知道中间映射后的坐标，而可以直接计算$(x_i\cdot x_j+1{)}^p$。

高斯核函数;$K(x,z)=\exp (-\frac{{\Vert x-z\Vert }^2}{2{\sigma }^2})$，计算难度大大减小，但是这个核函数对应的映射函数不容易求出来。
$$\begin{array}{rl}K(x,z)=& \exp (-\frac{(x_1-z_1{)}^2+(x_2-z_2{)}^2}{2{\sigma }^2})\\ =& \exp (-\frac{x_1^2+z_1^2-2x_1{z}_1+x_2^2+z_2^2-2x_2{z}_2}{2{\sigma }^2})\\ =& \exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{z_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})\exp (-\frac{z_2^2}{2{\sigma }^2})\exp (\frac{2x_1{z}_1}{2{\sigma }^2})\exp (\frac{2x_2{z}_2}{2{\sigma }^2})\\ =& \exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{z_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})\exp (-\frac{z_2^2}{2{\sigma }^2})[1+\frac{2x_1{z}_1}{2{\sigma }^2}+\cdots +\frac{1}{n!}(\frac{2x_1{z}_1}{2{\sigma }^2}{)}^n+\cdots ][1+\frac{2x_2{z}_2}{2{\sigma }^2}+\cdots +\frac{1}{n!}(\frac{2x_2{z}_2}{2{\sigma }^2}{)}^n+\cdots ]\\ =& \exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{z_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})\exp (-\frac{z_2^2}{2{\sigma }^2})[\sum _{t=0}^{+\infty }\sum _{k=0}^{+\infty }\frac{1}{t!}(\frac{2x_1{z}_1}{2{\sigma }^2}{)}^t\frac{1}{k!}(\frac{2x_2{z}_2}{2{\sigma }^2}{)}^k]\\ =& \exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})[1,\frac{x_1}{\sigma },\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1}{\sigma }{)}^n,\cdots ,\frac{x_2}{\sigma },\frac{x_1{x}_2}{{\sigma }^2},\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1^n{x}_2}{{\sigma }^{n+1}}),\cdots ,\sqrt{\frac{1}{t!n!}}\frac{x_1^t{x}_2^n}{{\sigma }^{t+n}},\cdots ]\ast \\ & \exp (-\frac{z_1^2}{2{\sigma }^2})\exp (-\frac{z_2^2}{2{\sigma }^2})[1,\frac{z_1}{\sigma },\cdots ,\sqrt{\frac{1}{n!}}(\frac{z_1}{\sigma }{)}^n,\cdots ,\frac{z_2}{\sigma },\frac{z_1{z}_2}{{\sigma }^2},\cdots ,\sqrt{\frac{1}{n!}}(\frac{z_1^n{z}_2}{{\sigma }^{n+1}}),\cdots ,\sqrt{\frac{1}{t!n!}}\frac{z_1^t{z}_2^n}{{\sigma }^{t+n}},\cdots ]\end{array}$$

所以两个映射函数分别如上所示：
$$\varphi (x)=\exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})[1,\frac{x_1}{\sigma },\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1}{\sigma }{)}^n,\cdots ,\frac{x_2}{\sigma },\frac{x_1{x}_2}{{\sigma }^2},\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1^n{x}_2}{{\sigma }^{n+1}}),\cdots ,\sqrt{\frac{1}{t!n!}}\frac{x_1^t{x}_2^n}{{\sigma }^{t+n}},\cdots ]$$

如果只看后面的向量的话，他就是泰勒展开式中各个项，但是它前面还乘上了系数$\exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})$缩放了一下。
换句话说，这个映射函数把原始特征映射为了一个无穷维的坐标，我们实际上做的是用这个映射后的坐标$\exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})[1,\frac{x_1}{\sigma },\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1}{\sigma }{)}^n,\cdots ,\frac{x_2}{\sigma },\frac{x_1{x}_2}{{\sigma }^2},\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1^n{x}_2}{{\sigma }^{n+1}}),\cdots ,\sqrt{\frac{1}{t!n!}}\frac{x_1^t{x}_2^n}{{\sigma }^{t+n}},\cdots ]$去构成分界面$w\exp (-\frac{x_1^2}{2{\sigma }^2})\exp (-\frac{x_2^2}{2{\sigma }^2})[1,\frac{x_1}{\sigma },\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1}{\sigma }{)}^n,\cdots ,\frac{x_2}{\sigma },\frac{x_1{x}_2}{{\sigma }^2},\cdots ,\sqrt{\frac{1}{n!}}(\frac{x_1^n{x}_2}{{\sigma }^{n+1}}),\cdots ,\sqrt{\frac{1}{t!n!}}\frac{x_1^t{x}_2^n}{{\sigma }^{t+n}},\cdots ]+b$作为分界面，其中$w$为无穷维向量，那么这个分界面问题的对偶函数中$\varphi (x_i)\varphi (x_j)$就是上面的$\exp (-\frac{(x_1-z_1{)}^2+(x_2-z_2{)}^2}{2{\sigma }^2})$的形式，也就是我们不用知道中间映射后的坐标，而可以直接计算$\exp (-\frac{(x_1-z_1{)}^2+(x_2-z_2{)}^2}{2{\sigma }^2})$。