支持向量机_支持向量机算法 - CSDN
支持向量机 订阅
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane) [1-3]  。SVM使用铰链损失函数(hinge loss)计算经验风险(empirical risk)并在求解系统中加入了正则化项以优化结构风险(structural risk),是一个具有稀疏性和稳健性的分类器 [2]  。SVM可以通过核方法(kernel method)进行非线性分类,是常见的核学习(kernel learning)方法之一 [4]  。SVM被提出于1964年,在二十世纪90年代后得到快速发展并衍生出一系列改进和扩展算法,在人像识别、文本分类等模式识别(pattern recognition)问题中有得到应用 [5-6]  。 展开全文
支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane) [1-3]  。SVM使用铰链损失函数(hinge loss)计算经验风险(empirical risk)并在求解系统中加入了正则化项以优化结构风险(structural risk),是一个具有稀疏性和稳健性的分类器 [2]  。SVM可以通过核方法(kernel method)进行非线性分类,是常见的核学习(kernel learning)方法之一 [4]  。SVM被提出于1964年,在二十世纪90年代后得到快速发展并衍生出一系列改进和扩展算法,在人像识别、文本分类等模式识别(pattern recognition)问题中有得到应用 [5-6]  。
信息
 提出时间
1964年 [7]
外文名
Support Vector Machine, SVM
提出者
V.N. Vapnik,A.Y. Chervonenkis,C. Cortes 等
类    型
机器学习算法
中文名
支持向量机
学    科
统计学,人工智能
应    用
计算机视觉,自然语言处理,生物信息学
支持向量机历史
SVM是由模式识别中广义肖像算法(generalized portrait algorithm)发展而来的分类器 [8]  ,其早期工作来自前苏联学者Vladimir N. Vapnik和Alexander Y. Lerner在1963年发表的研究 [9]  。1964年,Vapnik和Alexey Y. Chervonenkis对广义肖像算法进行了进一步讨论并建立了硬边距的线性SVM [7]  。此后在二十世纪70-80年代,随着模式识别中最大边距决策边界的理论研究 [10]  、基于松弛变量(slack variable)的规划问题求解技术的出现 [11]  ,和VC维(Vapnik-Chervonenkis dimension, VC dimension)的提出 [12]  ,SVM被逐步理论化并成为统计学习理论的一部分 [1]  。1992年,Bernhard E. Boser、Isabelle M. Guyon和Vapnik通过核方法得到了非线性SVM [13]  。1995年,Corinna Cortes和Vapnik提出了软边距的非线性SVM并将其应用于手写字符识别问题 [14]  ,这份研究在发表后得到了关注和引用,为SVM在各领域的应用提供了参考。
收起全文
精华内容
参与话题
  • 支持向量机通俗导论(理解SVM的三层境界)

    万次阅读 多人点赞 2019-01-27 11:49:45
    支持向量机通俗导论(理解SVM的三层境界) 作者:July 。致谢:pluskid、白石、JerryLead。 说明:本文最初写于2012年6月,而后不断反反复复修改&优化,修改次数达上百次,最后修改于2016年11月。 声明:...

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

    作者:July 。致谢:pluskid、白石、JerryLead。
    说明:本文最初写于2012年6月,而后不断反反复复修改&优化,修改次数达上百次,最后修改于2016年11月。
    声明:本文于2012年便早已附上所有参考链接,并注明是篇“学习笔记”,且写明具体参考了pluskid等人的文章。文末2013年的PDF是为证。另,如果本文的图片/公式无法正常显示,请点击本文的七月在线题库版

     

    前言

        动笔写这个支持向量机(support vector machine)是费了不少劲和困难的,原因很简单,一者这个东西本身就并不好懂,要深入学习和研究下去需花费不少时间和精力,二者这个东西也不好讲清楚,尽管网上已经有朋友写得不错了(见文末参考链接),但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明,我还是想尝试写一下,希望本文在兼顾通俗易懂的基础上,真真正正能足以成为一篇完整概括和介绍支持向量机的导论性的文章。

        本文在写的过程中,参考了不少资料,包括《支持向量机导论》、《统计学习方法》及网友pluskid的支持向量机系列等等,于此,还是一篇学习笔记,只是加入了自己的理解和总结,有任何不妥之处,还望海涵。全文宏观上整体认识支持向量机的概念和用处,微观上深究部分定理的来龙去脉,证明及原理细节,力保逻辑清晰 & 通俗易懂。

        同时,阅读本文时建议大家尽量使用chrome等浏览器,如此公式才能更好的显示,再者,阅读时可拿张纸和笔出来,把本文所有定理.公式都亲自推导一遍或者直接打印下来(可直接打印网页版或本文文末附的PDF)在文稿上演算,从而享受随时随地思考、演算的极致快感。

        OK,还是那句话,有任何问题,欢迎任何人随时不吝指正 & 赐教,感谢。

     

     

    第一层、了解SVM

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

    1.1、分类标准的起源:Logistic回归

        理解SVM,咱们必须先弄清楚一个概念:线性分类器。

        给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点,用y表示类别(y可以取1或者-1,分别代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),这个超平面的方程可以表示为( wT中的T代表转置):

                                                               

        可能有读者对类别取1或-1有疑问,事实上,这个1或-1的分类标准起源于logistic回归

        Logistic回归目的是从特征学习出一个0/1分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用logistic函数(或称作sigmoid函数)将自变量映射到(0,1)上,映射后的值被认为是属于y=1的概率。

        假设函数

        其中x是n维特征向量,函数g就是logistic函数。

        而的图像是

        可以看到,将无穷映射到了(0,1)。

        而假设函数就是特征属于y=1的概率。

        从而,当我们要判别一个新来的特征属于哪个类时,只需求即可,若大于0.5就是y=1的类,反之属于y=0类。

        此外,只和有关,>0,那么,而g(z)只是用来映射,真实的类别决定权还是在于。再者,当时,=1,反之=0。如果我们只从出发,希望模型达到的目标就是让训练数据中y=1的特征,而是y=0的特征。Logistic回归就是要学习得到,使得正例的特征远大于0,负例的特征远小于0,而且要在全部训练实例上达到这个目标。

        接下来,尝试把logistic回归做个变形。首先,将使用的结果标签y = 0和y = 1替换为y = -1,y = 1,然后将)中的替换为b,最后将后面的替换为(即)。如此,则有了。也就是说除了y由y=0变为y=-1外,线性分类函数跟logistic回归的形式化表示没区别。

        进一步,可以将假设函数中的g(z)做一个简化,将其简单映射到y=-1和y=1上。映射关系如下:

    1.2、线性分类的一个例子

        下面举个简单的例子。如下图所示,现在有一个二维平面,平面上有两种不同的数据,分别用圈和叉表示。由于这些数据是线性可分的,所以可以用一条直线将这两类数据分开,这条直线就相当于一个超平面,超平面一边的数据点所对应的y全是-1 ,另一边所对应的y全是1。

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

        注:有的资料上定义特征到结果的输出函数与这里定义的实质是一样的。为什么?因为无论是,还是,不影响最终优化结果。下文你将看到,当我们转化到优化的时候,为了求解方便,会把yf(x)令为1,即yf(x)是y(w^x + b),还是y(w^x - b),对我们要优化的式子max1/||w||已无影响。

        (有一朋友飞狗来自Mare_Desiderii,看了上面的定义之后,问道:请教一下SVM functional margin 为=y(wTx+b)=yf(x)中的Y是只取1和-1 吗?y的唯一作用就是确保functional margin的非负性?真是这样的么?当然不是,详情请见本文评论下第43楼

        换言之,在进行分类的时候,遇到一个新的数据点x,将x代入f(x) 中,如果f(x)小于0则将x的类别赋为-1,如果f(x)大于0则将x的类别赋为1。

        接下来的问题是,如何确定这个超平面呢?从直观上而言,这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以,得寻找有着最大间隔的超平面。

    1.3、函数间隔Functional margin与几何间隔Geometrical margin 

        在超平面w*x+b=0确定的情况下,|w*x+b|能够表示点x到距离超平面的远近,而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确,所以,可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此,我们便引出了函数间隔(functional margin)的概念。

        定义函数间隔(用表示)为:

        而超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值(其中,x是特征,y是结果标签,i表示第i个样本),便为超平面(w, b)关于训练数据集T的函数间隔:

         mini  (i=1,...n)

        但这样定义的函数间隔有问题,即如果成比例的改变w和b(如将它们改成2w和2b),则函数间隔的值f(x)却变成了原来的2倍(虽然此时超平面没有改变),所以只有函数间隔还远远不够。

        事实上,我们可以对法向量w加些约束条件,从而引出真正定义点到超平面的距离--几何间隔(geometrical margin)的概念。

        假定对于一个点 x ,令其垂直投影到超平面上的对应点为 x0 ,w 是垂直于超平面的一个向量,为样本x到超平面的距离,如下图所示:

    根据平面几何知识,有

        其中||w||为w的二阶范数(范数是一个类似于模的表示长度的概念),是单位向量(一个向量除以它的模称之为单位向量)。

        又由于x0 是超平面上的点,满足 f(x0)=0,代入超平面的方程,可得,即

        随即让此式的两边同时乘以,再根据,即可算出γ: 

      为了得到的绝对值,令乘上对应的类别 y,即可得出几何间隔(用表示)的定义:

        从上述函数间隔和几何间隔的定义可以看出:几何间隔就是函数间隔除以||w||,而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|,只是人为定义的一个间隔度量,而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

     

    1.4、最大间隔分类器Maximum Margin Classifier的定义

        对一个数据点进行分类,当超平面离数据点的“间隔”越大,分类的确信度(confidence)也越大。所以,为了使得分类的确信度尽量高,需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的Gap的一半。

        通过由前面的分析可知:函数间隔不适合用来最大化间隔值,因为在超平面固定以后,可以等比例地缩放w的长度和b的值,这样可以使得的值任意大,亦即函数间隔可以在超平面保持不变的情况下被取得任意大。但几何间隔因为除上了,使得在缩放w和b的时候几何间隔的值是不会改变的,它只随着超平面的变动而变动,因此,这是更加合适的一个间隔。换言之,这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔。

       于是最大间隔分类器(maximum margin classifier的目标函数可以定义为:

        同时需满足一些条件,根据间隔的定义,有

        其中,s.t.,即subject to的意思,它导出的是约束条件。

        回顾下几何间隔的定义,可知:如果令函数间隔等于1(之所以令等于1,是为了方便推导和优化,且这样做对目标函数的优化没有影响,至于为什么,请见本文评论下第42楼回复),则有 = 1 / ||w||且,从而上述目标函数转化成了

        相当于在相应的约束条件下,最大化这个1/||w||值,而1/||w||便是几何间隔。   

        如下图所示,中间的实线便是寻找到的最优超平面(Optimal Hyper Plane),其到两条虚线边界的距离相等,这个距离便是几何间隔,两条虚线间隔边界之间的距离等于2,而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上,所以它们满足(还记得我们把 functional margin 定为 1 了吗?上节中:处于方便推导和优化的目的,我们可以令=1),而对于所有不是支持向量的点,则显然有

        OK,到此为止,算是了解到了SVM的第一层,对于那些只关心怎么用SVM的朋友便已足够,不必再更进一层深究其更深的原理。

     

    第二层、深入SVM

    2.1、从线性可分到线性不可分

    2.1.1、从原始问题到对偶问题的求解

        接着考虑之前得到的目标函数:

         由于求的最大值相当于求的最小值,所以上述目标函数等价于(w由分母变成分子,从而也有原来的max问题变为min问题,很明显,两者问题等价):

        因为现在的目标函数是二次的,约束条件是线性的,所以它是一个凸二次规划问题。这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之:在一定的约束条件下,目标最优,损失最小。

        此外,由于这个问题的特殊结构,还可以通过拉格朗日对偶性(Lagrange Duality)变换到对偶变量 (dual variable) 的优化问题,即通过求解与原问题等价的对偶问题(dual problem)得到原始问题的最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题。

         那什么是拉格朗日对偶性呢?简单来讲,通过给每一个约束条件加上一个拉格朗日乘子(Lagrange multiplier),定义拉格朗日函数(通过拉格朗日函数将约束条件融合到目标函数里去,从而只用一个函数表达式便能清楚的表达出我们的问题):

        然后令

        容易验证,当某个约束条件不满足时,例如,那么显然有(只要令即可)。而当所有约束条件都满足时,则最优值为,亦即最初要最小化的量。

        因此,在要求约束条件得到满足的情况下最小化,实际上等价于直接最小化(当然,这里也有约束条件,就是≥0,i=1,…,n)   ,因为如果约束条件没有得到满足,会等于无穷大,自然不会是我们所要求的最小值。

        具体写出来,目标函数变成了:

        这里用表示这个问题的最优值,且和最初的问题是等价的。如果直接求解,那么一上来便得面对w和b两个参数,而又是不等式约束,这个求解过程不好做。不妨把最小和最大的位置交换一下,变成:

        交换以后的新问题是原始问题的对偶问题,这个新问题的最优值用来表示。而且有,在满足某些条件的情况下,这两者相等,这个时候就可以通过求解对偶问题来间接地求解原始问题。

        换言之,之所以从minmax的原始问题,转化为maxmin的对偶问题,一者因为的近似解,二者,转化为对偶问题后,更容易求解。

        下面可以先求L 对w、b的极小,再求L 对的极大。

    2.1.2、KKT条件

        上文中提到“在满足某些条件的情况下,两者等价”,这所谓的“满足某些条件”就是要满足KKT条件。

      勘误:经读者qq_28543029指出,这里的条件不应该是KKT条件,要让两者等价需满足strong duality (强对偶),而后有学者在强对偶下提出了KKT条件,且KKT条件的成立要满足constraint qualifications,而constraint qualifications之一就是Slater条件。所谓Slater 条件,即指:凸优化问题,如果存在一个点x,使得所有等式约束都成立,并且所有不等式约束都严格成立(即取严格不等号,而非等号),则满足Slater 条件。对于此处,Slater 条件成立,所以d*≤p*可以取等号。

        一般地,一个最优化数学模型能够表示成下列标准形式:

        其中,f(x)是需要最小化的函数,h(x)是等式约束,g(x)是不等式约束,p和q分别为等式约束和不等式约束的数量。

        同时,得明白以下两点:

    • 凸优化的概念:\mathcal{X} \subset \mathbb{R}^n 为一凸集, f:\mathcal{X}\to \mathbb{R} 为一凸函数。凸优化就是要找出一点 x^\ast \in \mathcal{X} ,使得每一 x \in \mathcal{X} 满足 f(x^\ast)\le f(x) 。
    • KKT条件的意义:它是一个非线性规划(Nonlinear Programming)问题能有最优化解法的必要和充分条件。

        而KKT条件就是指上面最优化数学模型的标准形式中的最小点 x* 必须满足下面的条件:

        经过论证,我们这里的问题是满足 KKT 条件的(首先已经满足Slater条件,再者f和gi也都是可微的,即L对w和b都可导),因此现在我们便转化为求解第二个问题。

        也就是说,原始问题通过满足KKT条件,已经转化成了对偶问题。而求解这个对偶学习问题,分为3个步骤:首先要让L(w,b,a) 关于 w 和 b 最小化,然后求对的极大,最后利用SMO算法求解对偶问题中的拉格朗日乘子。

    2.1.3、对偶问题求解的3个步骤

        (1)、首先固定要让 L 关于 w 和 b 最小化,我们分别对w,b求偏导数,即令 ∂L/∂w 和 ∂L/∂b 等于零(对w求导结果的解释请看本文评论下第45楼回复):

        将以上结果代入之前的L: 

        得到:

        提醒:有读者可能会问上述推导过程如何而来?说实话,其具体推导过程是比较复杂的,如下图所示:

          最后,得到:

        如 jerrylead所说:“倒数第4步”推导到“倒数第3步”使用了线性代数的转置运算,由于ai和yi都是实数,因此转置后与自身一样。“倒数第3步”推导到“倒数第2步”使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则。最后一步是上一步的顺序调整。

        从上面的最后一个式子,我们可以看出,此时的拉格朗日函数只包含了一个变量,那就是(求出了便能求出w,和b,由此可见,上文第1.2节提出来的核心问题:分类函数也就可以轻而易举的求出来了)。

        (2)、求对的极大,即是关于对偶问题的最优化问题。经过上面第一个步骤的求w和b,得到的拉格朗日函数式子已经没有了变量w,b,只有。从上面的式子得到:

        这样,求出了,根据,即可求出w,然后通过,即可求出b,最终得出分离超平面和分类决策函数。

        (3)在求得L(w, b, a) 关于 w 和 b 最小化,以及对的极大之后,最后一步则可以利用SMO算法求解对偶问题中的拉格朗日乘子

           上述式子要解决的是在参数上求最大值W的问题,至于都是已知数要了解这个SMO算法是如何推导的,请跳到下文第3.5节、SMO算法。

        到目前为止,我们的 SVM 还比较弱,只能处理线性的情况,下面我们将引入核函数,进而推广到非线性分类问题。

    2.1.4、线性不可分的情况

        OK,为过渡到下节2.2节所介绍的核函数,让我们再来看看上述推导过程中得到的一些有趣的形式。首先就是关于我们的 hyper plane ,对于一个数据点 x 进行分类,实际上是通过把 x 带入到算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到 

        因此分类函数为:

        这里的形式的有趣之处在于,对于新点 x的预测,只需要计算它与训练数据点的内积即可(表示向量内积),这一点至关重要,是之后使用 Kernel 进行非线性推广的基本前提。此外,所谓 Supporting Vector 也在这里显示出来——事实上,所有非Supporting Vector 所对应的系数都是等于零的,因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。

        为什么非支持向量对应的等于零呢?直观上来理解的话,就是这些“后方”的点——正如我们之前分析过的一样,对超平面是没有影响的,由于分类完全有超平面决定,所以这些无关的点并不会参与分类问题的计算,因而也就不会产生任何影响了。

        回忆一下我们2.1.1节中通过 Lagrange multiplier得到的目标函数:

         注意到如果 xi 是支持向量的话,上式中红颜色的部分是等于 0 的(因为支持向量的 functional margin 等于 1 ),而对于非支持向量来说,functional margin 会大于 1 ,因此红颜色部分是大于零的,而又是非负的,为了满足最大化,必须等于 0 。这也就是这些非Supporting Vector 的点的局限性。 

        至此,我们便得到了一个maximum margin hyper plane classifier,这就是所谓的支持向量机(Support Vector Machine)。当然,到目前为止,我们的 SVM 还比较弱,只能处理线性的情况,不过,在得到了对偶dual 形式之后,通过 Kernel 推广到非线性的情况就变成了一件非常容易的事情了(相信,你还记得本节开头所说的:“通过求解对偶问题得到最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题”)。

    2.2、核函数Kernel

    2.2.1、特征空间的隐式映射:核函数

        事实上,大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在。在上文中,我们已经了解到了SVM处理线性可分的情况,那对于非线性的数据SVM咋处理呢?对于非线性的情况,SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ,通过将数据映射到高维空间,来解决在原始空间中线性不可分的问题。

        具体来说,在线性不可分的情况下,支持向量机首先在低维空间中完成计算,然后通过核函数将输入空间映射到高维特征空间,最终在高维特征空间中构造出最优分离超平面,从而把平面上本身不好分的非线性数据分开。如图所示,一堆数据在二维空间无法划分,从而映射到三维空间里划分:

     

        而在我们遇到核函数之前,如果用原始的方法,那么在用线性学习器学习一个非线性关系,需要选择一个非线性特征集,并且将数据写成新的表达形式,这等价于应用一个固定的非线性映射,将数据映射到特征空间,在特征空间中使用线性学习器,因此,考虑的假设集是这种类型的函数:

        这里ϕ:X->F是从输入空间到某个特征空间的映射,这意味着建立非线性学习器分为两步:

    1. 首先使用一个非线性映射将数据变换到一个特征空间F,
    2. 然后在特征空间使用线性学习器分类。

        而由于对偶形式就是线性学习器的一个重要性质,这意味着假设可以表达为训练点的线性组合,因此决策规则可以用测试点和训练点的内积来表示:

        如果有一种方式可以在特征空间中直接计算内积〈φ(xi · φ(x),就像在原始输入点的函数中一样,就有可能将两个步骤融合到一起建立一个非线性的学习器,这样直接计算法的方法称为核函数方法:

        核是一个函数K,对所有x,z(-X,满足,这里φ是从X到内积特征空间F的映射。

    2.2.2、核函数:如何处理非线性数据

        来看个核函数的例子。如下图所示的两类数据,分别分布为两个圆圈的形状,这样的数据本身就是线性不可分的,此时咱们该如何把这两类数据分开呢(下文将会有一个相应的三维空间图)?

        事实上,上图所述的这个数据集,是用两个半径不同的圆圈加上了少量的噪音生成得到的,所以,一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。如果用来表示这个二维平面的两个坐标的话,我们知道一条二次曲线(圆圈是二次曲线的一种特殊情况)的方程可以写作这样的形式:

        注意上面的形式,如果我们构造另外一个五维的空间,其中五个坐标的值分别为, , , ,那么显然,上面的方程在新的坐标系下可以写作:

        关于新的坐标,这正是一个 hyper plane 的方程!也就是说,如果我们做一个映射,将 按照上面的规则映射为,那么在新的空间中原来的数据将变成线性可分的,从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。

        再进一步描述 Kernel 的细节之前,不妨再来看看上述例子在映射过后的直观形态。当然,你我可能无法把 5 维空间画出来,不过由于我这里生成数据的时候用了特殊的情形,所以这里的超平面实际的方程是这个样子的(圆心在轴上的一个正圆):

        因此我只需要把它映射到这样一个三维空间中即可,下图即是映射之后的结果,将坐标轴经过适当的旋转,就可以很明显地看出,数据是可以通过一个平面来分开的(pluskid:下面的gif 动画,先用 Matlab 画出一张张图片,再用 Imagemagick 拼贴成):

        核函数相当于把原来的分类函数:

        映射成:

        而其中的可以通过求解如下 dual 问题而得到的:

        这样一来问题就解决了吗?似乎是的:拿到非线性数据,就找一个映射,然后一股脑把原来的数据映射到新空间中,再做线性 SVM 即可。不过事实上好像并没有这么简单。

        细想一下,刚才的方法是不是有问题?

    • 在最初的例子里,我们对一个二维空间做映射,选择的新空间是原始空间的所有一阶和二阶的组合,得到了五个维度;
    • 如果原始空间是三维(一阶、二阶和三阶的组合),那么我们会得到:3(一次)+3(二次交叉)+3(平方)+3(立方)+1(x1*x2*x3)+2*3(交叉,一个一次一个二次,类似x1*x2^2) = 19维的新空间,这个数目是呈指数级爆炸性增长的,从而势必这给的计算带来非常大的困难,而且如果遇到无穷维的情况,就根本无从计算了。

        这个时候,可能就需要 Kernel 出马了。

        不妨还是从最开始的简单例子出发,设两个向量,而即是到前面说的五维空间的映射,因此映射过后的内积为:

            (公式说明:上面的这两个推导过程中,所说的前面的五维空间的映射,这里说的前面便是文中2.2.1节的所述的映射方式,回顾下之前的映射规则,再看那第一个推导,其实就是计算x1,x2各自的内积,然后相乘相加即可,第二个推导则是直接平方,去掉括号,也很容易推出来)

        另外,我们又注意到:

         二者有很多相似的地方,实际上,我们只要把某几个维度线性缩放一下,然后再加上一个常数维度,具体来说,上面这个式子的计算结果实际上和映射

         之后的内积的结果是相等的,那么区别在于什么地方呢?

    1. 一个是映射到高维空间中,然后再根据内积的公式进行计算;
    2. 而另一个则直接在原来的低维空间中进行计算,而不需要显式地写出映射后的结果

        (公式说明:上面之中,最后的两个式子,第一个算式,是带内积的完全平方式,可以拆开,然后,通过凑一个得到,第二个算式,也是根据第一个算式凑出来的)

        回忆刚才提到的映射的维度爆炸,在前一种方法已经无法计算的情况下,后一种方法却依旧能从容处理,甚至是无穷维度的情况也没有问题。

        我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function) ,例如,在刚才的例子中,我们的核函数为:

        核函数能简化映射空间中的内积运算——刚好“碰巧”的是,在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子,现在我们的分类函数为:

        其中 由如下 dual 问题计算而得:

        这样一来计算的问题就算解决了,避开了直接在高维空间中进行计算,而结果却是等价的!当然,因为我们这里的例子非常简单,所以我可以手工构造出对应于的核函数出来,如果对于任意一个映射,想要构造出对应的核函数就很困难了。

    2.2.3、几个核函数

        通常人们会从一些常用的核函数中选择(根据问题和数据的不同,选择不同的参数,实际上就是得到了不同的核函数),例如:

    • 多项式核,显然刚才我们举的例子是这里多项式核的一个特例(R = 1,d = 2)。虽然比较麻烦,而且没有必要,不过这个核所对应的映射实际上是可以写出来的,该空间的维度是,其中 m 是原始空间的维度。
    • 高斯核,这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过,如果选得很大的话,高次特征上的权重实际上衰减得非常快,所以实际上(数值上近似一下)相当于一个低维的子空间;反过来,如果选得很小,则可以将任意的数据映射为线性可分——当然,这并不一定是好事,因为随之而来的可能是非常严重的过拟合问题。不过,总的来说,通过调控参数,高斯核实际上具有相当高的灵活性,也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间:
    • 线性核,这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说,咱们有的时候,写代码,或写公式的时候,只要写个模板或通用表达式,然后再代入不同的核,便可以了,于此,便在形式上统一了起来,不用再分别写一个线性的,和一个非线性的)。

    2.2.4、核函数的本质

            上面说了这么一大堆,读者可能还是没明白核函数到底是个什么东西?我再简要概括下,即以下三点:

    1. 实际中,我们会经常遇到线性不可分的样例,此时,我们的常用做法是把样例特征映射到高维空间中去(如上文2.2节最开始的那幅图所示,映射到高维空间后,相关特征便被分开了,也就达到了分类的目的);
    2. 但进一步,如果凡是遇到线性不可分的样例,一律映射到高维空间,那么这个维度大小是会高到可怕的(如上文中19维乃至无穷维的例子)。那咋办呢?
    3. 此时,核函数就隆重登场了,核函数的价值在于它虽然也是将特征进行从低维到高维的转换,但核函数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高维上,也就如上文所说的避免了直接在高维空间中的复杂计算。

        最后引用这里的一个例子举例说明下核函数解决非线性问题的直观效果。

        假设现在你是一个农场主,圈养了一批羊群,但为预防狼群袭击羊群,你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢?你很可能需要依据牛群和狼群的位置建立一个“分类器”,比较下图这几种不同的分类器,我们可以看到SVM完成了一个很完美的解决方案。

        这个例子从侧面简单说明了SVM使用非线性分类器的优势,而逻辑模式以及决策树模式都是使用了直线方法。

        OK,不再做过多介绍了,对核函数有进一步兴趣的,还可以看看此文

    2.3、使用松弛变量处理 outliers 方法

        在本文第一节最开始讨论支持向量机的时候,我们就假定,数据是线性可分的,亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据,在上文2.2节使用 Kernel 方法对原来的线性 SVM 进行了推广,使得非线性的的情况也能处理。虽然通过映射将原始数据映射到高维空间之后,能够线性分隔的概率大大增加,但是对于某些情况还是很难处理。

        例如可能并不是因为数据本身是非线性结构的,而只是因为数据有噪音。对于这种偏离正常位置很远的数据点,我们称之为 outlier ,在我们原来的 SVM 模型里,outlier 的存在有可能造成很大的影响,因为超平面本身就是只有少数几个 support vector 组成的,如果这些 support vector 里又存在 outlier 的话,其影响就很大了。例如下图:

        用黑圈圈起来的那个蓝点是一个 outlier ,它偏离了自己原本所应该在的那个半空间,如果直接忽略掉它的话,原来的分隔超平面还是挺好的,但是由于这个 outlier 的出现,导致分隔超平面不得不被挤歪了,变成途中黑色虚线所示(这只是一个示意图,并没有严格计算精确坐标),同时 margin 也相应变小了。当然,更严重的情况是,如果这个 outlier 再往右上移动一些距离的话,我们将无法构造出能将数据分开的超平面来。

        为了处理这种情况,SVM 允许数据点在一定程度上偏离一下超平面。例如上图中,黑色实线所对应的距离,就是该 outlier 偏离的距离,如果把它移动回来,就刚好落在原来的 超平面 蓝色间隔边界上,而不会使得超平面发生变形了。

        插播下一位读者@Copper_PKU的理解:换言之,在有松弛的情况下outline点也属于支持向量SV,同时,对于不同的支持向量,拉格朗日参数的值也不同,如此篇论文《Large Scale Machine Learning》中的下图所示:

        对于远离分类平面的点值为0;对于边缘上的点值在[0, 1/L]之间,其中,L为训练数据集个数,即数据集大小;对于outline数据和内部的数据值为1/L。更多请参看本文文末参考条目第51条。

        OK,继续回到咱们的问题。我们,原来的约束条件为:

        现在考虑到outlier问题,约束条件变成了:

        其中称为松弛变量 (slack variable) ,对应数据点允许偏离的 functional margin 的量。当然,如果我们运行任意大的话,那任意的超平面都是符合条件的了。所以,我们在原来的目标函数后面加上一项,使得这些的总和也要最小:

        其中 是一个参数,用于控制目标函数中两项(“寻找 margin 最大的超平面”和“保证数据点偏差量最小”)之间的权重。注意,其中 是需要优化的变量(之一),而 是一个事先确定好的常量。完整地写出来是这个样子:

        用之前的方法将限制或约束条件加入到目标函数中,得到新的拉格朗日函数,如下所示:

         分析方法和前面一样,转换为另一个问题之后,我们先让针对最小化:

         将  带回 并化简,得到和原来一样的目标函数:

         不过,由于我们得到而又有(作为 Lagrange multiplier 的条件),因此有,所以整个 dual 问题现在写作:

        把前后的结果对比一下(错误修正:图中的Dual formulation中的Minimize应为maxmize):

        可以看到唯一的区别就是现在 dual variable  多了一个上限 。而 Kernel 化的非线性形式也是一样的,只要把换成即可。这样一来,一个完整的,可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。

        行文至此,可以做个小结,不准确的说,SVM它本质上即是一个分类方法,用w^T+b定义分类函数,于是求w、b,为寻最大间隔,引出1/2||w||^2,继而引入拉格朗日因子,化为对拉格朗日乘子a的求解(求解过程中会涉及到一系列最优化或凸二次规划等问题),如此,求w.b与求a等价,而a的求解可以用一种快速学习算法SMO,至于核函数,是为处理非线性情况,若直接映射到高维计算恐维度爆炸,故在低维计算,等效高维表现。

        OK,理解到这第二层,已经能满足绝大部分人一窥SVM原理的好奇心,然对于那些想在证明层面理解SVM的则还很不够,但进入第三层理解境界之前,你必须要有比较好的数理基础和逻辑证明能力,不然你会跟我一样,吃不少苦头的。

     

    第三层、证明SVM

        说实话,凡是涉及到要证明的东西.理论,便一般不是怎么好惹的东西。绝大部分时候,看懂一个东西不难,但证明一个东西则需要点数学功底,进一步,证明一个东西也不是特别难,难的是从零开始发明创造这个东西的时候,则显艰难(因为任何时代,大部分人的研究所得都不过是基于前人的研究成果,前人所做的是开创性工作,而这往往是最艰难最有价值的,他们被称为真正的先驱。牛顿也曾说过,他不过是站在巨人的肩上。你,我则更是如此)。

        正如陈希孺院士在他的著作《数理统计学简史》的第4章、最小二乘法中所讲:在科研上诸多观念的革新和突破是有着很多的不易的,或许某个定理在某个时期由某个人点破了,现在的我们看来一切都是理所当然,但在一切没有发现之前,可能许许多多的顶级学者毕其功于一役,耗尽一生,努力了几十年最终也是无功而返。

        话休絮烦,要证明一个东西先要弄清楚它的根基在哪,即构成它的基础是哪些理论。OK,以下内容基本是上文中未讲到的一些定理的证明,包括其背后的逻辑、来源背景等东西,还是读书笔记。

    本部分导述

    • 3.1节线性学习器中,主要阐述感知机算法;
    • 3.2节非线性学习器中,主要阐述mercer定理;
    • 3.3节、损失函数;
    • 3.4节、最小二乘法;
    • 3.5节、SMO算法;
    • 3.6节、简略谈谈SVM的应用;

    3.1、线性学习器

    3.1.1、感知机算法

        这个感知机算法是1956年提出的,年代久远,依然影响着当今,当然,可以肯定的是,此算法亦非最优,后续会有更详尽阐述。不过,有一点,你必须清楚,这个算法是为了干嘛的:不断的训练试错以期寻找一个合适的超平面(是的,就这么简单)。

        下面,举个例子。如下图所示,凭我们的直觉可以看出,图中的红线是最优超平面,蓝线则是根据感知机算法在不断的训练中,最终,若蓝线能通过不断的训练移动到红线位置上,则代表训练成功。

        既然需要通过不断的训练以让蓝线最终成为最优分类超平面,那么,到底需要训练多少次呢?Novikoff定理告诉我们当间隔是正的时候感知机算法会在有限次数的迭代中收敛,也就是说Novikoff定理证明了感知机算法的收敛性,即能得到一个界,不至于无穷循环下去。

    •  Novikoff定理:如果分类超平面存在, 仅需在序列S上迭代几次,在界为的错误次数下就可以找到分类超平面,算法停止。

        这里为扩充间隔。根据误分次数公式可知, 迭代次数与对应于扩充(包括偏置)权重的训练集的间隔有关。

        顺便再解释下这个所谓的扩充间隔即为样本到分类间隔的距离,即从引出的最大分类间隔。OK,还记得上文第1.3节开头的内容么?如下:

        在给出几何间隔的定义之前,咱们首先来看下,如上图所示,对于一个点x,令其垂直投影到超平面上的对应的为x0,由于w是垂直于超平面的一个向量,为样本x到分类间隔的距离,我们有

        然后后续怎么推导出最大分类间隔请回到本文第一、二部分,此处不重复板书。

        同时有一点得注意:感知机算法虽然可以通过简单迭代对线性可分数据生成正确分类的超平面,但不是最优效果,那怎样才能得到最优效果呢,就是上文中第一部分所讲的寻找最大分类间隔超平面。此外,Novikoff定理的证明请见这里

    3.2、非线性学习器

    3.2.1、Mercer定理

        Mercer定理 :如果函数K是上的映射(也就是从两个n维向量映射到实数域)。那么如果K是一个有效核函数(也称为Mercer核函数),那么当且仅当对于训练样例,其相应的核函数矩阵是对称半正定的。 

        要理解这个Mercer定理,先要了解什么是半正定矩阵,要了解什么是半正定矩阵,先得知道什么是正定矩阵(矩阵理论博大精深,关于矩阵推荐我正在看的一本《矩阵分析与应用》)。然后这里有一个此定理的证明,可以看下。

        正如@Copper_PKU所说:核函数在SVM的分类效果中起了重要的作用,最后这里有个tutorial可以看看。

    3.3、损失函数

        在本文1.0节有这么一句话“支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法,通过寻求结构化风险最小来提高学习机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量较少的情况下,亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险,什么又是经验风险。要了解这两个所谓的“风险”,还得又从监督学习说起。

        监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏,模型每一次预测的好坏用损失函数来度量。它从假设空间F中选择模型f作为决策函数,对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致,用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。

        常用的损失函数有以下几种(基本引用自《统计学习方法》):

         

        如此,SVM有第二种理解,即最优化+损失最小,或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM,boosting,LR等算法,可能会有不同收获”。

        OK,关于更多统计学习方法的问题,请参看此文

        关于损失函数,如下文读者评论中所述:可以看看张潼的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性,优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外,张潼还有另外一篇论文《Statistical analysis of some multi-category large margin classification methods》,在多分类情况下margin loss的分析,这两篇对Boosting和SVM使用的损失函数分析的很透彻。

    3.4、最小二乘法

    3.4.1、什么是最小二乘法?

        既然本节开始之前提到了最小二乘法,那么下面引用《正态分布的前世今生》里的内容稍微简单阐述下。

        我们口头中经常说:一般来说,平均来说。如平均来说,不吸烟的健康优于吸烟者,之所以要加“平均”二字,是因为凡事皆有例外,总存在某个特别的人他吸烟但由于经常锻炼所以他的健康状况可能会优于他身边不吸烟的朋友。而最小二乘法的一个最简单的例子便是算术平均。

        最小二乘法(又称最小平方法)是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据,并使得这些求得的数据与实际数据之间误差的平方和为最小。用函数表示为:

      使误差「所谓误差,当然是观察值与实际真实值的差量」平方和达到最小以寻求估计值的方法,就叫做最小二乘法,用最小二乘法得到的估计,叫做最小二乘估计。当然,取平方和作为目标函数只是众多可取的方法之一。

       最小二乘法的一般形式可表示为:

        有效的最小二乘法是勒让德在 1805 年发表的,基本思想就是认为测量中有误差,所以所有方程的累积误差为

        我们求解出导致累积误差最小的参数即可:

        勒让德在论文中对最小二乘法的优良性做了几点说明:

    •  最小二乘使得误差平方和最小,并在各个方程的误差之间建立了一种平衡,从而防止某一个极端误差取得支配地位
    •  计算中只要求偏导后求解线性方程组,计算过程明确便捷
    • 最小二乘可以导出算术平均值作为估计值

        对于最后一点,从统计学的角度来看是很重要的一个性质。推理如下:假设真值为,x1, ... , xn为n次测量值, 每次测量的误差为ei = xi - ,按最小二乘法,误差累积为

        求解 使达到最小,正好是算术平均

        由于算术平均是一个历经考验的方法,而以上的推理说明,算术平均是最小二乘的一个特例,所以从另一个角度说明了最小二乘方法的优良性,使我们对最小二乘法更加有信心。

        最小二乘法发表之后很快得到了大家的认可接受,并迅速的在数据分析实践中被广泛使用。不过历史上又有人把最小二乘法的发明归功于高斯,这又是怎么一回事呢。高斯在1809年也发表了最小二乘法,并且声称自己已经使用这个方法多年。高斯发明了小行星定位的数学方法,并在数据分析中使用最小二乘方法进行计算,准确的预测了谷神星的位置。

        说了这么多,貌似跟本文的主题SVM没啥关系呀,别急,请让我继续阐述。本质上说,最小二乘法即是一种参数估计方法,说到参数估计,咱们得从一元线性模型说起。

    3.4.2、最小二乘法的解法

        什么是一元线性模型呢? 请允许我引用这里的内容,先来梳理下几个基本概念:

    • 监督学习中,如果预测的变量是离散的,我们称其为分类(如决策树,支持向量机等),如果预测的变量是连续的,我们称其为回归。
    • 回归分析中,如果只包括一个自变量和一个因变量,且二者的关系可用一条直线近似表示,这种回归分析称为一元线性回归分析。
    • 如果回归分析中包括两个或两个以上的自变量,且因变量和自变量之间是线性关系,则称为多元线性回归分析。
    • 对于二维空间线性是一条直线;对于三维空间线性是一个平面,对于多维空间线性是一个超平面...   

        对于一元线性回归模型, 假设从总体中获取了n组观察值(X1,Y1),(X2,Y2), …,(Xn,Yn)。对于平面中的这n个点,可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看,这条直线处于样本数据的中心位置最合理。 

        选择最佳拟合曲线的标准可以确定为:使总的拟合误差(即总残差)达到最小。有以下三个标准可以选择:        

    1. 用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。
    2. 用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。
    3. 最小二乘法的原则是以“残差平方和最小”确定直线位置。用最小二乘法除了计算比较方便外,得到的估计量还具有优良特性。这种方法对异常值非常敏感。  

         最常用的是普通最小二乘法( Ordinary  Least Square,OLS):所选择的回归模型应该使所有观察值的残差平方和达到最小,即采用平方损失函数。  

         我们定义样本回归模型为:

        其中ei为样本(Xi, Yi)的误差。

        接着,定义平方损失函数Q:

        则通过Q最小确定这条直线,即确定,以为变量,把它们看作是Q的函数,就变成了一个求极值的问题,可以通过求导数得到。

        求Q对两个待估参数的偏导数:

        根据数学知识我们知道,函数的极值点为偏导为0的点。   

        解得:

            

        这就是最小二乘法的解法,就是求得平方损失函数的极值点。自此,你看到求解最小二乘法与求解SVM问题何等相似,尤其是定义损失函数,而后通过偏导求得极值。

       OK,更多请参看陈希孺院士的《数理统计学简史》的第4章、最小二乘法。

    3.5、SMO算法

        在上文中,我们提到了求解对偶问题的序列最小最优化SMO算法,但并未提到其具体解法。首先看下最后悬而未决的问题:

        等价于求解:

        1998年,Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法:SMO算法,它很快便成为最快的二次规划优化算法,特别是在针对线性SVM和数据稀疏时性能更优。

        接下来,咱们便参考John C. Platt的这篇文章来看看SMO的解法是怎样的。

    3.5.1、SMO算法的推导

        咱们首先来定义特征到结果的输出函数:

        注:这个u与我们之前定义的实质是一样的。

        接着,重新定义下咱们原始的优化问题,权当重新回顾,如下:

        求导得到:

        代入中,可得

        通过引入拉格朗日乘子转换为对偶问题后,得:

      s.t:

        注:这里得到的min函数与我们之前的max函数实质也是一样,因为把符号变下,即由min转化为max的问题,且yi也与之前的等价,yj亦如此。

        经过加入松弛变量后,模型修改为:

        从而最终我们的问题变为:

        下面要解决的问题是:在上求上述目标函数的最小值。为了求解这些乘子,每次从中任意抽取两个乘子,然后固定以外的其它乘子,使得目标函数只是关于的函数。这样,不断的从一堆乘子中任意抽取两个求解,不断的迭代求解子问题,最终达到求解原问题的目的。

        而原对偶问题的子问题的目标函数可以表达为:

        其中

        为了解决这个子问题,首要问题便是每次如何选取。实际上,其中一个乘子是违法KKT条件最严重的,另外一个乘子则由另一个约束条件选取。

        根据KKT条件可以得出目标函数中取值的意义:

        这里的还是拉格朗日乘子:

    1. 对于第1种情况,表明是正常分类,在间隔边界内部(我们知道正确分类的点);
    2. 对于第2种情况,表明了是支持向量,在间隔边界上;
    3. 对于第3种情况,表明了是在两条间隔边界之间;

        而最优解需要满足KKT条件,即上述3个条件都得满足,以下几种情况出现将会出现不满足:

    • <=1但是<C则是不满足的,而原本=C
    • >=1但是>0则是不满足的,而原本=0
    • =1但是=0或者=C则表明不满足的,而原本应该是0<<C

        也就是说,如果存在不满足KKT条件的,那么需要更新这些,这是第一个约束条件。此外,更新的同时还要受到第二个约束条件的限制,即

        因此,如果假设选择的两个乘子,它们在更新之前分别是,更新之后分别是,那么更新前后的值需要满足以下等式才能保证和为0的约束:

        其中,是常数。

        两个因子不好同时求解,所以可先求第二个乘子的解(),得到的解()之后,再用的解()表示的解()。

        为了求解,得先确定的取值范围。假设它的上下边界分别为H和L,那么有:

        接下来,综合这两个约束条件,求取的取值范围。

        当y1 != y2时,根据可得,所以有,如下图所示:

        当y1 = y2时,同样根据可得:,所以有,如下图所示:

        如此,根据y1和y2异号或同号,可得出的上下界分别为:

        回顾下第二个约束条件,令上式两边乘以y1,可得

        其中,

        因此可以用表示,,从而把子问题的目标函数转换为只含的问题:

        对求导,可得

        化简下:

        然后将、和代入上式可得:

     

     

        令(表示预测值与真实值之差),,然后上式两边同时除以,得到一个关于单变量的解:

        这个解没有考虑其约束条件,即是未经剪辑时的解。

        然后考虑约束可得到经过剪辑后的的解析解为:

        求出了后,便可以求出,得

        那么如何选择乘子呢?

    • 对于,即第一个乘子,可以通过刚刚说的那3种不满足KKT的条件来找;
    • 而对于第二个乘子可以寻找满足条件:的乘子。

        而b在满足下述条件:

        下更新b:

        且每次更新完两个乘子的优化后,都需要再重新计算b,及对应的Ei值。

        最后更新所有,y和b,这样模型就出来了,从而即可求出咱们开头提出的分类函数:

        此外,这里也有一篇类似的文章,大家可以参考下。

    3.5.2、SMO算法的步骤

        综上,总结下SMO的主要步骤,如下:

        意思是,

    1. 第一步选取一对,选取方法使用启发式方法;
    2. 第二步,固定除之外的其他参数,确定W极值条件下的表示。

        假定在某一次迭代中,需要更新对应的拉格朗日乘子,那么这个小规模的二次规划问题写为:

        那么在每次迭代中,如何更新乘子呢?引用这里的两张PPT说明下:

        知道了如何更新乘子,那么选取哪些乘子进行更新呢?具体选择方法有以下两个步骤:

    1. 步骤1:先“扫描”所有乘子,把第一个违反KKT条件的作为更新对象,令为a1;
    2. 步骤2:在所有不违反KKT条件的乘子中,选择使|E1 −E2|最大的a2进行更新,使得能最大限度增大目标函数的值(类似于梯度下降. 此外,而,求出来的E代表函数ui对输入xi的预测值与真实输出类标记yi之差)。

        最后,每次更新完两个乘子的优化后,都需要再重新计算b,及对应的Ei值。

        综上,SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到极致,SMO算法每次迭代只选出两个分量ai和aj进行调整,其它分量则保持固定不变,在得到解ai和aj之后,再用ai和aj改进其它分量。与通常的分解算法比较,尽管它可能需要更多的迭代次数,但每次迭代的计算量比较小,所以该算法表现出较好的快速收敛性,且不需要存储核矩阵,也没有矩阵运算。

    3.5.3、SMO算法的实现

        行文至此,我相信,SVM理解到了一定程度后,是的确能在脑海里从头至尾推导出相关公式的,最初分类函数,最大化分类间隔,max1/||w||,min1/2||w||^2,凸二次规划,拉格朗日函数,转化为对偶问题,SMO算法,都为寻找一个最优解,一个最优分类平面。一步步梳理下来,为什么这样那样,太多东西可以追究,最后实现。如下图所示:

        至于下文中将阐述的核函数则为是为了更好的处理非线性可分的情况,而松弛变量则是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。

        台湾的林智仁教授写了一个封装SVM算法的libsvm库,大家可以看看,此外这里还有一份libsvm的注释文档。

        除了在这篇论文《fast training of support vector machines using sequential minimal optimization》中platt给出了SMO算法的逻辑代码之外,这里也有一份SMO的实现代码,大家可以看下。

    3.6、SVM的应用

        或许我们已经听到过,SVM在很多诸如文本分类,图像分类,生物序列分析和生物数据挖掘,手写字符识别等领域有很多的应用,但或许你并没强烈的意识到,SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。

    3.6.1、文本分类

        一个文本分类系统不仅是一个自然语言处理系统,也是一个典型的模式识别系统,系统的输入是需要进行分类处理的文本,系统的输出则是与文本关联的类别。由于篇幅所限,其它更具体内容本文将不再详述。

        OK,本节虽取标题为证明SVM,但聪明的读者们想必早已看出,其实本部分并无多少证明部分(特此致歉),怎么办呢?可以参阅《支持向量机导论》一书,此书精简而有趣。本节完。

     

     

    读者评论

       本文发表后,微博上的很多朋友给了不少意见,以下是节选的一些精彩评论:

    1. “压力”陡增的评论→//@藏了个锋:我是看着July大神的博文长大的啊//@zlkysl:就是看了最后那一篇才决定自己的研究方向为SVM的。--http://weibo.com/1580904460/zraWk0u6u?mod=weibotime
    2. @张金辉:SVM的三重境界,不得不转的一篇。其实Coursera的课堂上Andrew Ng讲过支持向量机,但显然他没有把这作为重点,加上Ng讲支持向量机的方法我一时半会难以完全消化,所以听的也是一知半解。真正开始了解支持向量机就是看的这篇“三重境界”,之后才对这个算法有了大概的概念,以至如何去使用,再到其中的原理为何,再到支持向量机的证明等。总之,这篇文章开启了我长达数月的研究支持向量机阶段,直到今日--http://zhan.renren.com/profile/249335584?from=template#!//tag/三重境界
    3. @孤独之守望者:"最后,推出svm的cost function 是hinge loss,然后对比其他的方法的cost function,说明其实他们的目标函数很像,那么问题是svm为什么这么popular呢?您可以再加些VC dimension跟一些error bound的数学,点一下,提供一个思路和方向"。--http://weibo.com/1580904460/AiohoyDwq?mod=weibotime
    4. @夏粉_百度:在面试时,考察SVM可考察机器学习各方面能力:目标函数,优化过程,并行方法,算法收敛性,样本复杂度,适用场景,调参经验,不过个人认为考察boosting和LR也还不错啊。此外,随着统计机器学习不断进步,SVM只被当成使用了一个替代01损失hinge研究,更通用的方法被提出,损失函数研究替代损失与贝叶斯损失关系,算法稳定性研究替代损失与推广性能关系,凸优化研究如何求解凸目标函数,SVM,boosting等算法只是这些通用方法的一个具体组建而已。
    5. @居里猴姐:关于SVM损失函数的问题,可以看看张潼老师的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性,优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外,张潼老师还有另外一篇论文《Statistical analysis of some multi-category large margin classification methods》,在多分类情况下margin loss的分析,这两篇对Boosting和SVM使用的损失函数分析的很透彻。
    6. @夏粉_百度:SVM用了hinge损失,hinge损失不可导,不如其它替代损失方便优化并且转换概率麻烦。核函数也不太用,现在是大数据时代,样本非常大,无法想象一个n^2的核矩阵如何存储和计算。 而且,现在现在非线性一般靠深度学习了。//@Copper_PKU:请教svm在工业界的应用典型的有哪些?工业界如何选取核函数,经验的方法?svm的训练过程如何优化?
    7. @Copper_PKU:July的svm tutorial 我个人觉得还可以加入和修改如下部分:(1) 对于支持向量解释,可以结合图和拉格朗日参数来表达,松弛中sv没有写出来. (2) SMO算法部分,加入Joachims论文中提到的算法,以及SMO算法选取workset的方法,包括SMO算法的收敛判断,还有之前共轭梯度求解方法,虽然是较早的算法,但是对于理解SMO算法有很好的效果。模型的优化和求解都是迭代的过程,加入历史算法增强立体感。--  http://weibo.com/1580904460/Akw6dl3Yk#_rnd1385474436177
    8. //@廖临川: 之所以sgd对大训练集的效果更好,1.因为SGD优化每次迭代使用样本子集,比使用训练全集(尤其是百万数量级)要快得多;2.如果目标函数是凸的或者伪凸的,SGD几乎必然可以收敛到全局最优;否则,则收敛到局部最优;3.SGD一般不需要收敛到全局最优,只要得到足够好的解,就可以立即停止。//@Copper_PKU:sgd的核心思想:是迭代训练,每拿到一个样本就算出基于当前w(t) 的loss function,t代表训练第t次,然后进行下一w(t+1)的更新,w(t+1)=w(t)-(learning rate) * loss function的梯度,这个类比神经网络中bp中的参数训练方法。 sample by sample就是每次仅处理一个样本 而不是一个batch。
    9. //@Copper_PKU:从损失函数角度说:primal问题可以理解为正则化项+lossfunction,求解目标是在两个中间取平衡 如果强调loss function最小则会overfitting,所以有C参数。 //@研究者July:SVM还真就是在一定限定条件下,即约束条件下求目标函数的最优值问题,同时,为减少误判率,尽量让损失最小。
    10. ...

        非常享受这种全民大讨论的年代,没有谁一定就对或一定就错,而是各自发表各自的理解见解,真棒!

     

     

    参考文献及推荐阅读

    1. 支持向量机导论》,[英] Nello Cristianini / John Shawe-Taylor 著
    2. 支持向量机导论一书的支持网站:http://www.support-vector.net/
    3. 《数据挖掘导论》,[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著
    4. 《数据挖掘:概念与技术》,(加)Jiawei Han;Micheline Kamber 著;
    5. 《数据挖掘中的新方法:支持向量机》,邓乃扬 田英杰 著;
    6. 支持向量机--理论、算法和扩展》,邓乃扬 田英杰 著;
    7. 支持向量机系列pluskidhttp://blog.pluskid.org/?page_id=683
    8. http://www.360doc.com/content/07/0716/23/11966_615252.shtml
    9. 数据挖掘十大经典算法初探
    10. 《模式识别支持向量机指南》,C.J.C Burges 著;
    11. 统计学习方法》,李航著;
    12. 《统计自然语言处理》,宗成庆编著,第十二章、文本分类;
    13. SVM入门系列,Jasper:http://www.blogjava.net/zhenandaci/category/31868.html
    14. 最近邻决策和SVM数字识别的实现和比较,作者不详;
    15. 纯白板手推SVM:http://www.julyedu.com/video/play/18/429
    16. 斯坦福大学机器学习课程原始讲义:http://www.cnblogs.com/jerrylead/archive/2012/05/08/2489725.html
    17. 斯坦福机器学习课程笔记http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/
    18. http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html
    19. SMO算法的数学推导:http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
    20. 数据挖掘掘中所需的概率论与数理统计知识、上
    21. 关于机器学习方面的文章,可以读读:http://www.cnblogs.com/vivounicorn/category/289453.html
    22. 数学系教材推荐:http://blog.sina.com.cn/s/blog_5e638d950100dswh.html
    23. 《神经网络与机器学习(原书第三版)》,[加] Simon Haykin 著;
    24. 正态分布的前世今生:http://t.cn/zlH3Ygc
    25. 数理统计学简史》,陈希孺院士著;
    26. 《最优化理论与算法(第2版)》,陈宝林编著;
    27. A Gentle Introduction to Support Vector Machines in Biomedicinehttp://www.nyuinformatics.org/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf,此PPT很赞,除了对引入拉格朗日对偶变量后的凸二次规划问题的深入度不够之外,其它都挺好,配图很精彩,本文有几张图便引自此PPT中;
    28. 来自卡内基梅隆大学carnegie mellon university(CMU)的讲解SVM的PPT:http://www.autonlab.org/tutorials/svm15.pdf
    29. 发明libsvm的台湾林智仁教授06年的机器学习讲义SVM:http://wenku.baidu.com/link?url=PWTGMYNb4HGUrUQUZwTH2B4r8pIMgLMiWIK1ymVORrds_11VOkHwp-JWab7IALDiors64JW_6mD93dtuWHwFWxsAk6p0rzchR8Qh5_4jWHC
    30. http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf
    31. Introduction to Support Vector Machines (SVM),By Debprakash Patnai M.E (SSA),https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCwQFjAA&url=http%3a%2f%2fwww%2epws%2estu%2eedu%2etw%2fccfang%2findex%2efiles%2fAI%2fAI%26ML-Support%2520Vector%2520Machine-1%2eppt&ei=JRR6UqT5C-iyiQfWyIDgCg&usg=AFQjCNGw1fTbpH4ltQjjmx1d25ZqbCN9nA
    32. 多人推荐过的libsvmhttp://www.csie.ntu.edu.tw/~cjlin/libsvm/
    33. 《machine learning in action》,中文版为《机器学习实战》;
    34. SMO算法的提出:Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machineshttp://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf
    35. 《统计学习理论的本质》,[美] Vladimir N. Vapnik著,非常晦涩,不做过多推荐;
    36. 张兆翔,机器学习第五讲之支持向量机http://irip.buaa.edu.cn/~zxzhang/courses/MachineLearning/5.pdf
    37. VC维的理论解释:http://www.svms.org/vc-dimension/,中文VC维解释http://xiaoxia001.iteye.com/blog/1163338
    38. 来自NEC Labs America的Jason Weston关于SVM的讲义http://www.cs.columbia.edu/~kathy/cs4701/documents/jason_svm_tutorial.pdf
    39. 来自MIT的SVM讲义:http://www.mit.edu/~9.520/spring11/slides/class06-svm.pdf
    40. PAC问题:http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf
    41. 百度张潼老师的两篇论文:《Statistical behavior and consistency of classification methods based on convex risk minimization》http://home.olemiss.edu/~xdang/676/Consistency_of_Classification_Convex_Risk_Minimization.pdf,《Statistical analysis of some multi-category large margin classification methods》;
    42. http://jacoxu.com/?p=39
    43. 《矩阵分析与应用》,清华张贤达著;
    44. SMO算法的实现:http://blog.csdn.net/techq/article/details/6171688
    45. 常见面试之机器学习算法思想简单梳理:http://www.cnblogs.com/tornadomeet/p/3395593.html
    46. 矩阵的wikipedia页面:http://zh.wikipedia.org/wiki/%E7%9F%A9%E9%98%B5
    47. 最小二乘法及其实现:http://blog.csdn.net/qll125596718/article/details/8248249
    48. 统计学习方法概论:http://blog.csdn.net/qll125596718/article/details/8351337
    49. http://www.csdn.net/article/2012-12-28/2813275-Support-Vector-Machine
    50. A Tutorial on Support Vector Regression:http://alex.smola.org/papers/2003/SmoSch03b.pdf;SVR简明版:http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/SVR.pdf
    51. SVM Org:http://www.support-vector-machines.org/
    52. R. Collobert. Large Scale Machine Learning. Université Paris VI phd thesis. 2004:http://ronan.collobert.com/pub/matos/2004_phdthesis_lip6.pdf
    53. Making Large-Scale SVM Learning Practical:http://www.cs.cornell.edu/people/tj/publications/joachims_99a.pdf
    54. 文本分类与SVM:http://blog.csdn.net/zhzhl202/article/details/8197109
    55. Working Set Selection Using Second Order Information
      for Training Support Vector Machines:http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf
    56. SVM Optimization: Inverse Dependence on Training Set Size:http://icml2008.cs.helsinki.fi/papers/266.pdf
    57. Large-Scale Support Vector Machines: Algorithms and Theory:http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf
    58. 凸优化的概念:http://cs229.stanford.edu/section/cs229-cvxopt.pdf
    59. 《凸优化》,作者: Stephen Boyd / Lieven Vandenberghe,原作名: Convex Optimization;
    60. Large-scale Non-linear Classification: Algorithms and Evaluations,Zhuang Wang,讲了很多SVM算法的新进展:http://ijcai13.org/files/tutorial_slides/te2.pdf
    61. 基于SMO算法实现SVM:http://www.cs.iastate.edu/~honavar/smo-svm.pdf
    62. copper推荐的一些SVM相关的论文(当然,其中不少论文在上面的条目中都已经提到):http://c.blog.sina.com.cn/profile.php?blogid=68d0b92d89000h35
    63. 在线编辑Latex 公式:http://private.codecogs.com/latex/eqneditor.php?lang=zh-cn

     

     

    后记

        OK,此文从最初2012年5月开始动笔,到后续不断的修改,创造了三个之最,即所写时间最长,所花心血最大,所改次数最多,因为我的目标是让没有任何机器学习基础的都能看懂此文,所以总是不停的改,不停的改,不想放过任何一个小的细节。再者,引用侯捷的一句话是:天下大作,必作于细。

        最后,非常感谢pluskid及诸多朋友们的文章及著作,让我有机会在其基础上总结、深入。有任何问题,敬请广大读者随时不吝批评指正,感谢。

     

     

    本文PDF版

    • 13年11月25日,用chrome浏览器打开文章,右键打印,弹出打印框,把左上角的目标更改为“另存为PDF”,成第一个PDF:http://vdisk.weibo.com/s/zrFL6OXKghu5V
    • 13年12月7日,朋友吴新隆用“印象笔记”提取出博客正文,放到office内编辑成此PDF:http://vdisk.weibo.com/s/zrFL6OXKgQHm8,较上一版本添加了完整的书签。
    • 14年 2月18日,朋友邬书哲用Latex全部重排了本文所有公式,而且给所有公式和图片全部做了标记,Latex版PDF下载地址为:http://vdisk.weibo.com/s/zrFL6OXKgnlcp
    • 15年1月8日,朋友陈笙再为本SVM一文弄了最新的第二个LaTeX版本,下载地址为:http://pan.baidu.com/s/1eQrgiOU

        本文会一直不断翻新,再者,上述 4 个PDF的阅读体验也还不是最好的,如果有朋友制作了更好的PDF,欢迎分享给我:http://weibo.com/julyweibo,谢谢。

        July、二零一六年一月十七日第N次修改(N > 100)。

    重大消息:我的新书《编程之法:面试和算法心得》终于在2015年10月14日上架开卖了!京东抢购地址http://item.jd.com/11786791.html。京东、当当、亚马逊等各大网店均已有现货销售。新书收录了本篇SVM,且新书质量远高于博客。July、二零一五年十月二十九日。


    展开全文
  • 支持向量机的原理

    万次阅读 多人点赞 2018-09-26 20:56:38
    一、什么是支持向量机  支持向量机(support vector machine,简称SVM)是一种基于统计学习理论的新型学习机,是由前苏联教授Vapnik最早提出的。与传统的学习方法不同,支持向量机是结构风险最小化方法的近似实现。...

    一、什么是支持向量机

      支持向量机(support vector machine,简称SVM)是一种基于统计学习理论的新型学习机,是由前苏联教授Vapnik最早提出的。与传统的学习方法不同,支持向量机是结构风险最小化方法的近似实现。这个归纳原理是基于这样的事实,学习机器在测试数据上的误差率(即泛化误差率)以训练误差率和一个依赖于Vc维数(Vapnik-Chervonenkis dimension)的项的和为界;在可分模式情况下,支持向量机对于前一项的值为零,并且使第二项最小化。因此,尽管支持向量机不利用问题的领域知识,在模式分类问题上,仍能提供好的泛化性能,这个属性是支持向量机特有的。其实现的是如下的思想:通过某种事先选择的非线性映射将输入向量x映射到一个高维特征空间z,在这个空间中构造最优分类超平面,从而使正例和反例样本之间的分离界限达到最大。从概念上说,支持向量是那些离决策平面最近的数据点,它们决定了最优分类超平面的位置。

    二、支持向量机的原理

     超平面和最近的数据点之间的间隔被称为分离边缘,用P表示。支持向量机的目标是找到一个特殊的超平面,对于这个超平面分离边缘P最大。在这个条件下,决策曲面称为最优超平面。下图是二维输入空间中最优超平面的几何结构。

                            

    基本上,支持向量机的思想建立在两个数学运算上,概述如下
     1) 输入向量到高维特征空间的非线性映射,特征空间对输入和输出都是隐藏的
     2)  构造一个最优超平面用于分离在上一步中发现的特征。

    三、支持向量机的算法

     比较经典的如

    1)Vapnik提出的Chunking方法;其出发点是删除矩阵中对应Lagrange乘数为零的行和列将不会影响最终结果,然而,在训练集的支持向量数很大的时候,Chunking算法仍然无法将矩阵放入内存中。

    2)Qsuna提出的Qsuna算法;该算法存在效率问题,因为在每一步中,进行一次QP问题的最优化只能使一个样本符合Kuhn-Tucker条件。

    3)Plat提出的序贯最小优化方法(sequential minimal optimization,简称SMO);将一个大型的QP问题分解为一系列最小规模的QP子问题,即仅具有两个Lagrange乘数的QP问题,从而使得原问题可以通过分析的方法加以解决,避免了在内循环中使用数值算法进行QP最优化。该算法在训练线性SVM时,可以获得非常好的性能。

    四、支持向量机的几种内积核函数

       1)多项式学习机

      2)径向基函数网络

      3)两层感知器

    展开全文
  • 支持向量机(SVM)入门理解与推导

    万次阅读 多人点赞 2018-12-03 17:21:27
    支持向量机(support vector machines)是一种二分类模型,它的目的是寻找一个超平面来对样本进行分割,分割的原则是间隔最大化,最终转化为一个凸二次规划问题来求解。由简至繁的模型包括: 当训练样本线性可...

    一、简介

    支持向量机(support vector machines)是一种二分类模型,它的目的是寻找一个超平面来对样本进行分割,分割的原则是间隔最大化,最终转化为一个凸二次规划问题来求解。由简至繁的模型包括:

    • 当训练样本线性可分时,通过硬间隔最大化,学习一个线性可分支持向量机;
    • 当训练样本近似线性可分时,通过软间隔最大化,学习一个线性支持向量机;
    • 当训练样本线性不可分时,通过核技巧和软间隔最大化,学习一个非线性支持向量机;

    二、线性可分支持向量机

    1、间隔最大化和支持向量

    如果一个线性函数能够将样本分开,称这些数据样本是线性可分的。那么什么是线性函数呢?其实很简单,在二维空间中就是一条直线,在三维空间中就是一个平面,以此类推,如果不考虑空间维数,这样的线性函数统称为超平面。我们看一个简单的二维空间的例子,O代表正类,X代表负类,样本是线性可分的,但是很显然不只有这一条直线可以将样本分开,而是有无数条,我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。

    下面我们开始计算间隔,其实间隔就等于两个异类支持向量的差在 w 上的投影,即:
    这里写图片描述
    其中 x+{{\vec{x}}_{+}}x{{\vec{x}}_{-}} 分别表示两个正负支持向量,因为 x+{{\vec{x}}_{+}}x{{\vec{x}}_{-}} 满足 yi(wTxi+b)=1{{y}_{i}}({{w}^{T}}{{x}_{i}}+b)=1,即:
    这里写图片描述
    推出:
    这里写图片描述
    代入公式(4)中可以得到:
    这里写图片描述
    至此,我们求得了间隔,SVM的思想是使得间隔最大化,也就是:
    这里写图片描述
    显然,最大化 2w\frac{2}{||w||} 相当于最小化 ||w||,为了计算方便,将公式(6)转化成如下:
    这里写图片描述
    公式(7)即为支持向量机的基本型。

    2、对偶问题

    公式(7)本身是一个凸二次规划问题,可以使用现有的优化计算包来计算,但我们选择更为高效的方法。对公式(7)使用拉格朗日乘子法得到其对偶问题,该问题的拉格朗日函数可以写为:
    这里写图片描述
    公式(8)分别对 w 和 b求偏导:
    这里写图片描述
    令其分别为0,可以得到:
    这里写图片描述
    将公式(9)(10)代入公式(8),可得:
    这里写图片描述
    此时,原问题就转化为以下仅关于 $\alpha $ 的问题:
    这里写图片描述
    解出 $\alpha $ 之后,根据公式(9)可以求得 w , 进而求得 b,可以得到模型:
    这里写图片描述
    上述过程的KKT条件为:
    这里写图片描述
    我们分析一下,对于任意的训练样本 (xi,yi)({{x}_{i}},{{y}_{i}})

    • αi=0{{\alpha }_{i}}=0,则其不会在公式(13)中的求和项中出现,也就是说,它不影响模型的训练;
    • αi&gt;0{{\alpha }_{i}}&gt;0,则 yif(xi)1=0{{y}_{i}}f({{x}_{i}})-1=0,也就是 yif(xi)=1{{y}_{i}}f({{x}_{i}})=1,即该样本一定在边界上,是一个支持向量。

    这里显示出了支持向量机的重要特征:当训练完成后,大部分样本都不需要保留,最终模型只与支持向量有关。

    三、非线性支持向量机和核函数

    对于非线性问题,线性可分支持向量机并不能有效解决,要使用非线性模型才能很好地分类。先看一个例子,如下图,很显然使用直线并不能将两类样本分开,但是可以使用一条椭圆曲线(非线性模型)将它们分开。非线性问题往往不好求解,所以希望能用解线性分类问题的方法求解,因此可以采用非线性变换,将非线性问题变换成线性问题。
    这里写图片描述
    对于这样的问题,可以将训练样本从原始空间映射到一个更高维的空间,使得样本在这个空间中线性可分,如果原始空间维数是有限的,即属性是有限的,那么一定存在一个高维特征空间是样本可分。令ϕ(x)\phi (x)表示将 x 映射后的特征向量,于是在特征空间中,划分超平面所对应的的模型可表示为:

    f(x)=wTϕ(x)+bf(x)={{w}^{T}}\phi (x)+b          (14)

    于是有最小化函数:
    这里写图片描述
    其对偶问题为:
    这里写图片描述
    若要对公式(16)求解,会涉及到计算 ϕ(xi)Tϕ(xj)\phi {{({{x}_{i}})}^{T}}\phi ({{x}_{j}}),这是样本 xi{{x}_{i}}xj{{x}_{j}}映射到特征空间之后的内积,由于特征空间的维数可能很高,甚至是无穷维,因此直接计算 ϕ(xi)Tϕ(xj)\phi {{({{x}_{i}})}^{T}}\phi ({{x}_{j}})通常是困难的,于是想到这样一个函数:
    这里写图片描述
    xi{{x}_{i}}xj{{x}_{j}} 在特征空间中的内积等于他们在原始样本空间中通过函数 κ(xi,xj)\kappa ({{x}_{i}},{{x}_{j}}) 计算的函数值,于是公式(16)写成如下:
    这里写图片描述
    求解后得到:
    这里写图片描述
    这里的函数 κ(xi,xj)\kappa ({{x}_{i}},{{x}_{j}}) 就是核函数,在实际应用中,通常人们会从一些常用的核函数里选择(根据样本数据的不同,选择不同的参数,实际上就得到了不同的核函数),下面给出常用的核函数:

    • 线性核:
      这里写图片描述

    • 多项式核(d是多项式的次数,d=1是退化为线性核):
      这里写图片描述

    • 高斯核(σ&gt;0\sigma &gt;0):
      这里写图片描述

    • 拉普拉斯核(σ&gt;0\sigma &gt;0):
      这里写图片描述

    • sigmiod核(β&gt;0,θ&gt;0\beta &gt;0,\theta &gt;0):
      这里写图片描述
      此外,核函数也可以通过组合得到,在此不再赘述。

    四、线性支持向量机(软间隔支持向量机)与松弛变量

    1、线性支持向量机

    在前面的讨论中,我们假设训练样本在样本空间或者特征空间中是线性可分的,但在现实任务中往往很难确定合适的核函数使训练集在特征空间中线性可分,退一步说,即使瞧好找到了这样的核函数使得样本在特征空间中线性可分,也很难判断是不是由于过拟合造成。

    线性不可分意味着某些样本点 (xi,yi)({{x}_{i}},{{y}_{i}}) 不能满足间隔大于等于1的条件,样本点落在超平面与边界之间。为解决这一问题,可以对每个样本点引入一个松弛变量 ξi0{{\xi }_{i}}\ge 0,使得间隔加上松弛变量大于等于1,这样约束条件变为:
    这里写图片描述
    同时,对于每一个松弛变量 ξi0{{\xi }_{i}}\ge 0,支付一个代价 ξi0{{\xi }_{i}}\ge 0,目标函数变为:
    这里写图片描述
    其中 C&gt;0C&gt;0为惩罚参数,C值大时对误分类的惩罚增大, C值小时对误分类的惩罚减小,公式(21)包含两层含义:使 12w2\frac{1}{2}||w|{{|}^{2}} 尽量小即间隔尽量大,同时使误分类点的个数尽量小,C是调和两者的系数。
    有了公式(21),可以和线性可分支持向量机一样考虑线性支持向量机的学习过程,此时,线性支持向量机的学习问题变成如下凸二次规划问题的求解(原始问题):
    这里写图片描述

    2、对偶问题

    与线性可分支持向量机的对偶问题解法一致,公式(22)的拉格朗日函数为:
    这里写图片描述
    其中 αi0,μi0{{\alpha }_{i}}\ge 0,{{\mu }_{i}}\ge 0 是拉格朗日乘子。

    L(w,b,α,ξ,μ)L(w,b,\alpha ,\xi ,\mu ) 对 $w,b,\xi $的偏导数为0可得如下:
    这里写图片描述
    将公式(24)(25)(26)代入公式(23)得对偶问题:
    这里写图片描述
    解出 $\alpha $ 之后,根据公式(9)可以求得 w , 进而求得 b,可以得到模型:
    这里写图片描述
    上述过程的KKT条件为:
    这里写图片描述
    我们分析一下,对于任意的训练样本 (xi,yi)({{x}_{i}},{{y}_{i}}) ,总有 αi=0{{\alpha }_{i}}=0 或者 yif(xi)1+ξi=0{{y}_{i}}f({{x}_{i}})-1+{{\xi }_{i}}=0

    • αi=0{{\alpha }_{i}}=0 ,则该样本不出现在公式(13)中,不影响模型。
    • αi&gt;0{{\alpha }_{i}}&gt;0,必有 yif(xi)1+ξi=0{{y}_{i}}f({{x}_{i}})-1+{{\xi }_{i}}=0 ,即 yif(xi)=1ξi{{y}_{i}}f({{x}_{i}})=1-{{\xi }_{i}} ,此时该样本为支持向量。

    由于 C=αi+μiC={{\alpha }_{i}}+{{\mu }_{i}} (公式26)

    • αi&lt;C{{\alpha }_{i}}&lt;C, 则必有 μi&gt;0{{\mu }_{i}}&gt;0 ,根据公式(28)知 ξi=0{{\xi }_{i}}=0 ,即该样本恰好落在最大间隔的边界上;
    • αi=C{{\alpha }_{i}}=C ,则 μi=0{{\mu }_{i}}=0,此时若 ξi1{{\xi }_{i}}\le 1 则该样本在最大间隔内部,若 ξi&gt;1{{\xi }_{i}}&gt;1 则样本分类错误。

    五、总结

    至此,关于SVM的三类问题:线性可分支持向量机与硬间隔最大化,非线性支持向量机与核函数,线性支持向量机与软间隔最大化一一介绍完毕,最后附上博主 Duanxx 对SVM使用范围的一段总结:

    我们所面对的所有的机器学算法,都是有适用范围的,或者说,我们所有的机器学习算法都是有约束的优化问题。而这些约束,就是我们在推导算法之前所做的假设。

    比如:Logistics Regression,在Logistics Regression中,假设后验概率为Logistics 分布;再比如:LDA假设fk(x)fk(x)是均值不同,方差相同的高斯分布;这些都是我们在推导算法之前所做的假设,也就是算法对数据分布的要求。

    而对于SVM而言,它并没有对原始数据的分布做任何的假设,这就是SVM和LDA、Logistics Regression区别最大的地方。这表明SVM模型对数据分布的要求低,那么其适用性自然就会更广一些。如果我们事先对数据的分布没有任何的先验信息,即,不知道是什么分布,那么SVM无疑是比较好的选择。

    但是,如果我们已经知道数据满足或者近似满足高斯分布,那么选择LDA得到的结果就会更准确。如果我们已经知道数据满足或者近似满足Logistics 分布,那么选择Logistics Regression就会有更好的效果。

    如有问题,欢迎批评指正~

    展开全文
  • 【ML】支持向量机(SVM)从入门到放弃再到掌握

    万次阅读 多人点赞 2020-05-12 11:08:16
    朋友,你通过各种不同的途经初次接触支持向量机(SVM)的时候,是不是会觉得这个东西耳熟能详,感觉大家都会,却唯独自己很难理解? 每一次你的老板或者同仁让你讲解SVM的时候,你觉得你看过这么多资料,使用过...

    前言

    朋友,你通过各种不同的途经初次接触支持向量机(SVM)的时候,是不是会觉得这个东西耳熟能详,感觉大家都会,却唯独自己很难理解?
    每一次你的老板或者同仁让你讲解SVM的时候,你觉得你看过这么多资料,使用过这么多次,讲解应该没有问题,但偏偏在分享的时候结结巴巴,漏洞百出?
    每一次机器学习相关的面试在问到支持向量机(SVM)的时候,尽管你觉得你都准备好了,可是一次又一次败下阵来,以至于觉得问那些问题的人(是不是脑子有…)是那么的厉害,每一次都能精准发觉到你的不足和漏洞,让你怀疑你掌握的是假的SVM,然后让你怀疑人生?
    那还等什么,快来看看这篇文章吧,原价998,现在只要。。。(不好意思,扯偏了。)

    以上可能真的只是我的个人经历(在这里,学渣给各位大佬鞠躬了!),但不管怎么样,我还是要自己写一篇从头到尾的SVM的理解,然后呈现给各位大佬审阅,欢迎您批评指正!

    按照以下问题成文:

    • 由线性分类任务开始
    • 为何需要最大化间隔
    • 怎么解决凸二次规划问题
    • 对偶问题的求解
    • SMO算法
    • 核函数的由来和使用
    • SVM与LR的异同

    SVM由线性分类开始

    在这之前,假设读者们对线性分类模型和向量矩阵求导有大概的了解。

    给定训练样本集D=(x1,y1),(x2,y2),...,(xm,ym))),yi{1,1}D={(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})))}, y_{i}\in \left \{ -1, 1\right \}, 线性分类器基于训练样本D 在二维空间中找到一个超平面来分开二类样本。当然,这样的超平面有很多。

    这里写图片描述

    但我们可以直观感受到,这根红色线代表的超平面抗“扰动”性最好。这个超平面离直线两边的数据的间隔最大,对训练集的数据的局限性或噪声有最大的“容忍”能力。

    在这里,这个超平面可以用函数f(x)=wTx+bf(x) = w^{T}x+b 表示。 当f(x)f(x) 等于0的时候,x便是位于超平面
    上的点,而f(x)f(x) 大于0的点对应 y=1 的数据点,f(x)f(x) 小于0的点对应y=-1的点。

    为什么是yi{1,1}y_{i}\in \left \{ -1, 1\right \},换句话说,yy 只能是-1,和1吗?不能是yy =-100 表示反例,yy =2000表示正例,或yy =0表示反例,yy =300表示正例,或yy =5表示反例 yy =-7 表示正例吗?当然可以。y 只是一个label ,标注为{-1,+1}不过为了描述方便

    yy =0表示反例,yy =300表示正例,只不过分正类的标准变为(y150fx)>0(y-150)*f(x)>0

    不妨令:

    {wTxi+b+1,yi=+1;wTxi+b1,yi=1\left\{\begin{matrix}w^{T}x_{i}+b \geqslant +1, y_{i} = +1 ;& \\ w^{T}x_{i}+b \leq -1, y_{i} = -1 & \end{matrix}\right.

    为什么可以这么令呢?我们知道,所谓的支持向量,就是使得上式等号成立,即最靠近两条虚边界线的向量。那么,不难理解当wTx+bw^{T}x+b的值大于+1,或小于-1的时候,就更加支持“样本的分类”了。为什么要这么令呢?还是为了计算方便。接着往下看,你一定能悟到这么令的原因。

    我们可以计算得到空间中任意样本点xx到超平面的距离为:r=wTx+bwr = \frac{|w^{T}x+b|}{\left \| w \right \|}。为什么呢?
    这里写图片描述
    如图所示,有:x=x0+rwwx = x_{0}+r\frac{w}{\left \| w \right \|}(简单平面几何)
    又有:wTx0+b=0w^{T}x_{0}+b = 0,代入上式,求得:r=wTx+bwr = \frac{|w^{T}x+b|}{\left \| w \right \|}

    因为yi{1,1}y_{i}\in \left \{ -1, 1\right \},,两个异类支持向量到超平面的距离之和(也称为“间隔”)可表示为:r=2wr = \frac{2}{\left \| w \right \|}


    下面我们用严谨的逻辑来重新梳理横线“—”上面的内容:

    对于一个分类问题,我们假设yi{1,1}y_{i}\in \left \{ -1, 1\right \},同样的,{1,1}\left \{ -1, 1\right \}不过是正类和负类的类标表示。

    我们假设

    {wTxi+b0,yiyi=+1;wTxi+b0,yiyi=1;\left\{\begin{matrix}w^{T}x_{i}+b \geqslant 0, 时,对应y_{i}取正例,表示为y_{i} = +1 ;& \\ w^{T}x_{i}+b \leq 0, 时,对应y_{i}取负例,表示为 y_{i} = -1 ;& \end{matrix}\right.
    如上所述,SVM的目的是最大分类间隔即:
    maxmargins.t. yi(wTxi+b)0,fori=1,...,m\max{margin} \\s.t. \ y_i(w^Tx_i+b)\geqslant0 ,for \forall i = 1,...,m
    因为我们前面定义:
    wTxi+b0,yiw^{T}x_{i}+b \geqslant 0, 时,对应y_{i}取正,
    wTxi+b0,yiw^{T}x_{i}+b \leq 0, 时,对应y_{i}取负,
    显然有:
    maxmargins.t. yi(wTxi+b)0,fori=1,...,m\max{margin} \\s.t. \ y_i(w^Tx_i+b)\geqslant 0 ,for \forall i = 1,...,m
    margin是什么呢?
    按照点到直线的距离,每一类样本中的所有样本点到直线的距离为:
    wTxi+bw\frac{|w^{T}x_i+b|}{\left \| w \right \|}
    我们的单侧margin应该是每一类样本中,到超平面距离最近的点与超平面的距离。(支持向量到超平面的距离)那么margin 等于2倍的单侧margin。
    于是有:
    margin=2×w,b,ximinwTxi+bw,i=1,...,mmargin = 2\times _{w,b,x_i}^\textrm{min}\frac{|w^{T}x_i+b|}{\left \| w \right \|},i = 1,...,m

    回到我们之前的假设,我们有yi(wTxi+b)0yi(wTxi+b)y_i(w^Tx_i+b)\geqslant 0,y_i 与 (w^Tx_i+b) 同号,我们说有:
    margin=2×w,b,ximinwTxi+bw=2×w,b,xi,yiminyi(wTxi+b)w,i=1,...,mmargin = 2\times _{w,b,x_i}^\textrm{min}\frac{|w^{T}x_i+b|}{\left \| w \right \|} = 2\times _{w,b,x_i,y_i}^\textrm{min}\frac{y_i(w^{T}x_i+b)}{\left \| w \right \|}, \\i = 1,...,m
    我们以此来消除分子中的绝对值。

    于是SVM的目标变为:
    w,bmax1w2×xi,yiminyi(wTxi+b),s.t.yi(wTxi+b)0,i=1,...,m_{w,b}^\textrm{max}\frac{1}{\left \| w \right \|}2\times _{x_i,y_i}^\textrm{min}{y_i(w^{T}x_i+b)},\\s.t.\\y_i(w^Tx_i+b)\geqslant 0,i = 1,...,m

    单独考察
    yi(wTxi+b)0,i=1,...,m\\y_i(w^Tx_i+b)\geqslant 0,i = 1,...,m
    也就是说存在任意a >0 使得 xi,yiminyi(wTxi+b)=a_{x_i,y_i}^{min}y_i(w^Tx_i+b) = a

    我们令a = 1,来简化运算, 于是得到: xi,yiminyi(wTxi+b)=1_{x_i,y_i}^{min}y_i(w^Tx_i+b) = 1
    我们完全可以这样令a=1,试想,yiy_i是固定的,假设yiy_i是正例的情况下,wTxi+bw^Tx_i+b是一个个大于0的值,这个值是多少,并不重要,只需要其大于0即可。我们令 xi,yiminyi(wTxi+b)=1_{x_i,y_i}^{min}y_i(w^Tx_i+b) = 1相当于对w|w|作了约束。

    综上所述:
    于是SVM的目标进一步变为:
    w,bmax2w,s.t.yi(wTxi+b)1,i=1,...,m_{w,b}^\textrm{max}\frac{2}{\left \| w \right \|},\\s.t.\\y_i(w^Tx_i+b)\geqslant 1,i = 1,...,m

    很显然,我们要找到符合这样一个条件的超平面来分开两类数据
    这个超平面离两类样本都足够远,也就是使得“间隔”最大。即最终确定的参数wbw 和 b,使得rr最大。

    接下来我们继续

    w,bmax2w_{w,b}^\textrm{max}\frac{2}{\left \| w \right \|}
    s.t.yi(wTxi+b)1i=1,2,...,ms.t. y_{i}( w^{T}x_{i}+b)\geq 1,i=1,2,...,m

    等价于

    w,bmin12w2_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}
    s.t.yi(wTxi+b)1i=1,2,...,ms.t. y_{i}( w^{T}x_{i}+b)\geq 1,i=1,2,...,m

    由此我们得到了SVM的基本型

    ##凸优化
    我们可以看到,上面的基本型目标函数是二次的,约束条件是线性的,这是一个凸二次规划问题。可以直接用现成的优化计算包求解。但若利用“对偶问题”来求解,会更高效。

    • 啥是凸?什么是凸优化

      凸优化说的是这么一回事情,
      XRnX\subset R^{n} 为一凸集,f:XRf:X\rightarrow R 为一凸函数,凸优化就是要找出一点xX,x^{*} \in X,使得任意xX,x \in X,都满足f(x)f(x)f(x^{*})\leq f(x) .
      可以想象成给我一个凸函数,我要去找到最低点。当然凸优化是一个很大很厉害的领域,在这里,我们只需要知晓这个问题是这么一回事。然后,这回事要怎么样求解,就好,有兴趣的朋友可以参考凸优化的概念或者Stephen Boyd & Lieven Vandenberghe 的《Convex Optimization》。

    • 为啥叫二次规划问题呢?

    据了解(其实就是知道),目标函数和约束条件都为变量的线性函数,叫做-----线性规划问题
    目标函数为变量的二次函数和约束条件为变量的线性函数,叫做-----二次规划问题
    目标函数和约束条件都为非线性函数,叫做-----非线性规划问题

    对偶问题

    对于
    w,bmin12w2_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}
    s.t.yi(wTxi+b)1i=1,2,...,ms.t. y_{i}( w^{T}x_{i}+b)\geq 1,i=1,2,...,m
    为了后面的描述方便,记这个式子为(1)式。

    使用**拉格朗日乘子法**可以得到其“对偶问题”。
    这是拉格朗日对偶性,即,通过给每一个约束条件加上一个拉格朗日乘子。然后定义出拉格朗日函数,通过拉格朗日函数将约束条件融合进目标函数中。目的是,只需要通过一个目标函数包含约束条件,便可以清楚解释问题

    比如对(1)式每一个约束(共有m个约束,yi(wTxi+b)1y_{i}( w^{T}x_{i}+b)\geq 1),添加拉格朗日乘子 αi0\alpha _{i} \geq 0,则整个问题的拉格朗日函数可写为:

    • L(w,b,α)=12w2+i=1mαi(1yi(wTxi+b))L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2} +\sum _{i=1}^{m}\alpha _{i}(1- y_{i}( w^{T}x_{i}+b))

    为什么使用这样的拉格朗日乘子,又为何这样构建?这实际上是因为我们的目标函数是不等式约束,解这样的二次规划问题,我们选择用KKT条件,而KKT条件需要这样的一个约束αi0\alpha _{i} \geq 0。最终我们便通过KKT条件来产生原问题的对偶问题。
    同样的,将上面这个式子记为(2)式

    可以看到,由于αi0\alpha _{i} \geq 0, 这样,但凡有约束条件之一不满足,如yk(wTxk+b)<1y_{k}( w^{T}x_{k}+b)< 1),

    L(w,b,α)=L(w,b,\alpha )= \infty。只有约束条件均满足的时候,

    L(w,b,α)L(w,b,\alpha )有最优值,为L(w,b,α)=12w2L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2}

    所以优化12w2\frac{1}{2}\left \|w\right \| ^{2} 等价于优化L(w,b,α)L(w,b,\alpha )当然,要满足约束条件αi0\alpha _{i} \geq 0


    我们从逻辑上再来理解下上述内容:
    对于一个不等式约束优化问题:
    xminf(x)s.t.mi(x)0,i=1,...,m_x^{min}f(x) \\s.t.\\m_i(x)\leqslant 0,i=1,...,m
    我们总可以将其转化成拉格朗日形式:
    ιx,λ,η=f(x)+i=1mλimi\iota(x,\lambda ,\eta) = f(x) + \sum_{i=1}^{m}\lambda _im_i
    之后再转化为求如下的约束:
    xminλ,ηmaxι(x,λ,η)_x^{min}{_{\lambda,\eta }^{max}}\iota (x,\lambda,\eta)
    我们可以证明转化后的约束包含了原问题。
    转化后的约束是一个关于xx的函数。
    进一步的我们可构建其对偶问题:
    λ,ηmaxxminι(x,λ,η){_{\lambda,\eta }^{max}}{_x^{min}}\iota (x,\lambda,\eta)
    对偶问题是关于λ,η\lambda,\eta的函数。
    由于是先求最小然后求最大,我们的问题的求解就变得容易。

    接下来我们继续


    于是,我们的目标函数可以表示为:

    w,bmin_{w,b}^{min}α0max_{_{\alpha\geq 0}}^{max}L(w,b,α)L(w,b,\alpha )

    满足一定条件下,等价于(注意,这个满足一定条件,是指满足KKT条件)

    α0max_{_{\alpha\geq 0}}^{max}w,bmin_{w,b}^{min}L(w,b,α)L(w,b,\alpha )

    后者把最小和最大的位置交换,这样使得运算方便起来。

    ##KKT条件
    什么是KKT条件?其实在这之前,本文有稍微有提到过。在这里正式介绍一下。

    KKT条件是一个线性规划问题能有最优解的充分和必要条件。

    一般地,一个最优化数学模型可以表示成如下形式:

    minf(x)minf(x)
    s.t.hi(x)=0,i=1,2,...,ps.t. h_{i}(x) = 0 , i = 1,2,...,p
    gj(x)0,j=1,2,...,qg_{j}(x) \leq 0 , j = 1,2,...,q
    xXRnx\in X \in R^{n}

    h(x)h(x) 是等式约束。
    g(x)g(x) 是不等式约束。
    p,qp,q 表示约束的数量。

    而这个最优化数学模型的最优解xx^{*}须满足的条件,即KKT条件为:

    1. hi(x)=0,i=1,2,...,ph_{i}(x^{*}) = 0 , i = 1,2,...,p,和 gj(x)0,j=1,2,...,qg_{j}(x^{*}) \leq 0 , j = 1,2,...,q
    2. f(x)+i=1pλihi(x)+j=1qμkgk(x)=0\bigtriangledown f(x^{*}) + \sum_{i=1}^{p}\lambda _{i}\bigtriangledown h_{i}(x^{*}) + \sum_{j=1}^{q} \mu _{k}\bigtriangledown g_{k}(x^{*}) = 0
    3. λi0,μk0,μkgk(x)=0\lambda _{i}\neq 0, \mu _{k}\geq 0, \mu _{k}g_{k}(x^{*}) = 0

    于是我们的整个问题转化为

    1. L(w,b,α)L(w,b,\alpha)w,bw,b求最小

    2. 再对α\alpha 求最大。

    对于第一步,先令L(w,b,α)L(w,b,\alpha )w,bw,b求偏导为0,可得:
    w=i=1mαiyixi,w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},

    0=i=1mαiyi.0=\sum_{i=1}^{m}\alpha_{i}y_{i}.

    将此两个式子带入(2)式消去w,bw,b。便得到了(1)式的对偶问题。

    α0maxi=1mαi12i,j=1mαiαjyiyjxiTxj_{\alpha\geq 0 }^{max}\sum_{i=1}^{m}\alpha_{i}-\frac{1} {2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}

    s.t.i=1mαiyi.=0,s.t. \sum_{i=1}^{m}\alpha_{i}y_{i}.=0,
    αi0,i=1,2,...,m\alpha_{i}\geq 0 , i = 1,2,...,m

    类比来看,我们的目标函数没有h(x)=0h(x) = 0 的等式约束。
    于是,上面的过程,需要满足的KKT条件是

    {αi0;1yi(wTxi+b)0;αi(1yi(wTxi+b))=0.\left\{\begin{matrix}\alpha_{i} \geq 0 ;\\1- y_{i}( w^{T}x_{i}+b) \leq 0;\\ \alpha_{i}(1-y_{i}( w^{T}x_{i}+b))=0.\end{matrix}\right.

    我们看到,对于任意样本,总有αi=0\alpha_{i} = 0 或者 yi(wTxi+b)=1y_{i}( w^{T}x_{i}+b) =1 .若αi=0\alpha_{i} = 0 ,则由w=i=1mαiyixi,w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},w=0w = 0 , 则此αi\alpha_{i} 对应的向量不会对 f(x)f(x) 的确定有任何影响。而αi>0\alpha_{i} > 0 时,必有yi(wTxi+b)=1y_{i}( w^{T}x_{i}+b) =1 ,此时αi\alpha_{i} 对应的向量在最大间隔的边缘上(一开始示意图的虚线上),即是支持向量。这也说明,最终模型的确定,只与支持向量有关。

    接下来,怎么求α\alpha呢?
    ##序列最小优化算法(SMO算法)

    三种支持向量机

    我们先来体味一下支持向量机的分类吧。一般支持向量机可以分为三类:线性可分支持向量机(support vector machine in linearly separable case)、线性支持向量机(linear support vector machine )以及非线性支持向量机(non-linear support vector machine)这三个由简至繁的模型分别解决训练数据的三个不同情况。当训练数据线性可分时,训练一个线性可分支持向量机,也称硬间隔支持向量机,当训练数据近似线性可分时,通过软间隔最大化(什么是软间隔最大化?后面会讲的),训练一个线性支持向量机,当数据线性不可分,我们通过核技巧(核技巧由Boser,Guyon等引入。什么是核技巧?后面会讲到)及软间隔最大化学习非线性支持向量机。

    在这里引入一张图片,近距离体会上述三种数据类型。
    在这里插入图片描述
    自此我们也看出来了,上面的所有解法,都是针对于线性可分支持向量机来说的。不过以此为基础,另外两种支持向量机就特别好理解了。
    如何判断数据线性可分,推荐参考这篇博文:http://www.atyun.com/14182.html

    线性支持向量机

    还记得在介绍线性可分svm的时候,我们几乎强给的约束yi(wTxi+b)1y_i(w^Tx_i+b)\geqslant 1 吗?但当我们面对线性不可分数据时,意味着某些样本点不能满足间隔大于等于1 的约束了。我们可以看下方的示意图,在间隔内部,还存在一些样本点,并不满足约束yi(wTxi+b)1y_i(w^Tx_i+b)\geqslant 1

    在这里插入图片描述
    这时通过引入一个松弛变量 ξi0{\xi}_i\geq0 来使得函数间隔加上松弛变量大于等于1。此时,约束条件变为:yi(wTxi+b)1ξiy_i(w^Tx_i+b)\geqslant 1-{\xi}_i
    对于所有的样本都加上这样一个松弛变量,目标函数由原来的12w2\frac{1}{2}{\left \| w \right \|}^{2} 变为
    12w2+Ci=1Nξi\frac{1}{2}{\left \| w \right \|}^{2} + C\sum_{i=1}^{N}{\xi}_i
    同样的,我们通过求解如下凸二次规划问题:

    w,b,ξmin12w2+Ci=1Nξi_{w,b,{\xi}}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2} + C\sum_{i=1}^{N}{\xi}_i
    s.t.yi(wTxi+b)1ξi,i=1,2,....,Nξi0,i=1,2,....,Ns.t. y_i(w^Tx_i+b)\geqslant 1-{\xi}_i, i=1,2,....,N\\{\xi}_i\geq0,i=1,2,....,N
    来实现线性支持向量机的学习。我们可以发现,软间隔支持向量机的支持向量xix_i或在间隔边界上,或在间隔之间,或在分离超平面的误分一侧。

    在这里C是一个大于0的超参数,称惩罚参数,
    由于要最小化目标函数,仔细推敲不难发现:
    C值越小,对误分类的惩罚越小,(在gap内的样本点可能允许多些)。
    C值越大,对误分类的惩罚越大。
    由于时凸二次规划问题,同样通过求对偶问题来求解。
    w,b,ξ(w,b, {\xi})的解存在,且可以证明w 的解唯一,b的解在一个区间内。

    非线性支持向量机

    我们总是希望通过一个非线性变化,将非线性问题转化为线性可分问题来求解。

    当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过核方法可以学习非线性支持向量机,等价于在高维的特征空间中学习线性支持向量机。

    通俗点理解就是,当我们的数据在其本身的空间里面没办法做到线性可分的时候,我们把他们以某种方式映射到高维空间,以期实现在高维中间线性可分。这样操作的要点是要选择合适的映射方式,也是就是要选对核函数。

    举两个例子:
    在这里插入图片描述
    在这里插入图片描述
    可以看到,原本在低维不可分的数据,映射到高维之后,就变得线性可分了。
    再搬两张图,数据来源:https://www.zhihu.com/question/27210162
    在这里插入图片描述
    在这里插入图片描述
    好了,解决问题的关键就在于核函数,关于核函数的定义如下:
    在这里插入图片描述

    我们可以这样想(当然理论上不一定对),对于xiTxjx_i^Tx_j我们首先将其看作是两个映射函数在作内积,于是我们将其看作是一个映射至希尔伯特空间的线性核(因为线性核就是这样定义的),我们再将线性核替换成其他的核,实现在希尔伯特空间的变换,完成映射任务。

    于是,对于对偶问题中的xiTxjx_i^Tx_j,我们可以将其替换成合适的核函数k(xiTxj)k(x_i^Tx_j),实现非线性数据的高维线性可分。
    一般使用以下几种核函数:
    在这里插入图片描述

    SMO

    序列最小最优化算法SMO可以实现SVM的高效学习。
    他将凸二次规划的对偶问题不断的分解为子问题并求解,进而达到求解原问题的目的。
    参考文章:https://blog.csdn.net/luoshixian099/article/details/51227754

    ###############################
    一些延展:

    我们可以在这里从损失函数的角度看一下LR与SVM的异同:

    对于LR与SVM的异同我总结如下:

    LR的详细介绍:https://blog.csdn.net/b285795298/article/details/88683987

    - 相同点:

    • LR和SVM都是分类算法
    • LR和SVM都是监督学习算法。
    • LR和SVM都是判别模型
    • 如果不考虑核函数,LR和SVM都是线性分类算法,也就是说他们的分类决策面都是线性的。
      说明:LR也是可以用核函数的.但LR通常不采用核函数的方法.(计算量太大)

    LR和SVM不同点:

    1、LR采用log损失,SVM采用合页(hinge)损失。
    逻辑回归的损失函数:
    在这里插入图片描述
    支持向量机的目标函数:
    在这里插入图片描述
    ​逻辑回归方法基于概率理论,假设样本为1的概率可以用sigmoid函数来表示,然后通过极大似然估计的方法估计出参数的值(基于统计的,其损失函数是人为设定的凸函数) 。支持向量机​基于几何间隔最大化原理,认为存在最大几何间隔的分类面为最优分类面.(有严格的推导)

    2、LR对异常值敏感,SVM对异常值不敏感(抗燥能力,SVM要强)(https://www.jianshu.com/p/1a41a1567b87)。支持向量机只考虑局部的边界线附近的点,而逻辑回归考虑全局(远离的点对边界线的确定也起作用,虽然作用会相对小一些)。LR模型找到的那个超平面,是尽量让所有点都远离他,而SVM寻找的那个超平面,是只让最靠近中间分割线的那些点尽量远离,即只用到那些支持向量的样本。

    支持向量机改变非支持向量样本并不会引起决策面的变化:
    在这里插入图片描述逻辑回归中改变任何样本都会引起决策面的变化:
    在这里插入图片描述LR则受所有数据点的影响,如果数据不同类别strongly unbalance,一般需要先对数据做balancing。​(引自http://www.zhihu.com/question/26768865/answer/34078149)

    3、计算复杂度不同。对于海量数据,SVM的效率较低,LR效率比较高。 对于两者在feature和样本数量不同的情况下的效率问题,可以参考:https://blog.csdn.net/a244659184/article/details/81122521。该文章说明了:

    当样本较少,特征维数较低时,SVM和LR的运行时间均比较短,SVM较短一些。准确率的话,LR明显比SVM要高。当样本稍微增加些时,SVM运行时间开始增长,但是准确率赶超了LR。SVM时间虽长,但在接收范围内。当数据量增长到20000时,特征维数增长到200时,SVM的运行时间剧烈增加,远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算,造成SVM的二次规划问题)

    4、对非线性问题的处理方式不同,LR主要靠特征构造,必须组合交叉特征,特征离散化。SVM也可以这样,还可以通过kernel(因为只有支持向量参与核计算,计算复杂度不高)。(由于可以利用核函数,。SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时,表现较差。)

    5、SVM的损失函数就自带正则!!!(损失函数中的1/2||w||^2项),这就是为什么SVM是结构风险最小化算法的原因!!!而LR必须另外在损失函数上添加正则项!!!
    在这里插入图片描述
    关于正则化:
    给定一个数据集,一旦完成Linear SVM的求解,所有数据点可以被归成两类
    1)一类是落在对应分界平面外并被正确分类的点,比如落在正分界左侧的正样本或落在负分界右侧的负样本
    2)第二类是落在gap里或被错误分类的点。
    在这里插入图片描述
    假设一个数据集已经被Linear SVM求解,那么往这个数据集里面增加或者删除更多的一类点并不会改变重新求解的Linear SVM平面。这就是它区分与LR的特点,下面我们在看看LR。

    值得一提的是求解LR模型过程中,每一个数据点对分类平面都是有影响的,它的影响力远离它到分类平面的距离指数递减。换句话说,LR的解是受数据本身分布影响的。在实际应用中,如果数据维度很高,LR模型都会配合参数的L1 regularization。
    关于l1,l2正则化的深入介绍,推荐:https://blog.csdn.net/weixin_41481113/article/details/84304035

    要说有什么本质区别,那就是两个模型对数据和参数的敏感程度不同,Linear SVM比较依赖penalty的系数和数据表达空间的测度,而(带正则项的)LR比较依赖对参数做L1 regularization的系数。但是由于他们或多或少都是线性分类器,所以实际上对低维度数据overfitting的能力都比较有限,相比之下对高维度数据,LR的表现会更加稳定,为什么呢?
    因为Linear SVM在计算margin有多“宽”的时候是依赖数据表达上的距离测度(可以理解为度量标准,即在什么样的标准上计算gap的大小)的,换句话说如果这个测度不好(badly scaled,这种情况在高维数据尤为显著),所求得的所谓Large margin就没有意义了,这个问题即使换用kernel trick(比如用Gaussian kernel)也无法完全避免。所以使用Linear SVM之前一般都需要先对数据做
    normalization
    ,(这里的normalization是对数据的归一化,注意区分之前的LR在类别不平衡的时候做的balancing)而求解LR(without regularization)时则不需要或者结果不敏感。
    同时会有:feature scaling会使得gradient descent的收敛更好。
    如果不归一化,各维特征的跨度差距很大,目标函数就会是“扁”的:

    (图中椭圆表示目标函数的等高线,两个坐标轴代表两个特征)
    (图中椭圆表示目标函数的等高线,两个坐标轴代表两个特征)
    这样feature scaling之后,在进行梯度下降的时候,梯度的方向就会偏离最小值的方向,走很多弯路。
    如果归一化了,那么目标函数就“圆”了:
    在这里插入图片描述每一步梯度的方向都基本指向最小值,可以大踏步地前进。(引自https://www.zhihu.com/question/37129350)

    向您推荐我的其他文章:

    支持向量机(SVM)从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/81977271

    逻辑回归(Logistic Regression-LR)从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/88683987

    决策树(decesion Tree)从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/89086854

    随机森林(Random Forest) 从入门到放弃再到掌握:https://blog.csdn.net/b285795298/article/details/89084257

    #######################################################

    参考博文:
    机器学习中的线性代数之矩阵求导 https://blog.csdn.net/u010976453/article/details/54381248
    周志华老师的《机器学习》
    参考::https://www.jianshu.com/p/e8dca5613da6
    https://www.jianshu.com/p/1a41a1567b87
    https://www.cnblogs.com/bentuwuying/p/6616761.html
    https://blog.csdn.net/zwqjoy/article/details/82312783

    展开全文
  • 机器学习实战(六)——支持向量机

    万次阅读 多人点赞 2018-07-02 08:56:35
    第六章 支持向量机 6.1 什么是支持向量机 6.1.1 线性SVM 6.1.2 函数间隔和几何间隔 6.1.3 最大间隔分离超平面 6.1.4 支持向量和间隔边界 6.1.4 学习的对偶算法 6.2 线性支持向量机与软间隔最大化 6.2.1 线性支持...
  • 支持向量机

    2018-12-17 10:03:13
     动笔写这个支持向量机(support vector machine)是费了不少劲和困难的,原因很简单,一者这个东西本身就并不好懂,要深入学习和研究下去需花费不少时间和精力,二者这个东西也不好讲清楚,尽管网上已经有朋友写得...
  • 支持向量机实例

    2020-07-26 23:33:56
    对应于机器学习教程进行实战,通过代码的实现,理解机器学习中支持向量机的原理。
  • 支持向量机(SVM)

    万次阅读 多人点赞 2020-09-18 15:30:34
    支持向量机(Support Vector Machine)是一种十分常见的分类器,曾经火爆十余年,分类能力强于NN,整体实力比肩LR与RF。核心思路是通过构造分割面将数据进行分离。本文主要阐述SVM的基本工作原理和简单应用。 1....
  • 机器学习(支持向量机-SVM)

    千次阅读 2017-11-19 17:39:37
    训练集->提取特征向量->结合一定算法(分类器:比如决策树,KNN)->得到结果二、向量机的概念: 如图所示,就是一个二维几何空间中的分类。中间那条直线就是这个分类的超平面。我们不难发现,用来确定这条直线...
  • 基于支持向量机的图像分类(下篇:MATLAB实现)

    万次阅读 多人点赞 2020-04-13 12:31:05
    摘要:本文通过图文详细介绍如何利用支持向量机对图像进行分类,经过上篇文章对原理的介绍,这里介绍利用MATLAB编程实现。后续章节将介绍的主要部分有: 图片数据集整理 特征提取 SVM训练与测试 分类结果...
  • 支持向量机SVM、支持向量回归SVR详细推导

    万次阅读 多人点赞 2019-08-02 18:58:06
    文章详细介绍了支持向量机SVM及其拓展,支持向量回归SVR.并从线性分类和非线性分类的角度出发,详细推导了硬间隔、软间隔和核函数的支持向量机
  • 简单粗暴理解支持向量机(SVM)及其MATLAB实例

    万次阅读 多人点赞 2019-02-01 23:36:22
    目录 SVM概述 SVM的改进:解决回归拟合问题的SVR 多分类的SVM QP求解 SVM的MATLAB实现:Libsvm ...如果你要从零开始推导一个SVM,细致抠它全程的数学原理,我建议可以阅读此篇文章:Zhang Hao的《从零构建支...
  • 说来惭愧,断更快半个月了,本打算是一周一篇的。感觉SVM瞬间难了不少,推导耗费了很多时间,同时身边的事情也不少,忙了许久。本篇文章参考了诸多大牛的文章写成的,对于什么是SVM做出了生动的阐述,同时也进行了...
  • 基于支持向量机的图像分类(上篇)

    万次阅读 多人点赞 2018-03-31 21:28:29
    摘要:本文通过图文详细介绍如何利用支持向量机对图像进行分类。这篇文章从什么是图像分类任务开始一步步详细介绍支持向量机原理,以及如何用它解决图像多分类任务。将这部分内容分为上下两篇:上篇重点详细介绍实现...
  • SVM支持向量机原理及核函数

    万次阅读 多人点赞 2018-04-07 20:21:18
    SVM支持向量机原理详解及核函数 核函数的选择 分割超平面: 支持向量: 间距: SVM算法的原理就是找到一个分割超平面,它能把数据正确的分类,并且间距最大!
  • 基于支持向量机SVM的文本分类的实现

    万次阅读 多人点赞 2020-07-01 16:50:03
    SVM 文本分类算法主要分四个步骤:文本特征提取、文本特征表示、归一化处理和文本分类。
  • 支持向量机(预测)

    万次阅读 2017-07-04 11:13:20
    对于支持向量的回归预测,采用不同的核函数会有不用的性能,下面不去介绍具体的算法,而是采用预测波斯顿房价一个案例来介绍三种不同核函数下的支持向量机的回归预测模型,并比较他们的性能。 使用的语言是python...
  • 支持向量机SVM算法原理及应用(R)

    万次阅读 2019-07-22 23:11:11
    只要接触到数据挖掘/机器学习,相比都会听过“支持向量机”的大名。在机器学习领域,支持向量机SVM(Support Vector Machine)是一个有监督的学习模型,通常用来进行模式识别、分类、以及回归分析。SVM涉及的知识面...
1 2 3 4 5 ... 20
收藏数 89,100
精华内容 35,640
关键字:

支持向量机