[ML从入门到入门] 支持向量机：从SVM的推导过程到SMO的收敛性讨论

 

支持向量机（Support Vector Machine，SVM）在70年代由苏联人 Vladimir Vapnik 提出，主要用于处理二分类问题，也就是研究如何区分两类事物。

本文主要介绍支持向量机如何解决线性可分和非线性可分问题，最后还会对 SMO 算法进行推导以及对 SMO 算法的收敛性进行简要分析，但受限于篇幅，本文不会对最优化问题、核函数、原问题和对偶问题等前置知识做过于深入的介绍，需要了解相关知识的读者朋友请移步其它文章、资料。

SVM 推导过程主要参考自胡浩基教授的机器学习公开课程；SMO 算法相关则主要来自于 Platt 的论文以及网上公开资料，相关链接见文章末尾。

 

快速理解

举一个粗糙的例子。

科学家收集到一批天体的观测数据，现在需要按行星和恒星两种类型对这些未知天体进行分类。显然这是一项费时费力的工作，我们希望通过机器学习算法，让计算机自动帮我们做区分。

我们拿到了往年一批已经分类好的天体数据样本，将这些样本绘制到一个二维坐标系上，如下：

这是一个简单的二维特征空间，通过肉眼观察这些数据我们发现，恒星和行星这两种天体，根据他们的辐射强度和质量的不同，分别聚集在坐标系的左下角和右上角两个区域。

于是我们根据自己的判断作了这样一条直线：

 

这时，我们就拥有了一条可以区分恒星和行星的直线，当点落在直线左侧的可判断为行星，如果落在右侧则为恒星。

但是上面这条直线是我们凭借经验所作，显然在坐标系中能够划分这两类天体的直线有无数条，如下图：

这种情况下，如何定义一个性能指标去找到一条最合适的直线就是支持向量机要解决的首要问题。

Vapnik 提出了使用如下一对平行线的 间隔（Margin）来作为这个性能指标，间隔越大，意味着最终获得的直线更具普适性，如下图：

上面坐标系中，首先是在两种样本中间找一对平行线，我们从 0 开始扩大平行线的间隔 d，直到两条线分别经过两种样本的一个或多个点为止，这些点被称为 支持向量（Support Vector），当间隔 d 最大时，两条平行线的正中间我们可以取到第三条平行线，如下图红色虚线所示：

在众多的分界线当中，这条红色直线被认为是一个最优解，称为 决策边界（Decision Boundary）。

上面的例子中，两种样本各自会有一片聚集密度较高的区域，而远离这片区域，样本逐渐变得稀疏，样本越稀疏意味着落到该区域的概率越低。决策边界直线在兼顾划分不同样本的同时，还需要放置在两种样本之间最不可能出现的区域，那么，当间隔 d 取最大时即为最理想的状态。

目前为止我们可以得到一些初期结论：

$1）支持向量机用于解决二分类问题，目的是求出一条直线尽可能地划分两种不同的样本；\\2）支持向量到决策边界的距离都相等； \\3）在所有向量中，支持向量到决策边界的距离最短。$

实际应用场景中，我们经常会遇到比上面例子复杂得多的问题。例如通过图像区分月季和玫瑰，我们需要从颜色、花瓣形状、叶子形状等等多个特征进行综合判断，训练样本最终会落到一个多维特征空间中，此时划分两种训练样本的边界将会是一个超平面，称为 分离超平面（Separating Hyperplane）。

支持向量机本质是用线性方程去解决二分类问题，而在实际问题中，不同的样本在特征空间中往往“犬牙交错”，SVM 这种“一刀切”的方式似乎将变得不再奏效。别担心，后面笔者将会花大篇幅着墨如何处理这种线性不可分的样本。

 

支持向量机的两种模型

支持向量机有两种模型：线性模型、非线性模型

一个线性不可分的例子，无论如何作直线都无法区分两种样本

 

线性可分的例子

为了方便推导，接下来对样本做一些定义。

 

训练样本的定义

比如现在有 class1 和 class2 两种训练样本，分布在这样一个二维特征空间中：

那么，对于第 $i$ 个训练样本可以用 向量 和 标签 去定义它：

$\left( 向量,标签\right)\Leftrightarrow\left( X_{i},y_{i}\right)$

 

$X_{i}=\begin{bmatrix} x_{i1} \\ x_{i2} \end{bmatrix}$，$y_{i} \in \left\{ 1,-1 \right\}$

标签 $y_{i}$ 可以理解为第 $i$ 个样本所属的类别，SVM 用于处理二分类问题，那么我们可以使用 $+1$、$-1$ 分别表示 class1 和 class2 两种训练样本。

从上面二维特征空间的例子，进一步推广到 $m$ 维特征空间中的 $N$ 个训练样本：

$\left( X_{1},y_{1}\right), \left( X_{2},y_{2}\right), \cdots ,\left( X_{N},y_{N}\right)$

可以记作：

$\left\{ \left( X_{i},y_{i}\right)\right\} _{i=1}^{N}$

 

$X_{i}=\begin{bmatrix} x_{i1} \\ x_{i2} \\ \vdots \\ x_{im} \end{bmatrix}$，$y_{i} \in \left\{ 1,-1 \right\}$

现在我们已经知道了训练样本的定义，那么接下来将对 SVM 线性、非线性两种模型分别进行讨论。

 

线性模型

如果训练样本 线性可分（Linear Separable），可以用这样一个方程来表示分离超平面：

$\omega^{T}X+b=0$

这里的 $X$ 即上一小节提到的样本的向量，$\omega$ 和 $X$ 是维度相同的向量，$\omega^{T}$ 是向量 $\omega$ 的转置，$b$ 是某个实数：

$\omega=\begin{bmatrix} \omega_{1} \\ \omega_{2} \\ \vdots \\ \omega_{m} \end{bmatrix},X=\begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{m} \end{bmatrix},b\in R$

$X$ 是已知的向量，最终我们是要求出 $\omega$ 和 $b$，使得分离超平面正确分割开两种样本。

总结一下，一个正确分类所有样本的 SVM 线性模型可以记作：

对于 $\left\{ \left( X_{i},y_{i}\right) \right\} _{i=1}^{N}$，

$\exists \left( \omega,b\right)$，使：

$\forall i = 1,2,\cdots, N$，有：

a) 若 $y_{i}=+1$，则  $\omega^{T}X_{i}+b \geq 0$

b) 若 $y_{i}=-1$，则  $\omega^{T}X_{i}+b < 0$

上面 a、b 是为了方便推导而人为做出的定义，针对不同的场景我们会逐步修改这些定义，希望读者朋友们在后续的推导中能够灵活变通，举一反三。

联立 a、b 可以进一步简化得到：

$\begin{align}y_{i}\left( \omega^{T}X_{i}+b\right) \geq 0 \tag{公式1}\end{align}$

换句话说，满足公式1就代表着样本能够被正确分类。

一个可用的 SVM 模型，除了能够正确分类所有训练样本之外，还需要让间隔 $d$ 最大化，如何用代数式表达最大化 $d$ 是接下来要讨论的话题。

回顾高中知识，点 $\left( x_{0},y_{0}\right)$ 到直线 $\omega_{1}x+\omega_{2}y+b=0$ 的距离为：

$d=\dfrac{\left| \omega_{1} x_{0}+\omega_{2}y_{0}+b\right| }{\sqrt{\omega _{1}^{2}+\omega_{2}^{2}}}$

由此可以推导出，向量 $X_{i}$ 到超平面 $\omega^{T}X+b=0$ 的距离：

$\begin{align*} d &=\dfrac{\left| \omega^{T}X_{i}+b\right| }{\left\| \omega\right\| } \\ &=\frac{\left| \omega^{T}X_{i}+b\right| }{\scriptsize{\sqrt{\sum \limits^{m}_{i=1}\omega_{i}^{2}}}} \end{align*}$

这里我们需要再明确一个事实，无论我们如何对分离超平面的方程进行缩放，方程表示的都是同一个超平面，即：

$\omega^{T}X+b=0\ 与\ a\omega^{T}X+ab=0\ 是同一个超平面$

那么，我们总是可以找到一个缩放倍数 $a \in R^{+}$，使得分离超平面对于支持向量 $X_{s}$，有：

$\left| a\omega^{T}X_{s}+ab\right|=1$

因为每个支持向量到超平面的距离都是相等的，任何一个支持向量 $X_{s}$ 到分离超平面的距离将会是：

$d=\dfrac{\left| a\omega^{T}X_{s}+ab\right| }{\left\| a\omega\right\| }=\dfrac{1}{\left\| a\omega\right\| }$ 

上一节我们就知道，支持向量是到分离超平面最近的点，结合上面支持向量到超平面的距离 $d$，我们可以对任何一个向量 $X_{i}$ 做进一步的定义：

若 $y_{i}=+1$，则  $a\omega^{T}X_{i}+ab \geq 1$

若 $y_{i}=-1$，则  $a\omega^{T}X_{i}+ab < 1$

那么此时 $y_{i}\left( \omega^{T}X_{i}+b\right) \geq 0$（公式1），则变为：

$y_{i}\left( a\omega^{T}X_{i}+ab \right) \geq 1$

前面提到，支持向量机的任务是去找到一个最大的间隔 $d$，于是我们最终得到了一个优化问题，它的 目标函数（Objective Function）和限制条件如下（为了简化书写，$a\omega$、$ab$ 重新定义为 $\omega$、$b$，同时为了求导方便，目标函数也做了改造）：

最小化：$\dfrac{1}{2} \left\| \omega\right\|^{2}$

限制条件：$y_{i}\left( \omega^{T}X_{i}+b \right) \geq 1\ ,\ i=1,2,\cdots,N$

这个最优化问题是一个二次规划问题，二次规划（Quadratic Programming）是凸优化问题中的一种，它要求满足以下条件：

a）目标函数为二次函数

b）限制条件为一次函数

一个二次规划问题，要么无解，要么只有一个极值（这里不展开证明，我们直接使用这个结论）。

最后，回顾一下整个推导过程：

 

非线性模型

在实际应用中，我们得到的训练样本在特征空间里大概率是 非线性可分（Non-linear Separable）的。

一些非线性可分的情况

如果样本是线性不可分的，那么上一小节得到的最优化问题将会无解，接下来介绍如何把非线性可分转换为线性可分问题。

 

引入松弛变量

在图（2）中，因为两种训练样本存在小部分交叠的区域导致样本线性不可分，属于可容忍的范围，这时应该放宽限制条件，给每个训练样本引入一个松弛变量（Slack Variable）$\xi _{i}$，使一些离群的样本也能被分类，限制条件改造为（$i=1,2,\cdots,N$）：

限制条件：

$y_{i}\left( \omega^{T}X_{i}+b \right) \geq 1-\xi _{i}$

$\xi _{i} \geq 0$

我们在放宽限制条件的同时，也不能任由松弛变量无限变大，为了对松弛变量进行约束，我们将松弛变量加入到优化目标中，同时用 $C$ 调整松弛变量的权重，目标函数将变为：

最小化：$\dfrac{1}{2} \left\| \omega\right\|^{2}+C\sum \limits^{N}_{i=1}\xi _{i}$

这里的 $C\sum \limits^{N}_{i=1}\xi _{i}$ 被称为 正则项（Regulation Trem），$C$ 值越大，对目标函数的惩罚力度就越大，此时目标函数就需要相应地缩小 $\xi_{i}$ 的值，直观的表现是被错误分类的点会变少或到决策边界的距离会变短。

加入松弛变量后，取得最优解时可能得到类似下图的 SVM 模型：

无法解决问题，于是与问题和解了

在引入了松弛变量后，图（2）的问题得到了较好的解决，但如果直接套用到图（1）这种情况中，最终得到模型将会非常糟糕，因为决策边界在图（1）中可能会变为这样：

非常糟糕，但至少让你的生日蛋糕得到了很好的切分

显然，我们需要另辟蹊径处理这种情况。

 

低维映射到高维

对于上面这种情况，一般我们的想法是去构造一条曲线来区分两种样本，而 Vapnik 则提出了另一个极具创造性的思路，他的想法是对样本向量进行升维，因为在越高维的空间中，我们越是有概率用分离超平面区分两种样本；好比我们在网购时，商家给出商品的参数越多，我们越是能够判断商品质量的优劣。

接下来的一个例子，将演示如何通过对线性不可分的样本进行升维，使得样本线性可分。

一个二维特征空间中线性不可分的例子

上面的二维特征空间中存在线性不可分的四个向量，这四个向量分别属于 $C_{1}$、$C_{2}$ 两种标签：

$X_{1}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} , X_{2}=\begin{bmatrix} 1 \\ 1 \end{bmatrix} \in C_{1}$

$X_{3}=\begin{bmatrix} 1 \\ 0 \end{bmatrix} , X_{4}=\begin{bmatrix} 0 \\ 1 \end{bmatrix} \in C_{2}$

为了使这些样本变得线性可分，需要人为地制定一个规则 $\varphi$ ，比如仿射函数，将向量映射到高维空间：

$X_{i}=\begin{bmatrix} a \\ b \end{bmatrix}$

$\Downarrow$

$\varphi \left( X_{i}\right)=\begin{bmatrix} a^{2} \\ b^{2} \\ a \\ b \\ ab \end{bmatrix}$

四个向量经过升维将变为：

$\varphi \left(X_{1}\right)=\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} , \varphi \left(X_{2}\right)=\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \in C_{1}$

 

$\varphi \left(X_{3}\right)=\begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} , \varphi \left(X_{4}\right)=\begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \in C_{2}$

不要忘了我们的目标是要求出 $\omega$ 和 $b$，回顾一下 SVM 最优化问题的限制条件（公式1）：

$y_{i}\left( \omega^{T}X_{i}+b\right) \geq 0$

在通过 $\varphi$ 对向量 $X_{i}$ 进行升维后，限制条件公式变为：

$y_{i}\left[ \omega^{T}\varphi \left( X_{i}\right)+b\right] \geq 0$

（注意：$\omega$ 的维度也将得到提升，与 $\varphi \left( X_{i}\right)$ 保持一致）

不考虑优化目标，仅满足限制条件的情况下，下面是众多答案的其中一个：

$\omega=\begin{bmatrix} -1 \\ -1 \\ -1 \\ -1 \\ 6 \end{bmatrix}$，$b=1$

验证一下答案，将 $\omega$ 和 $b$ 代回限制条件公式，可以得到：

$\omega^{T}\varphi \left( X_{1}\right)+b=1 \Rightarrow y_{1}=1$

$\omega^{T}\varphi \left( X_{2}\right)+b=3 \Rightarrow y_{2}=1$

$\omega^{T}\varphi \left( X_{3}\right)+b=-1 \Rightarrow y_{3}=-1$

$\omega^{T}\varphi \left( X_{4}\right)+b=-1 \Rightarrow y_{4}=-1$

通过 $y_{i}$ 的值可以看到，我们已经成功将样本分成了两类。

当然，这是燃尽脑细胞后得出的一个结果，而这还是在不考虑优化目标且只有5维的情况下，可想而知，在更高维的情况下，运算将会变得多么艰难。

前面我们提到 $\omega$ 和 $X_{i}$ 的维度始终保持一致，当 $X_{i}$ 映射成一个无限维向量时，$\omega$ 也将变为一个无限维的向量，此时的方程变得难以求解。不仅是高维情况下的运算难题，如何找到一个合适的 $\varphi$ 使样本变得线性可分也不是一件容易的事。

为了解决这些问题，SVM 借助了 核函数（Kernel Function），通过一系列转换，核函数可以替换分离超平面方程中无限维的 $\omega$ 和 $\varphi\left(X_{i}\right)$，使得方程可解。

 

核函数

感谢核函数，我们不再需要关心 $\varphi \left( X\right)$ 的显式表达，也就是不需要知道 $\varphi$ 是如何对向量进行升维的，只通过核函数就可以计算两个升维后的向量 $\varphi \left( X_{1}\right)$、$\varphi \left( X_{2}\right)$ 的内积，它们的关系如下：

$K\left( X_{1},X_{2}\right) =\varphi \left( X_{1}\right) ^{T}\varphi \left( X_{2}\right)$

核函数 $K$ 有明确的代数式，高斯核、多项式核是两种常用的核函数：

 高斯核：$K\left( X_{1},X_{2}\right) ={\Large e}^{\scriptsize -\dfrac{\left\| X_{1}-X_{2}\right\| ^{2}}{2\sigma^{2} }}$

多项式核：$K\left( X_{1},X_{2}\right) =\left( X_{1}^{T}X_{2}+1\right) ^{d}$

多项式核中的阶数 $d$ 是有限的，那么 $\varphi \left( X_{i}\right)$ 也将是有限维度的向量；但是高斯核对应的 $\varphi \left( X_{i}\right)$ 则是一个无限维的向量，相关证明本文不做展开。

事实上，要使 $K\left( X_{1},X_{2}\right) =\varphi \left( X_{1}\right) ^{T}\varphi \left( X_{2}\right)$ 成立也是有条件的，等式成立的充要条件如下（Mercer 定理）：

充要条件 $2$ 中的 $C_{i}$ 是常量，$X_{i}$ 是向量，关于半正定性见文末推荐阅读。

现在，我们已经知道了核函数的作用，接下来将讨论如何使用原问题以及原问题的对偶问题等理论，让无限维的超平面方程变得可解。

 

原问题

先来看一下最优化问题的 原问题（Prime Problem）如何定义：

$\begin{align*}最小化：&f \left( \omega \right)\\ 限制条件：&g_{i} \left( \omega \right) \leq 0 \quad \left( i=1,2,\cdots,K \right) \\ &h_{i} \left( \omega \right) = 0 \quad \left( i=1,2,\cdots,M \right)\end{align*}$

这个定义具有非常高的普适性，目标函数是求最小化 $f \left( \omega \right)$，加入一个负号之后就变成了求最大化 $-f \left( \omega \right)$；$g_{i}$ 同理，加入负号就变成 $-g_{i} \left( \omega \right) \geq 0$，我们可以使用 $g_{i} \left( \omega \right) \leq 0$ 来表示任何不等式；同样的，$h_{i} \left( \omega \right) = 0$ 可以表示任何等式。

顾名思义，我们可以将任意最优化问题转化为上面原问题的格式。当然，限制条件是可选的，可以有一个或多个等式、不等式约束，我们上面展示的是最优化问题其中一种混合约束的情况，在做转换的时候需根据实际做增减。

 

对偶问题

接下来介绍原问题的 对偶问题（Dual Problem）。

通过原问题可以得到拉格朗日函数 $L$，关于拉格朗日函数的介绍见文章末尾的推荐阅读，这里不做展开，只需知道拉格朗日函数可用来求对偶问题的极值点，后面我们会对这个函数求偏导：

上面公式 (1) 可以用向量形式写成公式 (2) ，这两种书写方式都是可行的。

结合拉格朗日函数，可以得到对偶问题如下：

$最大化：\theta \left( \alpha, \beta \right)=\inf \limits_{\omega} \{ L \left( \omega, \alpha, \beta \right) \} \\ 限制条件：\alpha_{i} \geq 0 \quad \left( i=1,2,\cdots,K \right)$

解释一下这个目标函数。$\inf$ 表示集合的下确界，可以认为是取集合中的最小值，$\theta \left( \alpha, \beta \right)=\inf \limits_{\omega} \{ L \left( \omega, \alpha, \beta \right) \}$ 的意思是函数 $\theta$ 接收两个入参 $\alpha$ 和 $\beta$，这时 $\alpha$ 和 $\beta$ 就是已知的，然后通过改变 $\omega$ 找到最小的 $L \left( \omega, \alpha, \beta \right)$ 作为 $\theta \left( \alpha, \beta \right)$ 的输出结果；而优化目标是找到能使 $\theta \left( \alpha, \beta \right)$ 值最大的 $\alpha$、$\beta$。从编程角度理解，可以想象成是一个嵌套循环，内层循环找最小值，外层循环找最大值。

可以发现，原问题的优化目标是求最小值，而它的对偶问题中则变为求最大值。原问题及其对偶问题的特点是，两者的优化目标是相反的，而在特定条件下他们将拥有相同的最值点，这就引出下一节要介绍的强对偶定理。关于原问题及对偶问题更详细的内容见文末推荐阅读。

 

强对偶定理以及 KKT 条件

前面定义的原问题和对偶问题之间存在这样一个关系（弱对偶定理）：

可以证明一下上面的定理：

$f \left( \omega^{*} \right)$ 与 $\theta \left( \alpha^{*}, \beta^{*} \right)$ 的差称为原问题与对偶问题的 间距（Duality Gap），记作：

$G=f \left( \omega^{*} \right) - \theta \left( \alpha^{*}, \beta^{*} \right) \geq 0$

推导到这里，已经可以隐约看到原问题和对偶问题之间的联系了，但这还不足以帮助我们解决最优化问题。这两者之间存在更紧密的关系，被称作 强对偶定理（Strong Duality Theorem），这是在特定条件下，使得 $G=0$ 的一种情况：

这里提到了凸函数，顺便简要介绍一下凸函数的定义：

凸函数在不同专业领域有不同的称呼，你可以称它为凸函数或凹函数。它的特点是只有一个极值点，在本文中暂且认为凸函数的最值为最小值；它的另一个特点是在函数上任取两个不同的点连一条线段，两点之间凸函数总是在线段的下方。写成代数形式如下，当然，下面的式子同样适用于多维向量：

回到强对偶定理，在证明原问题和对偶问题的关系时，我们知道：

而在强对偶定理成立的条件下，因为 $f \left( \omega^{*} \right) = \theta \left( \alpha^{*}, \beta^{*} \right)$，即：

又因为 $h_{i}\left(\omega^{*} \right)=0$，不难推导出此时满足（被称为 KKT 条件，为了简洁，省略了一些前置条件）：

$\forall i=1,2,\cdots,K，\alpha^{*}_{i}=0 \enspace或\enspace g_{i} \left(\omega^{*} \right)=0$

简而言之，在强对偶定理成立的条件下，原问题及其对偶问题的最优解满足 KKT 条件的约束。

事实上，KKT 条件同时也是取得最优解的充要条件，因为在强对偶定理成立的条件下，变量满足 KKT 条件也就意味着 $f \left( \omega \right) = \theta \left( \alpha, \beta \right)$，而 $f \left( \omega \right)$ 和 $\theta \left( \alpha, \beta \right)$ 做为凸函数只会有一个最优解。

万事具备，接下来开始将 SVM 的原问题转换为对偶问题。

 

SVM 的原问题转换为对偶问题

前面我们已经知道了原问题及其对偶问题的定义，本节将介绍如何获得 SVM 最优化问题的原问题及其对偶问题。

我们在加入松弛变量之后得到这样一个 SVM 的最优化问题（使用 $\varphi$ 是为了更明显地看出核函数如何发挥作用）：

$\begin{align*}最小化：&\dfrac{1}{2} \left\| \omega\right\|^{2}+C\sum \limits^{N}_{i=1}\xi _{i}\\ 限制条件：&y_{i}\left[ \omega^{T}\varphi \left(X_{i} \right)+b \right] \geq 1-\xi _{i} \quad \left(i=1,2,\cdots,N \right) \\ &\xi _{i} \geq 0 \quad \left(i=1,2,\cdots,N \right) \end{align*}$

经过证明，SVM 最优化问题的目标函数是一个凸函数，那么它肯定有一个最小值。虽然还没开始推导，但我们已经可以看出它具有强对偶性。

先回顾一下原问题的定义：

$\begin{align*}最小化：&f \left( \omega \right)\\ 限制条件：&g_{i} \left( \omega \right) \leq 0 \quad \left( i=1,2,\cdots,K \right) \\ &h_{i} \left( \omega \right) = 0 \quad \left( i=1,2,\cdots,M \right)\end{align*}$

对比发现，原问题的限制条件和 SVM 最优化问题的限制条件有一定差距，但是原问题的定义具有很高的普适性，可以对 SVM 最优化问题做一些改造，让它和原问题保持一致。只需让松弛变量小于等于 $0$ 即可改造得到 SVM 最优化问题的原问题：

 $\begin{align*}最小化：&\dfrac{1}{2} \left\| \omega\right\|^{2}-C\sum \limits^{N}_{i=1}\xi _{i}\\ 限制条件：&1+\xi _{i}-y_{i} \omega^{T}\varphi\left(X_{i} \right)-y_{i}b \leq 0 \quad \left(i=1,2,\cdots,N \right) \\ &\xi _{i} \leq 0 \quad \left(i=1,2,\cdots,N \right) \end{align*}$

此时得到改造完成的限制条件存在两个不等式约束 $g_{i}\left(\omega \right)$，根据拉格朗日函数的构造方法，我们需要分别定义两个拉格朗日乘子 $\alpha_{i}$、$\beta_{i}$ 对 $g_{i}\left(\omega \right)$ 进行处理（关于拉格朗日函数见文末推荐阅读），此时可以得到 SVM 的对偶问题如下：

下图更直观地展示了整个推导过程：

为了方便后面的推导，需要进一步化简目标函数。前面说到 $\inf$ 是求最小值，那么先求偏导：

$\dfrac{\partial L}{\partial \omega}=0 \Rightarrow \omega=\sum \limits^{N}_{i=1} \alpha_{i} y_{i} \varphi \left(X_{i}\right) \\ \dfrac{\partial L}{\partial \xi_{i}}=0 \Rightarrow \beta_{i}+\alpha_{i}=C \quad \left(i=1,2,\cdots,N \right) \\ \dfrac{\partial L}{\partial b}=0 \Rightarrow \sum \limits^{N}_{i=1} \alpha_{i}y_{i}=0$

将结果代回目标函数，得：

最终，使用核函数替换 $\varphi\left(X_{i} \right)^{T}\varphi\left(X_{j} \right)$，并化简，得到 SVM 对偶问题的目标函数：

将限制条件联立求导结果，又可以得到 SVM 对偶问题的限制条件：

$\begin{align*}限制条件：&0\leq \alpha_{i} \leq C \quad \left(i=1,2,\cdots,N \right) \\ &\sum \limits^{N}_{i=1}\alpha_{i}y_{i}=0 \end{align*}$

可以看出最优化问题具有强对偶性，此时对偶问题的解即为 SVM 最优化问题的解。

到此，无限维向量 $\varphi \left(X_{i}\right)$ 和 $\omega$ 的内积已经被我们成功转化为核函数 $K$，我们只需求出有限维度的 $\alpha$。

 

SVM 的 KKT 条件

在介绍强对偶定理那一节里提及了 KKT 条件，而在接下来的章节中仍然会用到这个理论。趁热打铁， 我们已经通过对偶问题的定义得到了 SVM 原问题的对偶问题，那也就可以进一步得到 SVM 的 KKT 条件。

SVM 原问题中，存在一组不等式约束：

回顾上一节里提到的，根据拉格朗日函数的定义，我们需要分别给这两个限制条件引入拉格朗日乘子，两个乘子我们还是记作 $\alpha$ 和 $\beta$，此时 SVM 对偶问题的拉格朗日函数为：

根据前文 KKT 条件的推导过程，当取得最优解 $\omega^{*}$、$\xi^{*}$、$b^{*}$、$\alpha^{*}$、$\beta^{*}$ 时，有：

最终得到 SVM 的 KKT 条件为（省略了一些前置条件）：

也就是说，当满足上面的 KKT 条件时，SVM 取得最优解。

 

训练

上一节我们得到了 SVM 的对偶问题：

可以看到上面的最优化问题中，除了向量 $\alpha$，其他参数都是已知的，训练的目的是为了求出合适的 $\alpha$ 使得 SVM 能对样本正确地分类。接下来要介绍的 SMO 算法是一种常用的求解 $\alpha$ 的算法，其表现出的突出性能，值得笔者花费笔墨介绍它的原理。

 

SMO 算法

为了提高 SVM 的训练效率，John Platt 在 1998 年发表的论文《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》中提出了 SMO 算法。其基本思路是在 $\alpha$ 中选出两个分量作为变量，比如 $\alpha_{1}$、$\alpha_{2}$，而其余的分量 $\alpha_{3},\alpha_{4},\dots,\alpha_{N}$ 则作为固定的常数，这些常数都会被赋予初始值，接着通过求导等过程求出 $\alpha_{1}$、$\alpha_{2}$ 后，又会重新选出两个分量重复此过程，期间 $\alpha$ 的值将不断收敛，直到满足 KKT 条件时退出循环。

 

改造最优化问题

为了方便理解，我们设 $\alpha$ 中选出两个分量 $\alpha_{1}$、$\alpha_{2}$ 作为变量，其他分量看作常量，那么目标函数将变为（为了方便读者阅读时与 Platt 的论文进行对比，这里把优化目标转换为求最小值）：

为了书写方便，令 $K_{ij}=K\left(X_{i},X_{j}\right)=\varphi\left(X_{i}\right)^{T}\varphi\left(X_{j}\right)$，又因为 $y^{2}_{i}=1$，将目标函数继续拆分化简得：

红框内是常数项，在接下来的求导中就会被舍弃，为了简化公式，在当前阶段我们就可以忽略这两项。忽略常数项后，重新整理一下当前得到的最优化问题：

 

目标函数求导

在求导前，利用限制条件中 $\alpha_{1}$ 和 $\alpha_{2}$ 关系，将目标函数转换为只有变量 $\alpha_{2}$ 的一元函数。

令限制条件 $\alpha_{1}y_{1} + \alpha_{2}y_{i} = -\sum \limits_{i=3}^{N}\alpha_{i}y_{i}=\zeta$，等号两边乘上 $y_{1}$，可得 $\alpha_{1}$：

$\alpha_{1} = \left(\zeta - \alpha_{2}y_{2}\right)y_{1}$

如果我们最开始只选择一个分量作为变量，那么该变量会永远等于一个常数，算法将无法收敛，这也是 SMO 算法必须选择两个变量的原因。

重新将上面的等式代入目标函数，得到只有变量 $\alpha_{2}$ 的优化目标：

我们可以用符号来替代一些项，便于后面的求导：

别忘了前面章节我们提到核函数的交换性，即 $K_{ij}=K_{ji}$，写作 $K_{ij}$ 或 $K_{ji}$ 表达的含义都相同。

接下来对目标函数进行求导，得： 

 

求变量 $\alpha_{2}$

当导数为 0 时，得到一个新的 $\alpha_{2}$，我们记作 $\alpha_{2}^{new}$，而旧的值记作 $\alpha_{2}^{old}$。

令 $\frac{\partial \theta\left(\alpha_{2}\right)}{\partial \alpha_{2}}=0$，得：

重新展开 $\zeta$ 和 $v_{i}$，得到 $\alpha^{new}$ 和 $\alpha^{old}$ 之间的关系：

可以重新记作：

可以发现，$\eta$ 其实就是 $\theta \left(\alpha_{2} \right)$ 的二阶导，目标函数 $\theta \left(\alpha_{2} \right)$ 是一个凸函数，正常情况下它的二阶导 $\eta$ 将会大于 $0$。

 

裁剪 $\alpha_{2}^{new}$ 以及求解 $\alpha_{1}$

回顾一下目前最优化问题的限制条件：

上一小节我们使用 $\alpha_{1}y_{1} + \alpha_{2}y_{2} = \zeta$ 将目标函数转换为只有自变量 $\alpha_{2}$ 的一元函数，之后求导得到了 $\alpha_{2}^{new}$，本节将介绍如何使用 $0 \le \alpha_{1},\alpha_{2} \le C$ 对 $\alpha_{2}^{new}$ 进行“裁剪”。

为了始终满足 $\sum \limits^{N}_{i=1}\alpha_{i}y_{i}=0$ 的约束，训练开始时一般是把 $\alpha$ 所有的分量都初始化为 $0$，之后每次迭代中对 $\alpha_{1}$、$\alpha_{2}$ 的调整都是基于旧值，新旧值之间的关系如下：

将这两个限制条件绘制到坐标系中，可以更直观地看出 $\alpha_{2}^{new}$ 的上下限，分别用 $H$ 和 $L$ 表示。

当 $y_{i}\ne y_{j}$ 时：

当 $y_{i} = y_{j}$ 时：

根据得到的上下限 $H$ 和 $L$ 对 $\alpha_{2}^{new}$ 进行“裁剪”，得到 $\alpha_{2}^{new,clipped}$：

如上图所示，落在红色线段上的点 $\left(\alpha_{1}^{new},\alpha_{2}^{new,clipped} \right)$ 将满足限制条件的约束，我们可以通过 $\alpha_{2}^{new,clipped}$ 求得 $\alpha_{1}^{new}$：

$ \alpha_{1}^{new} = \alpha_{1}^{old} + y_{1}y_{2}\left(\alpha_{2}^{old} - \alpha_{2}^{new,clipped} \right)$

 

$\alpha_{i}$ 与 $u_{i}$ 的关系

推导进行到这里，你会发现函数 $u_{i}$ 中还有一个未知的常数项 $b$，SMO 每轮迭代都需要计算出 $b$，因为这关系到算法中的一个优化点，但是求解 $b$ 的前提是知道 $u_{i}$ 的输出值，为了解决这一问题，本节将介绍 $u_{i}$ 的取值范围与 $\alpha_{i}$ 之间的关系，为下一节求解 $b$ 做准备。

上文中，对于所有 $X_{i}$，我们设 SVM 的输出值：

$u_{i}=\omega^{T}\varphi\left(X_{i} \right)+b$

在原问题转对偶问题的那一节中，通过求偏导得到了 $\omega=\sum \limits^{N}_{j=1} \alpha_{j} y_{j} \varphi \left(X_{j}\right)$，这说明 $\alpha$ 影响着分离超平面多项式中的系数，它和常数项 $b$ 一样，对 SVM 模型能否正确工作起着决定性作用。

过分关注于公式推导，很容易让我们迷失其中，在开始本节的推导之前，有必要重申一下 $u_{i}$ 的含义。$u_{i}$ 这个输出值代表着 SVM 对训练样本 $X_{i}$ 的归类结果，而当我们改变 $\alpha_{i}$ 时，$u_{i}$ 也随之改变，这说明 $\alpha_{i}$ 的取值影响着 SVM 对样本 $X_{i}$ 的分类。

下面先罗列推导过程中需要用到的条件。

首先是 KKT 条件，这个理论是整个推导过程的关键。前文我们已经得到了 SVM 的 KKT 条件：

其次是 SVM 原问题的对偶问题中的限制条件：

最后是我们在对 SVM 对偶问题目标函数求偏导时，令 $\dfrac{\partial L}{\partial \xi_{i}}=0$ 得到的：

$\beta_{i}+\alpha_{i}=C \ ,\ i=1,2,\cdots,N$

结合上面的条件，从 $\alpha_{i}$ 可能出现的三种取值情况入手进行推导：

下面是推导过程：

最终得到 $\alpha_{i}$ 和 $u_{i}$ 之间的关系：

前面我们讨论过，支持向量是离分离超平面最近的点，且所有支持向量到分离超平面的距离都相等，对于任意支持向量 $X_{s}$，满足下面的关系式：

$\left| \omega^{T}\varphi\left(X_{s} \right)+b\right|=1$

$\Downarrow$

$y_{s}u_{s}=1$

显然，当 $0 < \alpha_{i} < C$ 时，样本向量 $X_{i}$ 在 SVM 模型中将作为支持向量。而除此之外的向量可能落在间隔内，也可能落在间隔外；可能被分离超平面正确分类，也可能被错误地分类。下面是一个简单的 SVM 模型例子，通过这个图可以更直观地看到样本和决策边界之间的关系：

 

更新偏置 $b$

偏置 $b$ 是 $u_{i}$ 中的常数项，但是它并不会影响 $\alpha_{2}^{new}$ 的求解结果，因为这一项在 $u_{1}-u_{2}$ 时就已经被消除了，它间接影响的是一个提高算法收敛效率的优化点，这在下一节中再做介绍，在此之前先来看一下如何计算 $b$。

上一小节我们确定了 $u_{i}$ 的取值和 $a_{i}$ 之间的关系，这为求解 $b$ 创造了条件。如果 $0<\alpha_{i}<C$，说明 $X_{i}$ 为支持向量，直接将 $\alpha_{i}$ 代入 $y_{i}u_{i}=1$ 即可求得 $b$；如果 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 的值都不在 $\left(0,C \right)$ 区间内，则分别代入 $y_{i}u_{i}=1$ 求得 $b_{1}$、$b_{2}$，再取他们的平均值作为 $b$。

下面是求解步骤。

将 $y_{1}u_{1}=1$ 等号两侧分别乘以 $y_{1}$，进而求得 $b_{1}$：

为了减少计算量，我们还使用了前面得到的 $E$ 参与运算。

同理，求出 $b_{2}$：

前面说到，本次迭代中的 $X_{1}$、$X_{2}$ 如果都不属于支持向量，偏置 $b$ 取 $b_{1}^{new}$、$b_{2}^{new}$ 的平均值：

Platt 在他1998年的论文中，2.3 小节末尾这样写道：

"When both new Lagrange multipliers are at bound and if L is not equal to H, then the interval between b1 and b2 are all thresholds that are consistent with the KKT conditions. SMO chooses the threshold to be halfway in between $b_{1}$ and $b_{2}$."

大概意思是说，如果 $H$ 不等于 $L$，$\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 两个拉格朗日乘子都在边界上（等于 $C$ 或 $0$）的时候，从 $b_{1}^{new}$ 到 $b_{2}^{new}$ 区间内的取值都是符合 KKT 条件约束的，这也是为什么取 $b_{1}^{new}$、$b_{2}^{new}$ 的平均值做为结果的原因。这里需要注意 $H$ 不等于 $L$ 这一前提，回看裁剪 $\alpha_{2}^{new}$ 那一节，你会发现只要 $C$ 大于 $0$，我们就能大概率保证 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 其中至少有一个在 $\left(0,C \right)$ 区间内。

那么在 $H\ne L$ 的前提下， $y_{1}=y_{2}$ 时，是否会出现 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 同时等于 $0$ 或同时等于 $C$ 的情况？在这种特殊情况下，如果取平均值做为 $b$，就会导致其中一个 $\alpha$ 违背 KKT 条件，我们又该如何处理？

还是回到裁剪 $\alpha_{2}^{new}$ 那一节中寻找答案，从 $y_{1}=y_{2}$ 的图里可以看出这种情况是有可能发生的，发生条件比较苛刻，分别是：

$\alpha_{1}^{old}=\alpha_{2}^{old}=0=\alpha_{2}^{new,clipped}$

或

$\alpha_{1}^{old}=\alpha_{2}^{old}=C=\alpha_{2}^{new,clipped}$

可以看到此时 $\alpha_{2}^{old}=\alpha_{2}^{new,clipped}$，在新旧值相等或变化极小的情况下，重新计算一遍 $b$ 是低效且无意义的。代码实现时，建议是在循环中直接跳过出现这种情况的迭代，那么也就不会出现 $b$ 无法满足 KKT 条件约束的问题。

 

用启发式方法选择两个变量

如何选择合适的 $\alpha_{1}$、$\alpha_{2}$ 以提高 SMO 算法的收敛速度是接下来要探讨的内容，前文铺垫许久的 $b$ 也将在本节发挥它的作用，事实上，如果不打算实现这一优化，我们完全可以在训练结束后再通过支持向量计算得到 $b$，但是大部分应用场景的训练集都非常庞大，我们必须见缝插针地对算法进行优化。

我们可以这样理解 SMO 的工作原理，SMO 每次从向量 $\alpha$ 中选择两个分量进行优化，$\alpha$ 可以想象成一条直线的斜率，我们通过修改 $\alpha$ 来转动这条直线，使直线不断逼近某个角度，直到正确地分隔开所有训练样本，即最终目的是要使所有样本都符合 KKT 条件的约束。

显然，在某一次迭代中，仅通过优化两个样本系数得到的分离超平面不一定能够正确地分类所有样本，那么，我们可以选择当前被错误分类（违背 KKT 条件）的样本系数作为下一轮迭代待优化的变量，以此提高算法的收敛速度，这也是 Platt 的论文 2.2 节中提到的启发式选择乘子的基本思想。

这时前面求出的 $b$ 就派上用场了。在某一轮迭代结束时，明确了 $b$ 和 $\alpha$，意味着可以通过函数 $u_{i}$ 计算出当前违背了 KKT 条件的训练样本。

先介绍如何选择 $\alpha_{1}$。注意这里 $\alpha_{1}$ 的含义不是指第一个样本系数，它代表的是第一个待求的变量，$\alpha_{2}$ 同理。

启发式算法会循环处理所有违背 KKT 条件的点，直到所有样本都满足 KKT 条件为止。循环内有两种子循环用于选择并处理变量，第一种是选所有违背 KKT 条件的样本系数做为 $\alpha_{1}$ 进行遍历，第二种是选择违背了 KKT 条件且不在边界上的样本系数（$y_{i}u_{i}\ne1$ 且 $0 < \alpha_{i} < C$）做为 $\alpha_{1}$ 进行遍历，且外层循环每次迭代只会执行其中一种子循环。整体流程是先执行一次第一种子循环，接着会一直调用第二种，直到 $0 < \alpha_{i} < C$ 的样本都被正确分类，然后又会从头开始，不断重复此过程。需要注意的是，子循环的每次有效迭代都会导致分离超平面方程的系数 $\alpha$ 发生改变，有些待处理的点可能因此变得符合 KKT 条件，所以子循环在执行时，还需要跳过那些已经符合条件约束的点。

在子循环的每次迭代中，选出 $\alpha_{1}$ 后，再从 $0 < \alpha_{i} < C$ 的样本系数中选出 $\alpha_{2}$，选择标准是使得 $\left| E_{1}-E_{2}\right|$ 的值达到最大。从 $\alpha_{2}^{new}$ 的求值公式可以看出 $\left| E_{1}-E_{2}\right|$ 一定程度上反映了每次迭代的步长，增大步长有助于算法更快收敛。

可以发现启发式算法在选择 $\alpha_{1}$ 时，优先选择不在边界上的样本，Platt 在他的论文中称之为 非边界样本（non-bound example）。非边界样本做为支持向量，只是占训练样本中的少数，Platt 认为优先处理非边界样本有助于减少迭代次数，秉承这一原则，$\alpha_{2}$ 也是从非边界样本中选出，只不过 $\alpha_{2}$ 不要求必须违背 KKT 条件，只要能使 $\left| E_{1}-E_{2}\right|$ 的值最大即可。

 

优化项，更新 $\omega$

在线性 SVM 中，可选用线性核 $K \left(X_{1},X_{2}\right)=X_{1}^{T}X_{2}$ 进行运算，其实相当于不使用核函数，那么在程序实现 $u_{i}$ 函数的时候，我们应该使用 $\omega$ 参与运算而不是使用 $\alpha$：

$u_{i}=\omega^{T}X_{i}+b$

$\alpha$ 直接参与运算会浪费大量算力，正确的做法是使用 $\alpha$ 计算 $\omega$，并对 $\omega$ 做好缓存：

 

关于 SMO 算法收敛性的讨论

关于 SMO 算法的收敛性证明可以看 Osuna 等人所著的论文《An Improved Training Algorithm for Support Vector Machines》，SMO 算法每次选择两个乘子进行优化的思想就是来源于 Osuna 等人的理论。

论文中，$\alpha$ 中的变量被拆分为两个集合 $B$ 和 $N$，$B$ 被称为 工作集（Working Set），工作集中是待求的变量，SMO 中选出的两个乘子就是工作集；$N$ 则代表固定的变量集合。

Osuna 他们先是证明了，将 $B$ 中的变量移动到 $N$ 后，目标函数的输出仍然保持不变（见 3.2 节 Proposition 3.1）。也就是说，$B$ 中变量的值取得最优解后，将其中一些变量移动到 $N$，此时 $B$ 中剩下的变量值仍然是当前目标函数的最优解。

但如果把 $N$ 中的变量移动到 $B$，即目标函数待求的变量变多了，那么此时 $B$ 中变量的值还是不是最优解就不得而知了。幸运的是，我们已经知道了 KKT 条件是目标函数取得最优解的充要条件，那么在每次迭代只取 $N$ 中违背 KKT 条件的变量移动到 $B$ ，就能保证移动后 $B$ 中的值不会是目标函数的解，也就不会导致优化过程做了无用功，这也是 SMO 算法在选择变量时，要求其中至少有一个变量违背 KKT 条件的原因。

总结一下上面的内容。$B$ 取得最优解后，将其中一些变量移入 $N$ ，$B$ 中剩下的变量仍然是目标函数的解；但是从 $N$ 中取出违背 KKT 条件的变量移动到 $B$，则会导致目标函数重新拥有待优化的空间。这说明 SMO 的每一次迭代都会让 $\alpha$ 往最优解靠近，又因为目标函数是凸函数，算法将会在有限次迭代后收敛到全局最优解。

 

测试

在训练开始前需要保留一部分训练样本，这些样本不能参与训练，而是用于训练结束后检验模型的可用性。这一步非常重要，通过分析测试中无法正确分类的样本，将帮助我们更好地完善算法，例如用来判断模型是否过拟合或欠拟合、$C$ 的值是否需要调整、核函数如何选型等等。

在介绍 SMO 的那一节中就已经提到了 $b$ 的计算方法，根据 SVM 的 KKT 条件，选一个支持向量 $X_{s}$ 即可通过下面公式计算得到：

$b=y_{s}- \sum \limits^{N}_{i=1} \alpha_{i} y_{i} K\left(X_{i},X_{s}\right)$

然后再通过 $y_{i}u_{i}$ 判断样本是否能够被正确分类。如果选用了线性核，同样可以学习 SMO 算法对 $\omega$ 进行缓存。

其实关于测试还有很多学问，但是受限于篇幅以及本文重点是 SVM 算法，后续有机会在新文章中再做详细介绍。

 

参考资料

浙江大学胡浩基机器学习公开课程

SMO算法原理

支持向量机（五）SMO算法

机器学习算法实践-SVM中的SMO算法

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines

An Improved Training Algorithm for Support Vector Machines

代码实现

 

推荐阅读

学习笔记-拉格朗日函数

知识点 | 全面理解支持向量机

正定(positive definite)与半正定(semi-positive definite)

线性规划的对偶问题

原始问题与对偶问题