[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$ 个训练样本，可以用 向量 和 标签 去定义它：

其中：

$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}$ 代表转置，$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$

我们通过调整 $\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$，同时为了求导方便，目标函数也做了改造）：

这个最优化问题是一个二次规划问题， 二次规划（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}$ 是标量，代数式可以写成矩阵的形式如下，设 $K_{ij}=K\left(X_{i},X_{j}\right)$，则：

所有核函数构成了一个 Gram 矩阵，矩阵具有半正定性，关于什么是半正定性见文末推荐阅读。

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

原问题

先来看一下最优化问题的 原问题（Prime Problem）如何定义，设函数的定义域为 $D$：

$\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)\ &\omega\in D\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）。

对偶问题可以粗糙地理解为原问题的”镜像”，例如原问题目标是求最小值，那么其对偶问题就是求最大值。在 SVM 优化问题中，原问题及其对偶问题具有相同的极值点，此时求出对偶问题的解，也即原问题的解。

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

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

有了拉格朗日函数即可构造对偶问题的目标函数。注意这里 $\omega$ 的取值范围不受原问题中 $g(\omega)\le 0$ 限制条件的约束，对偶问题定义如下：

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

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

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

凸函数

SVM 的优化目标是一个 凸函数（Convex Function），这里简要介绍一下凸函数的定义：

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

强对偶定理以及 KKT 条件

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

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

不等式 $f(\omega) \geq \theta \left( \alpha, \beta \right)$ 可以进一步推出：

$\min\limits_{\omega}f(\omega) \geq \theta(\alpha, \beta)$

$\Downarrow$

$\min\limits_{\omega}f(\omega) \geq \max\limits_{\alpha,\ \beta}\theta(\alpha, \beta)$

$\Downarrow$

$f(\omega^{}) \geq \theta(\alpha^{}, \beta^{*})$

$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）描述的是在特定条件下（更多条件见此Wiki链接），使得 $G=0$ 的情况，下面是 SVM 优化问题满足的 LCQ 条件：

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

因为 $h_{i}\left(\omega^{*} \right)=0$，又因为 $g_{i}(\omega)\le 0$ 且 $\alpha\ge 0$，所以必须满足条件：

上面这个条件被称为 互补松弛条件（Complementary Slackness Condition）。

我们将当前取得最优解时满足的所有条件罗列如下，这被称为 KKT 条件（Karush–Kuhn–Tucker Conditions）：

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

KKT 条件也是 SVM 优化问题取得最优解的充要条件，如果优化问题具有强对偶性，满足 KKT 条件也就意味着取得最优解。

顺便来看一下如何从几何层面理解弱对偶定理。将 $\mathbb{G}={\left(g(\omega),f(\omega)\right)\ |\ \omega\in D}$ 映射到二维空间，假设得到一个”凹”形区域如下图：

如上图所示，对偶问题中，不同 $\alpha$ 值的 $L$ 函数在 $\inf\limits_{\omega}{\cdot}$ 的作用下，最终在 $\mathbb{G}$ 的底部边缘取得最小值。

对偶问题的优化目标是使函数 $\theta(\cdot)=\inf\limits_{\omega}{L(\cdot)}$ 取得最大值，我们将上面三个不同 $\alpha$ 值的 $\theta(\cdot)$ 放到下图对比展示，显然，当 $\alpha=\alpha^{(1)}$ 时对偶问题取得最优解：

又因为原问题的解只会在可行域上（${\left(g(\omega),f(\omega)\right)\ |\ \omega\in S}$，即阴影部分），这就导致对偶问题的最优解始终小于原问题的最优解：

同理，如果 $\mathbb{G}$ 是一个圆形或者类似圆形的区域，那么强对偶定理将成立：

了解了以上原问题、对偶问题和 KKT 条件的基本概念后，接下来开始将 SVM 的原问题转换为对偶问题。

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

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

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

经过证明，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 最优化问题的原问题：

改造完成的原问题存在两个不等式约束，根据拉格朗日函数的定义，我们设引入的两个拉格朗日乘子分别为 $\alpha$、$\beta$（关于拉格朗日函数见文末推荐阅读），此时得到 SVM 的对偶问题如下：

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

为了方便后面的推导，需要进一步化简目标函数。前面说到 $\inf\limits_{\omega,\xi,b}{\cdot}$ 是求最小值，那么最小值必然在偏导为零时取得：

$\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 对偶问题的目标函数：

这相当于在满足限制条件的前提下，将 $\omega$、$\xi$、$b$ 都转换为 $\alpha$。

将偏导为零时得到的结果联立原本的限制条件，得到新的限制条件：

$\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 对偶问题的拉格朗日函数：

优化问题具有强对偶性时，如果取得最优解 $\omega^{}$、$\xi^{}$、$b^{}$、$\alpha^{}$、$\beta^{*}$，则有：

得到 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)$，这里也别忘了前面提到核函数的交换性，即 $K_{ij}=K_{ji}$。

又因为 $y^{2}_{i}=1$，将目标函数继续拆分化简得：

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

目标函数求导

由于核函数构成的矩阵具有半正定性，目标函数是一个具有最小值的凸函数，形似碗，示意图如下：

接下来结合限制条件，将目标函数转换为只有变量 $\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 算法必须选择两个变量的原因。

将上面的等式代入目标函数 $\theta(\alpha_{1},\alpha_{2})$，得到只有变量 $\alpha_{2}$ 的目标函数：

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

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

求变量 $\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}$，但由于不等式约束的存在，需要对 $\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}$ 这个输出值代表着 SVM 对训练样本 $X_{i}$ 的归类结果，在改变 $\alpha_{i}$ 时，$u_{i}$ 也随之变化，这说明 $\alpha_{i}$ 的取值影响着 SVM 对样本 $X_{i}$ 的分类。

进入正题，下面我们来分析 $u_{i}$ 与 $\alpha_{i}$ 之间的关系。

首先是上文得到的 KKT 条件：

又因为之前在对拉格朗日函数求偏导时，由 $\dfrac{\partial L}{\partial \xi_{i}}=0$ 解得：

$\beta_{i}+\alpha_{i}=C\quad \forall 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

Original: https://www.cnblogs.com/CookMyCode/p/16156768.html
Author: CookMyCode
Title: [ML从入门到入门] 支持向量机：从SVM的推导过程到SMO的收敛性讨论