线性不可分支持向量机
线性不可分
- 设有如下两类样本的训练集：
线性不可分情况意味着不存在这样的超平面，使训练点中的正类和负类样本能 够完全分别位于该超平面的两侧，即无法将它们完全分开。如果要用超平面来 划分的话，必然有错分的点。
现实情况：我们只会线性可分的方法；
处理思路：允许分类误差，并且在目标函数 中引入对分类误差的惩罚。
软间隔最大化
- 允许支持向量机在一些样本上出错，需要我们将硬间隔最大化改为软间隔最大化，当然，在最大化软间隔的同时，不满足约束的样本应尽可能的少。y i ( w ⋅ x + b ) = 1 软间隔要求是 y i ( w ⋅ x + b ) ≥ 1。
- 为了解决某些样本不满足约束的情况，对每个样本点(x i , y i )引入一个松弛变量ξ i ≥ 0 ，使函数间隔加上松弛变量大于等于1，这样约束条件就变为：
- 为了避免ξ i 取太大的值，需要在目标函数中对他们进行惩罚，其中C > 0称为惩罚系数，C值大时，对误分类的惩罚增加，C 值小时对误分类的惩罚减小。
有了上面的思路，可以和线性可分支持向量机一样来考虑线性支持向量机的学习问题，线性不可分的线性支持向量机的学习问题就变为如下凸二次规划问题：
通过求解以上凸二次规划问题，即软间隔最大化问题，得到分离超平面为：
相应的分类决策函数为：
基于对偶的学习算法
构建拉格朗日对偶函数：
可以推出：
(2) 将结果代入拉格朗日函数中，整理后可得：
对偶问题，凸二次规划问题，有唯一的最优解：
(4) 求解上述问题可得到最优的α ∗ ，进而求得w ∗ , b ∗ ，最终获得分离超平面和分类决策函数：
得到分类超平面：
得到分类决策函数：
以上是推导过程，实际使用过程是这样的：
- 构造并求解最优化问题
- 求得分离超平面：
- 获得分类决策函数：
软间隔支持向量
软间隔支持向量具有以下性质：
