[数据结构与算法]统计学习：线性可分支持向量机(SVM)

1. 模型
1.1 超平面
我们称下面形式的集合为超平面

{x|aTx?b=0}(1)
其中a∈Rn且a≠0,x∈Rn,b∈R。解析地看，超平面是关于x的非平凡线性方程的解空间（因此是一个仿射集，仿射集和凸集的概念参考Stephen Boyd的《凸优化》）从几何上看，它的的法向量为a，而常数b∈R决定了这个超平面从原点的偏移。这如何得到的呢？这是因为，若我们由法向量a和超平面上一点x0确定超平面，则对超平面上任意一点x，我们可以得到x?x0一定垂直于a，则超平面的集合便可以表示为

{x|aT(x?x0)=0}(2)
R2中的几何化的解释如下图所示，其中深色箭头表示x?x0：
线性可分支持向量机学习算法
一个超平面将Rn划分为两个半空间，（闭的）半空间是具有下列形式的集合：

{x|aTx?b?0}(3)
即（非平凡）的线性不等式的解空间，其中a≠0。半空间是凸的，但不是仿射的。集合{x|aTx?b<b}是半空间{x|aTx?b?0}的内部，称为开半空间。

1.2 线性可分支持向量机
我们定义样本空间为X?Rn，输出空间为Y={+1,?1}。X为输入空间上的随机向量，其取值为x，满足x∈X；Y为输出空间上的随机变量，设其取值为y，满足y∈Y。我们将容量为m的训练样本表示为:

D={{x(1),y(1)},{x(2),y(2)},...,{x(m),y(m)}}(4)
当y(i)=+1时，我们称x(i)为正例；当y(i)=?1时，称xi为负例。(x(i),y(i))称为样本点。
如果我们假设训练数据集是线性可分的，则我们可以在特征空间中找到一个分离超平面{x|wTx+b=0}，将特征空间划分为{x|wTx+b>0}和{x|wTx+b<0}两个开半空间(显然法向量w指
向的一侧为正，另一侧为负)，且为正的一侧对应负类，为负的一侧对应负类。

如果训练集线性可分，则我们存在无穷多个分离超平面将两类样本分开。如果我们采用感知机的误分类最小的训练策略(也就是仅仅保证分类的正确性)，那么我们将求得无穷多个解。我们接下来定义的线性可分支持向量机将利用“间隔最大化”求解最优分离超平面（即能将两组数据正确划分且间隔最大的超平面，我们在“学习策略”板块中将详述这一概念），这时解是唯一的。

形式化地说，给定线性可分的数据集，通过间隔最大化策略学习得到的分离超平面为

{x|w?Tx+b?=0}(5)
以及相应的分类决策函数

f(x)=sign(w?Tx+b?)(6)
称为线性可分支持向量机。

2. 学习策略
我们前面提到最好的超平面需要能将两组数据正确划分且间隔最大，那么间隔最大如何形式化地定义呢？我们先来看函数间隔和几何间隔的概念。

2.1. 函数间隔和几何间隔
直观地看，一个点距离超平面的远近可以表示则我们对它进行分类的确信程度。一个点距离超平面越远，则我们对它的分类则越有把握。我们给定超平面{x|wTx+b=0}和一个实例点x(i)，可以发现|wTx(i)+b|可以相对地表示点x(i)举例超平面的远近，而wTx(i)+b的符号与类标记y(i)是否一致可以反映分类是否正确。据此，我们用y(i)(w?x(i)+b)来对分类的确信度和正确性进行综合表示。y(i)(wTx(i)+b)为正数，表示分类器能够正确完成分类功能，且y(i)(wTx(i)+b)越大，则分类器越好；y(i)(wTx(i)+b)为负数，就表示分类器连正确分类功能都不能完成了，负得越多，表示错的越离谱(HaHa，应该可以这么理解叭)。 于是，我们给出下列函数间隔的定义。

函数间隔 对于给定的数据集D和超平面{x|wTx+b=0}，定义该超平面关于数据集中样本点(x(i),y(i))的函数间隔为

γ^(i)=y(i)(wTx(i)+b)(7)
定义该超平面关于训练集D的函数间隔为该超平面关于D中所有样本点函数间隔的最小值，即

γ^=mini=1,...,mγ^(i)(8)
如果单单根据函数间隔的大小来选顶最佳超平面，那还不够准确。因为我们知道，令超平面的法向量w经过缩放变换为λw，超平面的截距项缩放变换为λb，超平面是本身并没有改变的，但函数间隔γ^(i)却变为λγ^(i)，这显然与事实不符。因此，我们需要对超平面的法向量加一些约束，如规范化，令||w||=1，使得间隔是确定的。这时的函数间隔就是我们后面所提到的几何间隔的一种特殊情况。

我们定义实例(x(i),y(i))到超平面{x|wTx+b=0}的带符号距离为wTx(i)+b||w||（在法向量那一侧则为正），我们用这个做为来做为分类的确信度。类似地，我们我们用y(i)wTx(i)+b||w||来对分类的确信度和正确性进行综合表示。于是，我们给出下列几何间隔的定义。

几何间隔 对于给定的数据集D和超平面{x|wTx+b=0}，定义该超平面关于数据集中样本点(x(i),y(i))的几何间隔为

γ(i)=y(i)wTx(i)+b||w||(9)
定义该超平面关于训练集D的函数间隔为该超平面关于D中所有样本点函数间隔的最小值，即

γ=mini=1,...,mγ(i)(10)
对比一下式(7)、(8)和式(9)、(10)我们知道，函数间隔和集合间隔存在下列关系γ(i)=γ^(i)||w||，γ=γ^||w||。可以看到，若||w||=1，则函数间隔等于几何间隔，如果w和b都进行大小为λ的缩放变换，函数间隔也会缩放λ，但几何间隔不变。

2.2 间隔最大化
要想使分离超平面更可靠，我们只需要保证该超平面关于D中所有样本点几何间隔的最小值γ尽量大即可（这样自然就能保证所有点的几何间隔尽量大)，我们称此为间隔最大化策略（或称为硬间隔最大化，和后面训练集近似线性可分的软间隔最大化相对应）。

可以知道，满足间隔最大化的超平面是唯一的，它能够对所有训练数据有足够大的确信度分类，也就是说不仅能够对实例点进行分类，而且对于所有实例点能够有足够大的确信度分类，这样的超平面的未知的测试实例有很好的分类预测能力。我们将该问题表述为以下带约束优化问题：

maxw,bγs.t.y(i)wTx(i)+b||w||≥γ(i=1,2,...,m)(11)
根据γ=γ^||w||，我们可以将优化问题(11)写作：

maxw,bγ^||w||s.t.y(i)(wTx(i)+b)≥γ^(i=1,2,...,m)(12)
我们将w和b缩放变换为λw和λb，则函数间隔γ^变为λγ^。我们法线函数间隔的这一改变对(11)中最优化问题的约束目标函数和不等式约束都没有影响,也就是说它产生了一个等价的最优化问题。

这样，就可以取γ^=1。将γ^=1代入上面的最优化问题，相当于最大化1||w||。不过这样目标函数非凸，一般较难求解，为了将其转换为凸优化问题，我们将原本的优化目标函数等价转换为最小化12||w||2，这样我们就将线性可分支持向量机的学习策略转换为了一个(凸)二次规划问题:

maxw,b12||w||2s.t.y(i)(wTx(i)+b)?1≥0(i=1,2,...,m)(13)
该形式称为线性可分支持向量机的标准型。

附:

这里提一下凸优化问题和二次规划问题的概念。凸优化问题定义如下

minxf0(x)s.t.fi(x)≤0(i=1,2,...,m)hi(x)=0(i=1,2,...,p)(14)
其中目标函数f0(x)和约束函数fi(x)都为凸函数，且等式约束函数hi(x)为仿射函数(也就是说，hi(x)可以写成hi(x)=aTx+b的形式。

特别地，当凸优化问题的目标函数f0(x)是（凸）二次型并且约束函数fi(x)为仿射时，该问题称为二次规划(QP)。二次规划可以表述为：

minx(12)xTPx+qTx+rs.t.fi(x)≤0(i=1,2,...,m)hi(x)=0(i=1,2,...,p)(15)
其中P是对称正定矩阵(在式(13)中，P即是单位阵I)，约束函数fi(x)和等式约束函数hi(x)都是仿射函数。

接下来我们会介绍该凸二次规划问题的求解算法。

三. 算法
接下来我们推导求解线性可分支持向量机的高效算法。（真的是万般皆推导，难的是算法的推导过程，算法实现反而很简单）

直接求解式(13)计算复杂度过高，而凸优化理论中告诉了我们许多可以高效求解(13)问题的理论。我们将问题(13)的形式做为原始问题(primal problem)。应用拉格朗日对偶性。通过求解对偶问题(dual problem)同样得到原始问题的最优解，而且求解会更加高效。问题求解可分两步走。
第一步：推导原始问题的对偶形式并求得对偶问题的最优解α?。

我们引入拉格朗日乘子向量α=(α1,α2,...,αm)T，每个不等式约束对应一个拉格朗日乘子αi≥0,i=1,2,...,m，我们以此定义拉格朗日函数：

L(w,b,α)=12||w||2+(?∑i=1mαiy(i)(wTx(i)+b))+∑i=1mαi(16)
（注意，标准凸优化问题式(14)的约束项是小于等于，我们的式(13)是大于等于，在写出拉格朗日函数前，需要对原来的约束不等式两边同乘?1）

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

maxαminw,bL(w,b,α)(17)
我们将问题拆解为先对w、b求极小，再求对α求极大。

(1) 首先，我们求g(α)=minw,bL(w,b,α)。由凸函数L(w,b,α)极值满足的一阶必要条件有

?wL(w,b,α)=w?∑i=1mαiy(i)x(i)=0?bL(w,b,α)=?∑i=1mαiy(i)=0(18)
可得：

w=∑i=1mαiy(i)x(i)∑i=1mαiy(i)=0(19)
关于w的等式是一个对w的显式替换，而第二个等式是对式L(w,b,α)的一个约束，我们先将式(19)中的等式一代入式(16)的L(w,b,α)中有

L(w,b,α)=12∑i=1m∑j=1mαiαjy(i)y(j)?x(i),x(j)??∑i=1m∑j=1mαiαjy(i)y(j)?x(i),x(j)??∑i=1mαiy(i)b+∑i=1mαi(20)
虽然式(19)没有显式的关于b的等式可供代入，但我们发现将第二个等式∑mi=1αiy(i)=0带入后就可以将b的那项消掉，得到原问题的拉格朗日对偶函数(或对偶函数)为

g(α)=minw,bL(w,b,α)=?12∑i=1m∑j=1mαiαjy(i)y(j)?x(i),x(j)?+∑i=1mαi
(2) 接下来我们再求maxαg(α)，这也就是我们需要求的对偶问题。

maxα?12∑i=1m∑j=1mαiαjy(i)y(j)?x(i),x(j)?+∑i=1mαis.t.∑i=1mαiy(i)=0αi≥0,i,2,...,m(22)
可以看出，式(22)这个对偶问题只用求解α系数而α系数只有支持向量才非0，其他全为0，这样的话求解对偶问题的计算就会更加高效。至于求解式(22)算法的具体实现(一般采用内点法)可以调用凸优化库Gurobi，在此不再详述。
解式(22)后我们得到α的解α?=(α?1,α?2,...,α?m)T。

第二步：由对偶问题的最优解α?求得原始问题式(13)的最优解w?,b?

如果α?=(α?1,α?2,...,α?m)T是对偶最优化问题的解，我们将αi>0对应的实例点集合被称为支持向量，我们设U={αi|αi>0}，我们U从中随机采一个αs，对应的样本为(x(s),y(s))，可按下式求得原始最优化问题(13)的解w?,b?。

w?=∑i=1mα?iy(i)x(i)b?=y(s)?∑i=1mα?iy(i)?x(s),x(i)?(23)
附：

式(23)可根据KKT条件推导而得。KKT条件如下：

\nabla_{\bm{w}}L(\bm{w}^{*}, b^{*}, \bm{\alpha}^{*}) = \bm{w}^{*} - \sum_{i=1}^{m}\alpha_{i}y^{(i)}\bm{x}^{(i)} = 0 \\
\nabla_{b}L(\bm{w}^{*}, b^{*}, \bm{\alpha}^{*}) = ?- \sum_{i=1}^{m}\alpha_iy^{(i)} = 0 \\
\alpha_{i}^{*}[y^{(i)}(\bm{w^{*}}^T \bm{x}^{(i)}+b^{*}) - 1] = 0, \quad i=1,2,...,m \\
y^{(i)}(\bm{w^{*}}^T \bm{x}^{(i)}+b^{*}) - 1 \geq 0, \quad i=1, 2,..., m \\
a_i^* \geq 0
\tag{24}
由式(24)中第一个等式，我们可得：

w?=∑i=1mαiy(i)x(i)(25)
其中至少有一个α?i>0(用反证法，假设αi全为0，则w?为0，而易得w为0不是原始问题(13)的最优解，产生矛盾，故假设不符)。

式(24)中第三个等式称为KKT互补条件，我们设U={α?i|α?i>0}，我们U从中随机采一个α?s，对应的样本为(x(s),y(s))。因为有α?s>0，则必有

y^{(s)}(\bm{w^{*}}^T \bm{x}^{(s)}+b^{*}) - 1 = 0
\tag{26}
我们将式(25)代入式(26)，方程两边同乘y(s)，并注意到y(s)2=1，我们有

b?=y(s)?∑i=1mα?iy(i)?x(i),x(s)?(27)
这样，我们就可以得到分离超平面如下：

{x|∑i=1mα?iy(i)?x(i),x?+b?=0}(29)
分类决策函数如下:

f(x)=sign(∑i=1mα?iy(i)?x(i),x?+b?)(29)
(之所以写成?x(i),x?的内积形式是为了方便我们后面引入核函数)

给定测试样本x?，我们就能按照式(29)计算其类别f(x?)。由式(23)可知，w?和b?只依赖于αi>0的样本点(x(i),y(i))，而其他样本点对w?和b没有影响。我们将训练数据中对应于a?i>0的实例点x(i)∈Rn称为支持向量。
综上，按照式(13)的策略求解线性可分支持向量机的算法如下：　
线性可分支持向量机学习算法
一个超平面将Rn划分为两个半空间，（闭的）半空间是具有下列形式的集合：
观察算法的2、３步可知，我们只需要关注αi>0对应的相关的实例(也就是支持向量)，故实际计算复杂度其实很低。