支持向量机

这篇笔记主要总结一些关于支持向量机的知识。

简介

  1. 二分类模型,定义在特征空间上的间隔最大的线性分类器,加入核技巧,成为非线性分类器。
  2. 学习目标——特征空间找到一个分离超平面,能正确划分训练集,并且几何间隔最大化。

横向比较

  • 感知机(误分类最小,无穷多解)
  • SVM——间隔最大化(凸二次规划最优化问题,唯一解),直观解释,即,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。

3种情况

训练集线性可分 -> hard margin maximization -> 硬间隔SVM;

训练集近似线性可分 -> soft margin maximization -> 软间隔SVM;

训练集线性不可分 -> kernel trick/soft margin maximization -> 非线性SVM。

数据集的线性可分性——给定一个数据集T,如果存在某个超平面S(w·x+b=0)能够将数据集的正负样本完全正确的划分到超平面两侧,则T是线性可分数据集。

函数间隔可以表示分类预测的准确性及确信度。min(yi(wxi+b))—<规范化||w||=1>—> 几何间隔

最大间隔超平面,最大化超平面(w,b)关于训练集的几何间隔,几何间隔最小的样本为支持向量。

线性可分SVM

线性可分SVM对应着将两类数据正确划分并且间隔最大的直线,等价于求解对应的凸二次规划问题。如下图所示线性可分训练集,
line
max_margin

在决定分离超平面时只有支持向量起作用,其他实例点并不起作用。支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定。

学习的对偶算法

关于凸优化对偶,(参考我的博文)。针对上面的最优化问题的对偶问题是拉格朗日极大极小问题,$$\underset{\alpha }{max} \underset{w,b}{min}L(w,b,\alpha )$$,为得到对偶问题的解,需要先求$L(w,b,\alpha)$对w,b的极小,再求对$\alpha$的极大。

larg_learn

训练集中对应于$\alpha _{i}>0$的样本称为支持向量。

线性SVM

当训练集近似线性可分,如下图,即,训练集中有一些特异点,将这些特异点排除后,剩下大部分的样本点组成集合是线性可分的(也就是存在某些不符合函数间隔大于等于1的样本点)。soft_margin
解决这一问题,可以对每个样本点引进一个松弛变量 ai(大于等于0) ,使得函数间隔加上松弛变量大于等于1,满足线性可分的约束条件,同时,对每个松弛变量ai,支付一个代价ai目标函数由原来的$ \frac{1}{2} \left | W \right |^2 $变成soft_f,这里C>0称为惩罚参数,最小化目标函数就是,使$ \frac{1}{2} \left | W \right |^2 $尽量小(间隔尽量大),同时是误分类点的个数尽量小,C是调和二者的系数。这就是所谓的软间隔最大化
同样可以通过求解对偶问题的解得到原始问题的最优解。

合页损失函数

线性SVM原始最优化问题:
heye

等价于最优化问题
best_heye

,上式的第1项是经验损失,称为合页损失函数,下标表示取正值的函数,第2项是正则化项。

非线性SVM

SVM是线性分类器,但训练集线性不可分时,如下图情况,该如何学习呢?
notline
此时,核技巧的引入,完美的解决了该问题。核技巧应用到SVM,基本想法就是通过非线性变换将输入空间(欧式空间或离散集合)对应于一个特征空间(希尔伯特空间),使得在输入空间的超曲面模型对应于特征空间的超平面模型。这样,线性不可分的分类问题的学习任务通过在特征空间中求解线性SVM就可以了。
核技巧,在学习与预测中只定义核函数,而不显式地定义映射函数,避免了“维度灾难”。
线性SVM的对偶问题中,目标函数,决策函数都只涉及输入样本与样本间的内积,可以自然引入核函数,学习到含有核函数的非线性SVM。
常用的核函数有,多项式核函数,高斯核函数,线性核函数等。

实例

未完待续……

参考文献:
[1].《统计学习方法》,李航著

分享