文档介绍：支持向量机 (Support Vector Machine, SVM)
制作人:田媛
目录
SVM的理论基础
线性支持向量机:可分情况
线性支持向量机:不可分情况
非线性支持向量机
多类问题
SVM方法的特点
最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。
SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。
过两类样本中离分类面最近的点且平行于最优分类面的超平面上b11,b12的训练样本就叫做支持向量。
一个线性可分数据集上的可能决策边界
决策边界的边缘
泛化误差界的公式为:
公式中R就是真实风险,Re就是经验风险, 就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小。
经验风险,代表了分类器在给定样本上的误差;置信风险,代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。
根据训练误差Re、训练样本数N和模型的复杂度h,给出了分类器的泛化误差的一个上界R。
:可分情况
SVM的决策边界和边缘
线性分类器的决策边界可以表示成:
两条边缘直线可以表示成:
:可分情况
对于任意学习样本,其分布必然在直线之上或直线之下。即有
将以上两式合并,有
在选择分类线的过程中,上式对于任何学习样本都必须成立。在此前提下寻找最宽边界的问题,最后可以表示成一个约束优化问题:
:可分情况
根据上述条件构造拉格朗日函数:
分别对w和b求导:
:可分情况
处理不等式约束的一种方法就是把它变换成一组等式约束。只要限制拉格朗日乘子非负,这种变换便是可行的:
乍一看,拉格朗日乘子的数目好像和训练样本的数目一样多。事实上,应用上式给定的约束后,许多拉格朗日乘子都变为零。该约束表明,除非训练实例满足方程yi(w*xi+b)=1,否则拉格朗日乘子必须为零。那些λi>0的训练实例位于超平面l1或l2上,称为支持向量。
例:考虑下图给出的二维数据集,它包含8个训练实例
使用二次规划方法,可以得到每一个训练实例的拉格朗日乘子,如表的最后一列所示。注意,仅前面两个实例具有非零的拉格朗日乘子。这些实例对应于该数据集的支持向量。