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

1、线性支持向量机

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的。因为这时上述方法中的不等式约束并不能都成立。这时就需要修改硬间隔最大化，使其成为软间隔最大化。

假设给定一个特征空间上的训练数据集T={（x1,y1），（x2,y2），...，（xN,yN）}，其中xi∈χ=Rn（R的n次方），yi∈γ={-1,+1}，i=1,2,...,N, xi为第i个特征向量，yi为xi的类标记。再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点，将这些特异点去除后，剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点(xi,yi)不能满足函数间隔大于等于1的约束条件。即不能满足 yi(w*xi+b)-1≥0 这个条件。为了解决这个问题，可以对每个样本点(xi,yi)引进一个松弛变量 ξi≥0, 使得函数间隔加上松弛变量大于等于1。这样约束条件变为yi(w*xi+b)≥1-ξi, 同时，为每个松弛变量ξi支付一个代价ξi。

最小化目标函数(7.32)包含两层含义：使0.5*||w||2尽量小即间隔大，同时使误分类点的个数尽量小，C是调和二者的系数。

2、学习的对偶算法

步骤(2)中，对任一适合条件0<aj*<c的aj*，按式(7.51)都可求出b*，但是由于原始问题(7.32)~(7.34)对b的解并不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。

3、支持向量

软间隔的支持向量xi或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。

由上面的KKT条件知，若ai*<C，则ξi=0，支持向量xi恰好落在间隔边界上；若ai*=C, 0<ξi<1，则分类正确，xi在间隔边界与分离超平面之间；若ai*=C, ξi=1，则xi在分离超平面上；若ai*=C, ξi>1，则xi位于分离超平面误分一侧。

4、合页损失

参考：《统计学习方法》李航