支持向量机——间隔最大法

Posted on |

一般来说，机器学习方法由三个要素组成：模型、 策略、算法。

对于监督算法来说，其中：

  • 模型指的是所要学习的条件概率分布或决策函数；
  • 策略指的是学习模信的准测或标准，即将从假设空间 FF 中确定最优模型 ff 转化为具体最优化问题的策略；
  • 算法指的是学习模型的具体计算方法，通常为求解最优化模型的算法。

对于支持向量机（support vector machine, SVM）来说，它的基本模型是定义在特征空间（不是输入空间）上的间隔最大的线性分类器；学习策略是几何间隔最大化，将求解最优模型转化为求解一个凸二次规划问题；学习算法是求解凸二次规划问题的最优化算法，通常使用的是序列最小最优化算法（SMO）.

支持向量机分类

按照模型的复杂程度，SVM可以分为：线性可分支持向量机、线性支持向量机和非线性支持向量机。

  • 线性可分支持向量机是线性支持向量机的特殊情况，对应的是训练数据线性可分的情况，学习策略为硬间隔最大化；
  • 当训练数据近似线性可分时，学习策略为软间隔最大化，可以理解为将硬间隔最大化的最优化问题的约束条件加上松弛；
  • 当训练数据线性不可分时，通过使用核技巧，将输入空间映射到特征中间中，在特征空间上使用软间隔最大化学习策略，学习非线性支持向量机。

因此，理解支持向量机需要从几个方面入手，分别为: 最大间隔法及其对偶问题以及核技巧。

最大间隔法

线性可分支持向量机的定义为：
给定先行可分训练数据集，通过间隔最大或等价地求解相应的凸二次规划问题学习到的分离超平面为
w∗⋅x+b∗=0
w∗·x+b∗=0
以及相应的分类决策函数
f(x)=sign(w∗⋅x+b∗)
f(x)=sign(w∗·x+b∗)
称为线性可分支持向量机。
线性可分支持向量机对应着将训练数据中正负例正确划分且间隔最大的超平面。

函数间隔

函数间隔的定义为：
对于给定的训练数据集 TT 和超平面 (w,b)(w,b) ，定义超平面 (w,b)(w,b) 关于样本点 (xi,yi)(xi,yi) 的函数间隔为
γ^i=yi(w⋅xi+b)
γ^i=yi(w·xi+b)
定义超平面 (w,b)(w,b) 关于训练数据集 TT 的函数间隔为超平面 (w,b)(w,b) 关于 TT 中所有样本点 (xi,yi)(xi,yi) 的函数间隔的最小值，即
γ^=mini=1,…,Nγ^i
γ^=mini=1,…,N⁡γ^i

在 γ^iγ^i 的表达式中，|w⋅x+b||w·x+b| 能够相对地表示点 xx 距离超平面的远近，而 y(w⋅x+b)y(w·x+b) 的符号可以用来表示点 xx 是否被该超平面正确分类，因此 γ^iγ^i 既可以表示分类的正确性，也可以表示分类的确定度。

几何间隔

对于给定的训练数据集 TT 和超平面 (w,b)(w,b)，定义超平面 (w,b)(w,b) 关于样本点 (xi,yi)(xi,yi) 的几何间隔为
γi=yi(w||w||⋅xi+b||w||)
γi=yi(w||w||·xi+b||w||)
同样地，超平面 (w,b)(w,b) 关于训练数据集 TT 的几何间隔为超平面 (w,b)(w,b) 关于 TT 中所有样本点 (xi,yi)(xi,yi) 的几何间隔的最小值，即
γ=mini=1,…,Nγi
γ=mini=1,…,N⁡γi

几何间隔的定义表明，超平面 (w,b)(w,b) 关于样本点 (xi,yi)(xi,yi) 的几何间隔是实例点到超平面的带符号的距离，符号表示样本点 (xi,yi)(xi,yi) 是否被超平面 (w,b)(w,b) 正确分类。

间隔最大化

按照几何间隔的定义，对训练数据集找到几何间隔最大的分类超平面意味着以充分大的确信度对训练数据进行分类。这样的超平面对未知的新实例也有很好的分类预测能力，具有结构风险小的特点。
求解几何间隔最大的分离超平面可以转化为以下的最优化问题：
maxw,bγ
maxw,b⁡γ
s.t.yi(w||w||⋅xi+b||w||)≥γ,i=1,…N
s.t.yi(w||w||·xi+b||w||)≥γ,i=1,…N

该问题可以改写为
maxw,bγ^||w||
maxw,b⁡γ^||w||
s.t.yi(w⋅xi+b)≥γ^,i=1,…N
s.t.yi(w·xi+b)≥γ^,i=1,…N

由于函数间隔 γ^γ^ 的取值对最优化问题的解没有影响，可以取 γ^=1γ^=1 来进一步简化上述优化问题：
minw,b12||w||2
minw,b⁡12||w||2
s.t.yi(w⋅xi+b)−1≥0,i=1,…N
s.t.yi(w·xi+b)−1≥0,i=1,…N

在目标函数中对 ||w||||w|| 乘以系数 1212 是出于后面推导对偶问题求解梯度时方便考虑。
到此，求解线性可分支持向量机的问题转换为了上式表达的凸二次规划问题。

最大间隔法的对偶问题

为了方便上述最优化问题的求解，将上述最优化问题作为原始最优化问题，通过求解其对偶问题得到原始问题的最优解，这样做同时还可以自然地引入核函数，从而将算法推广到非线性的分类问题。
对上述原始最优化问题中的每一个不等式约束引入拉格朗日乘子 αi≥0,i=1,2,…Nαi≥0,i=1,2,…N，构建拉格朗日函数：
L(w,b,α)=12||w||2−∑i=1Nαiyi(w⋅xi+b)+∑i=1Nαi
L(w,b,α)=12||w||2−∑i=1Nαiyi(w·xi+b)+∑i=1Nαi

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
maxaminw,bL(w,b,α)
maxa⁡minw,b⁡L(w,b,α)

在求解这个对偶问题的时候，需要先求 L(w,b,α)L(w,b,α) 对 w,bw,b 的极小，再求对 αα 的极大。此处省略对对偶问题的求解推导过程，得到的与之等价的对偶最优化问题为：
minα12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi
minα⁡12∑i=1N∑j=1Nαiαjyiyj(xi·xj)−∑i=1Nαi
s.t.∑i=1Nαiyi=0
s.t.∑i=1Nαiyi=0
αi≥0,i=1,2,…N
αi≥0,i=1,2,…N

求出该对偶最优化问题对 αα 的解 α∗α∗ 后，可以由 α∗α∗ 求得原始最优化问题对 (w,b)(w,b) 的解 w∗,b∗w∗,b∗：
w∗=∑i=1Nα∗yixi
w∗=∑i=1Nα∗yixi
b∗=yi−∑i=1Nα∗yi(xi⋅xj)