文章目录

• 经典线性二分类算法:支持向量机(SVM)
• • 1. SVM进行二分类的基本思想
  • • 从感知机的缺陷引出SVM
    • 最大化分类间隔：SVM提高泛化性的insight
    • SVM的数学本质:带不等式约束的最优化问题
    • 化繁为简：化简优化函数的一些tricks
    • 练手
  • 2. 将SVM优化函数进行转化
  • • 2.1 转化为拉格朗日函数
    • • 2.1.1假设优化问题的约束条件只有一个等式约束：
      • 2.1.2 假设优化问题的约束条件是不等式约束：
      • 2.1.3 假设优化问题的约束条件是若干不等式约束：
    • 2.2 将原问题转化为对偶问题
    • 2.3 推出SVM优化函数的对偶问题
  • 3. 软间隔SVM
  • • 3.1 松弛变量的引入
    • 3.2 如何确定松弛变量的值：损失函数的选择
    • 3.3 软间隔SVM优化问题的转化
  • 4.非线性SVM
  • • SVM解决非线性问题的杀手锏：核函数的引入
  • 5. 如何求解？基于SMO迭代优化算法
  • • 5.1 将问题转化为求解一个二元函数
    • 5.2 将二元函数转化为一元函数
    • 5.3 求解一元函数的极值，求得α1，α2
    • 5.4 对原始的解添加约束
    • 5.5 每个迭代轮如何高效的选取i和j?，SMO的启发式选择
    • 5.6 参数b的计算

经典线性二分类算法:支持向量机(SVM)

可以毫不夸张的说，在深度学习算法尚未崛起之前，SVM一度是最受欢迎的机器学习算法之一。由于其优异的泛化性能以及鲁棒的应用场景，使其在学术界甚至工业界都有着十分广泛的应用。如果你翻看大约十年前的相关论文，就会发现SVM以及一些SVM的变体都是实验数据中不可缺少的Baseline和benchmark。以至于在CNN崛起之后，SVM算法推理过程的相对高效以及可解释性使得一些基于CNN的深度学习模型仍然使用SVM分类器执行流程中的特定任务，其中比较有名的要数目标检测算法RCNN(2014),使用SVM对CNN输出的ROI features进行分类：

当然，SVM在发展的过程中也衍生出了许许多多的改进以及变体，比如用于回归的SVR，用于文本分类的NBSVM，基于最小二乘的LSSVM，以及扩展到非线性分类的基于核函数的SVM等等。其中的原理和分类方法同经典的SVM大同小异。然而，SVM背后的分类原理以及涉及的数学优化方法仍然会使得一些刚接触SVM算法的新手(包括我)望而却步。因此在本篇博客中，我将会基于最原始的SVM分类器，加上自己的一些理解，对算法原理进行一个详细的介绍。

1. SVM进行二分类的基本思想

想到线性二分类算法，相信大家脑海中不自觉的就会产生这样一个画面，画面上是两堆属于不同类别的点，有一条直线恰好能把这两堆点分开来。在直线之上的这些点大于0，直线之下的点堆小于0。现在新来一个点，算法通过判断这个点代入直线方程即判断其属于直线的上方还是下方，进而预测这个点所属类别。

从感知机的缺陷引出SVM

一个经典的机器学习算法：感知机(perceptron)，就是基于上述的分类原理，其中的直线就是算法通过最优化方法学习出的决策边界。我们今天的主角SVM也不例外，不过我们仍然可以横向对比一下，SVM和感知机算法的差异。

考虑以下三种决策边界：

如上图所示，如果说哪条直线对于图中点的分类效果最好，其实是无法进行比较的，因为三条线都能100%将图中不同类别的点完美的区分开来。在感知机看来，上面三种决策边界都是算法的最优解。（因此感知机算法的往往有无穷多解）

感知机的损失函数期望分类错误的所有样本到决策边界的距离之和最小，只和分类错误的样本有关（如果一条样本分类正确，那么它的损失函数为0)。如果z代表分类错误的样本，决策边界是wx+b=0，最小化感知机损失函数就是(基于点到超平面的距离公式)：
a r g m i n ( W , b ) ∑ i = 1 m ( ∣ W t z i + b ∣ ∥ W ∥ 2 ) 等 价 于 : a r g m i n ( W , b ) ( ∣ W T Z + b ∣ ) argmin_{(W,b)}\sum_{i=1}^m (\frac{\left|W^{t} z_i+b\right|}{\|W\|_2})\\ 等价于:\\ argmin_{(W,b)} (\left|W^{T} Z+b\right|)\\ argmin(W,b)​i=1∑m​(∥W∥2​∣Wtzi​+b∣​)等价于:argmin(W,b)​(∣∣​WTZ+b∣∣​)
但如果此时新来了几个测试数据，三种决策边界的好坏便能很明显的体现出来：

很明显，如果依据前两条决策边界分类新来的样本点，就会产生错误(这实则就是过拟合)，而第三条决策边界对于新来的样本点是鲁棒的。所以我们就可以下结论说第三条直线的分类效果最好，因为它对于测试数据的泛化能力强。但是，如何量化的衡量决策边界的泛化性能呢？光凭后知后觉的直观感受可不行，我们需要算法仅在训练数据上就能尽量学到第三种决策边界。

最大化分类间隔：SVM提高泛化性的insight

SVM算法在基于感知机决策方法的基础上，敏锐的察觉到了这一点。**如何度量一条决策边界的泛化能力，一个简洁且可行的方法是：对于训练数据中距离决策边界最近的那些点，我们希望它们离决策边界越远越好。**因此在损失函数中应该包含支持向量距离最大化的优化项。如下图所示：

那些离决策边界最近的样本点，我们也称作支持向量(Support Vector)，这便是SVM名字的由来。

相应的，优化函数就是：
a r g m a x ( W , b ) [ ( m a r g i n ( W , b ) ) ] 其 中 : margin ⁡ ( W , b ) = min ⁡ i = 1 , 2 … . N 1 ∥ W ∥ 2 ⋅ ∣ W T ⋅ X i + b ∣ \begin{aligned} &argmax_{(W,b)}[(margin(W,b))] \\ 其中:\\ &\operatorname{margin}(W, b)=\min _{i=1,2 \ldots . N} \frac{1}{\|W\|_{2}} \cdot\left|W^{T} \cdot X_i+b\right| \end{aligned} 其中:​argmax(W,b)​[(margin(W,b))]margin(W,b)=i=1,2….Nmin​∥W∥2​1​⋅∣∣​WT⋅Xi​+b∣∣​​
其中的xi就表示离分类超平面(决策边界)最近的那些点(支持向量)。

SVM的数学本质:带不等式约束的最优化问题

然而，光优化支持向量的距离而不考虑样本是否分类正确也是不行的，因此，我们还需添加决策边界能够保证所有样本点分类正确的约束条件：
{ W T X i + b > 0 , y i = 类 别 1 W T X i + b < 0 , y i = 类 别 2 \begin{cases}\boldsymbol{W}^{\mathrm{T}} \boldsymbol{X}_{i}+b >0, & y_{i}=类别1 \\ \boldsymbol{W}^{\mathrm{T}} \boldsymbol{X}_{i}+b <0, & y_{i}=类别2\end{cases} {WTXi​+b>0,WTXi​+b<0,​yi​=类别1yi​=类别2​
一个小trick是，我们将在决策边界上方的数据的标签人为的设置为1，将决策边界下方的标签设置为-1，这样一来，约束条件就可以合并为：
y i ( W T X i + b ) > 0 y_i(W^TX_i+b)>0 yi​(WTXi​+b)>0
这样一来，完整的带约束条件的优化函数就是：
argmax ⁡ ( W , b ) ( min ⁡ i = 1 , 2 … . N 1 ∥ W ∥ 2 ⋅ ∣ W T ⋅ X i + b ∣ ) s . t . y T ( W T X + b ) > 0 \begin{aligned} &\operatorname{argmax}_{(W, b)}(\min _{i=1,2 \ldots . N} \frac{1}{\|W\|_{2}} \cdot\left|W^{T} \cdot X_i+b\right|)\\ &s.t.\\ &y^T(W^TX+b)>0 \end{aligned} ​argmax(W,b)​(i=1,2….Nmin​∥W∥2​1​⋅∣∣​WT⋅Xi​+b∣∣​)s.t.yT(WTX+b)>0​
用图示来直观理解：

化繁为简：化简优化函数的一些tricks

事实上，上面给出的优化问题仍然十分复杂，难以处理。就比如计算支持向量的最大间隔，每优化一步，算法还需要重新寻找支持向量，十分的不方便。

因此我们仍然需要对原始的优化函数做一个简化操作，这里又会用到一些小技巧:

对于支持向量而言，它们到决策边界的距离一定是一致的且是所有数据中最小的。并且我们知道，对于参数(W,b)的放缩并不会影响最终决策边界的位置，因此我们假设支持向量代入分类超平面得到的值(函数距离)为ξ：
KaTeX parse error: Expected 'EOF', got '&' at position 2: &̲\min _{i=1,2 \l…
两边同时除以ξ，就是：
min ⁡ i = 1 , 2 … . N ∣ W T ξ ⋅ X i + b ξ ∣ = 1 s . t . y i ( W T ξ X i + b ξ ) ⩾ 1 由 于 W 和 b 都 是 优 化 问 题 的 变 量 ， 相 当 于 将 原 始 W 和 b 替 换 为 W ξ ， b ξ ， 对 于 原 优 化 函 数 不 会 造 成 任 何 影 响 。 \begin{aligned} &\min _{i=1,2 \ldots . N}\left|\frac{W^{T}}{ξ} \cdot X_i+\frac{b}{ξ}\right|=1\\ &s.t.\\ &y_i(\frac{W^{T}}{ξ}X_i+\frac{b}{ξ})\geqslant1\\ &由于W和b都是优化问题的变量，相当于将原始W和b替换为\frac{W}{ξ}，\frac{b}{ξ}，对于原优化函数不会造成任何影响。 \end{aligned} ​i=1,2….Nmin​∣∣∣∣​ξWT​⋅Xi​+ξb​∣∣∣∣​=1s.t.yi​(ξWT​Xi​+ξb​)⩾1由于W和b都是优化问题的变量，相当于将原始W和b替换为ξW​，ξb​，对于原优化函数不会造成任何影响。​
因此对于支持向量距离最大化的优化问题就转化为这一简洁的形式：
argmax ⁡ ( W ) ( 1 ∥ W ∥ 2 ) \operatorname{argmax}_{(W)}( \frac{1}{\|W\|_{2}} ) argmax(W)​(∥W∥2​1​)

此时取倒数可以将最大化转为最小化：
argmin ⁡ ( W ) ( ∥ W ∥ 2 ) \operatorname{argmin}_{(W)}( \|W\|_{2}) argmin(W)​(∥W∥2​)
在对优化问题作了适当变形后，优化问题就转化成：
min ⁡ ( ∥ W ∥ 2 ) s . t . y i T ( W T X i + b ) ⩾ 1 ; i = 1 , 2 , 3 , . . . , m \begin{aligned} &\operatorname{min}( \|W\|_{2})\\ &s.t.\\ &y_i^T(W^TX_i+b)\geqslant1;i=1,2,3,...,m \end{aligned} ​min(∥W∥2​)s.t.yiT​(WTXi​+b)⩾1;i=1,2,3,...,m​
(来自博主的虾bb：事实上，我曾想过把最大化支持向量到超平面的距离转化为最大化所有数据到超平面的距离(两者是等价的)，这虽然也可以解决每迭代一次就寻找一次支持向量的繁琐，但由于每个点到超平面的距离都是不一样的(不能一股脑的全规定函数距离为1)，因此这个问题反而也不好简化，反而是简化后的公式只计算支持向量能大大减小计算量。这大概也是为什么SVM只关注支持向量的缘由吧（只能说那些机器学习大佬们在这些问题上的数学认知的确比一般人来的深刻)

练手

好了，既然我们已经初步懂得了SVM算法的分类原理以及它的优化函数，我们就来举个超级无敌简单的例子练练手