线性可分支持向量机

定义

给定线性可分训练数据集，通过间隔最大化或等价求解相应凸二次规划问题学习得到的分离超平面为
<nobr> w∗⋅x+b∗=0 </nobr>
以及相应的分类决策函数
<nobr> f(x)=sign(w∗⋅x+b∗) </nobr>
称为线性可分支持向量机。

函数间隔与几何间隔

函数间隔

对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点 <nobr> (xi,yi) </nobr>的函数间隔为
<nobr> γ^i=yi(w⋅xi+b) </nobr>
定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点 <nobr> (xi,yi) </nobr>的函数间隔之最小值，即
<nobr> γ^=mini=1,...,Nγ^i </nobr>

函数间隔可以表示分类预测的正确性和确信度，但是在选择分离超平面时，只有函数间隔还不够。因为成比例地改变w和b，超平面没有改变，函数间隔却变为2倍。

几何间隔

对分离超平面的法向量w进行约束，使得间隔是确定的，这时就成了几何间隔。
<nobr> γi=yi(w⋅xi+b||w||) </nobr>
<nobr> γ=mini=1,...,Nγi </nobr>
超平面关于样本点的几何间隔一般是实例点到超平面的带符号距离，当样本点被正确分类时，就是距离。

间隔最大化

最大间隔分离超平面

求一个几何间隔最大的分离超平面。

<nobr> maxw,bγs.t. yi(w⋅xi+b||w||)≥γ,i=1,2,...,N </nobr>

根据几何间隔与函数间隔关系，改写为
<nobr> maxw,bγ^||w||s.t. yi(w⋅xi+b)≥γ^,i=1,2,...,N </nobr>

函数间隔 <nobr> γ^ </nobr> 的取值并不影响最优化问题的解。取 <nobr> γ^=1 </nobr> ,并将最大化 <nobr> 1||w|| </nobr> 转化为等价的最小化 <nobr> 12||w||2 </nobr> 。
得到以下的线性可分SVM的最优化问题。
<nobr> minw,b12||w||2 (7.13)s.t. yi(w⋅xi+b)−1≥0 (7.14) </nobr>

这是一个凸优化问题同时是一个凸二次规划问题。

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。也就是使得不等式约束 <nobr> yi(w⋅xi+b)−1≥0 </nobr>等号成立的点，即
<nobr> yi(w⋅xi+b)−1=0 </nobr>
正例点和负例点支持向量所在的间隔边界之间的距离为 <nobr> 2||w|| </nobr>。
在决定分离超平面时，只有支持向量起作用。

学习的对偶算法

对于原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题的到原始问题的最优解，这就是线性可分SVM的对偶算法。
优点
1. 对偶问题往往更容易求解
2. 自然引入和函数，进而推广到非线性分类问题

拉格朗日函数

<nobr> L(w,b,a)=12||w||2−∑Ni=1aiyi(w⋅xi+b)+∑Ni=1ai (7.18) </nobr>，其中 <nobr> ai≥0 </nobr>

拉格朗日对偶问题

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
<nobr> maxaminw,bL(w,b,a) </nobr>
为了得到对偶问题的解，先求L对w,b的极小，再求对a的极大
1. 求 <nobr> minw,bL(w,b,a) </nobr>

<nobr> ∇wL(w,b,a)∇bL(w,b,a)得w∑i=1N=w−∑i=1Naiyixi=0=−∑i=1Naiyi=0=∑i=1Naiyixi (7.19)aiyi=0 (7.20) </nobr>

将式(7.19)带入拉格朗日函数(7.18)，并利用式(7.20)，得
<nobr> L(w,b,a)=−12∑i=1N∑j=1Naiajyiyj(xi⋅xj)+∑i=1Nai </nobr>
即
<nobr> minw,bL(w,b,a)=−12∑i=1N∑j=1Naiajyiyj(xi⋅xj)+∑i=1Nai </nobr>
2. 求 <nobr> minw,bL(w,b,a)对a得极大，即是对偶问题 </nobr>
<nobr> maxa−12∑i=1N∑j=1Naiajyiyj(xi⋅xj)+∑i=1Nais.t.∑i=1Naiyi=0ai≥0,i=1,2,..,N </nobr>

将上式目标函数由求极大转成求极小，得到下面与之等价得对偶最优化问题。
<nobr> mina12∑i=1N∑j=1Naiajyiyj(xi⋅xj)−∑i=1Nai (7.22)s.t.∑i=1Naiyi=0 (7.23)ai≥0,i=1,2,..,N (7.24) </nobr>

由于原始问题(7.13)-(7.14)满足 弱化的Slater条件，对偶问题(7.22)-(7.24)的最优值和原始问题最优值相同，设 <nobr> w∗,b∗, </nobr> 是原始问题最优解， <nobr> a∗ </nobr> 是对偶问题最优解，根据 KKT条件， <nobr> w∗,b∗,a∗ </nobr> 满足：
<nobr> 1−yi(w∗⋅xi+b∗)a∗ia∗i⋅[1−yi(w∗⋅xi+b∗)]∇wL(w∗,b∗,a∗)∇bL(w∗,b∗,a∗)=∑i=1Na∗iyi≤0≥0=0=w∗−∑i=1Na∗iyixi=0 (7.27)=0 </nobr>

由此得
<nobr> w∗=∑ia∗iyixi(7.25) </nobr>
其中至少由一个 <nobr> a∗j>0 </nobr> （反证法,假设 <nobr> a∗=0 </nobr> ，由式(7.27)知 <nobr> w∗=0 </nobr> ,而 <nobr> w∗=0 </nobr> 不是原始最优化问题(7.13)-(7.14)的解，产生矛盾），对此j有
<nobr> yj(w∗⋅xj+b∗)−1=0( 7.28)根据互补松弛性 </nobr>
将(7.27)带入(7.28)，并有 <nobr> y2j=1 </nobr> ，即得
<nobr> b∗=yj−∑i=1Na∗iyi(xi⋅xj) </nobr>
由此，分离超平面可以写成
<nobr> ∑i=1Na∗iyi(x⋅xi)+b∗=0 </nobr>
决策函数
<nobr> f(x)=sign(∑i=1Na∗iyi(x⋅xi)+b∗) (7.30) </nobr>
也就是说，分类决策函数只依赖于输入x和训练样本输入的内积。式(7.30)称为线性可分SVM的对偶形式。

综上，对于给定的线性可分的数据集，可以先求对偶问题(7.22)-(7.24)的解 <nobr> a∗ </nobr>；再利用式(7.25)和(7.26)求得原始问题的解 <nobr> w∗,b∗ </nobr>。

支持向量

训练集中对应于 <nobr> a∗i>0 </nobr>的样本点 <nobr> (xi,yi) </nobr>的实例 <nobr> xi </nobr>称为支持向量。
由KKT互补松弛条件可以推得，支持向量一定在间隔边界上。

参考文献

《统计学习方法》第7章