温州市企业网站制作,如何自己建公司网站,wordpress 页面标题,中山市企业网站seo营销工具机器学习中的算法-支持向量机(SVM)基础 版权声明#xff1a; 本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用#xff0c;但请注明出处#xff0c;如果有问题#xff0c;请联系wheeleastgmail.com。也可以加我的微博: leftnotea… 机器学习中的算法-支持向量机(SVM)基础 版权声明 本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用但请注明出处如果有问题请联系wheeleastgmail.com。也可以加我的微博: leftnoteasy 前言 又有很长的一段时间没有更新博客了距离上次更新已经有两个月的时间了。其中一个很大的原因是不知道写什么好-_-最近一段时间看了看关于SVM(Support Vector Machine)的文章觉得SVM是一个非常有趣而且自成一派的方向所以今天准备写一篇关于关于SVM的文章。 关于SVM的论文、书籍都非常的多引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”。SVM对于大部分的普通人来说要完全理解其中的数学是非常困难的所以要让这些普通人理解得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些数学对学习其他的内容也是大有裨益的。我就是属于绝大多数的普通人为了看明白SVM看了不少的资料这里把我的心得分享分享。 其实现在能够找到的关于SVM的中文资料已经不少了不过个人觉得每个人的理解都不太一样所以还是决定写一写一些雷同的地方肯定是不可避免的不过还是希望能够写出一点与别人不一样的地方吧。另外本文准备不谈太多的数学因为很多文章都谈过了尽量简单地给出结论就像题目一样-机器学习中的算法之前叫做机器学习中的数学所以本系列的内容将更偏重应用一些。如果想看更详细的数学解释可以看看参考文献中的资料。 一、线性分类器 首先给出一个非常非常简单的分类问题线性可分我们要用一条直线将下图中黑色的点和白色的点分开很显然图上的这条直线就是我们要求的直线之一可以有无数条这样的直线 假如说我们令黑色的点 -1 白色的点 1直线f(x) w.x b这儿的x、w是向量其实写成这种形式也是等价的f(x) w1x1 w2x2 … wnxn b, 当向量x的维度2的时候f(x) 表示二维空间中的一条直线 当x的维度3的时候f(x) 表示3维空间中的一个平面当x的维度n 3的时候表示n维空间中的n-1维超平面。这些都是比较基础的内容如果不太清楚可能需要复习一下微积分、线性代数的内容。 刚刚说了我们令黑色白色两类的点分别为1, -1所以当有一个新的点x需要预测属于哪个分类的时候我们用sgn(f(x))就可以预测了sgn表示符号函数当f(x) 0的时候sgn(f(x)) 1, 当f(x) 0的时候sgn(f(x)) –1。 但是我们怎样才能取得一个最优的划分直线f(x)呢下图的直线表示几条可能的f(x) 一个很直观的感受是让这条直线到给定样本中最近的点最远这句话读起来比较拗口下面给出几个图来说明一下 第一种分法 第二种分法 这两种分法哪种更好呢从直观上来说就是分割的间隙越大越好把两个类别的点分得越开越好。就像我们平时判断一个人是男还是女就是很难出现分错的情况这就是男、女两个类别之间的间隙非常的大导致的让我们可以更准确的进行分类。在SVM中称为Maximum Marginal是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是由很多道理的比如说从概率的角度上来说就是使得置信度最小的点置信度最大听起来很拗口从实践的角度来说这样的效果非常好等等。这里就不展开讲作为一个结论就ok了:) 上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。 上图就是一个对之前说的类别中的间隙的一个描述。Classifier Boundary就是f(x)红色和蓝色的线plus plane与minus plane就是support vector所在的面红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。 这里直接给出M的式子从高中的解析几何就可以很容易的得到了也可以参考后面Moore的ppt 另外支持向量位于wx b 1与wx b -1的直线上我们在前面乘上一个该点所属的类别y还记得吗?y不是1就是-1就可以得到支持向量的表达式为y(wx b) 1这样就可以更简单的将支持向量表示出来了。 当支持向量确定下来的时候分割函数就确定下来了两个问题是等价的。得到支持向量还有一个作用是让支持向量后方那些点就不用参与计算了。这点在后面将会更详细的讲讲。 在这个小节的最后给出我们要优化求解的表达式 ||w||的意思是w的二范数跟上面的M表达式的分母是一个意思之前得到M 2 / ||w||最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数我们可以对其加入平方和前面的系数熟悉的同学应该很容易就看出来了这个式子是为了方便求导。 这个式子有还有一些限制条件完整的写下来应该是这样的原问题 s.t的意思是subject to也就是在后面这个限制条件下的意思这个词在svm的论文里面非常容易见到。这个其实是一个带约束的二次规划(quadratic programming, QP)问题是一个凸问题凸问题就是指的不会有局部最优解可以想象一个漏斗不管我们开始的时候将一个小球放在漏斗的什么位置这个小球最终一定可以掉出漏斗也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体我们要做的就是在这个凸多面体中找到最优解。这些问题这里不展开因为展开的话一本书也写不完。如果有疑问请看看wikipedia。 二、转化为对偶问题并优化求解: 这个优化问题可以用拉格朗日乘子法去解使用了KKT条件的理论这里直接作出这个式子的拉格朗日目标函数 求解这个式子的过程需要拉格朗日对偶性的相关知识另外pluskid也有一篇文章专门讲这个问题并且有一定的公式推导如果不感兴趣可以直接跳到后面用蓝色公式表示的结论该部分推导主要参考自plukids的文章。 首先让L关于wb最小化分别令L关于wb的偏导数为0得到关于原问题的一个表达式 将两式带回L(w,b,a)得到对偶问题的表达式 新问题加上其限制条件是对偶问题: 这个就是我们需要最终优化的式子。至此得到了线性可分问题的优化式子。 求解这个式子有很多的方法比如SMO等等个人认为求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情所以在这篇文章中准备完全不涉及如何求解这个话题如果之后有时间可以补上一篇文章来谈谈:)。 三、线性不可分的情况软间隔 接下来谈谈线性不可分的情况因为线性可分这种假设实在是太有局限性了 下图就是一个典型的线性不可分的分类图我们没有办法用一条直线去将其分成两个区域每个区域只包含一种颜色的点。 要想在这种情况下的分类器有两种方式一种是用曲线去将其完全分开曲线就是一种非线性的情况跟之后将谈到的核函数有一定的关系 另外一种还是用直线不过不用去保证可分性就是包容那些分错的情况不过我们得加入惩罚函数使得点分错的情况越合理越好。其实在很多时候不是在训练的时候分类函数越完美越好因为训练函数中有些数据本来就是噪声可能就是在人工加上分类标签的时候加错了如果我们在训练学习的时候把这些错误的点学习到了那么模型在下次碰到这些错误情况的时候就难免出错了假如老师给你讲课的时候某个知识点讲错了你还信以为真了那么在考试的时候就难免出错。这种学习的时候学到了“噪声”的过程就是一个过拟合over-fitting这在机器学习中是一个大忌我们宁愿少学一些内容也坚决杜绝多学一些错误的知识。还是回到主题用直线怎么去分割线性不可分的点 我们可以为分错的点加上一点惩罚对一个分错的点的惩罚函数就是这个点到其正确位置的距离 在上图中蓝色、红色的直线分别为支持向量所在的边界绿色的线为决策函数那些紫色的线表示分错的点到其相应的决策面的距离这样我们可以在原函数上面加上一个惩罚函数并且带上其限制条件为 公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分当xi在正确一边的时候ε0R为全部的点的数目C是一个由用户去指定的系数表示对分错的点加入多少的惩罚当C很大的时候分错的点就会更少但是过拟合的情况可能会比较严重当C很小的时候分错的点可能会很多不过可能由此得到的模型也会不太正确所以如何选择C是有很多学问的不过在大部分情况下就是通过经验尝试得到的。 接下来就是同样的求解一个拉格朗日对偶问题得到一个原问题的对偶问题的表达式 蓝色的部分是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题不同的地方就是α的范围从[0, ∞)变为了[0, C]增加的惩罚ε没有为对偶问题增加什么复杂度。 四、核函数 刚刚在谈不可分的情况下提了一句如果使用某些非线性的方法可以得到将两个分类完美划分的曲线比如接下来将要说的核函数。 我们可以让空间从原本的线性空间变成一个更高维的空间在这个高维的线性空间下再用一个超平面进行划分。这儿举个例子来理解一下如何利用空间的维度变得更高来帮助我们分类的例子以及图片来自pluskid的kernel函数部分 下图是一个典型的线性不可分的情况 但是当我们把这两个类似于椭圆形的点映射到一个高维空间后映射函数为 用这个函数可以将上图的平面中的点映射到一个三维空间z1,z2,z3)并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。 用另外一个哲学例子来说世界上本来没有两个完全一样的物体对于所有的两个物体我们可以通过增加维度来让他们最终有所区别比如说两本书从(颜色内容)两个维度来说可能是一样的我们可以加上 作者 这个维度是在不行我们还可以加入 页码可以加入 拥有者可以加入 购买地点可以加入 笔记内容等等。当维度增加到无限维的时候一定可以让任意的两个物体可分了。 回忆刚刚得到的对偶问题表达式 我们可以将红色这个部分进行改造令 这个式子所做的事情就是将线性的空间映射到高维的空间,k(x, xj)有很多种下面是比较典型的两种 上面这个核称为多项式核下面这个核称为高斯核高斯核甚至是将原始空间映射为无穷维空间另外核函数有一些比较好的性质比如说不会比线性条件下增加多少额外的计算量等等这里也不再深入。一般对于一个问题不同的核函数可能会带来不同的结果一般是需要尝试来得到的。 五、一些其他的问题 1如何进行多分类问题 上面所谈到的分类都是2分类的情况当N分类的情况下主要有两种方式一种是1 vs (N – 1)一种是1 vs 1前一种方法我们需要训练N个分类器第i个分类器是看看是属于分类i还是属于分类i的补集出去i的N-1个分类。 后一种方式我们需要训练N * (N – 1) / 2个分类器分类器(i,j)能够判断某个点是属于i还是属于j。 这种处理方式不仅在SVM中会用到在很多其他的分类中也是被广泛用到从林教授libsvm的作者的结论来看1 vs 1的方式要优于1 vs (N – 1)。 2SVM会overfitting吗 SVM避免overfitting一种是调整之前说的惩罚函数中的C另一种其实从式子上来看min ||w||^2这个看起来是不是很眼熟在最小二乘法回归的时候我们看到过这个式子这个式子可以让函数更平滑所以SVM是一种不太容易over-fitting的方法。 参考文档 主要的参考文档来自4个地方wikipedia在文章中已经给出了超链接了pluskid关于SVM的博文Andrew moore的pp
