机器学习 -支持向量机（2）- 线性 SVM（软间隔最大化）
线性 SVM
上一篇文章介绍了在数据线性可分时 SVM 的构建过程，即硬间隔最大化。而当数据线性不可分时，硬间隔最大化是不适用的。（对比与感知器算法，感知器算法在面对线性不可分的数据时是无法收敛的。）
为了解决线性不可分的数据，我们使用软间隔最大化。
软间隔最大化
线性不可分意味着某些数据样本不满足点到超平面距离大于等于 1 的约束条件，所以我们可以对每一个样本点加入一个松弛变量，使得函数间隔加上松弛变量后大于等于 1，此时对原本就满足约束条件的样本点也没有影响。
则约束条件变为：yi(w⋅xi+b)−1+ξi≥0
同时对每一个松弛变量 ξi，付出一个代价的 ξi，则目标函数变为：21∣∣w∣∣2+C∑i=1Mξi
这里 C > 0 称为惩罚参数，一般根据不同的应用场景决定。C 值越大，意味着对误分类的惩罚越大；C 值越小，意味着对误分类的惩罚越小。此时最小化目标函数包含了两层含义：使 21∣∣w∣∣2 尽量小即间隔尽量大，同时使误分类点的个数尽量小，C 是调和二者的系数。
那么此时线性 SVM 的学习问题变成如下凸二次规划（Convex quadratic programming）问题：
w,bmax21∣∣w∣∣2+C∑i=1Mξi
s.t. yi(w⋅xi+b)−1≥0,i=1,2,...,M
ξi≥0,i=1,2,...,M
解上述约束问题，得最优解 w∗,b∗，得到分离超平面 w∗x+b∗=0，存在且唯一；
决策函数 f(x)=sign(w∗x+b∗)
从问题描述中我们可以看出，线性 SVM 是包含之前所讲的线性可分 SVM 的，而且由于现实中数据往往线性不可分，所以线性 SVM 具有更广的适用性。
值得注意的是，在最终的分离超平面以及决策函数中没有 ξ 的出现。因为 ξ 所对应的样本点是误分类点，即到超平面距离小于 1 的点，它只影响 w∗,b∗ 的值，一旦 w∗,b∗ 确定以后，这些点就没有用了。我们需要的仍然只是支持向量。
对偶算法
线性 SVM 的学习过程与线性可分 SVM 的过程是类似的：
构建 拉格朗日函数
L(w,b,α,ξ,μ)=21∣∣w∣∣2+C∑i=1Mξi−∑i=1Mαi[yi(w⋅xi+b)−1+ξi]−∑i=1Mμiξi
w,b,ξminαmaxL(w,b,α,ξ,μ)⟹αmaxw,b,ξminL(w,b,α,ξ,μ)
对 w,b,ξ 求偏导并令其等于 0
∇wL(w,b,α,ξ,μ)=w−∑i=1Mαiyixi=0
∇bL(w,b,α,ξ,μ)=∑i=1Mαiyi=0
∇ξL(w,b,α,ξ,μ)=C−αi−μi=0
得
w=∑i=1Mαiyixi
∑i=1Mαiyi=0
C−αi−μi=0
将结果代回，得
w,bminL(w,b,α,ξ,μ)=−21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)+∑i=1Mαi
求 w,bminL(w,b,α,ξ,μ) 对 α 的极大 αmaxw,bminL(w,b,α,ξ,μ)
添 “负号”将求极大转化为求极小，得到，
αmin21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi
根据 C−αi−μi=0 可将 μi 消去，从而只留下变量 αi，所以约束变为
0≤αi≤C
最终问题变为
αmin21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi
s.t. ∑i=1Mαiyi=0
0≤αi≤C,i=1,2,...,M
求得最优解 α∗=(α1,α2,...,αM)T，根据 KKT 条件，
由此可得到
w∗=∑i=1Mαi∗yixi
b∗=yj−∑i=1Mαi∗yi(xi⋅xj)
最终
分离超平面可写成：∑i=1Mαi∗yi(x⋅xj)+b∗=0
分类决策函数可写成：f(x)=sign(∑i=1Mαi∗yi(x⋅xj)+b∗)
支持向量
在线性不可分的情况下，将对应于 αi∗>0 的数据样本 xi 称为支持向量。
在软间隔最大化的情况中，支持向量要比线性可分时的硬间隔最大化复杂一些。
分类正确：
若 αi∗<C，则 ξi=0，支持向量恰好落在间隔边界上；
若 αi∗=C，0<ξi<1，支持向量在间隔边界与分离超平面之间；
若 αi∗=C，ξi=1，支持向量在分离超平面上；
分类错误
若 αi∗=C，ξi>1，支持向量在分离超平面误分类一侧；