Support Vector Machine

Table of Contents

1 支持向量机简介

支持向量机(Support Vector Machine, SVM)是一种二类分类模型。

从简单到复杂,下面将介绍三种支持向量机模型:线性可分支持向量机(linear support vector machine in linearly separable case)、线性支持向量机(linear support vector machine)及非线性支持向量机(non-linear support vector machine)。

参考:
本文主要摘自《统计学习方法,李航著》第7章 支持向量机

2 线性可分支持向量机

线性可分支持向量机是最简单的SVM,它仅能处理“线性可分”的训练数据集。

在感知机(Perceptron)模型中,对线性可分的训练数据集,其对应的分离超平面有很多个。其中, 离两类训练数据间隔最大的那个分离超平面显然更好,这就是线性可分支持向量机采用的策略。 如图 1 所示。

线性可分支持向量机又称为“硬间隔支持向量机”。

Sorry, your browser does not support SVG.

Figure 1: 感知机中分离超平面H2和H3都是可行的,SVM中选择比较好的H3

2.1 回忆感知机模型

首先,回忆一下感知机模型的基本知识。

感知机模型表示如下:
\[f(\boldsymbol{x}) = \begin{cases} +1 & \text{if} \; \boldsymbol{w} \cdot \boldsymbol{x} + b > 0 \\ -1 & \text{otherwise} \end{cases}\]

对于训练数据 \((\boldsymbol{x_i}, y_i)\) ,可以通过测试 \(\boldsymbol{w} \cdot \boldsymbol{x_i} + b\) 的符号与类标记 \(y_i\) 的符号是否一致来判断分类是否正确。

我们知道,输入空间 \(\mathbb{R}^n\) 中任一点 \(\boldsymbol{x}\) 到分离超平面 \(\boldsymbol{w} \cdot \boldsymbol{x} + b = 0\) 的距离为:
\[\frac{1}{\Vert \boldsymbol{w} \Vert} | \boldsymbol{w} \cdot \boldsymbol{x} + b |\]

特别地,当输入空间为 \(\mathbb{R}^2\) 时,这就是点到线的距离公式 \(d=\frac{|ax_0 + by_0 + c|}{\sqrt{a^2+b^2}}\) ;当输入空间为 \(\mathbb{R}^3\) 时,这就是点到平面的距离公式 \(d=\frac{|Ax_0 + By_0 + Cz_0 + D|}{\sqrt{A^2+B^2+C^2}}\) 。

2.2 几何间隔和函数间隔

定义训练数据样本点到分离超平面的几何间隔(Geometrical Margin)为:
\[\gamma_i = y_i \left(\frac{1}{\Vert \boldsymbol{w} \Vert} ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \right)\]

由于可以通过测试 \(\boldsymbol{w} \cdot \boldsymbol{x_i} + b\) 的符号与类标记 \(y_i\) 的符号是否一致来判断分类是否正确,且有 \(y_i \in \{+1, -1\}\) ,所以 对于分类正确的点来说几何间隔就是实例点到分离超平面的距离,但对于分类不正确的点来说几何间隔是一个负数(实例点到超平面的距离的相反数)。 可以认为几何间隔是一个带符号距离(signed distance)。

我们把正(或负)训练数据集到分离超平面的几何间隔定义为所有正(或负)样本点 \((\boldsymbol{x_i}, y_i)\) 到分离超平面的几何间隔的最小值,即:
\[\gamma = \min_{i=1,\cdots,N} \gamma_i\]

定义训练数据样本点到分离超平面的函数间隔(Functional Margin)为:
\[\hat{\gamma_i} = y_i (\boldsymbol{w} \cdot \boldsymbol{x_i} + b )\]

我们把正(或负)训练数据集到分离超平面的函数间隔定义为所有正(或负)样本点 \((\boldsymbol{x_i}, y_i)\) 到分离超平面的函数间隔的最小值,即:
\[\hat{\gamma} = \min_{i=1,\cdots,N} \hat{\gamma_i}\]

显然,正(或负)训练数据集到分离超平面的函数间隔 \(\hat{\gamma}\) 和几何间隔 \(\gamma\) 有下面关系:
\[\gamma = \frac{\hat{\gamma}}{\Vert \boldsymbol{w} \Vert}\]

函数间隔和几何间隔都可以表示训练数据分类的正确性(因为分类正确时 \(\boldsymbol{w} \cdot \boldsymbol{x_i} + b\) 和 \(y_i\) 符号相同,故函数间隔和几何间隔都为正数)。

2.2.1 同一模型的函数间隔可取“任何正数”

考虑输入空间为 \(\mathbb{R}^2\) 时的情况。在图 2 中,正实例点 \((2,2)\) 到分离超平面的函数间隔为多少呢?

SVM_functional_margin.png

Figure 2: 分离超平面的表达形式不同,函数间隔会不同

显然,函数间隔没有唯一值。如果分离超平面表示为 \(x^{(1)} + x^{(2)} - 1 = 0\) ,则函数间隔为 \((+1)(2 + 2 - 1) = 3\) ;如果分离超平面表示为 \(\frac{1}{3} x^{(1)} + \frac{1}{3} x^{(2)} - \frac{1}{3} = 0\) ,则函数间隔为 \((+1)(\frac{2}{3} + \frac{2}{3} - \frac{1}{3}) = 1\) 。

所以,在同一模型中,函数间隔可取“任何正数”,我们总可以找到对应的分离超平面的参数。

如果约定正(或负)训练数据集到分离超平面的函数间隔为1,则几何间隔可表示为:
\[\gamma = \frac{1}{\Vert \boldsymbol{w} \Vert}\]

下文将利用这个约定来简化优化问题。

2.3 最大间隔分类器(Large Margin Classifier)

“最大化间隔(显然是几何间隔)”有什么意义呢?可以这样直观地表述: 不仅能将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度(confidence)将它们分开。 这样的分离超平面对未知的新实例有很好的分类预测能力。

设训练数据集实例数为 \(N\) ,最大间隔分离超平面可以用下面的约束最优化问题表述:
\[\begin{aligned} & \underset{\boldsymbol{w},b}{\text{maximize}} && \gamma \\ & \text{subject to} && y_i \left(\frac{1}{\Vert \boldsymbol{w} \Vert} ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \right) \ge \gamma, \quad i=1,2,\cdots,N\\ \end{aligned}\]
即希望最大化整个训练数据集到分离超平面的几何间隔 \(\gamma\) ,约束条件表示每个训练数据点到分离超平面的几何间隔至少是 \(\gamma\) 。

利用几何间隔和函数间隔的关系,上面这个优化问题,可以改写为:
\[\begin{aligned} & \underset{\boldsymbol{w},b}{\text{maximize}} && \frac{\hat{\gamma}}{\Vert \boldsymbol{w} \Vert} \\ & \text{subject to} && y_i \left(\frac{1}{\Vert \boldsymbol{w} \Vert} ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \right) \ge \frac{\hat{\gamma}}{\Vert \boldsymbol{w} \Vert}, \quad i=1,2,\cdots,N\\ \end{aligned}\]

函数间隔 \(\hat{\gamma}\) 的取值不会影响这个最优化问题的解(上文有具体解释),我们取函数间隔 \(\hat{\gamma} = 1\) 。同时我们把极大化问题变换为其等价的极小化问题(极大化 \(\frac{1}{\Vert \boldsymbol{w} \Vert}\) 显然等价于极小化 \(\Vert \boldsymbol{w} \Vert\) ,等价于极小化 \(\Vert \boldsymbol{w} \Vert^2\) ,也等价于极小化 \(\frac{1}{2} \Vert \boldsymbol{w} \Vert^2\) )。所以,上面的优化问题等价于:
\[\begin{aligned} & \underset{\boldsymbol{w},b}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 \\ & \text{subject to} && y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1, \quad i=1,2,\cdots,N\\ \end{aligned}\]

这是一个凸二次规划(convex quadratic programming)问题,至此我们把不好求解的原始优化问题转换为了有现成算法或优化软件的凸二次规划问题。

设求解上面优化问题得到的解为: \(\boldsymbol{w}^{*}, b^{*}\)
则最终我们得到的分离超平面为: \(\boldsymbol{w}^{*} \cdot \boldsymbol{x} + b^{*} = 0\) ,从而得到的“线性可分支持向量机”的决策函数可写为:
\[f(\boldsymbol{x}) = sign(\boldsymbol{w}^{*} \cdot \boldsymbol{x} + b^{*})\]

2.4 支持向量(“支持向量机”名字的由来)

训练数据集线性可分时,与分离超平面距离最近的样本点实例称为 支持向量(support vector) ,即支持向量是使约束条件 \(y_i ( \boldsymbol{w} \cdot \boldsymbol{x} + b ) \ge 1\) 中等号成立的点。
在图 3 中,对于 \(y_i = 1\) 的正实例点,支持向量在超平面 \(H_1 : \boldsymbol{w} \cdot \boldsymbol{x} + b = 1\) 上,对于 \(y_i = -1\) 的负实例点,支持向量在超平面 \(H_2 : \boldsymbol{w} \cdot \boldsymbol{x} + b = -1\) 上。 在超平面 \(H_1\) 和 \(H_2\) 上的点就是支持向量。

SVM_support_vector.png

Figure 3: 支持向量

超平面 \(H_1\) 和 \(H_2\) 是平行的, \(H_1\) 和 \(H_2\) 之间的距离称为间隔(margin) ,其间隔等于 \(\dfrac{2}{\Vert \boldsymbol{w} \Vert}\) (因为原始的最优化问题中即要求每个点到分离超平面距离至少为 \(\gamma = \dfrac{\hat{\gamma}}{\Vert \boldsymbol{w} \Vert} = \dfrac{1}{\Vert \boldsymbol{w} \Vert}\) ,当然由 \(H_1\) 和 \(H_2\) 的方程也可以直接推导出其间隔为 \(\dfrac{1 - (-1)}{\Vert \boldsymbol{w} \Vert} = \dfrac{2}{\Vert \boldsymbol{w} \Vert}\) )。

在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机。 支持向量的个数一般很少,支持向量机由很少的“重要的”训练样本(支持向量)确定。

2.5 “硬间隔支持向量机”求解过程及实例

前面介绍过,硬间隔支持向量机等价于下面凸二次规划问题:
\[\begin{aligned} & \underset{\boldsymbol{w},b}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 \\ & \text{subject to} && y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1, \quad i=1,2,\cdots,N\\ \end{aligned}\]
其中, \(N\) 为训练数据集实例数。
这是一个纯粹的数学优化问题,具体求解过程可参考本文附录。

“硬间隔支持向量机”的简单实例可参考:http://aandds.com/blog/dual-problem.html

3 线性支持向量机

如果训练数据不是线性可分的,而仅仅是近似线性可分的,无法使用前面介绍的硬间隔最大化(因为不等式约束无法都满足)。
我们通过把硬间隔最大化(hard margin maximization)修改为软间隔最大化(soft margin maximization)可以处理近似线性可分的数据。这称为“软间隔支持向量机”,又称线性支持向量机(linear support vector machine)。

3.1 软间隔最大化(处理近似线性可分数据集)

假设训练数据中有一些特异点(outlier),将这些特异点除去后,剩下的样本点组成的集合是线性可分的。这样的数据集是近似线性可分数据集。

特异点不能满足函数间隔大于等于1的约束条件 \(y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1\) 。为了解决这个问题,我们对每个样本点 \((\boldsymbol{x_i}, y_i)\) 引进一个松弛变量 \(\zeta_i\) ,使函数间隔加上松弛变量大于等于1。这样,约束条件变为了:
\[y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i\]

同时,对每个松弛变量 \(\zeta_i\) ,增加一个代价 \(\zeta_i\) ,所以目标函数由原来的 \(\dfrac{1}{2} \Vert \boldsymbol{w} \Vert^2\) 变为了:
\[\dfrac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i\]
这里, \(C > 0\) 称为惩罚参数,一般根据不同的应用问题由用户决定, \(C\) 值大时对误分类的惩罚增加, \(C\) 值小时对误分类的惩罚减小。
最小化上面的目标函数有两层含义:使 \(\dfrac{1}{2} \Vert \boldsymbol{w} \Vert^2\) 尽量小即间隔尽量大,同时使误分类点的个数尽量小, \(C\) 用来调和二者的系数。

相对于硬间隔最大化,上面的思路称为软间隔最大化。

从而, 线性支持向量机等价于下面的凸二次规划问题:
\[\begin{aligned} & \underset{\boldsymbol{w},b,\boldsymbol{\zeta}}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i \\ & \text{subject to} && y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i, \quad i=1,2,\cdots,N \\ &&& \zeta_i \ge 0, \quad i=1,2,\cdots,N \\ \end{aligned}\]
其中, \(N\) 为训练数据集实例数。

设求解上面优化问题得到的解为: \(\boldsymbol{w}^{*}, b^{*}\)
则最终我们得到的分离超平面为: \(\boldsymbol{w}^{*} \cdot \boldsymbol{x} + b^{*} = 0\) ,从而得到的“线性支持向量机”的决策函数可写为:
\[f(\boldsymbol{x}) = sign(\boldsymbol{w}^{*} \cdot \boldsymbol{x} + b^{*})\]

3.2 “软间隔支持向量机”求解过程

和“硬间隔支持向量机”求解过程类似,这是一个纯粹的数学优化问题。具体求解过程可参考本文附录。

3.3 用“合页损失函数”表示线性支持向量机

“软间隔支持向量机”有时也表示为下面的无约束优化问题:
\[\underset{\boldsymbol{w},b}{\text{minimize}} \sum_{i=1}^{N} \max(0, 1 - y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b)) + \lambda \Vert \boldsymbol{w} \Vert^2\]
其中, \(\max(0, 1 - y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b))\) 称为合页损失(Hinge loss)函数。

上面这个无约束优化问题等价于(推导过程可参考《统计学习方法,李航著》7.2.4 合页损失函数):
\[\begin{aligned} & \underset{\boldsymbol{w},b,\boldsymbol{\zeta}}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i \\ & \text{subject to} && y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i, \quad i=1,2,\cdots,N \\ &&& \zeta_i \ge 0, \quad i=1,2,\cdots,N \\ \end{aligned}\]

4 非线性支持向量机

“软间隔支持向量机”对偶问题中 只出现了训练数据的内积形式 ,这可以方便地应用核方法(Kernel Method)使得“软间隔支持向量机”可以处理线性不可分的数据。

5 附录

5.1 “硬间隔支持向量机”求解过程

硬间隔支持向量机等价于下面优化问题(称为原问题):
\[\begin{aligned} & \underset{\boldsymbol{w},b}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 \\ & \text{subject to} && y_i \left ( \langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b \right ) \ge 1, \quad i=1,2,\cdots,N\\ \end{aligned}\]

其中, \(N\) 为训练数据的总数。设每个训练数据有 \(m\) 维特征, \(\boldsymbol{w} = (w^{(1)},w^{(2)},\cdots,w^{(m)})^\mathsf{T} \in \mathbb{R}^m\) 。 \(\Vert \cdot \Vert\) 是向量的范数记号,有 \(\Vert \boldsymbol{w} \Vert = \sqrt{{w^{(1)}}^2 + {w^{(2)}}^2 + \cdots + {w^{(m)}}^2}\) 。

直接求解这个优化问题比较难,我们通过求解它的对偶问题来求解原问题。

5.1.1 求解对偶问题

广义拉格朗日函数为:
\[\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big)\]

原问题的对偶问题为:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{maximize}} & & \min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\\ & \text{subject to} & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

下面化简 \(\min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\) ,分别对 \(\boldsymbol{w},b\) 求偏导数并令其为0,有:
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \end{cases}\]
由上式,有:
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \\ \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \end{cases}\]
利用上面两式,化简广义拉格朗日函数,有:
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \sum_{i=1}^{N} \alpha_i y_i \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \boldsymbol{x_i} \right \rangle - \sum_{i=1}^{N} \alpha_i y_i b + \sum_{i=1}^{N} \alpha_i \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \sum_{i=1}^{N} \alpha_i y_i \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \boldsymbol{x_i} \right \rangle + \sum_{i=1}^{N} \alpha_i \\ & = \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 - \left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \rangle + \sum_{i=1}^{N} \alpha_i \\ \end{aligned}\]
由于 \(\left \langle \sum\limits_{j=1}^{N} \alpha_j y_j \boldsymbol{x_j} , \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \rangle = \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2\) ,所以上式可写为:
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) & = - \frac{1}{2} \left \Vert \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \right \Vert^2 + \sum_{i=1}^{N} \alpha_i \\ & = - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i \end{aligned}\]

化简广义拉格朗日函数时利用了 \(\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha})\) 取极值时的结论,从而有 \(\min\limits_{\boldsymbol{w},b} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\alpha}) = - \dfrac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i\)

所以,对偶问题等价于:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{maximize}} & & - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

又可以写为:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

利用KKT最优化条件容易求解上面的对偶问题(求解它比直接求解原始优化问题容易得多,可以用 Sequential minimal optimization, SMO 算法快速地求解它)。
假设求得的对偶问题解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) (注:在这里我们把向量的分量记为下标形式,这和 \(\boldsymbol{w},\boldsymbol{x}\) 把向量分量记为上标形式不同),如何利用对偶问题的解(即 \(\boldsymbol{\alpha}^{*}\) )得到原始优化问题的解呢?请看下文分解。

5.1.2 利用对偶问题的解求原问题

原问题满足“强对偶定理”的条件,由“强对偶定理”知,对偶问题的解 \(\boldsymbol{\alpha}^{*}\) 就是原问题取得最小值时广义拉格朗日函数 \(\mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha})\) 中 \(\boldsymbol{\alpha}\) 的值。有了这个信息,原问题的KKT最优化条件迎刃而解,原始问题也迎刃而解。

原问题的KKT条件:
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i^* y_i = 0 \\ \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) = 0, \; i = 1,2,\cdots,N \\ y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \ge 0, \; i = 1,2,\cdots,N \\ \alpha_i^* \ge 0, \; i = 1,2,\cdots,N \\ \end{cases}\]
上式中,只有 \(\boldsymbol{w},b\) 是待求的参数, \(\boldsymbol{\alpha}^{*}\) 是求解对偶问题时得到的解, \(\boldsymbol{x_i}, y_i\) 分别是训练数据及其分类标记。
由上面方程组可知:
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]
现在我们来求解 \(b\) 。至少可以找到一个 \(\alpha_j^* > 0\) (用反证法,如果 \(\forall i, \alpha_i = 0\) ,那么 \(\boldsymbol{w} = \boldsymbol{0}\) ,这不是原始问题的解)。所以,对满足 \(\alpha_j^* > 0\) 的 \(j\) 有:\(\alpha_j^* \big ( y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 \big) = 0\) ,即有:
\[y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 = 0\]
注意到 \(y_j^2 = 1\) ,所以有:
\[\begin{aligned} b & = y_j - \langle \boldsymbol{w}, \boldsymbol{x_j} \rangle \\ & = y_j - \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} , \boldsymbol{x_j} \right \rangle \\ & = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{aligned}\]

至此,原优化问题中的 \(\boldsymbol{w}, b\) 都已经得到。

5.1.3 硬间隔支持向量机算法总结

前面已经完整介绍了线性可分支持向量机(硬间隔支持向量机)的求解过程,现在总结如下。

设有线性可分的训练数据集 \(T = \{ (\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), \cdots, (\boldsymbol{x_N},y_N) \}\) ,其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{ -1 , +1 \}, i=1,2,\cdots, N\) ,求最大间隔分类器。

求解过程如下:
第一步,构造并求解下面约束优化问题:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]
求解它(如用SMO算法),假设得到的解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\)

第二步,计算 \(\boldsymbol{w},b\) :
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]
任意选择 \(\boldsymbol{\alpha}^{*}\) 的一个正分量 \(\alpha_j^* >0\) ,找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ,计算:
\[b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle\]

特别说明 :由 \(\boldsymbol{w},b\) 的计算公式可知, \(\boldsymbol{w},b\) 只依赖于训练数据集中对应于 \(\alpha_i^{*} >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) ,而其他训练数据对 \(\boldsymbol{w},b\) 没有影响。 这些对应于 \(\alpha_i^* >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) 就是 支持向量(Support Vector)

第三步,分类决策函数为:
\[\begin{aligned} f(\boldsymbol{x}) & = sign(\langle \boldsymbol{w}, \boldsymbol{x} \rangle + b) \\ & = sign \left( \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \\ & = sign \left( \sum\limits_{i=1}^{N} \alpha_i^* y_i \left \langle \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \end{aligned}\]

5.2 “软间隔支持向量机”求解过程

线性支持向量机等价于下面的凸二次规划问题(称为原问题):
\[\begin{aligned} & \underset{\boldsymbol{w},b,\boldsymbol{\zeta}}{\text{minimize}} && \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i \\ & \text{subject to} && y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i, \quad i=1,2,\cdots,N \\ &&& \zeta_i \ge 0, \quad i=1,2,\cdots,N \\ \end{aligned}\]
其中, \(N\) 为训练数据的总数。设每个训练数据有 \(m\) 维特征, \(\boldsymbol{w} = (w^{(1)},w^{(2)},\cdots,w^{(m)})^\mathsf{T} \in \mathbb{R}^m\) 。

直接求解这个优化问题比较难,我们通过求解它的对偶问题来求解原问题。

5.2.1 求解对偶问题

广义拉格朗日函数为:
\[\begin{aligned} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r} ) & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 + C \sum_{i=1}^{N} \zeta_i - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) - \sum_{i=1}^{N} r_i \zeta_i \\ & = \frac{1}{2} \Vert \boldsymbol{w} \Vert^2 - \sum_{i=1}^{N} \alpha_i \big ( y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 \big) + \sum_{i=1}^N (C - \alpha_i - r_i) \zeta_i \\ \end{aligned}\]

原问题的对偶问题为:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}, \boldsymbol{r}}{\text{maximize}} & & \min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r} ) \\ & \text{subject to} & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \\ & & & r_i \ge 0, \; i = 1,2,\cdots,N \end{aligned}\]

下面化简 \(\min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r})\) ,分别对 \(\boldsymbol{w},b,\boldsymbol{\zeta}\) 求偏导数并令其为0,有:
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_1} = C - \alpha_i - r_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_2} = C - \alpha_i - r_i = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_N} = C - \alpha_i - r_i = 0 \\ \end{cases}\]
由上式,有:
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i y_i \boldsymbol{x_i} \\ \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ C - \alpha_i - r_i = 0 \\ \end{cases}\]

利用上面三式,化简广义拉格朗日函数,可得(具体过程和“硬间隔支持向量机”中化简对偶问题时非常类似):
\[\min\limits_{\boldsymbol{w},b,\boldsymbol{\zeta}} \mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r}) = - \dfrac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum\limits_{i=1}^{N} \alpha_i\]

所以,对偶问题等价于:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}, \boldsymbol{r}}{\text{maximize}} & & - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle + \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & C - \alpha_i - r_i = 0, \; i = 1,2,\cdots,N \\ & & & \alpha_i \ge 0, \; i = 1,2,\cdots,N \\ & & & r_i \ge 0, \; i = 1,2,\cdots,N \\ \end{aligned}\]

又可以写为:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

说明:这个对偶问题和“硬间隔支持向量机”的对偶问题非常相似,仅仅是多了一个约束条件 \(\alpha_i \le C\) 。

利用KKT最优化条件容易求解上面的对偶问题(求解它比直接求解原始优化问题容易得多,可以用 Sequential minimal optimization, SMO 算法快速地求解它)。
假设求得的对偶问题解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) ,下文将介绍如何利用对偶问题的解(即 \(\boldsymbol{\alpha}^{*}\) )得到原始优化问题的解。

5.2.2 利用对偶问题的解求原问题

原问题满足“强对偶定理”的条件,由“强对偶定理”知,对偶问题的解 \(\boldsymbol{\alpha}^{*}\) 就是原问题取得最小值时广义拉格朗日函数 \(\mathcal{L}(\boldsymbol{w},b, \boldsymbol{\zeta}, \boldsymbol{\alpha}, \boldsymbol{r})\) 中 \(\boldsymbol{\alpha}\) 的值。有了这个信息,原问题的KKT最优化条件迎刃而解,原始问题也迎刃而解。

先直接给出结论:
设 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\) 是对偶问题的解,如果存在 \(\boldsymbol{\alpha}^{*}\) 的一个分量 \(\alpha_j^*\) 满足条件 \(0 < \alpha_j^* < C\) ,我们找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ,则原始问题的解可以按下式求得( \(\boldsymbol{\zeta}\) 没有出现在“软间隔支持向量机”的决策函数中,所以不用求它):
\[\begin{cases} \boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} \\ b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{cases}\]

证明如下:
原问题的KKT条件:
\[\begin{cases} \dfrac{\partial \mathcal{L}}{\partial w^{(1)}} = w^{(1)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(1)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial w^{(2)}} = w^{(2)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(2)} = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial w^{(m)}} = w^{(m)} - \sum\limits_{i=1}^{N} \alpha_i^* y_i {x_i}^{(m)} = 0 \\ \dfrac{\partial \mathcal{L}}{\partial b} = - \sum\limits_{i=1}^{N} \alpha_i^* y_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_1} = C - \alpha_i^* - r_i = 0 \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_2} = C - \alpha_i^* - r_i = 0 \\ \quad \vdots \\ \dfrac{\partial \mathcal{L}}{\partial \zeta_N} = C - \alpha_i^* - r_i = 0 \\ y_i ( \boldsymbol{w} \cdot \boldsymbol{x_i} + b ) \ge 1 - \zeta_i, \quad i=1,2,\cdots,N \\ \zeta_i \ge 0, \quad i=1,2,\cdots,N \\ \alpha_i^* \ge 0, \; i = 1,2,\cdots,N \\ r_i \ge 0, \; i = 1,2,\cdots,N \\ \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ r_i \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

上式中, \(C\) 是用户设定的惩罚参数, \(\boldsymbol{\alpha}^{*}\) 是求解对偶问题时得到的解, \(\boldsymbol{x_i}, y_i\) 分别是训练数据及其分类标记,它们都是已知的。

由方程组中前几个式子有:
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]

方程组中最后两个式子可以写为:
\[\begin{cases} \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ (C - \alpha_i^*) \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

由上面式子可知,如果存在 \(\boldsymbol{\alpha}^{*}\) 的一个分量 \(\alpha_j^*\) 满足条件 \(0 < \alpha_j^* < C\) ,我们找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ,则 \(y_j (\langle \boldsymbol{w}, \boldsymbol{x_j} \rangle + b) - 1 = 0\) ,又由于 \(y_j^2 = 1\) ,所以有:
\[\begin{aligned} b & = y_j - \langle \boldsymbol{w}, \boldsymbol{x_j} \rangle \\ & = y_j - \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i} , \boldsymbol{x_j} \right \rangle \\ & = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle \end{aligned}\]

至此,原优化问题中的 \(\boldsymbol{w}, b\) 都已经得到。

5.2.3 软间隔支持向量机中的支持向量

由 \(\boldsymbol{w},b\) 的计算公式可知, \(\boldsymbol{w},b\) 只依赖于训练数据集中对应于 \(\alpha_i^{*} >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) ,而其他训练数据对 \(\boldsymbol{w},b\) 没有影响。 这些对应于 \(\alpha_i^* >0\) 的训练数据 \((\boldsymbol{x_i}, y_i)\) 就是 支持向量(Support Vector) ,如图 4 所示。

SVM_soft_margin_support_vector.png

Figure 4: 软间隔支持向量机中的支持向量(摘自:http://steve-cronin.blogspot.com/2010/09/modern-analytics-look-at-smo.html

上一节分析的KKT条件中有:
\[\begin{cases} \alpha_i^* \big (y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) - 1 + \zeta_i \big) = 0, \; i = 1,2,\cdots,N \\ (C - \alpha_i^*) \zeta_i = 0, \; i = 1,2,\cdots,N \\ \end{cases}\]

从而可以得到下表:

Table 1: 软间隔支持向量机中的支持向量
分情况讨论 此时会满足 支持向量的位置描述
\(0 < \alpha_i < C\) (此时一定有 \(\zeta_i = 0\) ) \(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) = 1\) 对应的支持向量恰好在正确分类那一侧的“间隔边界”上
\(\alpha_i = C, 0 < \zeta_i <1\) \(0 < y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) < 1\) 对应的支持向量在正确分类那一侧的“间隔边界”和“分离超平面”之间
\(\alpha_i = C, \zeta_i = 1\) \(\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b = 0\) 对应的支持向量在“分离超平面”上
\(\alpha_i = C, \zeta_i > 1\) \(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) < 0\) 对应的支持向量在“分离超平面”错误分类的那一侧
\(\alpha_i = 0\) \(y_i (\langle \boldsymbol{w}, \boldsymbol{x_i} \rangle + b) > 1\) 不是支持向量
\(\alpha_i > C\)   不会出现,因为和对偶问题的约束条件矛盾

5.2.4 软间隔支持向量机算法总结

前面已经完整介绍了线性支持向量机(软间隔支持向量机)的求解过程,现在总结如下。

设有近似线性可分的训练数据集 \(T = \{ (\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), \cdots, (\boldsymbol{x_N},y_N) \}\) ,其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{ -1 , +1 \}, i=1,2,\cdots, N\) ,求软间隔支持向量机决策函数。

求解过程如下:
第一步,选择一个惩罚参数 \(C=0\) ,构造并求解下面约束优化问题:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

求解它(最常用的算法是SMO算法),假设得到的解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\)

第二步,计算 \(\boldsymbol{w},b\) :
\[\boldsymbol{w} = \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}\]

选择满足条件 \(0 < \alpha_j^* < C\) 的 \(\boldsymbol{\alpha}^{*}\) 的分量 \(\alpha_j^*\) ,找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ,计算:
\[b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i \langle \boldsymbol{x_i} , \boldsymbol{x_j} \rangle\]

第三步,分类决策函数为:
\[\begin{aligned} f(\boldsymbol{x}) & = sign(\langle \boldsymbol{w}, \boldsymbol{x} \rangle + b) \\ & = sign \left( \left \langle \sum\limits_{i=1}^{N} \alpha_i^* y_i \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \\ & = sign \left( \sum\limits_{i=1}^{N} \alpha_i^* y_i \left \langle \boldsymbol{x_i}, \boldsymbol{x} \right \rangle + b \right) \end{aligned}\]

5.3 “非线性支持向量机”学习算法

“非线性支持向量机”是“软间隔支持向量机”应用核函数而得到的。其算法和“软间隔支持向量机”是一样的,只是把内积换为了核函数。

设有训练数据集(线性不可分) \(T = \{ (\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), \cdots, (\boldsymbol{x_N},y_N) \}\) ,其中 \(\boldsymbol{x_i} \in \mathbb{R}^n, y_i \in \{ -1 , +1 \}, i=1,2,\cdots, N\) ,求非线性支持向量机。

求解过程如下:
第一步,选择适当的核函数 \(K()\) 和一个惩罚参数 \(C=0\) ,构造并求解下面约束优化问题:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i {\color{red}{K(\boldsymbol{x_i}, \boldsymbol{x_j})}} - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

求解它(最常用的算法是SMO算法),假设得到的解为 \(\boldsymbol{\alpha}^{*} = (\alpha_1^* , \alpha_2^*, \cdots, \alpha_N^*)^{\mathsf{T}}\)

第二步,选择满足条件 \(0 < \alpha_j^* < C\) 的 \(\boldsymbol{\alpha}^{*}\) 的分量 \(\alpha_j^*\) ,找到对应的训练数据 \((\boldsymbol{x_j}, y_j)\) ,计算:
\[b = y_j - \sum\limits_{i=1}^{N} \alpha_i^* y_i {\color{red}{K(\boldsymbol{x_i}, \boldsymbol{x_j})}} \]

第三步,分类决策函数为:
\[f(\boldsymbol{x}) = sign \left( \sum\limits_{i=1}^{N} \alpha_i^* y_i {\color{red}{K(\boldsymbol{x_i}, \boldsymbol{x})}} + b \right)\]

5.4 Sequential Minimal Optimization(SMO)算法

有很多最优化算法可以求解软间隔支持向量机的对偶问题,但是当训练数据集的数据很多时,其效率很低,Microsoft Research的John C. Platt在1998年提出了一个快速求解方法——Sequential Minimal Optimization(SMO)算法。

SMO解决下面问题:
\[\begin{aligned} & \underset{\boldsymbol{\alpha}}{\text{minimize}} & & \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_i \langle \boldsymbol{x_i}, \boldsymbol{x_j} \rangle - \sum_{i=1}^{N} \alpha_i \\ & \text{subject to} & & \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\ & & & 0 \le \alpha_i \le C, \; i = 1,2,\cdots,N \end{aligned}\]

变量是拉格朗日乘子 \(\boldsymbol{\alpha}\) ,变量个数等于训练数据的总数 \(N\) 。
SMO算法是一种启发式算法。基本思路是:如果所有变量的解都满足KKT条件,那么这个最优化问题的解就得到了。 否则,选择两个变量,固定其它变量,针对这两个变量构建一个二次规划问题(这个子问题可以通过解析方法快速求解),这个二次规划问题关于这两个变量的解会更接近原始二次规划问题的解,因为这会使原始二次规则问题的目标函数值变得更小。 这样不断将原问题分解为子问题并求解子问题,从而达到求解原问题的目的。

详细过程略,可参考:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, by John C. Platt


Author: cig01

Created: <2015-06-27 Sat 00:00>

Last updated: <2017-11-22 Wed 22:45>

Creator: Emacs 25.3.1 (Org mode 9.1.2)