SVM支持向量机学习笔记

作者:ww2041

学习SVM,主要阅读了以下两位的博客:

July——支持向量机通俗导论(理解SVM的三层境界)

JerryLead——支持向量机系列

个人感觉,为了真正理解SVM,以上博客至少得认真仔细阅读五遍,当然数学好的话除外。以下是学习SVM的个人笔记,方便以后需要使用时能快速回忆。


SVM原理公式推导笔记


1.线性可分简单推导


        支持向量机,因其英文名为support vector machine,故一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

分类函数

当f(x) 等于0的时候,x便是位于超平面上的点,而f(x)大于0的点对应 y=1 的数据点,f(x)小于0的点对应y=-1的点,如下图所示:

                                                                                


为了使超平面离数据点的“间隔”越大,我们定义几何间隔,假定对于一个点 ,令其垂直投影到超平面上的对应点为 x0 是垂直于超平面的一个向量,为样本x到超平面的距离,如下图所示:


根据平面几何知识,有


等式两边乘上,由于x0满足f(x0)=0即可算出: 


通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确,所以,可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此,y来表示我们的几何间隔。为了方便推导,我们定义yf(x)=1,最大化几何间隔,得到目标函数是:




通过给每一个约束条件加上一个拉格朗日乘子(Lagrange multiplier),定义拉格朗日函数


接着是


目标函数变成


通过拉格朗日对偶性转化目标函数


由此通过让L(w,b,a) 关于 w 和 b 最小化,然后求对的极大,最后利用SMO算法求解对偶问题中的拉格朗日乘子,从而得到我们的分类函数。以上的理论细节见July的支持向量机导论


开始我们的对偶问题的求解,固定要让 L 关于 w 和 b 最小化,我们分别对w,b求偏导数,即令 L/w 和 L/b 等于零,得到


代入公式中


得到


由此目标函数转化为


这样通过SMO算法,求得拉格朗日乘子,便可得到分类函数中的w和b



从而得到分类函数


2.线性不可分引入核函数

首先是线性不可分的图例,由下图可知,一开始的二维平面上两股数据无法用一根直线分割,而旋转一下到三维平面上,就可以划分开来,这就是在线性不可分的情况下,通过将低维数据映射到高维度上实现可分,但是映射后出现的是高维度的计算复杂度提高,由此引入核函数,即低维度的计算结果可以映射高维度的表现结果。


通过引入高维映射函数后的分类函数:


其中的可以通过求解如下 dual 问题而得到目标函数为:


引入核函数后分类函数为(此形式,w已经用表示):


其中的可以通过求解如下 dual 问题而得到目标函数为:



3.使用松弛变量处理噪音数据

由于机器学习对数据的依赖性很强,而数据的收集过程中或多或少存在错误数据

通过改变约束条件


其中称为松弛变量 (slack variable) ,对应数据点允许偏离的 functional margin 的量,得到目标优化函数


又由拉格朗日对偶性等推到的到最终优化目标函数为


接着便是通过SMO算法求出拉格朗日乘子,得到w和b,得到分类函数,从而待分类数据代入分类函数中,实现分类。

发表评论

0个评论

我要留言×

技术领域:

我要留言×

留言成功,我们将在审核后加至投票列表中!

提示x

人工智能机器学习知识库已成功保存至我的图谱现在你可以用它来管理自己的知识内容了

删除图谱提示×

你保存在该图谱下的知识内容也会被删除,建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗?

删除节点提示×

无法删除该知识节点,因该节点下仍保存有相关知识内容!

删除节点提示×

你确定要删除该知识节点吗?