精华内容
下载资源
问答
  • lagrange dual problem
    千次阅读
    2018-06-13 19:45:48

    很高兴阿森纳能在欧冠上战胜拜仁,在虎扑上看到这样的一句话,颇有感触,借来作为这篇博文的开始,生活中我们需要一些勇气去追寻自己的理想。回到本篇内容上,对偶是个神奇的东西,从文学角度而言,对偶和对仗属于一种修辞手法,即用字数相等,语义对称的方法来表征想法或抒发情感。“凡心所向,素履所往,生如逆旅,一苇以航”或者“棋逢对手,将遇良才”都可看成是一种对偶。

    但是,本文是要阐述在数学问题上的对偶问题,它是优化问题中非常重要的方法,类似于文学的对偶,也是一种配对方式,只不过是将某种数学结构AA转换为另一种对等的数学结构BB。在优化问题中,可以将非凸问题转化为凸优化问题进行求解。虽然文学上和数学上表达对偶的意思相差甚远,但是我觉得二者在各自领域的重要性是可以比拟的。

    update: 在完成本篇博文时,拜仁5:1战胜阿森纳,小组出线堪忧。

    说到对偶问题,我们先从线性规划谈起,考虑以下简单的线性规划(LP)问题,我们如何求得函数的下界:

    minx,ysubjecttox+3yx+y2x,y0minx,yx+3ysubjecttox+y≥2x,y≥0

    实际上,我们可以从两个角度求解这个问题:首先,我们可以采用图解法找寻问题的解。下图中蓝线代表x+3y=0x+3y=0的直线,黑线表示约束x+y=2x+y=2,我们可以通过移动蓝线的位置,使得蓝线右上方的所有点xxyy满足约束,因此,直至蓝线移至红线位置才能满足上述LP问题的约束,而黄线代表的x+3y=0.6x+3y=0.6则不能满足约束,因为点(x,y)=(0,0.2)(x,y)=(0,0.2)不满足x+y2x+y≥2的条件。

    因此,通过作图,移动目标函数直线的位置,我们都能获得上述LP问题的最小值,即为2。

    同样,我们也可以利用以下变换获得目标函数的最小值:

    x+y2+2y0=x+3y2x+y≥2+2y≥0=x+3y≥2

    很明显,x+3yx+3y的最小值为2。如果我们泛化上述LP问题为:

    minx,ysubjecttopx+qyx+y2x,y0minx,ypx+qysubjecttox+y≥2x,y≥0

    我们如何求解?按照变换方法,我们可以获得:

    a(x+y)2a+bx0+cy0=(a+b)x+(a+c)y2aa(x+y)≥2a+bx≥0+cy≥0=(a+b)x+(a+c)y≥2a

    因此,我们只要使得a+b=pa+b=p,同时a+c=qa+c=q,那么上述问题的最优解为2a2a。这里2a2apx+qypx+qy的下界,即px+qy2apx+qy≥2a永远成立,所以,我们应当使得下界最大化,找到满足约束条件a+b=pa+b=pa+c=qa+c=q的最大值aa,才能求得左式的最小值。

    综上所述,上述LP问题就转换为求下面形式的最大值:

    maxa,b,csubjectto2aa+b=pa+c=qa,b,c0maxa,b,c2asubjecttoa+b=pa+c=qa,b,c≥0

    我们即称上述变换为原问题(Primal)的对偶(dual)问题。

    2. 线性规划问题的对偶问题

    对于一般形式的线性规划问题:

    minxRnsubjecttocTxAx=bGxhminx∈RncTxsubjecttoAx=bGx≤h

    我们可以获得其对偶问题:

    maxuRm,vRrsubjecttobTuhTvATuGTv=cv0maxu∈Rm,v∈Rr−bTu−hTvsubjectto−ATu−GTv=cv≤0

    因为:

    uTAx=bTu+vTGxhTv=(ATuGTv)TxbTuhTv−uTAx=−bTu+−vTGx≥−hTv=(−ATu−GTv)Tx≥−bTu−hTv

    如果cc满足c=ATuGTvc=−ATu−GTv,那么我们可以获得LP问题解得下界bTuhTv−bTu−hTv

    3. 拉格朗日函数

    根据LP对偶问题的构建方法,我们可以令L(x,u,v):=cTx+uT(Axb)+vT(Gxh)L(x,u,v):=cTx+uT(Ax−b)+vT(Gx−h),其中v0v≥0。因为,Axb=0Ax−b=0且对于v,vt(Gxh)0∀v,vt(Gx−h)≤0,因此,L(x,u,v)cTxL(x,u,v)≤cTx

    如果我们假设集合CC为原问题的解集合,ff⋆为最优解,那么对于任意uuv0v≥0,我们可以获得:

    f=minxCcTxminxCL(x,u,v)minxL(x,u,v)=minx(c+uTA+vTG)TxuTbvTh:=g(u,v)f⋆=minx∈CcTx≥minx∈CL(x,u,v)≥minxL(x,u,v)=minx(c+uTA+vTG)Tx−uTb−vTh:=g(u,v)

    对于上式,minxL(x,u,v)minxL(x,u,v)为关于xx的线性函数,因此,如果c+uTA+vTGc+uTA+vTG不等于0,那么对于所有xx,函数L(x,u,v)L(x,u,v)最小值为−∞,所以,想要保证求得原问题的最小值,我们必须保证c+uTA+vTG=0c+uTA+vTG=0,此时,g(u,v)=minxL(x,u,v)=bTuhTvg(u,v)=minxL(x,u,v)=−bTu−hTv

    综上所述,我们可以获得函数g(u,v)g(u,v)的一般形式:

    g(u,v)={bTuhTvifc=uTAvTGotherwiseg(u,v)={−bTu−hTvifc=−uTA−vTG−∞otherwise

    现在我们最大化函数g(u,v)g(u,v),获得原问题的紧致下界(tightest bound),这与上面之前定义的对偶问题完全一致。同时,这种变换或者解释方法可以适用于任意优化问题上,甚至是非凸优化问题。我们可以根据有约束的优化问题获得函数L(x,u,v)L(x,u,v),然后求解minxL(x,u,v)minxL(x,u,v)得到函数g(u,v)g(u,v),即为原问题的对偶问题。

    综上所述,对于一般有约束的优化问题,如下:

    minxsubjecttof(x)hi(x)0,i=1,,mli(x)=0,j=1,,rminxf(x)subjecttohi(x)≤0,i=1,…,mli(x)=0,j=1,…,r

    无论f(x)f(x)是否为凸函数,我们都可以定义拉格朗日函数(Lagrangian)为:

    L(x,u,v)=f(x)+i=1muihi(x)+j=1rvjlj(x)L(x,u,v)=f(x)+∑i=1muihi(x)+∑j=1rvjlj(x)

    其中,u0u≥0,同时,定义朗格朗日函数L(x,u,v)=foru<0L(x,u,v)=−∞foru<0。意味着对于任意可行解xx,且u0u≥0f(x)L(x,u,v)f(x)≥L(x,u,v)。下图是Boyd凸优化一书中给出拉格朗日函数的实例图:

    图中,实线表示函数f(x)f(x),虚线表示函数h(x)h(x),为约束,点线表示不同u,vu,v下的函数L(x,u,v)L(x,u,v)。根据约束信息,我们可以获得函数可行解域为[-0.46,0.46],在该区域下f(x)L(x,u,v)f(x)≥L(x,u,v)

    同样,如果我们假设集合CC为原问题的解集合,ff⋆为最优解,那么对于任意xx,最小化函数L(x,u,v)L(x,u,v)可以获得函数下界:

    f=minxCcTxminxCL(x,u,v)minxL(x,u,v):=g(u,v)f⋆=minx∈CcTx≥minx∈CL(x,u,v)≥minxL(x,u,v):=g(u,v)

    我们称函数g(u,v)g(u,v)拉格朗日对偶函数(Lagrange dual function),对于对偶可行解u,vu,v,它给定了ff⋆的下界(其中u0u≥0),我们最大化g(u,v)g(u,v),即可获得ff⋆的逼近解。如下图,虚线表示原问题最优解ff⋆,实线表征不同uug(u)g(u)的值,可以看出,最大化g(u)g(u)可以逼近ff⋆,(图中的λλuu):

    3. 对偶函数实例:二次规划

    这里,我们用二次函数的优化问题作为一个例子来说明如何获得拉格朗日对偶函数,我们定义二次规划为:

    minxsubjectto12xTQx+cTxAx=bx0minx12xTQx+cTxsubjecttoAx=bx≥0

    其中,Q0Q≻0

    因此,拉格朗日函数L(x,u,v)=12xTQx+cTxuTx+vT(Axb)=12xTQx+(c+vTAu)Tx+vTbL(x,u,v)=12xTQx+cTx−uTx+vT(Ax−b)=12xTQx+(c+vTA−u)Tx+vTb,对于形如ax2+bx+cax2+bx+c的二次函数,我们可以获得函数的根为x=b2ax=−b2a,即x=(cu+ATv)Q1x=(c−u+ATv)Q−1,函数L(x,u,v)L(x,u,v)的最小值为12(cu+ATv)TQ1(cu+ATv)bTv−12(c−u+ATv)TQ−1(c−u+ATv)−bTv

    所以,我们可以获得拉格朗日对偶函数g(u,v)=minxRnL(x,u,v)=12(cu+ATv)TQ1(cu+ATv)bTvg(u,v)=minx∈RnL(x,u,v)=−12(c−u+ATv)TQ−1(c−u+ATv)−bTv,其中u0u≥0vv为任意值。

    4. 拉格朗日对偶问题

    拉格朗日对偶问题是指对于原问题:

    minxsubjecttof(x)hi(x)0,i=1,,mli(x)=0,j=1,,rminxf(x)subjecttohi(x)≤0,i=1,…,mli(x)=0,j=1,…,r

    我们通过构造对偶函数g(u,v)g(u,v),然后最大化该对偶函数的优化问题,即:

    maxu,vsubjecttog(u,v)u0maxu,vg(u,v)subjecttou≥0

    对于原问题的对偶问题,它有两个重要性质:

    • 弱对偶性(weak duality):无论是凸优化或非凸优化原问题,fgf⋆≥g⋆(因为f(x)g(u,v)f(x)≥g(u,v));

    • 对偶问题是凸优化问题:无论原问题是凸优化还是非凸,因为lj(x)lj(x)为凸函数

    这里需要指出的是,是不是我们可以获得任意原问题的对偶问题,这样就可以采用之前提到过的下降算法等来求解该凸优化问题?

    答案是否定的,虽然无论原问题为何种形式,其对偶问题永远是凸优化问题,但是这里的关键并不是说不能用下降算法求解,而是我们对于非凸问题一般无法获得或者较难获得其对偶问题的表达式g(u,v)g(u,v),这就限制了我们对于非凸优化问题的求解方法。

    对于对偶问题,弱对偶性永远成立,更进一步,如果我们可以获得f=gf⋆=g⋆,那么我们就可以保证求解对偶问题获得的最优解可以变换为原问题的最优解。我们将f=gf⋆=g⋆形式成为强对偶性(strong duality)

    Slater’s condition:如果原(primal)问题为凸优化问题(即:f,h1,,hmf,h1,…,hm为凸函数,l1,,lrl1,…,lr是仿射函数),同时存在至少一个可行解满足h1(x)<0,,hm(x)<0,l1(x)==lr(x)=0h1(x)<0,…,hm(x)<0,l1(x)=…=lr(x)=0,那么该问题的强对偶性成立,即f=gf⋆=g⋆

    因此,根据强对偶性的定义和成立条件,我们可以获得以下性质:

    • LP问题对偶问题的对偶问题为原问题(the dual of the dual LP is the primal LP);

    • 如果LP问题存在可行解,那么LP问题满足具有强对偶性;

    根据强对偶性定义,我们可以衍伸出对偶间隙(duality gap)的定义,对偶间隙是指f(x)g(u,v)f(x)−g(u,v),很明显,f(x)ff(x)g(u,v)f(x)−f⋆≤f(x)−g(u,v),因此,如果对偶间隙为0,那么f(x)f=f(x)gf(x)−f⋆=f(x)−g⋆,这时,u,vu,v和对应获得的xx分别为对偶问题和原问题的最优解。

    对偶间隙的最大用途是作为算法停止迭代的条件,即如果我们想要保证f(x)fϵf(x)−f⋆≤ϵ,那么需要f(x)g(u,v)ϵf(x)−g(u,v)≤ϵ

    5. 对偶问题实例:SVM对偶问题

    之前我们提到过,SVM问题是:

    minβ,β0,ξsubjectto12β22+Cinξiξ0,i=1,,nyi(xTiβ+β0)1ξi,i=1,,nminβ,β0,ξ12∥β∥22+C∑inξisubjecttoξ≥0,i=1,…,nyi(xiTβ+β0)≥1−ξi,i=1,…,n

    引入对偶变量(dual variables),v,w0v,w≥0,我们可以构建拉格朗日函数:

    L(β,β0,ξ,v,w)=12β22+Ci=1nξi=1nviξ+i=1nwi(1ξyi(xTiβ+β0))L(β,β0,ξ,v,w)=12∥β∥22+C∑i=1nξ−∑i=1nviξ+∑i=1nwi(1−ξ−yi(xiTβ+β0))

    如想获得拉格朗日对偶函数,我们需要对β,β0,ξβ,β0,ξ求导。

    (1)对β0β0求导,我们获得:Lβ0=i=1nyiwi=wTy∂L∂β0=−∑i=1nyiwi=wTy。因为拉格朗日函数LL是关于β0β0的仿射函数,所以wTy=0wTy=0,否则,min(L)=min(L)=−∞,即获得约束wTy=0wTy=0

    (2)对ξiξi求导,我们获得:Lξi=i=1ncviwi=CIvw∂L∂ξi=−∑i=1nc−vi−wi=CI−v−w。因为拉格朗日函数LL是关于ξiξi的仿射函数,所以需要CIvw=0CI−v−w=0,否则,min(L)=min(L)=−∞,即获得约束w=CIvw=CI−v

    (3)对ββ求导,我们获得:Lβ=(12βTβwT(diag(Y)X)β)∂L∂β=(12βTβ−wT(diag(Y)X)β)′,因此,β=wT(diag(Y)X)β=wT(diag(Y)X)。因为,拉格朗日函数LL是关于ββ的二次函数,所以存在最小值12wT(diag(y)X)(diag(Y)X)Tw+ITw−12wT(diag(y)X)(diag(Y)X)Tw+ITw

    综上所述,通过最小化β,β0,ξβ,β0,ξ,我们获得拉格朗日函数L(β,β0,ξ,v,w)L(β,β0,ξ,v,w)的拉格朗日对偶函数g(v,w)g(v,w)

    g(v,w)={12wT(diag(Y)X)(diag(Y)X)Tw+ITwifwTy=0,w=CIvotherwiseg(v,w)={−12wT(diag(Y)X)(diag(Y)X)Tw+ITwifwTy=0,w=CI−v−∞otherwise

    又因为ξξ为原问题的松弛因子,且v0v≥0,因此我们可以消除对偶问题中的松弛因子vv(slack variable),SVM对偶优化问题就变为:

    maxwsubjectto12wT(diag(y)X)(diag(Y)X)Tw+ITw0wCI,wTy=0maxw−12wT(diag(y)X)(diag(Y)X)Tw+ITwsubjectto0≤w≤CI,wTy=0

    如果SVM原问题满足Slater’s Condition,那么SVM具有强对偶性(事实上SVM具有强对偶性),我们可以通过求解对偶问题的最优解,进而获得原问题最优解β=(diag(Y)X)Twβ=(diag(Y)X)Tw

    更多相关内容
  • 这就是Lagrange multiplier. 而很多地方都会直接跳到下面的方程,我看了蛮久才理解: 其实就是分别对x, y,λ求偏导,能够得到上面的方程组(仔细比较),算是反向构思?注意λ和上面是反过来的 多个约束...

    关于支持向量机里的拉格朗日乘子法有很多文章,作为学习笔记这里就不详细描述了,只记录一些一般文章里跳过的难以理解部分
    Support Vector Machine wiki : https://en.wikipedia.org/wiki/Support_vector_machine

    1. 拉格朗日乘子法和KKT条件

    1.1 对于无约束优化问题中,如果一个函数f是凸函数,那么可以直接通过f(x)的梯度等于0来求得全局极小值点。
    1.2 对于等式约束,以下例子来说明:
    f(x,y) = x
    在这里插入图片描述
    令g(x, y) 为约束条件,我们需要求f(x, y)的min/max value. 用下面的图来直观理解:
    在这里插入图片描述
    f(x, y)是中间的圆,随着x和y变大会不断外扩,两条蓝线就是g(x, y) = 0的曲线
    他们相切的时候就是min/max value(不详细解释,很多文章可以看)
    相切意味着梯度方向相同,这里经常会跳过一段,梯度向量的表达方式:
    在这里插入图片描述
    在这里插入图片描述
    就是矩阵形式求偏导,既然他们方向一致,那么我们就有:
    在这里插入图片描述
    把方程都联立起来,我们就有:
    在这里插入图片描述

    在这里插入图片描述
    这就是Lagrange multiplier. 而很多地方都会直接跳到下面的方程,我看了蛮久才理解:
    在这里插入图片描述
    在这里插入图片描述
    其实就是分别对x, y,λ求偏导,能够得到上面的方程组(仔细比较),算是反向构思?注意λ和上面是反过来的
    在这里插入图片描述

    多个约束条件:
    在这里插入图片描述

    1.3 不等式约束和KTT条件
    极值在约束域内,显然我们直接求导就能找到极值,跟约束域无关。
    接着讨论极小值点落在可行域内(不包含边界)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在那个极值点上两个图像的梯度应该是相反的,于是我们能得到:
    走到极小值点的时候,g(x)的梯度和f(x)的负梯度同向。因为极小值点在边界上,这个时候g(x)等于0,直接贴结论了,很多文章描述这块

    KKT条件的全称是Karush-Kuhn-Tucker条件,KKT条件是说最优值条件必须满足以下条件:

    条件一:经过拉格朗日函数处理之后的新目标函数L(w,b,α)对x求导为零:
    条件二:h(x) = 0;
    条件三:α*g(x) = 0;
    在这里插入图片描述

    1. SVM 支持向量机

    上面花了很多篇幅介绍拉格朗日乘子法,下面在简单做个关于SVM的学习笔记,作为以后回顾的依据
    2.1 什么是支持向量机:
    In machine learning, support vector machines (SVMs, also support vector networks[1]) are supervised learning models with associated learning algorithms that analyze data used for classification and regression analysis. Given a set of training examples, each marked as belonging to one or the other of two categories, an SVM training algorithm builds a model that assigns new examples to one category or the other, making it a non-probabilistic binary linear classifier
    例如下图:
    在这里插入图片描述
    先从二维平面来理解这个问题,我们要区分一系列的点,分别是蓝色和绿色的点,我们要找到一条线把他们分开
    这条线需要满足两个条件,严格区分两边的点,并且和两边的点保持最大距离
    当然,这只是二维的线性可分情况,我们想象一下,可能这些点并不能被直线分开,还有可能是三维图像,那么需要超平面去划分。
    这里我先记录线性可分平面的情况

    2.2 SVM 算法
    我们的训练数据:
    就是这些点,{(x1, y1),(x2, y2), …, (xN, yN)}, 其中x1 = [a,b], a和b 是x1和x2的值,表示一个点,y代表分类,这里我们用1 和 -1
    我们要找到中间那条线,f = wx + b, f 大于0时, 输出1, f小于0时,输出-1
    而f = wx - b = 0就是这条线,而且这条线要满足两个条件:
    (1)没有任何样本在这两个平面之间;
    (2)这两个平面的距离需要最大。
    先看第二个条件,我们可以看到一些样本存在于wx - b = 1 和 wx - b = -1两条线上,他们叫支持向量,我们需要最大化这个距离
    根据高中数学,ax+by=c1和ax+by=c2两条直线之间的距离是:
    在这里插入图片描述
    那么我们图里的直线方程是:
    w = [w1, w2], x = [a1, a2], w1a1 + w2a2 = b+1 和 w1a1 + w2a2 = b-1
    带入高中方程,
    在这里插入图片描述
    distance= 2/||w||
    同时我们还需要满足条件(1),也就是同时要满足没有数据点分布在两条虚线之间
    也就是,对于任何一个正样本yi=+1,它都要处于右边,也就是要保证:y= wx + b>=+1。对于任何一个负样本yi=-1,它都要处于左边,也就是要保证:y = wx + b<=-1。这两个约束,其实可以合并成同一个式子:yi (wxi + b)>=1。
    于是我们的问题就变成数学问题:
    在这里插入图片描述

    在约束条件下求极值,跟第一章对应起来了。

    2.3 求解最小值
    a. 将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数, 其中αi是拉格朗日乘子,αi大于等于0,是我们构造新目标函数时引入的系数变量(我们自己设置)。
    在这里插入图片描述
    b. 划分可行性区域
    在这里插入图片描述
    在这里插入图片描述
    现在我们做到了建立一个在可行解区域内与原目标函数相同,在可行解区域外函数值趋近于无穷大的新函数。于是我们的问题就变成了求下面的最小值
    在这里插入图片描述
    c. 函数转化:
    将不易求解的优化问题转化为易求解的优化,新目标函数,先求最大值,再求最小值。这样的话,我们首先就要面对带有需要求解的参数w和b的方程,而αi又是不等式约束,这个求解过程不好做。所以,我们需要使用拉格朗日函数对偶性,将最小和最大的位置交换一下,这样就变成了
    在这里插入图片描述
    交换以后的新问题是原始问题的对偶问题,这个新问题的最优值用d来表示。而且d<=p*。我们关心的是d=p的时候,这才是我们要的解。需要什么条件才能让d=p呢?

    首先必须满足这个优化问题是凸优化问题。
    其次,需要满足KKT条件。
    凸优化问题的定义是:求取最小值的目标函数为凸函数的一类优化问题。目标函数是凸函数我们已经知道,这个优化问题又是求最小值。所以我们的最优化问题就是凸优化问题。

    d. 对偶问题求解
    固定α,要让L(w,b,α)关于w和b最小化,我们分别对w和b偏导数,令其等于0,即:
    在这里插入图片描述
    将上述结果带回L(w,b,α)得到此时的L(w,b,α)函数在这里插入图片描述
    从上面的最后一个式子,我们可以看出,此时的L(w,b,α)函数只含有一个变量,即αi。
    再求外面的最大值:
    在这里插入图片描述

    这个就是dual problem(如果我们知道α,我们就知道了w。反过来,如果我们知道w,也可以知道α)。这时候我们就变成了求对α的极大,即是关于对偶变量α的优化问题(没有了变量w,b,只有α)。当求解得到最优的α后,就可以同样代入到上面的公式,导出w和b*了,最终得出分离超平面和分类决策函数。也就是训练好了SVM。那来一个新的样本x后,就可以这样分类了:
    在这里插入图片描述

    展开全文
  • Lagrange函数,对偶问题,KKT条件

    千次阅读 2018-10-31 10:24:47
    广义拉格朗日函数(generalized Lagrange function): 是是拉格朗日乘子 特别要求: 原始问题的描述等价为: 这个地方如下理解: 原始问题最优化: 最优值: 对偶问题 对偶问题: 对偶问题一定...

    1. 原始问题

    约束最优化问题的原始问题:

    在这里插入图片描述
    在这里插入图片描述

    约束最优化问题转化为无约束最优化问题:

    广义拉格朗日函数(generalized Lagrange function):

    在这里插入图片描述
    在这里插入图片描述是是拉格朗日乘子
    特别要求:在这里插入图片描述

    原始问题的描述等价为:

    在这里插入图片描述
    这个地方如下理解:
    在这里插入图片描述

    原始问题最优化:

    在这里插入图片描述
    最优值:
    在这里插入图片描述

    2. 对偶问题

    对偶问题:

    在这里插入图片描述
    对偶问题一定是凹的。

    对偶问题最优化(极大值):

    在这里插入图片描述

    原始问题最优化(极小值):

    在这里插入图片描述

    对偶问题的最优值:

    在这里插入图片描述

    原始问题最优值:

    在这里插入图片描述

    3. 原始问题与对偶问题的关系

    定理:若原始问题与对偶问题都有最优值,则

    在这里插入图片描述

    在这里插入图片描述
    分别是原始问题和对偶问题的最优解的充分必要条件是:

    在这里插入图片描述
    满足KKT条件:
    在这里插入图片描述
    关于KKT 条件的理解:前面三个条件是由解析函数的知识,对于各个变量的偏导数为0(这就解释了一开始为什么假设三个函数连续可微,如果不连续可微的话,这里的偏导数存不存在就不能保证),后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。

    由KKT对偶互补条件可知:a>0时,c =0`, SVM会用到.
    
    展开全文
  • SVM支持向量机二(Lagrange Duality)

    千次阅读 2013-12-02 11:13:04
    SVM支持向量机二(Lagrange Duality) 各科

    SVM支持向量机二(Lagrange Duality)



    上一节我们得到了结论就是 Maximum margin 的化简结论:
    然而我们应该怎么解决他呢,我们可以把s.t.的约束表示为gi(w)<=0,可以的把,自己看看就会了?这里就要用到 Lagrange Duality 数学知识了,不急我们下面先抛开上面的结论,至讲解一些数学知识:

    1.Lagrange数学方法
    2.Duality(对偶性问题)转换过程(必须满足KKT条件)
    3.满足KKT条件转化 min max L()到 max min L()
    4.为什么叫做支持向量机(Support Vector Machine)
    --------------------------------------------------------------------------------------------------------------
    1.Lagrange数学方法

    (1)Lagrange去掉等式约束 的情况:
    最大化问题带等式约束 g(X)==0 的情况:处理方法就是给约束乘以一个系数加到原命题上,然后求导得出结果:下面回顾一下本科阶段做的简单例题加深印象吧!

    (2)Lagrange去掉不等式约束 的情况:

    这里是不等式约束的情况,大家千万注意我画的两个红圆圈,这个对以后判断 支持向量 的点很重要,那是你就明白为什么叫支持向量机(Support Vector Machine)了

    (3)Lagrange同时去掉等式约束和不等式约束 的情况:

    至此Lagrange数学知识介绍完毕了!下面再进一步看看,就可以解决我们开头提出的问题了
    ---------------------------------------------------------------------------------------------------------------------------------------------

    2.Duality(对偶性问题)转换过程(必须满足KKT条件)



    我们可以看到,在满足约束条件的情况下 max L()== f(w),而我们的原问题是 min f(w),所以问题变成了:
    minw max(w,a,b)L(w,a,b),问题又来了,如果我们按照 先求 max L时问题又还原了,所以我们要想办法,更改
    min max L的求值顺序,这就要转化为: Duality(对偶性问题):


    相信上面的不等式很容易理解,例如班级当中 个头最矮的一批中个头最高的 肯定小于等于 班级中个头最高的一批中个头最矮的,是不是?在此我查阅了资料如下:

    极小极大值(min max)思想是指

         在某一博弈中如果一个局中人根据极小极大值理论的标准来选择他可以采取的战略,那么就是说对他的每一种策略,他首先考虑他采取该策略后能收到的最低支付,然后他在所有最低支付中选择能得到最大支付值的那个战略。极小极大值理论表明二人零和有限纯战略(或连续纯战略和连续纯凸支付函数)的博弈是确定的(即有解)。

    证明:
       
         第一个有限纯战略的二人机会与技巧博弈的极小极大值定理是由冯.诺依曼于1928年发表的论文“关于伙伴游戏理论”(Zur Theorie der Gesellschaftsspiele)中给出的[7],结果表明所有的双人零和博弈都是有一个极小极大值解,而这个证明已经出现在他于1926年12月7日提交给了哥廷根数学会的一篇论文中了。冯.诺依曼1928年的这个证明是复杂的,其中既有初等的概率,也有拓扑学的概念,而且不易为读者所读懂。但这个证明是有效的。在一个角注中,冯.诺依曼注明:“当这篇文章快最后完成时,我得知了E波莱尔的工作,波莱尔明确用公式表示了一个对称的二人博弈的双线性形式问题,并且说找不到MaxMin<MinMax的例子。我们以上的结果则回答了他的疑问”。而且冯.诺依曼把他的结果寄给了波莱尔,波莱尔又于1928年6月把它交给了法国科学院。

    第一个初等的(非拓朴)的极小极大值原理的证明是波莱尔的学生威莱(Jean Ville)于1938年给出的,收录在波莱尔丛书中[8],这个证明用到了凸性的论证和支撑超平面的概念。同年威莱对连续纯战略的情况作出了第一个极小极大值原理的证明。而冯`诺依曼和摩根斯坦1944年出版的书中对极小极大值的证明正是以Ville1938年的证明为基础的,而不是以冯.诺伊曼1928年的证明为基穿

    1944年冯.诺依曼和奥地利经济学家奥.摩根斯坦合作《博弈论与经济行为》(Theory of games and economic behavior)一书的出版,标志着博弈论的创立。此后以卢密斯(Loomis,美国数学家)的完全代数方法的极小极大值定理的证明为开端,在数学界发起了一场进一步证明极小极大值定理的运动,其中,以赫尔曼.外尔(Hermann Weyl,美国数学家)1950年给出的一个更简明的极小极大值定理的初等证明为高潮,这个证明依据了他早期关于凸多面体的工作。所有的这些证明大致可以分为两个类别:一个类别是以不动点理论或迭代程序为基础,另一类别是以凸集理论为基穿

    综上所述,尽管瓦德哥锐的贡献是孤立的,被人们忽视了,但最先发现极小极大值混合策略解的荣誉应归功于他。而属于波莱尔的荣誉应有:第一个用现代公式表示混合策略,首次给出了找到具有3个或5个纯策略的博弈的极小极大值解的一般方法。冯.诺依曼则应得到第一个证明极小极大值定理的荣誉。而第一个用初等方法证明极小极大值定理的荣誉应属于威莱,而且他还把这一原理推广到了具有无限多的连续策略的博弈例子中。

    那么 min max 和 max min 何时相等呢?请看下面KKT条件!!!

    3.满足KKT条件转化 min max L()到 max min L()


    解释:

    convex的定义:凸形曲线-----即g(w)是直线(凸曲线特例,还是凸曲线),高维就是凸曲线了,
    affine(仿射变换)的定义: 若变换S∶Rn→Rn,S(x)=T(x)+a,T是非奇异线性变换,a∈Rn,则变换S称为仿射变换
    也就是非奇异线性变换加一个平移,h(w)是满足的

    其实就是满足KKT条件,下面我们来看一下KKT条件什么样子就行了:

    下面加深理解哈!
    我们开头的

    其中约束条件s.t.可以表示成: gi(w)= 1 -  yi*(wT*xi+ b)<= 0 对吧!等于0的情况正好落在 那两条虚线上,就是支持向量的点,这时候 对应的 ai != 0 .

    这个时候我们的问题就转化成了 

    到此为止,我们的原问题转化为了 带红色边框的 max min L问题了,下面我们就要分步去求解 :
    第一步:求 minw L(w,a,b)
    第二步:求 maxL(w,a,b)

    第一步:求 minw L(w,a,b)

    我们可以看出 L(w,b,a)是一个关于w的二次凸函数,所以有最小值,求导即可


    经过对 w 和 b 求偏导之后就得到上图的’‘ *号等式 ‘’回代到 L(w,a,b)得到:
    这个时候第一步就解决了,最小值问题就解决了。
    具体推导公式为:



    得到:



    4.为什么叫做支持向量机(Support Vector Machine)









    第二步:求 maxL(w,a,b)
    至此我们很有技巧的地方就是,w,b 被化解完了,只剩下 ai 等参数了,而 w可以用 ai 表示出来:

    现在问题就是我们该如何求解 alpha 呢? alpha如何更新呢? w更新可以有alpha表示更新,还有就是为什么这样更新可以是 W(alphas)值逐渐增大呢??

    在这个问题之前我们要先进行软间隔处理哈:


    关于这个问题,我们可以有两种方法求解

    可以参考我另一篇文章: SVM求解之坐标上升算法(Coordinate Ascent)

    2. SVM之SMO算法
    可以参考我另一篇文章SVM支持向量机四(SMO算法)
    展开全文
  • Lagrange

    千次阅读 2018-06-08 17:23:40
    转自:https://dubur.github.io/2015/11/24/Lagrange-Dual-Problem/Lagrange对偶函数首先我们定义优化问题:我们称这个问题为原始问题(primal problem),对于这样的优化问题,相信之前学习过Lagrange乘数法的话会...
  • Lagrange multipliers - 拉格朗日乘子法

    千次阅读 2017-08-27 23:14:43
    Lagrange multipliers - 拉格朗日乘子法拉格朗日乘子法是一种寻找多元函数在一组约束下的极值方法。通过引入拉格朗日乘子,可将多约束的最优化问题转化为多变量的无约束优化问题求解。本文主要讲解其中的数学原理,...
  • 最优间隔分类器(optimal margin classifier) 重新回到SVM的优化问题: 我们将约束条件改写为: 从KKT条件得知只有函数间隔是1(离超平面最近的点)的线性约束式前面的系数,也就是说这些约束式,对于其他的不在线...
  • Lagrange duality 对偶问题是利用拉格朗日对偶性将原始问题转换为对偶问题, 通过解对偶问题得到原始问题的解。 学习拉格朗日对偶性原理重要的是理解构造所得的原始问题和原函数的等价性,以及原始问题和对偶问题解...
  • 最近打算把svm过一遍,结果发现已经把拉格朗日对偶性忘个差不多了(也许当时也没学会),试着总结一下。 主要参考书目《统计学习方法》 参考了的文章 浅谈最优化问题的KKT条件 拉格朗日乘子法证明 不太会latex排版 式...
  • 拉格朗日乘子法(Lagrange multiplier)

    千次阅读 2018-01-03 14:51:34
    经过我们优化(不要管什么方法),就是求α,β的值使得 L ( x , α , β ) L(x,α,β) 取得最大值(此过程中把x看做常量),一旦求出, m a x L ( x , α , β ) max L(x,α,β) 就是只和x有关的函数,定义这个函数...
  • 在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去...
  • 之前说到过拉格朗日乘数法以及推导过程,那么今天要说的就是拉格朗日对偶性以及KKT条件本文主要分为以下几个部分:1.Lagrange multipliers 2.Generalized Lagrangian 3.Primal and dual optimization problem 4....
  • Ensembling, Lagrange

    2018-01-09 19:00:10
    Ensembling, Lagrange  据我观察,名字带“拉”的人一般都很厉害,比如马拉多纳、希拉里、狄波拉、张娜拉、杜拉拉、陈法拉、尼古拉斯·赵四、地铁站的罗拉……  但跟我们今天的大神拉格朗日(Lagrange)一比...
  •   在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT...
  • 引进广义拉格朗日函数(generalized Lagrange function): 不要怕这个式子,也不要被拉格朗日这个高大上的名字给唬住了,让我们慢慢剖析!这里 , 是拉格朗日乘子(名字高大上,其实就是上面函数中的参数而已...
  • 方法简化了在线学习过程中Lagrange乘子的求解过程,利用训练数据集滑动时间窗口的移动来控制新样本的加入和旧样本的移除,通过线性运算完成Lagrange乘子的更新,进而完成预测模型的在线更新。测试结果表明,相对已...
  • 本文目录SVM介绍SVM算法理论知识函数...非线性可分:采用核函数核技巧的方法训练出非线性支持SVM。当然我们知道针对非线性可分数据还存在用感知机方法以及多层感知机(神经网络)方法来训练,但本文仅介绍基于核技巧
  • SVM支持向量机---(Lagrange Duality)

    千次阅读 2014-06-06 10:32:45
    SVM支持向量机二(Lagrange Duality) 上一节我们得到了结论就是 Maximum margin 的化简结论: 然而我们应该怎么解决他呢,我们可以把s.t.的约束表示为g i (w),可以的把,自己看看就会了?...
  • 文章目录拉格朗日对偶性(Lagrange duality)1. 从原始问题到对偶问题2. 弱对偶与强对偶3. KKT条件Reference: 拉格朗日对偶性(Lagrange duality) 1. 从原始问题到对偶问题  对偶性是优化理论中一个重要的部分,带...
  • 在上篇文章《Support Vector Machine(1):线性可分集的决策边界》中,我们最后得到,求SVM最佳Margin的问题,转化为了如下形式: 到这一步后,我个人又花了很长的时间去查阅资料,因为数学较差的原因,理解起来...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,138
精华内容 855
关键字:

lagrange方法 svm