支持向量机（二）

前言

总算要对稍微有点难度的地方动手了，前面介绍的线性可分或者线性不可分的情况，都是使用平面作为分割面的，现在我们采用另一种分割面的设计方法，也就是核方法。
核方法涉及的分割面不再是$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$，计算难度大大减小，而且这个多项式核函数对应的映射函数也比较好求：
K ( x , z ) = ( x ⋅ z + 1 ) 2 = ( x 1 z 1 + x 2 z 2 + 1 ) 2 = x 1 2 z 1 2 + 2 x 1 x 2 z 1 z 2 + 2 x 1 z 1 + x 2 2 z 2 2 + 2 x 2 z 2 + 1 = [ x 1 2 , 2 x 1 x 2 , 2 x 1 , x 2 2 , 2 x 2 , 1 ] ∗ [ z 1 2 , 2 z 1 z 2 , 2 z 1 , z 2 2 , 2 z 2 , 1 ] T

K(x,z)​=(x⋅z+1)2=(x1​z1​+x2​z2​+1)2=x12​z12​+2x1​x2​z1​z2​+2x1​z1​+x22​z22​+2x2​z2​+1=[x12​,2 ​x1​x2​,2 ​x1​,x22​,2 ​x2​,1]∗[z12​,2 ​z1​z2​,2 ​z1​,z22​,2 ​z2​,1]T​

相当于截取了泰勒展开式中的前几项。
换句话说，如果我们想将坐标映射为$[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})$，计算难度大大减小，但是这个核函数对应的映射函数不容易求出来。
K ( x , z ) = exp ⁡ ( − ( x 1 − z 1 ) 2 + ( x 2 − z 2 ) 2 2 σ 2 ) = exp ⁡ ( − x 1 2 + z 1 2 − 2 x 1 z 1 + x 2 2 + z 2 2 − 2 x 2 z 2 2 σ 2 ) = exp ⁡ ( − x 1 2 2 σ 2 ) exp ⁡ ( − z 1 2 2 σ 2 ) exp ⁡ ( − x 2 2 2 σ 2 ) exp ⁡ ( − z 2 2 2 σ 2 ) exp ⁡ ( 2 x 1 z 1 2 σ 2 ) exp ⁡ ( 2 x 2 z 2 2 σ 2 ) = exp ⁡ ( − x 1 2 2 σ 2 ) exp ⁡ ( − z 1 2 2 σ 2 ) exp ⁡ ( − x 2 2 2 σ 2 ) exp ⁡ ( − z 2 2 2 σ 2 ) [ 1 + 2 x 1 z 1 2 σ 2 + ⋯ + 1 n ! ( 2 x 1 z 1 2 σ 2 ) n + ⋯   ] [ 1 + 2 x 2 z 2 2 σ 2 + ⋯ + 1 n ! ( 2 x 2 z 2 2 σ 2 ) n + ⋯   ] = exp ⁡ ( − x 1 2 2 σ 2 ) exp ⁡ ( − z 1 2 2 σ 2 ) exp ⁡ ( − x 2 2 2 σ 2 ) exp ⁡ ( − z 2 2 2 σ 2 ) [ ∑ t = 0 + ∞ ∑ k = 0 + ∞ 1 t ! ( 2 x 1 z 1 2 σ 2 ) t 1 k ! ( 2 x 2 z 2 2 σ 2 ) k ] = exp ⁡ ( − x 1 2 2 σ 2 ) exp ⁡ ( − x 2 2 2 σ 2 ) [ 1 , x 1 σ , ⋯   , 1 n ! ( x 1 σ ) n , ⋯   , x 2 σ , x 1 x 2 σ 2 , ⋯   , 1 n ! ( x 1 n x 2 σ n + 1 ) , ⋯   , 1 t ! n ! x 1 t x 2 n σ t + n , ⋯   ] ∗ exp ⁡ ( − z 1 2 2 σ 2 ) exp ⁡ ( − z 2 2 2 σ 2 ) [ 1 , z 1 σ , ⋯   , 1 n ! ( z 1 σ ) n , ⋯   , z 2 σ , z 1 z 2 σ 2 , ⋯   , 1 n ! ( z 1 n z 2 σ n + 1 ) , ⋯   , 1 t ! n ! z 1 t z 2 n σ t + n , ⋯   ]

K(x,z)======​exp(−2σ2(x1​−z1​)2+(x2​−z2​)2​)exp(−2σ2x12​+z12​−2x1​z1​+x22​+z22​−2x2​z2​​)exp(−2σ2x12​​)exp(−2σ2z12​​)exp(−2σ2x22​​)exp(−2σ2z22​​)exp(2σ22x1​z1​​)exp(2σ22x2​z2​​)exp(−2σ2x12​​)exp(−2σ2z12​​)exp(−2σ2x22​​)exp(−2σ2z22​​)[1+2σ22x1​z1​​+⋯+n!1​(2σ22x1​z1​​)n+⋯][1+2σ22x2​z2​​+⋯+n!1​(2σ22x2​z2​​)n+⋯]exp(−2σ2x12​​)exp(−2σ2z12​​)exp(−2σ2x22​​)exp(−2σ2z22​​)[t=0∑+∞​k=0∑+∞​t!1​(2σ22x1​z1​​)tk!1​(2σ22x2​z2​​)k]exp(−2σ2x12​​)exp(−2σ2x22​​)[1,σx1​​,⋯,n!1​ ​(σx1​​)n,⋯,σx2​​,σ2x1​x2​​,⋯,n!1​ ​(σn+1x1n​x2​​),⋯,t!n!1​ ​σt+nx1t​x2n​​,⋯]∗exp(−2σ2z12​​)exp(−2σ2z22​​)[1,σz1​​,⋯,n!1​ ​(σz1​​)n,⋯,σz2​​,σ2z1​z2​​,⋯,n!1​ ​(σn+1z1n​z2​​),⋯,t!n!1​ ​σt+nz1t​z2n​​,⋯]​

所以两个映射函数分别如上所示：
$$\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})$。