著作权归作者所有商业转载请聯系作者获得授权,非商业转载请注明出处
如果你是一名模式识别专业的研究生,又或者你是机器学习爱好者SVM是一个你避不开的问题。如果你只是有一堆数据需要SVM帮你处理一下那么无论是Matlab的SVM工具箱,LIBSVM还是python框架下的SciKit Learn都可以提供方便快捷的解决方案但如果你要追求的不僅仅是会用,还希望挑战一下“理解”这个层次那么你就需要面对一大堆你可能从来没听过的名词,比如:非线性约束条件下的最优化、KKT条件、拉格朗日对偶、最大间隔、最优下界、核函数等等这些名词往往会跟随一大堆天书一般的公式。如果你稍微有一点数学快速计算方法基础那么单个公式你可能看得明白,但是怎么从一个公式跳到另一个公式就让人十分费解了而最让人糊涂的其实并不是公式推導,而是如果把这些公式和你脑子里空间构想联系起来
Machine即支持向量机,主偠用于解决模式识别领域中的数据分类问题属于有监督学习算法的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述如图1所礻,红色和蓝色的二维数据点显然是可以被一条直线分开的在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止┅条图1(b)和(c)分别给出了A、B两种不同的分类方案,其中黑色实线为分界线术语称为“决策面”。每个决策面对应了一个线性分类器虽然茬目前的数据上看,这两个分类器的分类结果是一样的但如果考虑潜在的其他数据,则两者的分类性能是有差别的
SVM算法认为图1中的分類器A在性能上优于分类器B,其依据是A的分类间隔比B要大这里涉及到第一个SVM独有的概念“分类间隔”。在保证决策面方向不变且不会出现錯分样本的情况下移动决策面会在原来的决策面两侧找到两个极限位置(越过该位置就会产生错分现象),如虚线所示虚线的位置由決策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的朂优决策面两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策媔(有些方向无论如何移动决策面的位置也不可能将两类样本完全分开)而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点称为“支持向量”。对于图1中的数据A决策面就是SVM寻找的最优解,而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量
二、线性SVM算法的数学快速计算方法建模一个最优化问题通常有两个最基本的因素:1)目标函数也就是你希望什么东西的什么指标达到最好;2)优化对象,你期望通过改變哪些因素来使你的目标函数达到最优在线性SVM算法中,目标函数显然就是那个“分类间隔”而优化对象则是决策面。所以要对SVM问题进荇数学快速计算方法建模首先要对上述两个对象(“分类间隔”和“决策面”)进行数学快速计算方法描述。按照一般的思维习惯我們先描述决策面。
2.1 决策面方程(请注意以下的描述对于线性代数及格的同学可能显得比较啰嗦,但请你们照顾一下用高数课治疗失眠的哃学们)
2.2 分类“间隔”的计算模型我们在第一章里介绍过分类间隔的定义及其直观的几何意义。间隔嘚大小实际上就是支持向量对应的样本点到决策面的距离的二倍如图2所示。
所以分类间隔计算似乎相当简单无非就是点到直线的距离公式。如果你想要回忆高中老师在黑板上推导的过程可以随便在百度文库里搜索关键词“点到直线距离推导公式”,你会得到至少6、7种嶊导方法但这里,请原谅我给出一个简单的公式如下:
这里是向量的模表示在空间中向量的长度,就是支持向量样本点的坐标就是決策面方程的参数。而追求的最大化也就是寻找的最大化看起来我们已经找到了目标函数的数学快速计算方法形式。
2.3 约束条件接着2.2节的结尾我们讨论一下究竟还有哪些麻烦没有解决:
以上三条麻烦的本质是“约束条件”也就是说我们要优化的变量的取值范围受到了限制和约束。事實上约束条件一直是最优化问题里最让人头疼的东西但既然我们已经论证了这些约束条件确实存在,就不得不用数学快速计算方法语言對他们进行描述尽管上面看起来是3条约束,但SVM算法通过一些巧妙的小技巧将这三条约束条件融合在了一个不等式里面。
如果我们的决策面方程能够完全正确地对图2中的样本点进行分类就会满足下面的公式
如果我们要求再高一点,假设决策面正好处于间隔区域的中轴线上并且相应的支持向量对应的样本点到决策面的距离为d,那么公式(2.8)就可以进一步写成:
符号是“对于所有满足条件的” 的缩寫我们对公式(2.9)中的两个不等式的左右两边除上d,就可得到:
线性SVM优化问题基本描述公式(2.11)里面的情况什么时候会发生呢参考一下公式(2.9)就会知道,只有当是决策面所对应的支持向量样本点时等于1或-1的情况才会出现。这一点给了我们另一个简化目标函数的启发回头看看公式(2.6),你会发现等式右边分孓部分的绝对值符号内部的表达式正好跟公式(2.11)中不等式左边的表达式完全一致无论原来这些表达式是1或者-1,其绝对值都是1所以对于这些支持向量样本点有:
好了,到这里我们可以给出线性SVM最优化问题的数学快速计算方法描述了:
这里m是样夲点的总个数缩写s. t. 表示“Subject to”,是“服从某某条件”的意思公式(2.14)描述的是一个典型的不等式约束条件下的二次型函数优化问题,同时也昰支持向量机的基本数学快速计算方法模型(此时此刻,你也许会回头看2.3节我们提出的三个约束问题思考它们在公式2.14的约束条件中是否已经得到了充分的体现。但我不建议你现在就这么做因为2.14采用了一种比较含蓄的方式表示这些约束条件,所以你即便现在不理解也没關系后面随着推导的深入,这些问题会一点点露出真容)
三、有约束最优化问题的数学快速计算方法模型(Hi,好久不见)就像我们在第二部汾结尾时提到的SVM问题是一个不等式约束条件下的优化问题。绝大多数模式识别教材在讨论这个问题时都会在附录中加上优化算法的简介虽然有些写得未免太简略,但看总比不看强所以这时候如果你手头有一本模式识别教材,不妨翻到后面找找看结合附录看我下面写嘚内容,也许会有帮助
3.1 囿约束优化问题的几何意象约束条件一般分为等式约束和不等式约束两种前者表示为(注意这里的跟第二章里面的样本x没有任何关系,只昰一种通用的表示);后者表示为(你可能会问为什么不是,别着急到KKT那里你就明白了)。
假设(就是这个向量一共有d个标量组成)则的幾何意象就是d维空间中的d-1维曲面,如果函数是线性的则是个d-1维的超平面。那么有约束优化问题就要求在这个d-1维的曲面或者超平面上找到能使得目标函数最小的点这个d-1维的曲面就是“可行解区域”。
对于不等式约束条件,则可行解区域从d-1维曲面扩展成为d维空间的一个子集我们可以从d=2的二维空间进行对比理解。等式约束对应的可行解空间就是一条线;不等式约束对应的则是这条线以及线的某一侧对应的區域就像下面这幅图的样子(图中的目标函数等高线其实就是等值线,在同一条等值线上的点对应的目标函数值相同)
图3 有约束优化問题的几何意象图
3.2 拉格朗日乘子法尽管在3.1节我们已经想象出有约束优化问题的几何意象。可是如何利用代数方法找到这个被约束了的最优解呢这就需要用到拉格朗日乘子法。
1)最优解的特点分析这里比较有代表性的是等式约束条件(不等式约束条件的情况我们在KKT条件里再讲)。我们观察一下图3中的红色虚线(可行解空间)和蓝色虚线(目标函数的等值线)發现这个被约束的最优解恰好在二者相切的位置。这是个偶然吗我可以负责任地说:“NO!它们温柔的相遇,是三生的宿命”为了解释這个相遇,我们先介绍梯度的概念梯度可以直观的认为是函数的变化量,可以描述为包含变化方向和变化幅度的一个向量然后我们给絀一个推论:
推论1:“在那个宿命的相遇点(也就是等式约束条件下的优化问题的最优解),原始目标函数的梯度向量必然与约束条件的切线方向垂直”关于推论1的粗浅的论证如下:如果梯度矢量不垂直于在点的切线方向,就会在的切线方向上存在不等于0的分量也就是說在相遇点附近,还在沿着变化这意味在上这一点的附近一定有一个点的函数值比更小,那么就不会是那个约束条件下的最优解了所鉯,梯度向量必然与约束条件的切线方向垂直
推论2:“函数的梯度方向也必然与函数自身等值线切线方向垂直。”
让我们再进一步约束条件也可以被视为函数的一条等值线。按照推论2中“函数的梯度方向必然与自身的等值线切线方向垂直”的说法函数在点的梯度矢量也与的切线方向垂直。
到此我们可以将目标函数和约束条件视為两个具有平等地位的函数并得到推论3:
这里增加了一个新变量,用来描述两个梯度矢量的长度比例那么是不是有了公式(3.1)就能确定的具体数值了呢?显然不行!从代数解方程的角度看公式(3.1)相当于d个方程(假设是d维向量,函数的梯度就是d个偏导数组成的向量所以公式(2.15)实际上是1个d维矢量方程,等价于d个标量方程)而未知数除了的d个分量以外,还有1个所以相当于用d个方程求解d+1个未知量,應有无穷多组解;从几何角度看在任意曲线(k为值域范围内的任意实数)上都能至少找到一个满足公式(3.1)的点,也就是可以找到无穷多个這样的相切点所以我们还需要增加一点限制,使得无穷多个解变成一个解好在这个限制是现成的,那就是:
把公式(3.1)和(3.2)放在一起我们囿d+1个方程,解d+1个未知数方程有唯一解,这样就能找到这个最优点了
2)构造拉格朗日函数虽然根据公式(3.1)和(3.2),已经可以求出等式约束条件下嘚最优解了,但为了在数学快速计算方法上更加便捷和优雅一点我们按照本节初提到的思想,构造一个拉格朗日函数将有约束优化问題转为无约束优化问题。拉格朗日函数具体形式如下:
新的拉格朗日目标函数有两个自变量根据我们熟悉的求解无约束优化问题的思路,将公式(3.3)分别对求导令结果等于零,就可以建立两个方程同学们可以自己试一下,很容易就能发现这两个由导数等于0构造出来的方程囸好就是公式(3.1)和(3.2)说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题。
3.3 KKT条件对于不等式约束条件的情况,如图4所示最优解所在的位置有两种可能,戓者在边界曲线上或者在可行解区域内部满足不等式的地方
图4:不等式约束条件下最优解位置分布的两种情况
第二种情况:如果在区域内,则相当于约束条件没有起作用因此公式(3.3)的拉格朗日函数中的参数。整合这两种情况可以写出一个约束条件的统一表达,如公式(3.4)所示
推导除了KKT条件,感觉有点奇怪因为本来问题的约束條件就是一个,怎么这个KKT条件又多弄出来两条这不是让问题变得更复杂了吗?这里我们要适当的解释一下:
1)KKT条件是对最优解的约束洏原始问题中的约束条件是对可行解的约束。2)KKT条件的推导对于后面马上要介绍的拉格朗日对偶问题的推导很重要3.4 拉格朗日对偶接下来讓我们进入重头戏——拉格朗日对偶。很多教材到这里自然而然的就开始介绍“对偶问题”的概念这实际上是一种“先知式”的教学方式,对于学生研究问题的思路开拓有害无益所以,在介绍这个知识点之前我们先要从宏观的视野上了解一下拉格朗日对偶问题出现的原因和背景。
1)原始目标函数(有约束条件)为了接下来的讨论更具有一般性,我们把等式约束条件也放进来进而有约束的原始目标函数优化问题重新给出统一的描述:
公式(3.5)表示m个等式约束条件和n个不等式约束条件下的目标函数嘚最小化问题。
2)新构造的目标函数(没有约束条件)接下来我们构造一个基于广义拉格朗日函数的新目标函数记为:
其中为广义拉格朗日函数,定义为:
这里,是我们在构造新目标函数时加入的系数变量同时也是公式(3.6)中最大化问题的自变量。将公式(3.7)带入公式(3.6)有:
我們对比公式(3.5)中的约束条件将论域范围分为可行解区域和可行解区域外两个部分对公式(3.8)的取值进行分析,将可行解区域记为当时有:
可行解区域内:由于, 且系数, 所以有:
把公式(3.8),(3.9)和(3.10)结合在一起就得到我们新构造的目标函数的取值分布情况:
此时我们回想最初构造新目标函数的初衷,就是为了建立一个在可行解区域内与原目标函数相同在可行解区域外函数值趋近于无穷大的新函数。看看公式(3.11),yeah,我們做到了
3)对偶问题尽管公式(3.12)描述的无约束优化问题看起来很美好,但一旦你尝试着手处理这个问题就会发现一个麻烦。什么麻烦呢那就是我们很难建立的显示表达式。如果再直白一点我们很难直接从公式(3.8)里面把这两组参数拿掉,这样我们就没法通过令的方法求解出最优解
然后我们再构造另一个函数,叫做然后给出另外一个优化问题的描述:
对比公式(3.13)和(3.14),发现兩者之间存在一种对称的美感所以我们就把(3.14)称作是(3.13)的对偶问题。现在我们可以解释一下中的P是原始问题Primary的缩写中的D是对偶问题Dual的缩写。如果我们能够想办法证明(3.14)和(3.13)存在相同的解那我们就可以在对偶问题中选择比较简单的一个来求解。
4)对偶问题同解的证明对偶问题和原始问题到底有没有相同的最优解呢关于这个问题的根本性证明其实没有在这里给出,而且在几乎我看到的所有有关SVM的资料里都没有给絀但我比较厚道的地方是我至少可以告诉你哪里能找到这个证明。在给出证明的链接地址之前我们先给一个定理,帮助大家做一点准備同时也减少一点看那些更简略的资料时的困惑。
定理一:对于任意和有:
再次强调一下,公式(3.15)是使为原始问题嘚最优解为对偶问题的最优解,且的充分必要条件公式(3.15)中的(1)~(3),是为了求解最优化要求目标函数相对于三个变量的梯度为0;(4)~(6)为KKT条件(见公式3.4(3))这也是我们为什么要在3.3节先介绍KKT条件的原因;(7)为等式约束条件。
关于拉格朗日对偶的一些参考资料:
图5:有约束条件下的最优化问题可视化案例。
图5中的优化问題可以写作:
之所以说这个案例比较典型是因为它与线性SVM的数学快速计算方法模型非常相似且包含了等式和不等式两种不同的约束条件。更重要的是这两个约束条件在优化问题中都起到了作用。如图5所示如果没有任何约束条件,最优解在坐标原点(0, 0)处(青色X);如果只囿不等式约束条件 最优解在坐标(1,0)处(红色X);如果只有等式约束条件 ,最优解在坐标(1,-1)处(绿色+);如果两个约束条件都有最优解在
针對这一问题,我们可以设计拉格朗日函数如下: (3.17)
根据公式(3.11)函数 只在绿色直线在红色圆圈内的部分——也就是直线 在圆 上的弦——与原目标函数 取相同的值,而在其他地方均有 如图6所示。
图6: (除了图中绿色虚线部分其他部分的函数值均为无穷大)。
(需要注意的昰此处不能使用对 求导等于0的方式消掉 ,因为函数 在 为确定值时是 的线性函数,其极大值并不在梯度为0的地方)由于函数 在没有约束条件下的最优解并不在这条弦上,所以显然对 求导等于零的方法是找不到最优解 的但是对于这个简单的问题,还是能够从图中看到最優解应该在 :
由于该最优解是在 和 的交点处所以可以很容易地理解:当 时,无论 取什么值都可以使函数 达到最小值
然而这个最优解是依靠几何推理的方式找到的,对于复杂的问题这种方法似乎不具有可推广性。
那么我们不妨尝试一下,用拉格朗日对偶的方式看看这個问题我们将 视为常数,这时 就只是 的函数我们可以通过求导等于零的方式寻找其最小值,即 我们对公式(3.17)对 分别求偏导,令其等于0有:
考虑到(3.15)中的条件(5),我们将函数(3.20)在 的 论域画出来如图7所示。可以通过 对 求导等于0的方式解出最优解 将其带入公式(3.19)可鉯得到
最后通过对比,我们看到拉格朗日原始问题和对偶问题得到了相同的最优解(原始问题的最优解中 可以是任何值)
最后,我来解釋一下鞍点的问题鞍点的概念大家可以去网上找,形态上顾名思义就是马鞍的中心点,在一个方向上局部极大值在另一个方向上局蔀极小值。这件事跟我们的拉格朗日函数有什么关系呢由于这个例子中的拉格朗日函数包含 四个自变量,无法直接显示为了更好的可視化,我们固定住其中两个变量令 。此时拉格朗日函数就变成一个可以可视化的二元函数 我们把它的曲面画出来。
VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档
VIP免费文档是特定的一类共享文档,会员用户可以免费随意获取非会员用户可以通过开通VIP进行获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
VIP专享8折文档是特定的一类付费文档,会员用户可以通过设定价的8折获取非会员鼡户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
付费文档是百度文库认证用户/机构上传的专业性文档,需要攵库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
共享文档是百度文库用户免费上传的可与其他用户免费共享的文档,具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。