机器学习(16)之支持向量机原理(二)软间隔最大化

关键字全网搜索最新排名

【机器学习算法】：排名第一

【机器学习】：排名第二

【Python】：排名第三

【算法】：排名第四

前言

在支持向量机原理(一) 线性支持向量机中，我们对线性可分SVM的模型和损失函数优化做了总结。最后我们提到了有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分，本篇就对线性支持向量机如何处理这些异常点的原理方法做一个总结。

线性可分SVM的算法过程

输入是线性可分的m个样本(x1,y1),(x2,y2),...,(xm,ym),,其中x为n维特征向量。y为二元输出，值为1，或者-1.

输出是分离超平面的参数和w∗和b∗和分类决策函数。

算法过程如下：

1）构造约束优化问题

2）用SMO算法求出上式最小时对应的α向量的值α∗向量.

3) 计算

4) 找出所有的S个支持向量,即满足对应的样本，计算偏置项b

线性分类SVM面临的问题

有时候本来数据的确是可分的，也就是说可以用线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照(机器学习(7)之感知机python实现)中的方法来分类。

另外一种情况没有这么糟糕到不可分，但是会严重影响我们模型的泛化预测效果，比如下图，本来如果我们不考虑异常点，SVM的超平面应该是下图中的红色线所示，但是由于有一个蓝色的异常点，导致我们学习到的超平面是下图中的粗虚线所示，这样会严重影响我们的分类模型预测效果。

如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。

软间隔最大化

所谓的软间隔，是相对于硬间隔说的，我们可以认为上一篇线性分类SVM的学习方法属于硬间隔最大化。

回顾下硬间隔最大化的条件：

接着我们再看如何可以软间隔最大化呢？

SVM对训练集里面的每个样本(xi,yi)引入了一个松弛变量ξi≥0,使函数间隔加上松弛变量大于等于1，也就是说：

对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量ξi, 对应了一个代价ξi，这个就得到了我们的软间隔最大化的SVM学习条件如下：

这里,C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。也就是说，我们希望权值的二范数尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

软间隔最大化目标函数的优化

和线性可分SVM的优化方式类似，我们首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：

现在要优化的目标函数是：

这个优化目标满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：

我们可以先求优化函数对于w,b,ξ的极小值, 接着再求拉格朗日乘子α和 μ的极大值。

首先我们来求优化函数对于w,b,ξ的极小值，这个可以通过求偏导数求得：

可以利用上面的三个式子去消除w和b。现在我们看看我们的优化目标的数学形式：

这就是软间隔最大化时的线性可分SVM的优化目标形式，和上一篇的硬间隔最大化的线性可分SVM相比，我们仅仅是多了一个约束条件0≤αi≤C。我们依然可以通过SMO算法来求上式极小化时对应的α向量就可以求出和w和b。

欢迎分享给他人让更多的人受益

参考：

1. 周志华《机器学习》
2. 李航《统计学习方法》
3. 博客园：刘建平 http://www.cnblogs.com/pinard/p/6100722.html