SVM 算法原理总结

Algorithm

1. 整体的算法逻辑

• 基于 kernel function 对原始 dataSet 进行升维处理，基于 Cover 定理可知，在低维空间线性不可分的问题在高维空间线性可分。
• 当问题变为线性可分时，会存在多种划分方案。
• 
• 问题进而转化为，当问题在高维线性可分，如何做到最优划分？SVM 对最优划分的定义是：具有最大间隔的划分hyperplane为最优解。
• 
• “间隔”是指，两个异类支持向量到超平面的距离之和。hyperplane 为间隔区域的中轴线。

2. 数学表达

2.1 SVM 的原问题

• 定义 hyperplane 的数学公式
  $w^Tx+b=0$
• 样本空间中的任意点到 hyperplane 的距离为：
  $r = \frac{|w * x_i + b|}{||w||}$
  (1). 整个式子可以理解为点到线的距离公式；
  (2). 分子是向量的2范数，可以理解为欧式距离。
  $\|\vec x\|_2 = (|x_1|^2 + \cdots+|x_m|^2)^{\frac{1}2}$
• 当样本点被正确分类时，数学表达为：
  $\begin{cases} w*x_i+b\geq1, & \text {$y_i = +1$} \\ w*x_i+b\leq1, & \text{$y_i = -1$} \end{cases}$
  等价于：
  $\quad y_i(w*x_i+b)\geq1, i=1,2,\cdots,m$

• 如下图所示
  

• 两个异类支持向量到超平面的距离之和为:
  $\gamma = \frac{2}{||w||}$，称$\gamma$为“间隔”。
  欲使划分的超平面对训练样本的局部扰动“容忍”性最好，需要使间隔最大。故得到如下的约束优化模型

• SVM 的原问题的数学表达为：
  $\eqalign{ & \mathop {\max }\limits_{w,b} {{2} \over {||w||}} \cr & s.t.\;{y_i}(w^T{x_i} + b) \ge 1 {\qquad i = 1,2,...,N} \cr}$
• 因为$\max {1 \over {||w||}}$和$\min {1 \over 2}||w|{|^2}$等价，考虑目标函数的优化方向为最小化更容易让人舒服，故将 SVM 的原问题改为：
  $\eqalign{ & \min\limits_{w,b} {1 \over 2}||w|{|^2} \cr & s.t.\;{y_i}(w^T{x_i} + b) \ge 1 {\qquad i = 1,2,...,N} \cr}$

2.2 SVM 的对偶问题

• SVM 的原问题是一个凸二次规划：
  
  1. General speaking，引入对偶问题后，求解方法更为简单。
  2. 引入对偶问题后，意外地可以用 kernel trick 来简化计算。
• 对 SVM 的原问题使用拉格朗日乘子法即可得到其“对偶问题（dual problem）”，具体来说是对 SVM 的原问题加入拉格朗日乘子${\alpha _i} \ge 0$，拉格朗日函数可写为：
  $\eqalign{ & L(w,b,\alpha ) = {1 \over 2}||w|{|^2} + \sum\limits_{i = 1}^N {{\alpha _i}(1 - } {y_i}(w{x_i} + b)) \cr & s.t.\; {\alpha _i} \ge 0\qquad i = 1,2,...,N \cr}$
• 令$L(w,b,\alpha )$对$w$和$b$偏导为零，带回$L(w,b,\alpha )$，即可得到 SVM 的对偶问题数学表达式：
  $\begin{aligned} & \max_{\boldsymbol{\alpha}}\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j}\\ & s.t.\quad\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\quad\alpha_{i}\geq 0, i=1,2,\dots,m. \end{aligned}$
• 对偶问题的 KKT 条件，即若一个可行解为最优解，那么它必须满足 KKT 条件。KKT 条件的数学表达：
  $\begin{cases} \alpha_{i}\geq 0;\\ y_{i}f(\boldsymbol{x}_{i})-1\geq 0;\\ \alpha_{i}(y_{i}f(\boldsymbol{x}_{i})-1)=0. \end{cases}$
• 解出$α$后，求出$w$和$b$，即可得到模型：
  $f(\boldsymbol{x})=\boldsymbol{w}^{T}\boldsymbol{x}+b=\sum_{i=1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{x}+b\tag{*}$
• KKT 条件为了告诉我们，对于任意训练样本$(x_i,y_i)$，总有$α_i=0$或$y_if(x_i)=1$。若$α_i=0$，则该样本不会在式(*)的求和中出现。若$α_i>0$，则必有$y_if(x_i)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
• KKT条件对应最优解，而约束条件对应的是可行解。

2.3 使用 SMO 求解 SVM 的过程

• 确定了 SVM 的目标函数（对偶问题），接下来就是如何用计算机求解出最优解。
• 一个比较高效的方法是 SMO（Sequential Minimal Optimization）
• SMO 算法的思想是将一个大的优化问题分解为多个小优化问题，这些小优化问题往往容易求解，并且对它们进行顺序求解的结果和将它们作为整体进行求解的结果完全一致。
• SMO 的求解依据是：可行解满足 KKT 条件，即为最优解，即可停止计算。
  可以理解为：SMO 是一种启发式算法，若所有的变量都满足 KKT 条件，即确认得到最优解。
• SMO 的算法逻辑是：
  
  1. 在所有的$\alpha_i$中选择违反 KKT 条件最严重的；（SMO的外层循环变量选择）
  2. 选择能够最大化$|E_i-E_j|$的拉格朗日乘子（目的是为了加快更新速度），$E_i$为输入的$x_i$的预测值与真实输出$y_i$之间的差
  3. 当所有的样本都满足KKT条件，那么就表示迭代结束了。但是由于KKT条件本身是比较苛刻的，所以也需要设定一个容忍值，即所有样本在容忍值范围内满足KKT条件则认为训练可以结束。
• SMO 的整个计算过程一定是收敛的：
  因为每次求解的$\alpha_i$与$\alpha_j$，是对偶问题在$\alpha_i$与$\alpha_j$上的极小值（习惯性地将目标函数的优化方向设为min，即给原对偶问题的目标函数乘以-1即可），所以每一步优化都会使目标函数比上一次优化结果变小。
• 详细过程，请参见

2.4 Kernel Function

• 回顾一下 SVM 的对偶问题形式为：
  $\begin{aligned} & \max_{\boldsymbol{\alpha}}\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})\\ & s.t.\quad\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\quad\alpha_{i}\geq 0, i=1,2,\dots,m. \end{aligned}\tag{21}$
• 式（21）中最大的计算量来自计算$\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})$。特别地，当特征空间维数较高时直接计算会更加困难。为了避开这个barrier，希望有一个function能实现：
  $\kappa(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\langle\phi(\boldsymbol{x}_{i}),\phi(\boldsymbol{x}_{j})\rangle=\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})\tag{22}$
• 即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过函数$κ(⋅,⋅)$计算的结果，于是，(21)可重写为
  $\begin{aligned} & \max_{\boldsymbol{\alpha}}\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\kappa(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\\ & s.t.\quad\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\quad\alpha_{i}\geq 0, i=1,2,\dots,m. \end{aligned}\tag{23}$
• 函数$κ(⋅,⋅)$就是“核函数” (kernel function)。通过 kernel trick，将高维空间的对偶问题求解过程简化至原始样本空间的对偶问题求解。
• 通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。于是，“核函数选择”称为支持向量机的最大变数，若选择不合适，意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。
• 常用的 kernel function 如下表所示：
  
• kernel function 的内涵（容易混淆的点）：
  
  • 核函数和映射没有关系，核函数和映射没有关系，核函数和映射没有关系。核函数只是用来计算映射到高维空间之后的内积的一种简便方法。
  • 核函数的作用，是隐含着一个从低维空间到高维空间的映射，这个映射可以把低维空间中线性不可分的两类点变成线性可分的。

• kernel function 的选择 tricks:

  • 从DataSet的角度分析：
    
    • 如果Feature的数量非常大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM； （例如文档分类）
    • 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM + Gaussian Kernel（RBF）；
    • 如果Feature的数量比较小，样本数量很多，需要手工添加一些feature变成第一种情况；
  • 从实验的角度分析：
    
    • 从拟合程度来讲，linear在线性可分的情况下和rbf想过差不多，在线性不可分的情况下rbf明显优于linear，poly在前两种情况下效果都不怎么好，但是在变化剧烈的情况下ploy稍微好点。
    • 从速度来讲，linear是最快的，poly的话因为参数很多，测试中最慢。
    • 从参数而言，linear简单易用，rbf, poly参数较多，但是调参好的话可以得到较好的结果。

• Linear SVM 和 Logistic Regression 的区别

  1. Linear SVM 不直接依赖数据的 distribution，分类平面不受一类点的影响。LR 受所有数据点的影响，如果 dataSet 不同类别 strongly unbalanced，一般会对 data 先做一次 balancing；
  2. Linear SVM 在计算margin有多“宽”的时候是依赖数据表达上的距离测度的，换句话说如果这个测度不好（badly scaled，这种情况在高维数据尤为显著），所求得的所谓 Large margin就没有意义了，这个问题即使换用 kernel trick（比如用Gaussian kernel）也无法完全避免。所以使用 Linear SVM 之前一般都需要先对数据做 normalization，而求解LR（without regularization）时则不需要或者结果不敏感。
  3. Linear SVM 受到 penalty 的参数影响，实验时要做 validation，比如依赖参数 C。
  4. Linear SVM 和 LR 的 performance 都会收到outlier的影响，其敏感程度而言，谁更好很难下明确结论。

• Kernel Trick 实例

  1. 核函数的牛逼之处是：巧妙的跳过了如何从低维空间映射到高维空间这个过程，而直接求出了低维空间的两个向量在高维空间的内积$<=>$只要两个低维空间的向量输入到一个核函数之后，这个函数值就可以表示为：把这两个向量映射到某高维空间后的内积。

  2. 
     可以看出：高斯核函数将样本映射成无穷维，如果不用核函数，这无穷维是无法计算。但通过核函数可以巧妙的绕过直接计算无穷维，通过高斯核函数计算无穷维就方便多了。

  3. 
     核函数的图像理解就是 将样本升维，再分割

• SVM 高斯核函数中，C 与 Gamma 对模型的影响：

  1. C 是所有松弛因子之和的系数，当系数越大是，1-C *松弛因子的值就越小，导致支撑间距就越窄，即 C 越大，支撑间距越小，精度越高，但分类不一定就合理，容易出现过拟合。
  2. Gamma 越大，方差越小，图像就越瘦，衰减就越快，当两个样本之间衰减速度过快时，有理由认为他们不是一类。即 Gamma 越大，精度越高，容易出现过拟合。

• 

2.5 软间隔与正则化

• 现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，因此可以允许支持向量机载一些样本上出错，这里引入“软间隔” (soft margin)的概念
  
• 软间隔则是允许某些样本不满足约束：
  $y_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i}+b)\geq 1\tag{28}$
• 在最大化间隔的同时，不满足约束的样本尽可能少，于是优化目标写为
  $\min_{\boldsymbol{w},b}\frac{1}{2}\Vert\boldsymbol{w}\Vert^{2}+C\sum_{i=1}^{m}\ell_{0/1}\big(y_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i}+b)-1\big)\tag{29}$
• 其中$C>0$是一个常数，$\ell_{0/1}$是“0/1损失函数”，数学表达为：
  $\ell_{0/1}=\begin{cases} 1,\quad z<0\\ 0,\quad otherwise \end{cases}$
• 当$C$无穷大时，(29)迫使所有样本满足约束(28)。当$C$取有限值时，(29)允许一些样本不满足约束。
• $\ell_{0/1}$非凸、非连续，使得(29)不易直接求解。于是常采用一些函数来替代它，称为“替代损失” (surrogate loss)，这些函数通常侍凸的连续函数且是$\ell_{0/1}$的上界。
  

• 只有当 SVM 的 surrogate loss 是 hinge loss 的时候，SVM 才是 SVM。

  1. hinge loss 存在一块零区域，对应的正是非支持向量的普通样本。因为$hinge(z)=max(0,1-z)= max(0,1-y_i(w^Tx_i+b))$。若$hinge(z)=0$，则有$1-y_i(w^Tx_i+b)<0$，即$y_i(w^Tx_i+b)>1$。根据 KKT 条件可知，最优解必须满足$\alpha_i(y_i(w^t+b))=0$，即此时的$\alpha_i=0$。$\alpha_i=0$ 等价于非支持向量。
  2. 当 SVM 选用$hinge(z)$作为 surrogate loss 时，就会利用 hinge loss 零区域的优势，使得 SVM 在寻找最优 hyperplane 时只选取少量的样本（support vector），所有的普通样本（非 support vector）不参与最优 hyperplane的确定，对训练样本的依赖大大减少，即 SVM不依赖样本（feature）的 distribution。$<=>$hinger loss 的零区域与 SVM 只用少量样本来确定最优 hyperplane 的思想不谋而合。

• SVM loss(hinge loss) 和 LR loss(MSE loss)的区别

  1. 两个 cost function 的目标都是增加对分类影响较大的数据点的权重，减少与分类关系不大的数据点的权重；
  2. SVM 只考虑 support vectors，即利用 hyperplane最相关的少数点去学习分类器；
  3. LR 通过 sigmod function 的非线性变化（映射），大大减少了离分类平面较远的点的权重，提升与分类最相关的数据点的权重；
  4. SVM 关注局部，LR 关注全局。
• 当采用 hinge loss 时，式(29)变为：
  $\min_{\boldsymbol{w},b}\frac{1}{2}\Vert\boldsymbol{w}\Vert^{2}+C\sum_{i=1}^{m}\max\big(0,1-y_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i}+b)\big)\tag{34}$
• 引入“松弛变量” (slack variables) $ξ≥0$，则可将上式重写为：
  $\min_{\boldsymbol{w},b,\xi_{i}}\frac{1}{2}\Vert\boldsymbol{w}\Vert^{2}+C\sum_{i=1}^{m}\xi_{i}\tag{35}$
  
  1. 使用 hinge loss，实际是将 slack variables 作为 cost function 的一部分进行优；
  2. 式(35)可以漂亮地看成是 L2-Norm 与 hinge loss 之和；
  3. 也可以将式(35)理解为是 SVM 在 hinge loss 的基础上加入了 L2-Norm；
  4. 这就是常用的“软间隔支持向量机”，其拉格朗日表达式为：
     $L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})= \frac{1}{2}\Vert\boldsymbol{w}\Vert^{2}+C\sum_{i=1}^{m}\xi_{i}+ \sum_{i=1}^{m}\alpha_{i}\big(1-\xi_{i}-y_{i}(\boldsymbol{w}^{T}\boldsymbol{x}_{i}+b)\big)- \sum_{i=1}^{m}\mu_{i}\xi_{i}\tag{36}$
     其中$\alpha_i≥0$，$\mu_{i}\geq 0$是拉格朗日乘子。令$L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})$对$\boldsymbol{w}$，$b$，$\xi_{i}$的偏导为零可得：
     $\boldsymbol{w}=\sum_{i}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}\tag{37}$
     $0=\sum_{i=1}^{m}\alpha_{i}y_{i}\tag{38}$
     $C=\alpha_{i}+\mu_{i}\tag{39}$
  5. 将上面三个式子代入(36)可得到(35)的对偶问题:
     $\begin{aligned} & \max_{\boldsymbol{\alpha}}\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j}\\ & s.t.\quad\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\quad 0\leq\alpha_{i}\leq C, i=1,2,\dots,m \end{aligned}\tag{40}$
     从数学表达式来看，软间隔和硬间隔的SVM的对偶表达式，只是在约束条件上有不同，等价于只影响KKT条件，而不影响求解的逻辑。

• 对软间隔支持向量机，KKT条件要求:
  $\begin{cases} \alpha_{i}\geq 0,\quad\mu_{i}\geq 0,\\ y_{i}f(\boldsymbol{x}_{i})-1+\xi_{i}\geq 0,\\ \alpha_{i}\big(y_{i}f(\boldsymbol{x}_{i})-1+\xi_{i}\big)=0,\\ \xi_{i}\geq 0,\quad\mu_{i}\xi_{i}=0, \end{cases}\tag{41}$

  1. 若$α_i=0$，则该样本不会对$f(x)$有任何影响，即非支持向量。
  2. 若$α_i>0$，则必有$y_if(x_i)=1−ξ_i$，即该样本是支持向量。
     2.1 若$α_i<C$，则$μ_i>0$，进而有$ξ_i=0$，即该样本恰在最大间隔边界上；
     2.2 若$α_i=C$，则$μ_i=0$，此时若$ξ_i≤1$则该样本落在最大间隔内部。【这里体现“软间隔”的一方面】
     2.3 若$ξ_i>1$，则该样本被错误分类。因此，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用 hinge loss 仍保持了稀疏性。
     解释：
     $\alpha_i=c≠0$，则$y_if(x_i)-1+ξ_i=0$
     若$ξ_i≤1$，即分对了tag，但是在最大间隔内部；
     若$ξ_i>1$，则$y_if(x_i)-1<-1$，$y_if(x_i)<-2$，$y_i$与$f(x_i)$异号，即被错分。

• L2 范数$∥w∥_2$向于$w$的分量取值尽量均衡，即非零分量个数尽量稠密。原因：
  L2范数的梯度下降过程是一小步一小步进行的，直观上来看L2范数的极小值（最优解）是一定沿着均匀分摊的方向优化。故用它进行正则化会使各个参数的系数逐步逼近0，而不会等于0，即实现非零分量个数稠密的效果。