支持向量机

支持向量机

@(2016/08/02)

阅读笔记——周志华《机器学习》和李航《统计学习方法》

支持向量机（support vector machine）是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；通过核技巧（kernel trick），使得支持向量机可以完成非线性空间上的分类。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题。

支持向量机包含三种由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case）、线性支持向量机（linear support vector machine）及非线性支持向量机（non-linear support vector machine）。

在线性可分支持向量机模型中，通过硬间隔最大化（hard margin maximization）从线性可分的训练数据中学习该线性分类器；在线性支持向量机模型中，通过软间隔最大化（soft margin maximization）从近似线性可分的训练数据中学习该线性分类器；在非线性支持向量机中，通过核技巧和软间隔最大化可从线性不可分的数据中学习该非线性分类器。事实上，无论是哪种模型，最终都是在特征空间中进行支持向量机的学习，只不过在前两种模型中，假设输入空间和特征空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量，而非线性支持向量机是利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量的。

支持向量机的优点：
1） 可用于高维空间中的数据分类
2） 在数据维度高于样本个数时，仍然可以有效学习
3） 真正对支持向量机产生影响的是支持向量，通常支持向量只占一小部分，所以，其内存消耗低
4） 多功能性。可选的核有很多，既有常用的核函数，也可自行定制特殊的核函数。

1. 线性可分支持向量机

1.1 线性可分支持向量机——硬间隔最大化

给定训练集T=(x1,y1),(x2,y2),...,(xN,yN),y=−1 or +1,支持向量机就是从D中找出具有最大间隔的超平面，超平面可由下式表示：

w⋅x+b=0

则样本空间内任意点x到超平面的距离可写为：

r=|w⋅x+b|||w||

假设数据线性可分，则超平面能将训练样本正确分类，有：

{w⋅xi+b≥+1, yi=+1w⋅xi+b≤−1, yi=−1

其中 (xi,yi)∈T 。
距离超平面最近的几个训练样本点使以上两式的等号成立，它们就是 支持向量(support vector)，则两个异类支持向量到超平面的距离之和为

γ=2||w||

这里的 γ 就是该超平面分类边界的 几何间隔（geometric margin），则使得几何间隔最大且满足前述不等式，即

maxw,b2||w||s.t.yi(w⋅xi+b)≥1, i=1,2,...,N

也可写为

minw,b12||w||2s.t.yi(w⋅xi+b)≥1, i=1,2,...,N

这就是 支持向量机的基本型，是一个凸二次规划问题。
凸优化问题是指约束最优化问题

minwf(w)s.t.gi(w)≤0, i=1,2,...,khi(w)=0, i=1,2,...,l

其中目标函数 f(w) 和约束函数 gi(w) 都是 Rn 上的连续可微的凸函数，约束函数 hi(w) 是 Rn 上的仿射函数。
综上，可得出线性可分支持向量机学习算法——最大间隔法。

算法 1 （线性可分支持向量机学习算法——最大间隔法）
输入：线性可分训练数据集T=(x1,y1),(x2,y2),...,(xN,yN)，其中，xi∈X=Rn,yi∈Y,i=1,2,...,N；
输出：最大间隔分离超平面
(1) 构造并求解约束最优化问题：

minw,b 12||w||2

s.t. yi(w⋅xi+b)−1≥0, i=1,2,...,N

求得最优解 w∗,b∗ 。
(2) 由此得到分离超平面：

w∗⋅x+b∗=0

可证明线性可分训练数据集的最大间隔分离超平面是存在且唯一的。

1.2 学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数（kernel method）进而推广到非线性分类问题。
首先构建拉格朗日函数

L(w,b,α)=12||w||2−N∑i=1αiyi(w⋅xi+b)+N∑i=1αi

其中 α=(α1,α2,...,αN)T 为拉格朗日乘子向量。
原始问题可表示为该拉格朗日函数的极小极大问题，即

minw,bmaxαL(w,b,α)

由拉格朗日对偶性可得其 对偶问题为极大极小问题，即

maxαminw,bL(w,b,α)

为了求解对偶问题的最优解，需要先解决极小问题，然后求极大问题的解
(1) 求 minw,bL(w,b,α)
令 L 的偏导数为零，即

∇wL(w,b,α)=0∇bL(w,b,α)=0}⟹{w=∑Ni=1αiyixi∑Ni=1αiyi=0

将上述右式带入 L(w,b,α) 中，有

minw,bL(w,b,α)=−12N∑i=1N∑j=1αiαjyiyj(xi⋅xj)+N∑i=1αi

(2) 求 maxαminw,bL(w,b,α) 等价于求极小问题

minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αis.t.∑Ni=1αiyi=0αi≥0,i=1,2,...,N

考虑原始最优化问题和对偶最优化问题，原始问题满足 拉格朗日对偶性中的定理2的条件，所以存在 w∗,b∗,α∗ ，使 w∗,b∗ 是原始问题的解， α∗ 是对偶问题的解。
对线性可分训练数据集，假设对偶最优化问题对 α 的解为 α∗=(α∗1,α∗2,...,α∗N)T ，可以由 α∗ 求得原始问题的最优解 w∗,b∗ 。求解过程如下：
根据 拉格朗日对偶性中的定理3知，KKT条件成立，有

∇wL(w∗,b∗,α∗)=w∗−∑Ni=1α∗iyixi=0∇bL(w∗,b∗,α∗)=−∑Ni=1α∗iyi=0α∗i≥0, i=1,2,...,Nα∗i(yi(w∗⋅xi+b∗)−1)=0, i=1,2,...,Nyi(w∗⋅xi+b∗)−1≥0, i=1,2,...,N

可得

w∗=N∑i=1α∗iyixi

在 α 中至少有一个 αj>0 (反证法，如果不存在，那么 w∗=0 ，而 w∗=0 不是原始优化问题的最优解)，此时 yj(w∗⋅xj+b∗)−1=0 ,将上式代入该式中，有

yj(N∑i=1α∗iyi(xi⋅xj)+b∗)−1=0

注意到 y2j=1 ，可得

b∗=yj−N∑i=1α∗iyi(xi⋅xj)

至此， w∗ 和 b∗ 都求解出来了，可给出线性可分支持向量机学习算法

算法 2 （线性可分支持向量机学习算法）
输入：线性可分训练数据集T=(x1,y1),(x2,y2),...,(xN,yN)，其中，xi∈X=Rn,yi∈Y,i=1,2,...,N；
输出：分离超平面
(1) 构造并求解约束最优化问题

minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αis.t.∑Ni=1αiyi=0αi≥0,i=1,2,...,N

求得最优解 α∗=(α∗1,α∗2,...,α∗N)T 。
(2) 计算

w∗=N∑i=1α∗iyixi

并选择 α∗ 中的一个正分量 α∗j>0 ，计算

b∗=yj−N∑i=1α∗iyi(xi⋅xj)

(3) 求得分离超平面

w∗⋅x+b∗=0

从该算法中，可以看出，线性可分支持向量机中， w∗,b∗ 只依赖于训练数据中对应 α∗i>0 的样本点 (xi,yi) ，而其它样本点对 w∗ 和 b∗ 没有影响，这些实例点称为支持向量。

2. 线性支持向量机

2.1 线性支持向量机——软间隔最大化

通过修改原来的硬间隔最大化为软间隔最大化，从近似线性可分的训练数据中学习到一个线性分类器——线性支持向量机。
线性不可分意味着某些样本点(xi,yi)不能满足函数间隔大于1的约束条件，为此，我们为每一个样本点(xi,yi)引入一个松弛变量ξi，使得约束条件变为

yi(w∗⋅xi+b)≥1−ξi

同时，在目标函数中加入惩罚项，如下

12||w||2+CN∑i=1ξi

这里 C>0 称为惩罚参数。
线性不可分的线性支持向量机的学习问题变成了如下凸二次规划问题（ 原始问题）：

minw,b,ξ12||w||2+C∑Ni=1ξis.t.yi(w⋅xi+b)≥1−ξi, i=1,2,...,Nξi≥0,i=1,2,...,N

原始问题关于 (w,b,ξ) 的解是存在的，可以证明 w 的解是唯一的，但b的解不唯一， b 的解在一个区间中1。

2.2 学习的对偶算法

原始问题的拉格朗日函数为

L(w,b,ξ,α,μ)=12||w||2+CN∑i=1ξi−N∑i=1αi(yi(w⋅xi+b)+ξi−1)−N∑i=1μiξi

其中， αi≥0,μi≥0 。
与线性可分支持向量机学习的对偶算法一样，求解对偶问题最优解分为两步
(1)求 minw,b,ξL(w,b,ξ,α,μ)
令 L(w,b,ξ,α,μ) 的偏导数为0得

∇wL(w,b,ξ,α,μ)=0∇bL(w,b,ξ,α,μ)=0∇ξiL(w,b,ξ,α,μ)=0}⟹{w=∑Ni=1αiyixi∑Ni=1αiyi=0C=αi+μi,i=1,2,...,N

将计算偏导的结果代入拉格朗日函数中可得

minw,b,ξL(w,b,ξ,α,μ)=−12N∑i=1N∑j=1αiαjyiyj(xi⋅xj)+N∑i=1αi

(2) 求 maxα,μminw,b,ξL(w,b,ξ,α,μ) ，可得对偶问题

minα,μ12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αis.t.∑Ni=1αiyi=0C−αi−μi=0, i=1,2,...,Nαi≥0, i=1,2,...,Nμi≥0, i=1,2,...,N

利用等式消去 μi 对偶问题变为

minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αis.t.∑Ni=1αiyi=00≤αi≤C, i=1,2,...,N

设 α∗=(α∗1,α∗2,...,α∗N)T 是对偶问题的一个解，若存在 α∗ 的一个分量 α∗j,0<α∗j<C ，且原始问题是凸二次规划问题，解 (w∗,b∗) 满足KKT条件，即得

∇wL(w∗,b∗,ξ∗,α∗,μ∗)=w∗−∑Ni=1α∗iyixi=0∇bL(w∗,b∗,ξ∗,α∗,μ∗)=−∑Ni=1α∗iyi=0∇ξL(w∗,b∗,ξ∗,α∗,μ∗)=C−α∗−μ∗=0α∗i(yi(w∗⋅xi+b∗)−1+ξ∗i)=0, i=1,2,...,Nμ∗iξ∗i=0, i=1,2,...,Nyi(w∗⋅xi+b∗)−1+ξ∗i≥0, i=1,2,...,Nξ∗i≥0, i=1,2,...,Nα∗i≥0, i=1,2,...,Nμ∗i≥0, i=1,2,...,N

由于 0<α∗j<C ，所以 ξj=0 ,则 yj(w∗⋅xj+b∗)−1=0 ，联合第一个公式得

w∗=∑Ni=1α∗iyixib∗=yj−∑Ni=1α∗iyi(xi⋅xj)

至此， w∗ 和 b∗ 都求解出来了，可给出线性支持向量机学习算法

算法 3 （线性支持向量机学习算法）
输入：训练数据集T=(x1,y1),(x2,y2),...,(xN,yN)，其中，xi∈X=Rn,yi∈Y,i=1,2,...,N；
输出：分离超平面
(1) 选择惩罚参数C>0，构造并求解凸二次规划问题

minα12∑Ni=1∑Nj=1αiαjyiyj(xi⋅xj)−∑Ni=1αis.t.∑Ni=1αiyi=00≤αi≤C, i=1,2,...,N

(2)计算

w∗=N∑i=1α∗iyixi

选择 α∗ 的一个分量 α∗j 适合条件 0<α∗j<C ，计算

b∗=yj−N∑i=1α∗iyi(xi⋅xj)

(3)求得分离超平面

w∗⋅x+b∗=0

由于原始问题对 b 的解并不唯一2，所以实际计算时可以取在所有符合条件的样本点上的平均值。

2.3 合页损失函数

线性支持向量机的学习还有另外一种解释，就是最小化以下目标函数：

N∑i=1[1−yi(w⋅xi+b)]++λ||w||2

目标函数的第一项是经验损失或者经验风险，函数

L(y(w⋅x+b))=[1−y(w⋅x+b)]+

称为 合页损失函数(hinge loss function)。下标 “+”表示以下取正值的函数。

[z]+={z,z>00,z≤0

因此线性支持向量机的最优化问题等价于

minw,b N∑i=1[1−yi(w⋅x+b)]++λ||x||2

3. 非线性支持向量机

在真实的分类问题中，非线性可分问题经常遇到，也可以说，线性可分和线性不可分问题是非线性可分问题的特殊情况。在输入空间中，非线性可分问题可用超曲面将正负例正确分开，不同问题的超曲面千差万别，很难找到一个合适的等式来描述它。非线性支持向量机所采用的方法是使用一个非线性变换将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题，总而言之，线性分类方法求解非线性分类问题可分为两步：
(1) 使用一个变换将原空间的数据映射到新空间；
(2) 在新空间里用线性分类学习方法从训练数据中学习分类模型。
这种方法就称为核技巧。

核技巧应用到支持向量机，其基本想法是通过一个非线性变换将输入空间（欧式空间Rn或离散集合）对应于一个特征空间（希尔伯特空间H），使得在输入空间Rn中的超曲面模型对应于特征空间H中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。
核函数：设T是输入空间（欧式空间Rn的子集或离散集合），又设H为特征空间（希尔伯特空间），如果存在一个从T到H的映射

ϕ(x):T→H

使得对所有 x,z∈T ，核函数 K(x,z) 满足条件

K(x,z)=ϕ(x)⋅ϕ(z)

则称 K(x,z) 为核函数， ϕ(x) 为映射函数，式中 ϕ(x)⋅ϕ(z) 为 ϕ(x) 和 ϕ(z) 的内积。

结合线性支持向量机算法的b∗,w∗公式来看，核技巧的想法是，在学习和预测中只定义核函数K(x,z)，而不显示地定义映射函数ϕ。这里不对核函数进行进一步的介绍，直接给出非线性支持向量机的算法。

算法4（非线性支持向量机学习算法）
输入：训练数据集T=(x1,y1),(x2,y2),...,(xN,yN)，其中，xi∈X=Rn,yi∈Y,i=1,2,...,N；
输出：分类决策函数
(1) 选择合适的核函数K(x,z)和惩罚参数C>0，构造并求解凸二次规划问题

minα12∑Ni=1∑Nj=1αiαjyiyjK(xi,xj)−∑Ni=1αis.t.∑Ni=1αiyi=00≤αi≤C, i=1,2,...,N

(2)选择 α∗ 的一个分量 α∗j 适合条件 0<α∗j<C ，计算

b∗=yj−N∑i=1α∗iyiK(xi,xj)

(3)求得分类决策函数

f=sign(N∑i=1αiyiK(x,xi)+b∗)

这些算法通常需要借助序列最小优化算法(Sequential minimal optimization, SMO)实现，后续将给出该算法的介绍。

---

1. 邓乃扬. 数据挖掘中的新方法[M]. 科学出版社, 2004. ↩
2. 邓乃扬. 数据挖掘中的新方法[M]. 科学出版社, 2004. ↩