SVM 支持向量机(上):基本型

支持向量和 SMO 算法

Posted by Xiaosheng on April 16, 2017

支持向量机 (support vector machines, SVM) 是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器。

1. 间隔与支持向量

给定训练样本集 $D = {(\boldsymbol{x}^{(1)},y^{(1)}),(\boldsymbol{x}^{(2)},y^{(2)}),…,(\boldsymbol{x}^{(m)},y^{(m)}}$,$y^{(i)} \in {-1,+1}$,分类学习最基本的想法就是基于训练集 $D$ 在样本空间中找到一个划分超平面,将不同类别的样本分开。但能将训练样本分开的划分超平面可能有很多,支持向量机通过间隔最大化求得唯一的最优划分超平面。

在样本空间中,划分超平面可通过如下线性方程来描述:

其中 $\boldsymbol{w} = (w_1;w_2;…,w_d)$ 为法向量,决定了超平面的方向;$b$ 为位移项,决定了超平面与原点之间的距离。显然,划分超平面可被法向量 $\boldsymbol{w}$ 和位移 $b$ 确定,下面我们将其记为 $(\boldsymbol{w},b)$。样本空间中任意点 $\boldsymbol{x}$ 到超平面 $(\boldsymbol{w},b)$ 的距离可写为

假设超平面 $(\boldsymbol{w},b)$ 能将训练样本正确分类,即对于 $(\boldsymbol{x}^{(i)},y^{(i)}) \in D$,若 $y^{(i)} = +1$,则有 $\boldsymbol{w}^\top\boldsymbol{x}^{(i)} + b > 0$;若 $y^{(i)} = -1$,则有 $\boldsymbol{w}^\top\boldsymbol{x}^{(i)} + b < 0$。令

注:若超平面 $(\boldsymbol{w}’,b’)$ 能将训练样本正确分类,则总存在缩放变换使得 $(1.3)$ 成立。

训练样本集中与超平面距离最近的训练样本点称为支持向量 (support vector)。如下图所示,支持向量使 $(1.3)$ 的等号成立,即

  • 对于 $y^{(i)} = +1$ 的正例点,支持向量在超平面 $H_1:\boldsymbol{w}^\top\boldsymbol{x} + b = 1$ 上;
  • 对于 $y^{(i)} = -1$ 的负例点,支持向量在超平面 $H_2:\boldsymbol{w}^\top\boldsymbol{x} + b = -1$ 上。

1

可以看到 $H_1$ 和 $H_2$ 平行,划分超平面与它们平行且位于它们中央。其中两个异类支持向量到超平面的距离之和,或者说 $H_1$ 与 $H_2$ 之间的距离称为间隔 (margin),为

欲找到具有“最大间隔” (maximum margin) 的划分超平面,也就是要找到能满足 $(1.3)$ 中约束的参数 $\boldsymbol{w}$ 和 $b$,使得 $\gamma$ 最大,即

显然,为了最大化间隔,仅需最大化 $\frac{1}{\Vert \boldsymbol{w} \Vert}$,这等价于最小化 $\Vert \boldsymbol{w} \Vert^2$。于是,式 $(1.5)$ 可重写为

这就是支持向量机 (Support Vector Machine, SVM) 的基本型。

  1. 间隔貌似仅与 $\boldsymbol{w}$ 有关,但事实上 $b$ 通过约束隐式地影响着 $\boldsymbol{w}$ 的取值,进而对间隔产生影响。
  2. 在决定划分超平面时只有支持向量起作用,而其他样本点并不起作用。如果移动支持向量将改变所求的解,而移动其他样本点,甚至去掉这些点,解都不会改变。由于支持向量在确定划分超平面中起着确定性作用,因此将这种分类模型称为支持向量机。

2. 学习算法

2.1 对偶问题

我们希望求解 $(1.6)$ 来得到大间隔划分超平面所对应的模型

对 $(1.6)$ 使用拉格朗日乘子法可得到其“对偶问题”。具体来说,对 $(1.6)$ 的每条约束添加拉格朗日乘子 $\alpha_i \ge 0$,则该问题的拉格朗日函数可以写为

根据拉格朗日对偶性,原始问题 $(1.6)$ 的对偶问题是:

所以需要先求 $L(\boldsymbol{w},b,\boldsymbol{\alpha})$ 对 $\boldsymbol{w},b$ 的极小,再求对 $\boldsymbol{\alpha}$ 的极大。令 $L(\boldsymbol{w},b,\boldsymbol{\alpha})$ 对 $\boldsymbol{w}$ 和 $b$ 的偏导为零可得

将 $(2.4)$ 代入 $(2.2)$,即可将 $L(\boldsymbol{w},b,\boldsymbol{\alpha})$ 中的 $\boldsymbol{w}$ 和 $b$ 消去,

再考虑 $(2.5)$ 的约束,$(2.3)$ 就可以化为

将 $(2.6)$ 的目标函数由求极大转换成求极小,就得到下面与之等价的对偶最优化问题:

解出 $\boldsymbol{\alpha}$ 后,求出 $\boldsymbol{w}$ 和 $b$ 即可得到模型

注意到 $(1.6)$ 式中有不等式约束,因此上述过程需要满足 $\text{KKT}$ (Karush-Kuhn-Tucker) 条件,即要求:

于是,对任意训练样本 $(\boldsymbol{x}^{(i)}, y^{(i)})$,总有 $\alpha_i = 0$ 或 $y^{(i)}f(\boldsymbol{x}^{(i)}) = 1$。

  • 若 $\alpha_i= 0$,则该样本将不会在 $(2.8)$ 的求和中出现,也就不会对 $f(\boldsymbol{x})$ 有任何影响;
  • 若 $\alpha_i > 0 $,则必有 $y^{(i)}f(\boldsymbol{x}^{(i)}) = 1$,所对应的样本点位于最大间隔边界上,是一个支持向量。

这证明了我们之前的描述,即:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关。

2.2 SMO 算法

式 $(2.7)$ 是一个二次规划问题,可使用通用的二次规划算法来求解;然而,该问题的规模正比于训练样本数,这会在实际任务中造成很大的开销。为了避开这个障碍,人们通过利用问题本身的特性,提出了很多高效的算法,$\text{SMO}$ (Sequential Minimal Optimization) 是其中一个著名的代表。

SMO 的基本思想是先固定 $\alpha_i$ 之外的所有参数,然后求 $\alpha_i$ 上的极值。由于存在约束 $\sum_{i=1}^m \alpha_iy^{(i)} = 0$,若固定 $\alpha_i$ 之外的其他变量,则 $\alpha_i$ 可由其他变量导出。于是,SMO 每次选择两个变量 $\alpha_i$ 和 $\alpha_j$,并固定其他参数。这样,在参数初始化后,SMO 不断执行如下两个步骤直至收敛:

  • 选取一对需更新的变量 $\alpha_i$ 和 $\alpha_j$;
  • 固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数,求解 $(2.7)$ 获得更新后的 $\alpha_i$ 和 $\alpha_j$。

注意到只需选取的 $\alpha_i$ 和 $\alpha_j$ 中有一个不满足 $\text{KKT}$ 条件 $(2.9)$,目标函数就会在迭代后减小。直观来看,$\text{KKT}$ 条件违背的程度越大,则变量更新后可能导致的目标函数值减幅越大。于是,SMO 先选取违背 $\text{KKT}$ 条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量,但由于比较各变量所对应的目标函数值减幅的复杂度过高,因此 SMO 采用了一个启发式:使选取的两变量所对应样本之间的间隔最大。

一种直观的解释是,这样的两个变量有很大的差别,与对两个相似的变量进行更新相比,对它们进行更新会带给目标函数值更大的变化。

SMO 算法之所以高效,恰由于在固定其他参数后,仅优化两个参数的过程能做到非常高效。具体来说,仅考虑 $\alpha_i$ 和 $\alpha_j$ 时,$(2.7)$ 中的约束可重写为

其中

是使 $\sum_{i=1}^m\alpha_iy^{(i)} = 0$ 成立的常数。用

消去 $(2.7)$ 中的变量 $\alpha_j$,则得到一个关于 $\alpha_i$ 的单变量二次规划问题,仅有的约束是 $\alpha_i \ge 0$。这样的二次规划问题具有闭式解,于是不必调用数值优化算法即可高效地计算出更新后的 $\alpha_i$ 和 $\alpha_j$。

最后确定偏置项 $b$。注意到对任意支持向量 $(\boldsymbol{x}^{(s)},y^{(s)})$ 都有 $y_sf(\boldsymbol{x}_s)=1$,即

其中 $S = {i \mid \alpha_i > 0, i = 1,2,…,m}$ 为所有支持向量的下标集。理论上,可选取任意支持向量并通过求解 $(2.13)$ 获得 $b$,但现实任务中常采用一种更鲁棒的做法:使用所有支持向量求解的平均值。

参考

李航《统计学习方法》
周志华《机器学习》