文档介绍：数学之路(3)-机器学****3)-机器学****算法-SVM[1]分类:智能与数学2013-07-1020:38450人阅读评论(0)收藏举报数学SVMSVM支持向量机我们考虑以下形式的样本点超平面的数学形式可以写作。其中是超平面上的点,是垂直于超平面的向量。根据几何知识,我们知道向量垂直于分类超平面。加入位移b的目的是增加间隔。如果没有b的话,那超平面将不得不通过原点,限制了这个方法的灵活性。由于我们要求最大间隔,因此我们需要知道支持向量以及(与最佳超平面)平行的并且离支持向量最近的超平面。我们可以看到这些平行超平面可以由方程族:。来表示。由于只是超平面的法向量,长度未定,是一个变量,所以等式右边的1和-1只是为计算方便而取的常量,其他常量只要互为相反数亦可。如果这些训练数据是线性可分的,那就可以找到这样两个超平面,在它们之间没有任何样本点并且这两个超平面之间的距离也最大。通过几何不难得到这两个超平面之间的距离是2/|w|,因此我们需要最小化|w|。同时为了使得样本数据点都在超平面的间隔区以外,我们需要保证对于所有的满足其中的一个条件这两个式子可以写作:在数学最优化问题中,拉格朗日乘数法(以数学家约瑟夫·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n个变量与k个约束条件的最优化问题转换为一个有n+k个变量的方程组的极值问题,其变量不受任何约束。这种方法引入了一种新的标量未知数,即拉格朗日乘数:约束方程的梯度(gradient)的线性组合里每个向量的系数。简单举例:最大化受限于引入新变量拉格朗日乘数,即可求解下列拉格朗日方程微积分中最常见的问题之一是求一个函数的极大极小值(极值)。但是很多时候找到极值函数的显式表达是很困难的,特别是当函数有先决条件或约束时。拉格朗日乘数则提供了一个非常便利方法来解决这类问题,而避开显式地引入约束和求解外部变量。先看一个二维的例子:假设有函数:,要求其极值(最大值/最小值),且满足条件c为常数。对不同的值,不难想像出的等高线。而方程的等高线正好是。想像我们沿着的等高线走;因为大部分情况下和的等高线不会重合,但在有解的情况下,这两条线会相交。想像此时我们移动上的点,因为是连续的方程,我们因此能走到更高或更低的等高线上,也就是说可以变大或变小。只有当和相切,也就是说,此时,我们正同时沿着和走。这种情况下,会出现极值或鞍点。绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f的等高线。箭头表示斜率,和等高线的法线平行。气象图中就很常出现这样的例子,当温度和气压两列等高线同时出现的时候,切点就意味着约束极值的存在。用向量的形式来表达的话,我们说相切的性质在此意味着和的斜率在某点上平行。此时引入一个未知标量λ,并求解:且λ≠,将其套入下式,易求在无约束极值和极值所对应的点。=新方程在达到极值时与相等,因为达到极值时总等于零。如f定义为在Rn上的方程,约束为gk(x)=ck(或将约束左移得到gk(x)?ck=0)。定义拉格朗日Λ为注意极值的条件和约束现在就都被记录到一个式子里了:和拉格朗日乘数常被用作表达最大增长值。原因是从式子:求此方程的最小值:同时未知数满足因为只有一个未知数的限制条件,,得到一个方程组,最大值是以下方程组的解中的一个:求解方程组,结果如下:lambda=00-1/3*3^(1/2)-1/3*3^(1/2)1/3*3^(1/2)1/3*3^(1/2)x=001/3*6^(1/2)-1/3*6^(1/2)1/3*6^(1/2)-1/3*6^(1/2)y=1-11/3*3^(1/2)1/3*3^(1/2)-1/3*3^(1/2)-1/3*3^(1/2)因此,f(x,y)的最小值为-(1)这个约束条件下最小化|w|.这是一个二次规划QP(quadraticprogramming)最优化中的问题。更清楚的表示:最小化,满足其中。1/2这个因子是为了数学上表达的方便加上的。:假如我们能找到一族超平面将这些点分割开来;,此最小值对这一族内所有成员都有效,而不是解决原问题的最优解。不过以前的约束问题可以表示为此式表明我们寻找一个鞍点。这样所有可以被分离的点就无关紧要了,因为我们必须设置相应的为零。这个问题现在可以用标准二次规划技术标准和程序解决。,: