机器学习-支持向量机的数学讨论

1 支持向量机的特点：

• 泛化错误率较低，计算开销不大，结果容易解释；
• 对于参数和核函数选择敏感
• 可以适用于标称型数据和数值型数据

2 SVM解释如下：

• 对于二分类问题，寻找其线性可分的可能性。如果能够实现分割，则称为分割超平面。具体的，对于N维数据，需要构建一个(N-1)维的超平面。
• 由于超平面的构建的多样性，可以引入支持向量的概念，来量化分割超平面的好坏，从而定义超平面两侧的点到超平面的最小垂直距离
• 将超平面两侧点到超频面的最小垂直距离称为间隔，希望间隔越小越好，这样能够实现较高的数据容差，保证了分类器的稳健。而支持向量就是离分隔超平面最近的点。

3 如何求解点到分割超平面的距离？

• 为了研究分割超平面，首先需要给出其数学形式，最简单的N维数据分割超平面形式为w⃗ Tx⃗ +b=0${\overrightarrow{w}}^T\overrightarrow{x}+b=0$，其中w⃗ $\overrightarrow{w}$为
  N*1向量，x⃗ $\overrightarrow{x}$为N*1向量，而b为标量。
• 对于任意一点A，坐标记为(x1,x2,...,xN)$(x_1,x_2,...,x_N)$，距离上述分割超平面的距离为|w⃗ TA⃗ +b|||w⃗ ||$\frac{|{\overrightarrow{w}}^T\overrightarrow{A}+b|}{||\overrightarrow{w}||}$。数学证明可以采用向量方式，初等数学即可。

4 如何评价分类情况的好坏

• 对于计算得到的超平面方程，可以将测试点带入，这样可以得到一个数据，具体来说，代入点u⃗ $\overrightarrow{u}$，计算y=w⃗ Tu⃗ +b$y={\overrightarrow{w}}^T\overrightarrow{u}+b$。然后将结果输入到一个二分类的非线性函数中，得到映射后的分类情况。
• 支持向量机使用的非线性函数是采用label=+-1映射的情况，因此可以使用label(w⃗ Tu⃗ +b)$label({\overrightarrow{w}}^T\overrightarrow{u}+b)$，这样当结果较大时，则表明点u在离超平面很远的地方，间距较大。当然，如果分类错误，则会产生一个负数，负数越大，证明分类的误差越大。

5 如何定义优化的目标函数

• 根据上述分析，可以定义出一个优化问题： 存在参数(向量w和标量b)，需要步骤4的表达式，也就是label(w⃗ Tu⃗ +b)$label({\overrightarrow{w}}^T\overrightarrow{u}+b)$尽量大。由于存在多个u，则可以定义评价函数。
• 问题表述为(较难求解)
  
  argmaxw⃗ ,b{min(label∗(w⃗ Tu⃗ +b)||w⃗ ||)}$$\arg \underset{\overrightarrow{w},b}{max}\{min(\frac{label\ast ({\overrightarrow{w}}^T\overrightarrow{u}+b)}{||\overrightarrow{w}||})\}$$

6 标准形式的推导

• 上式较难求解，可以采用等效变换的方式。首先，向量w⃗ $\overrightarrow{w}$和标量b$b$可以同时放大或者缩小k倍，这并不会影响上述求解值（向量平移性质有关）。因此，可以利用该条件，定义label(w⃗ Tu⃗ +b)>=1$label({\overrightarrow{w}}^T\overrightarrow{u}+b)>=1$，其中支持向量能够使得等式成立。如果满足该条件，那么原问题也成立。当然，这是假设分类均正确
• 接下来，对于分数形式的优化，可以采用最小化分子项和最大化分母项来进行，分子项最小为1，因此该式可以转换为如下的优化问题：
  
  argminw⃗ ,b1||w⃗ ||$$\arg \underset{\overrightarrow{w},b}{min}\frac{1}{||\overrightarrow{w}||}$$
• 为了能够求解上一个优化问题，结合二次规划算法，可以最终将等式转化如下：
  
  argminw⃗ ,b12||w⃗ ||2,st.yi(w⃗ Txi→+b)>=1$$\arg \underset{\overrightarrow{w},b}{min}\frac{1}{2}||\overrightarrow{w}|{|}^2,st.y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b)>=1$$
• 对于上述问题，可以利用凸二次优化方法进行求解。QP方法 quadratic programming

7 对偶形式推导

7.1 拉格朗日乘子法： 将带约束的情况转换为无约束情况。

• 对于等式约束的拉格朗日乘子法，其原理为（可能的一种理解方法）：
  
  1. 对于minf(x⃗ ),st.wi→Tx⃗ +bi=0,i=1...N$minf(\overrightarrow{x}),st.{\overrightarrow{w_i}}^T\overrightarrow{x}+b_i=0,i=\mathrm{1...}N$，可以转换为无约束的等式L(x⃗ ,αi)=f(x⃗ )+∑i=1 to Nαi(wi→Tx⃗ +bi)$L(\overrightarrow{x},{\alpha }_i)=f(\overrightarrow{x})+\sum _{i=1toN}{\alpha }_i({\overrightarrow{w_i}}^T\overrightarrow{x}+b_i)$；
  2. 对于上式L，求解对于x的偏导项，则可以得到x关于αi${\alpha }_i$的表示，x项从∂f/∂x$\mathrm{\partial }f/\mathrm{\partial }x$产生，而αi${\alpha }_i$从后面的项产生；
  3. 将x关于αi${\alpha }_i$的表示带入约束等式中，可以得到αi${\alpha }_i$的值，该值能够保证约束等式成立，也就是说，L(x,αi)=L(αi)=f(x)$L(x,{\alpha }_i)=L({\alpha }_i)=f(x)$。而对于L(x,α)$L(x,\alpha )$显然是通过进行偏微分求最小化的过程，这也意味着，得到的α$\alpha$能够保证f(x)$f(x)$得到最小化的结果；
  4. 将αi${\alpha }_i$带入x等式，得到满足条件的等式。
     综上，也就是说，如果能够找到一组αi${\alpha }_i$，使得x能用αi${\alpha }_i$表示，保证满足约束等式。那么，无约束问题等于有约束问题，而对于无约束问题的求导，则对应了有约束问题的导数值为0的情况。
• 一般的拉格朗日乘子法(KKT条件)，这里将非线性优化问题转换为固定的优化问题，可以尝试采取算法进行求解。
  
• 对于KTT条件的一种理解方法是，如果存在一个优化的x不满足该条件，如果h(x)!=0，那么可以取β$\beta$很大，则L趋于无穷大；如果g(x)>0，那么取α$\alpha$很大，则L也趋于无穷大。这两种情况都不存在极值。
• 或者另外一种理解方法（不一定对），对于L进行α$\alpha$偏导时，得到的是g(x)，该函数始终小于0，则导致无法得到有效极值。因此需要存在第四项条件。
• 第三项条件是由于g(x)<=0约束得到，当不满足α>=0$\alpha >=0$，则α$\alpha$可以取极小的负数，也不存在极值。

综上，得到了一个无约束条件的函数Θp(x)=maxα,β;α>=0L(x,α,β)${\mathrm{\Theta }}_p(x)=\underset{\alpha ,\beta ;\alpha >=0}{max}L(x,\alpha ,\beta )$,求解该问题时，如果x满足约束条件，则Θp(x)=f(x)${\mathrm{\Theta }}_p(x)=f(x)$，否则将趋于无穷大。

7.2 对于SVM的等效变换

• 对于下列优化问题，
  

  argminw⃗ ,b12||w⃗ ||2,st.yi(w⃗ Txi→+b)>=1$$\arg \underset{\overrightarrow{w},b}{min}\frac{1}{2}||\overrightarrow{w}|{|}^2,st.y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b)>=1$$
  
  可以利用拉格朗日乘子法进行等效，
  
  argmaxw⃗ ,b12||w⃗ ||2+∑i=1Nαi(1−yi(w⃗ Txi→+b))$$\arg \underset{\overrightarrow{w},b}{max}\frac{1}{2}||\overrightarrow{w}|{|}^2+\sum _{i=1}^N{\alpha }_i(1-y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b))$$
  
  该广义变换需要满足如下条件：
  
  ∂L(w⃗ ,b,αi)/∂w⃗ =0$$\mathrm{\partial }L(\overrightarrow{w},b,{\alpha }_i)/\mathrm{\partial }\overrightarrow{w}=0$$
  
  
  ∂L(w⃗ ,b,αi)/∂b=0$$\mathrm{\partial }L(\overrightarrow{w},b,{\alpha }_i)/\mathrm{\partial }b=0$$
  
  
  ∂L(w⃗ ,b,αi)/∂αi=0$$\mathrm{\partial }L(\overrightarrow{w},b,{\alpha }_i)/\mathrm{\partial }{\alpha }_i=0$$
  
  
  αi>=0$${\alpha }_i>=0$$
  
  
  yi(w⃗ Txi→+b)>=1$$y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b)>=1$$
  
  
  ∑i=1Nαi(1−yi(w⃗ Txi→+b)=0$$\sum _{i=1}^N{\alpha }_i(1-y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b)=0$$
  
  该问题本质是求解一个minw⃗ ,bΘp(x)=minw⃗ ,bmaxαi;αi>=0L(w⃗ ,b,αi)$\underset{\overrightarrow{w},b}{min}{\mathrm{\Theta }}_p(x)=\underset{\overrightarrow{w},b}{min}\underset{{\alpha }_i;{\alpha }_i>=0}{max}L(\overrightarrow{w},b,{\alpha }_i)$，这是一个极小极大值问题，内层带约束项，可以利用拉格朗日对偶原理转换为极大极小值问题，内层优化问题无约束。

• 由于内层优化无约束，则可以利用导数为零获得，获得的w和b为内层最优化的候选解。
  

  ∂L(w⃗ ,b,αi)/∂w⃗ =0$$\mathrm{\partial }L(\overrightarrow{w},b,{\alpha }_i)/\mathrm{\partial }\overrightarrow{w}=0$$
  
  
  ∂L(w⃗ ,b,αi)/∂b=0$$\mathrm{\partial }L(\overrightarrow{w},b,{\alpha }_i)/\mathrm{\partial }b=0$$
  
  该等式的结果为：
  
  w⃗ =∑i=1Nαiyixi→$$\overrightarrow{w}=\sum _{i=1}^N{\alpha }_i{y}_i\overrightarrow{x_i}$$
  
  
  ∑i=1Nαiyi=0$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$
  
  将这两个等式带入，则得到只包含外层优化的情况，该优化问题是一个约束优化问题：
  
  maxαi;αi>=0(∑i=1Nαi−12∑i=1N∑j=1Nαiαjyiyjxi→Txj→)$$\underset{{\alpha }_i;{\alpha }_i>=0}{max}(\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{\overrightarrow{x_i}}^T\overrightarrow{x_j})$$
  
  
  st. αi>=0;∑i=1Nαiyi=0$$st.{\alpha }_i>=0;\sum _{i=1}^N{\alpha }_i{y}_i=0$$

8 SVM的求解和最终形式确定

• 通过SMO等方法，可以求得上述优化问题的αi${\alpha }_i$，然后w⃗ $\overrightarrow{w}$可以利用w⃗ =∑i=1Nαiyixi→$\overrightarrow{w}=\sum _{i=1}^N{\alpha }_i{y}_i\overrightarrow{x_i}$得到。
• b的确定需要追溯到开始的简化条件，因为前面，我们假设了yi(w⃗ Txi→+b)>=1$y_i({\overrightarrow{w}}^T\overrightarrow{x_i}+b)>=1$，并且对于支持向量等号成立。另外一方面，根据拉格朗日乘子法的一些性质，当αi>0${\alpha }_i>0$，则对应的输入xi$x_i$即为支持向量。
• 具体的操作是，选取所有αi>0${\alpha }_i>0$，对于每一个αi${\alpha }_i$，带入下面等式，其中下标为i代表支持向量。
  
  b∗=yi−∑j=1Nαjyj<xi→,xj→>$$b^{\ast }=y_i-\sum _{j=1}^N{\alpha }_j{y}_j<\overrightarrow{x_i},\overrightarrow{x_j}>$$

• 为了进一步缩小误差，可以采用平均方法，将所有的αi>0${\alpha }_i>0$的情况得到的b进行平均

• 最终得到的分类器如下所示，因此对于SVM的结果存储，可以只存储求解得到的αi>0${\alpha }_i>0$和对应的支持向量xi→$\overrightarrow{x_i}$，以及求解得到的b∗$b^{\ast }$。预测过程中所需要的内存空间非常小。
  

  f(x⃗ )=sign{∑i=1N(α∗iyi<xi→,x⃗ >+b∗)}$$f(\overrightarrow{x})=sign\{\sum _{i=1}^N({\alpha }_i^{\ast }{y}_i<\overrightarrow{x_i},\overrightarrow{x}>+b^{\ast })\}$$

• SVM没有假设数据的分布情况，其最优的思想来源于使得不同类别距离分类平面的间距尽量大。

9 允许分类错误的SVM推导

• 如下图所示，左侧为无分类错误的硬间隔SVM，右侧为存在分类错误的软间隔SVM。在右图中，存在训练错误的包括了ξ∗1,ξ∗2,ξ∗3,ξ∗4,ξ∗5${\xi }_1^{\ast },{\xi }_2^{\ast },{\xi }_3^{\ast },{\xi }_4^{\ast },{\xi }_5^{\ast }$。
  
  因此对于软间隔SVM，存在以下五种分类情况：

  • 在间隔以外的情况，这是分类正确的情况，并且这类数据不构成支持向量(αi=0,yif(xi→)−1>0,ξi=0${\alpha }_i=0,y_{i}f(\overrightarrow{x_i})-1>0,{\xi }_i=0$)
  • 在间隔线上，这也是分类正确的情况，这类数据构成支持向量(C>αi>0,yif(xi→)−1=0,ξi=0$C>{\alpha }_i>0,y_{i}f(\overrightarrow{x_i})-1=0,{\xi }_i=0$)
  • 在间隔内部，但是未达到分类错误的地步，例如ξ∗1,ξ∗2,ξ∗4${\xi }_1^{\ast },{\xi }_2^{\ast },{\xi }_4^{\ast }$，此时对应了αi=C,yif(xi→)−1<0,0<ξi<1${\alpha }_i=C,y_{i}f(\overrightarrow{x_i})-1<0,0<{\xi }_i<1$
  • 在分类超平面上，此时对应了αi=C,yif(xi→)−1<0,ξi=1${\alpha }_i=C,y_{i}f(\overrightarrow{x_i})-1<0,{\xi }_i=1$
  • 跨过分类超平面，此时分类错误，对应了αi=C,yif(xi→)−1<0,ξi>1${\alpha }_i=C,y_{i}f(\overrightarrow{x_i})-1<0,{\xi }_i>1$

• 综合上述分析，可以得到下列的基于hinge-loss的SVM优化问题：

- 同样利用拉格朗日乘子法进行优化，并结合拉格朗日对偶原理，得到的优化问题如下：

为了使得上述两式相等，需要满足KKT条件：







对于上上式，内层求解为无约束情况，则可以通过求解偏导数为0得到候选等式，然后带入外层得到等效的问题，该问题得以极大简化，与硬间隔SVM相比，多了一个上约束，同样可以采用SMO进行求解。（多了一个等式约束αi+μi=C${\alpha }_i+{\mu }_i=C$）

• 在获得可行的αi${\alpha }_i$后，可以得到w⃗ =∑i=1Nαiyixi→$\overrightarrow{w}=\sum _{i=1}^N{\alpha }_i{y}_i\overrightarrow{x_i}$，然后选取C>αi>0$C>{\alpha }_i>0$的情况，这对应了支持向量，求解得到b∗=yi−∑Nj=1αjyj<xi→,xj→>$b^{\ast }=y_i-\sum _{j=1}^N{\alpha }_j{y}_j<\overrightarrow{x_i},\overrightarrow{x_j}>$。而上述分析中的C控制允许误差的大小，ξi${\xi }_i$对应了每一项的分类误差情况，输出为hinge-loss的大小。
• 总体总结如下：
  
  • αi=0${\alpha }_i=0$，此时分类正确，在间隔外部，ξi=0,μi=C${\xi }_i=0,{\mu }_i=C$
  • C>αi>0$C>{\alpha }_i>0$，此时为支持向量，ξi=0,0<μi<C${\xi }_i=0,0<{\mu }_i<C$
  • αi=C${\alpha }_i=C$，此时间隔内，误差由ξi${\xi }_i$决定，μi=0${\mu }_i=0$

10. 非线性SVM的推导

• 实际操作时，将上述的x⃗ Tx⃗ ${\overrightarrow{x}}^T\overrightarrow{x}$换成核函数即可。
• 非线性SVM运用的原理是，有限维属性的数据可以通过高维映射转化为高维可分的情况。而映射问题会出现无法预估映射后线性可分的可行性，以及可能会带来的过拟合问题，因此可以使用核函数代替高维映射操作，简化了操作。

• 值得注意的时，高维映射操作和核函数操作无直接关联，高维映射操作是通过升维内积的方式，而核函数是通过内积变换的方式，二者不存在对应关系。
  

• 能够作为核函数需要满足核函数定理，即对于任意一个矩阵，其列向量的内积构成的矩阵元素通过核函数操作后得到的矩阵是半正定的，那么该对称函数可以作为核函数。对称半正定还带来其他性质，例如行列式非负、顺序主子式非负、特征值非负等，其定义来自于二次型非负。

• 常用的核函数包括线性、多项式、高斯核、拉普拉斯核、sigmoid核。
• 核函数的正数线性组合、核函数的积、核函数与任意函数的组合同样为核函数，可以参考西瓜书page128~129.

http://blog.****.net/daunxx/article/details/52079403