统计学习方法笔记（十一）支持向量机（二）

线性可分支持向量机与软间隔最大化

一、线性支持向量机
当数据是线性不可分的时候，不等式约束并不总是成立的，所以需要修改硬间隔最大化，使其成为软间隔最大化。
对于训练数据来说，所谓的线性不可分，指数据中有一些特异点，其无法满足函数间隔大于等于1的约束条件。为了解决这个问题，对每个样本点引入了一个松弛变量，使其函数间隔加上这个松弛变量满足相应的条件，这样，约束条件变为：
yi(w⋅xi+b)≥1−ξi$y_i(w\cdot x_i+b)\ge 1-{\xi }_i$
同时，因为引入了一个松弛变量，所以要支付一个代价，目标函数变为：
12||w||2+C∑i=1Nξi$\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i$
所以，可以得到如下的凸二次规划问题：
minw,b,ξ12||w||2+C∑i=1Nξi$\underset{w,b,\xi }{min}\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i$
s.t.yi(w⋅xi+b)≥1−ξi,i=1,2,⋯,N ξi≥0,i=1,2,⋯,N$\begin{array}{l}s.t.y_i(w\cdot x_i+b)\ge 1-{\xi }_i,i=1,2,\cdots ,N{\xi }_i\ge 0,i=1,2,\cdots ,N\end{array}$
最终可以证明，w的解是唯一的，而b的解不唯一，且存在一个区间上。
线性支持向量机的模型：
w∗⋅x+b∗=0$w^{\ast }\cdot x+b^{\ast }=0$
f(x)=sign(w∗⋅x+b∗)$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$
二、学习的对偶算法
1、原始问题的对偶问题变为：
minα12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi$\underset{\alpha }{min}\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$
s.t.∑i=1Nαiyi=0$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0$
0≤αi≤C,i=1,2,⋯,N$0\le {\alpha }_i\le C,i=1,2,\cdots ,N$
最终可求得，其解为：
w∗=∑i=1Nα∗iyixi$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$
b∗=yj−∑i=1Nyiα∗i(xi⋅xj)$b^{\ast }=y_j-\sum _{i=1}^N{y}_i{\alpha }_i^{\ast }(x_i\cdot x_j)$
2、支持向量

如图所示，支持向量是对应于α∗i>0${\alpha }_i^{\ast }>0$ 的实例点。其或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分的一侧。
三、合页损失函数
合页损失函数是对线性支持向量机学习的另一种解释，其实质是实现以下目标函数的最小化：
∑i=1N[1−yi(w⋅xi+b)]++λ||w||2$\sum _{i=1}^N{[1-y_i(w\cdot x_i+b)]}_{+}+\lambda ||w|{|}^2$
显然，正常来说，yi(w⋅xi+b)$y_i(w\cdot x_i+b)$ 应该大于1，代表没有被误分类，损失为0，一旦被误分类，其损失为上式中的第一项。
合页损失函数与原始最优化问题等价。