支持向量机(二)——松弛变量处理异常点
2 松弛变量处理异常点
2.1 原始问题
在博文支持向量机(一)——线性可分支持向量机 一文中,我们介绍了训练数据集线性可分的情况下,应用硬间隔最大化策略得到最优超平面。但是在实际情况中,训练集有很大可能存在噪声,使得某些样本偏离正常范围,称这些样本为异常点,如下图所示
这时如果应用硬间隔最大化,得到的最优超平面是图中的黑色实线;而如果不迁就左上角的异常点,得到的最优分类超平面为黑色虚线。可以看出实线是对训练集过拟合的结果,而虚线的泛化能力更好。所以完全正确分类的超平面不一定是最好的。
另外,当训练集本身线性不可分的时候,是不存在能将数据集完全正确分离的超平面的。
线性不可分数据集:
不存在超平面能将数据集完全正确划分,但是去除掉一小部异常点之后,剩下的大部分数据是线性可分数据。
对于以上两种情况,硬间隔最大策略不再受欢迎或者有效。此时,我们需要考虑软间隔最大化。软间隔最大化允许样本点落在间隔边界内部甚至允许误分类样本点存在(我们称这些点为超平面的异常点)。这是通过为每个样本点引入一个松弛变量
优化问题(1)可以这样理解:从训练集中选择部分样本,称为剩余训练集,剩余训练集是线性可分的,其余样本点作为异常点。对剩余训练集进行硬间隔最大化,也就是说从函数间隔为1的超平面中选择几何间隔最大的,但同时还要考虑异常点对超平面的偏移程度最小。遍历所有可能的剩余训练集,得到最优的超平面。
2.2 对偶问题
通过极大极小拉格朗日函数,可以得到原始问题(26)的对偶问题。
引入拉格朗日乘子
原始问题的对偶问题为:
为了求对偶问题,首先需要求极小化问题
得到:
代入到L中,得到
然后再对
约束条件(35)(36)(37)等价于
重写上面的优化问题:
优化问题(38)是原始问题(26)的对偶问题,两个优化问题的最优解存在,并且满足KKT条件:
求出对偶问题(38)的最优解
至于
于是
于是
于是得到最优超平面
2.3 支持向量
由公式(48)可知,
支持向量包含:
- 当
0<α∗i<C 时,由公式(41)知道μ∗I>0 ,再由公式(45)知道ξ∗i=0 ,于是由(42)知道1−yj(ω∗Txj+b∗)=0.
所以当
-
当
α∗i=C 时,有μ∗i=0 ,对应的ξ∗i 可取的值就比较多了:-
ξ∗i=0 时,有yj(ω∗Txj+b∗)=1,
意味着分类正确,对应的支持向量位于间隔边界上; -
0<ξ∗i<1 时,有0<yj(ω∗Txj+b∗)<1,
意味着分类正确,对应的支持向量位于间隔边界内部; -
ξ∗i=1 时,有yj(ω∗Txj+b∗)=0,
意味着对应的支持向量位于超平面上 ; -
ξ∗i>1 时,有yj(ω∗Txj+b∗)<0,
意味着对应的支持向量被误分类 。
-