精华内容
下载资源
问答
  • 1)几个重要名词(间隔、支持向量) 2)一些定义(训练数据、标签、超平面等) 3)机器学习任务与步骤 三、支持向量优化问题 1、优化问题(怎么将问题转化为最优化问题?) 2、转化为最优化问题过程...

    目录

    一、没有免费的午餐定理

    二、支持向量机SVM(support vector machine)

    1、线性模型和非线性模型

    2、如何在线性模型中画出一条直线(优化过程——vplink)

    1)多少条?

    2)如何画出最好的直线?

    3、如何去描述这个优化的过程(数学描述)

    1)几个重要的名词(间隔、支持向量)

    2)一些定义(训练数据、标签、超平面等)

    >>>问题1:怎么求解w,b?

    3)机器学习的任务与步骤(求解w,b)

    三、支持向量机的优化问题(求最优划分直线,性能指标为d)

    1、优化问题(怎么将问题转化为最优化问题?)

    2、转化为最优化问题的过程?

    1)由支持向量X0和模型得到距离d的公式

     2)如何取得d最大?——(转化问题的最优化量的思想)

    >>>问题2:需不需要计算a?

    >>>问题3:支持向量是怎么得到的?如何保证它满足下面的式子?

    3)转化后的最优化问题数学描述(dmax——||w||min)

    >>>问题4:以上的限制条件中哪些是已知哪些是未知?

    >>>问题5:缩放后的w,b怎么求解?

    >>>问题6:限制条件为什么大于等于1?

    四、总结

    1、机器学习与最优化联系与区别

    1)区别

    2)联系


     


     


     


    课程链接:《浙江大学-研究生机器学习课程》

    一、没有免费的午餐定理

    没有免费的午餐定理:如果我们不对特征空间有先验假设,则所有算法的平均表现是一样的。

    特征差距小的样本更有可能是一类

    二、支持向量机SVM(support vector machine)

    vplink发明的支持向量机

    SVM是最大化间隔的分类算法,是一种进行二元分类的广义线性分类器;SVM也可以通过核方法来对非线性模型进行分类。

    1、线性模型和非线性模型

    通过一条直线可以将样本分开为两个特征的部分叫线性模型,反之叫非线性模型

    2、如何在线性模型中画出一条直线(优化过程——vplink)

    1)多少条?

    该直线将圆圈和叉区分开,按道理来说有无数条,所以需要找出一条最好的直线

    2)如何画出最好的直线?

    先定义一个性能指标,比较每一条直线的性能指标,取性能指标最好的那条线作为最好的直线

    这里是以d:间隔(margin)作为性能指标进行分析

    ①最优的情形

    这里的性能指标是距离——将待定的直线向左和向右移动,直到该直线分别与各特征区域的一个或者多个特征值相交时停止移动,测量这时候两条直线的距离,取该距离最大的直线为最优直线备选。

    但是最优的直线也有无数条,因为与其平行的直线有无数条,该怎么取舍呢?

    这时候将直线在d/2处的直线作为最终的直线,作为最优直线

    ②不是最优的情形

    标题

    3、如何去描述这个优化的过程(数学描述)

    如何去描述这个优化的过程(数学描述)?

    1)几个重要的名词(间隔、支持向量)

    间隔d:margin——最优直线与两边最近特征值的距离和叫做间隔

    支持向量X0:support vector——被平行线插到的向量叫做支持向量

    2)一些定义(训练数据、标签、超平面等)

     

    训练数据(XN=【XN1,XN2,XN3,,,XNN】T是一个向量)及标签(yi是1或-1):

     

    线性模型:(W,b)——待定参数

    W的转置.dot(xi) + b = 0——超平面(Hyperplane)的方程,关于xi的一次线性方程

     

    >>>问题1:怎么求解w,b?

    答:超平面方程中X=xi,其中i = 1~N,而xi = (xi1,xi2,...,xin)T,因此根据方程可以得到N个方程,N取决于训练的样本数,n取决于样本数的维数,通过求解N个关于w的一次方程组,即可以求解得到w,b,求解方程组的方法有高斯法等,具体可参考《数值分析》

    线性模型最优化的任务——在二维的的时候找直线,在三维的时候找平面,在多维的时候找超平面,这里以二维为例

     

     

    线性可分:

    即:

     

    3)机器学习的任务与步骤(求解w,b)

    任务(已知(xN,yN),未知(W,b)):

    通过这些训练数据和标签((xN,yN)),其中XN = (XN1,XN2,...,XNn)是一个向量,N表示训练的样本个数,n表示每一个样本数的维度;在限定的模型(超平面方程)下,求解出待定系数(W,b),最后确定模型,机器学习的过程也就结束了

     

    步骤:

    a,通过一个方程来限定模型,如用一个超平面来限定多维模型;

    b.在限定的模型中确定待定系数

    c.通过训练数据和限定的模型(方程)求解出待定系数,最后确定模型

    三、支持向量机的优化问题(求最优划分直线,性能指标为d)

    1、优化问题(怎么将问题转化为最优化问题?)

    2、转化为最优化问题的过程?

    公式1:

    1)由支持向量X0和模型得到距离d的公式

     2)如何取得d最大?——(转化问题的最优化量的思想)

    通过缩放求得d的公式(已知w,b,未知a,也就是后来的aw,ab,支持向量X0未知)

    使得d最大的问题转化为求||w||的最小值问题

     

    >>>问题2:需不需要计算a?

    答:不需要!因为这里主要是引入a来讲解一下缩放的思想,即告诉我们通过a的缩放能够将求解d最大值问题转化为||w||最小值的问题,至于a缩放多少,因为不管a缩放多少,都要假设满足以下式子(至于为什么这么假设,我也不知道,反正肯定是为了方便计算):

    最后d的公式为:

    d的公式分子为常数,因此问题dmax依据转化为求||w||min

     

    >>>问题3:支持向量是怎么得到的?如何保证它满足下面的式子?

    答:这里只是一个假设,实际上支持向量还未知,为我们最优化时的工作,这里只是相当于下了一个定义,限定了a的值来满足这个假设,最优化的问题就是对缩放后的w进行求解,所以a没必要进行求解,这里也求不出来

     

    3)转化后的最优化问题数学描述(dmax——||w||min)

    凸函数的定义:《最优化课堂笔记04:非线性规划——凸规划》

    凸函数及二次规划问题的求解方法:《最优化课程笔记07——约束问题的非线性规划方法(拉格朗日乘子法和惩罚函数法)》

    >>>问题4:以上的限制条件中哪些是已知哪些是未知?

    答:已知:xi,yi——即样本数据,未知——w,b

    注意这里要区分开前面通过训练数据求得的w,b,前面的w,b是一个超平面方程,对所有的训练数据都满足,而这里的w,b是在超平面的基础上进行缩放得到的,虽然平面是一样的(由事实1得到):

    但是w,b值已经发生了改变,并且这里要求解的w,b是在限制条件下进行求解的,虽然目标函数中看起来只有w,没有b,但b在限制条件中,如果b的取值不能破坏了约束条件,也是不可以的。

     

    >>>问题5:缩放后的w,b怎么求解?

    答:先转化为对偶问题,再使用拉格朗日函数进行求解

     

     

    >>>问题6:限制条件为什么大于等于1?

    答:首先根据线性可分性得到限制条件必然大于等于0,又因为问题dmax转化为||w||min的问题时在支持向量上满足,

    所以在非支持向量上有:yi=1时,平面方程的模会大于1;即:

    yi=-1时,平面方程的模会小于-1,即:

    所以二者相乘就会大于等于1,当然也可以大于等于任何的正整数N,此时a的缩放就应该满足:

    结果一致,一般是大于等于1

    四、总结

    1、机器学习与最优化联系与区别

    1)区别

    机器学习:通过已知的训练数据在限定的模型下求解出模型的待定系数,得到这个问题的一个确切具体的模型,重点在于求解模型的待定系数w,b,求得的w,b只是满足了将二元分类了,但不一定是最优的分类平面

    最优化:求解出问题的最优解,即找到最优的分类平面

    2)联系

    机器学习包含了最优化,其实机器学习就是在不断地对数据进行优化,得到最优解。起初机器学习是通过现有的训练数据得到一个模型,后面再通过学习(优化)求得最优解。

     

     

    非线性模型的最优化问题该怎么求解呢?请看:《机器学习理论——支持向量机SVM之非线性模型

     

    还可以参考:《[机器学习笔记] 支持向量机SVM如何求解最佳模型?》

    展开全文
  • 该方法主要有两个特点:一是将摄像机安装在机器人上,使光轴垂直工作平面,通过比较面积大小来获得深度信息,从而将三维信息获取问题转化为二维信息提取,并利用仿射变换获得空间信息;二是利用激光器与摄像机相...
  • SVM支持向量机一、简介支持向量机(support vector machines)是一种二分类模型,它目的是寻找一个超平面来对样本进行分割,分割原则是间隔最大化,最终转化为一个凸二次规划问题来求解。由简至繁模型包括:当...

    SVM支持向量机

    一、简介

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

    当训练样本线性可分时,通过硬间隔最大化,学习一个线性可分支持向量机;

    当训练样本近似线性可分时,通过软间隔最大化,学习一个线性支持向量机;

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

    二、线性可分支持向量机

    给定训练样本集D=(x1,y1),(x2,y2),⋯,(xm,ym)D=(x1,y1),(x2,y2),⋯,(xm,ym),其中yi∈{−1,+1}yi∈{−1,+1},分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面,将不同类别的样本分开。

    2ad9a072684e5ba93f303e0ab7173a85.png

    直观看上去,能将训练样本分开的划分超平面有很多,但应该去找位于两类训练样本“正中间”的划分超平面,即图6.1中红色的那条,因为该划分超平面对训练样本局部扰动的“容忍”性最好,例如,由于训练集的局限性或者噪声的因素,训练集外的样本可能比图6.1中的训练样本更接近两个类的分隔界,这将使许多划分超平面出现错误。而红色超平面的影响最小,简言之,这个划分超平面所产生的结果是鲁棒性的。

    ​ 那什么是线性可分呢?

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

    9fc23a3abfb186e2b472e20ad88d52e7.png

    那么我们考虑第一个问题,为什么要间隔最大呢?一般来说,一个点距离分离超平面的远近可以表示分类预测的确信度,如图中的A B两个样本点,B点被预测为正类的确信度要大于A点,所以SVM的目标是寻找一个超平面,使得离超平面较近的异类点之间能有更大的间隔,即不必考虑所有样本点,只需让求得的超平面使得离它近的点间隔最大。

    接下来考虑第二个问题,怎么计算间隔?只有计算出了间隔,才能使得间隔最大化。在样本空间中,划分超平面可通过如下线性方程来描述:

    WTx+b=0

    WTx+b=0

    其中w为法向量,决定了超平面的方向,b为位移量,决定了超平面与原点的距离。假设超平面能将训练样本正确地分类,即对于训练样本(xi,yi)(xi,yi),满足以下公式:

    {WTxi+b≥+1WTxi+b≤−1yi=+1yi=−1

    {WTxi+b≥+1yi=+1WTxi+b≤−1yi=−1

    该公式被称为最大间隔假设,yi=+1 表示样本为正样本,yi=−1 表示样本为负样本,式子前面选择大于等于+1,小于等于-1只是为了计算方便,原则上可以是任意常数,但无论是多少,都可以通过对 w 的变换使其为 +1 和 -1 。实际上该公式等价于;yi(WTxi+b)≥+1yi(WTxi+b)≥+1

    如图6.2所示,距离超平面最近的这几个样本点满足yi(WTxi+b)=1yi(WTxi+b)=1,它们被称为“支持向量”。虚线称为边界,两条虚线间的距离称为间隔(margin)。

    4a3a440863fb254a3e0a0ff79440cb40.png

    关于间隔的计算:它就等于两个异类支持向量的差在 W方向上的投影 ,W方向是指图6.2所示实线的法线方向。

    即:

    进而可以推出:

    故有:γ=(x→+−x→−)W−→T||W||=1−b+1+b||W||=2||W||γ=(x→+−x→−)W→T||W||=1−b+1+b||W||=2||W||

    至此,我们求得了间隔,SVM的思想是使得间隔最大化,也就是:

    ​ max2||W||max2||W||

    ​ s.t.yi(WTxi+b)≥+1s.t.yi(WTxi+b)≥+1

    显然,最大化 2/||w|| 相当于最小化 ||w||,为了计算方便,将公式转化成如下公式,它即为支持向量机的基本型:

    ​ min12||W||2min12||W||2

    ​ s.t.yi(WTxi+b)≥+1s.t.yi(WTxi+b)≥+1

    该基本型是一个凸二次规划问题,可以采用拉格朗日乘子法对其对偶问题求解求解,拉格朗日函数:

    对W,b求导可得;

    令其分别为0,可得:

    将其带入拉格朗日函数(8)中,可得:

    原问题就转换为如下关于aa的问题:

    解出 α 之后,根据公式(9)可以求得 w , 进而求得 b,可以得到模型:

    该过程的KTT条件为;

    我们分析一下,对于任意的训练样本 (xi,yi),

    αi=0αi=0,则其不会在公式(13)中的求和项中出现,也就是说,它不影响模型的训练;

    若 αi>0αi>0,则yif(xi)−1=0yif(xi)−1=0,也就是 yif(xi)=1yif(xi)=1,即该样本一定在边界上,是一个支持向量。

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

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

    对于非线性问题,线性可分支持向量机并不能有效解决,要使用非线性模型才能很好地分类。先看一个例子,如下图,很显然使用直线并不能将两类样本分开,但是可以使用一条椭圆曲线(非线性模型)将它们分开。非线性问题往往不好求解,所以希望能用解线性分类问题的方法求解,因此可以采用非线性变换,将非线性问题变换成线性问题。

    ![这里写图片描述](D:markdown Document20180329114634529.png)

    对于这样的问题,可以将训练样本从原始空间映射到一个更高维的空间,使得样本在这个空间中线性可分,如果原始空间维数是有限的,即属性是有限的,那么一定存在一个高维特征空间使样本可分。令ϕ(x)表示将 x 映射后的特征向量,于是在特征空间中,划分超平面所对应的的模型可表示为:

    f(x)=wTϕ(x)+b (14)

    于是有最小化函数:

    其对偶问题为:

    若要对公式(16)求解,会涉及到计算ϕ(xi)Tϕ(xj)ϕ(xi)Tϕ(xj),这是样本 xi 和 xj映射到特征空间之后的内积,由于特征空间的维数可能很高,甚至是无穷维,因此直接计算ϕ(xi)Tϕ(xj)ϕ(xi)Tϕ(xj)通常是困难的,于是想到这样一个函数:

    即 xi和 xj在特征空间中的内积等于他们在原始样本空间中通过函数 κ(xi,xj)计算的函数值,于是公式(16)写成如下:

    求解后得到:

    这里的函数 κ(xi,xj) 就是核函数,在实际应用中,通常人们会从一些常用的核函数里选择(根据样本数据的不同,选择不同的参数,实际上就得到了不同的核函数)

    5b1b731b62862913d22c000ff7bbdc60.png

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

    1、线性支持向量机

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

    线性不可分意味着某些样本点 (xi,yi) 不能满足间隔大于等于1的条件,样本点落在超平面与边界之间。为解决这一问题,可以对每个样本点引入一个松弛变量 ξi≥0,使得间隔加上松弛变量大于等于1,这样约束条件变为:

    五、拉格朗日乘子法:

    在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求取。当然,这两个方法求得的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候,只知道直接应用两个方法,但是却不知道为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够起作用,为什么要这样去求取最优值呢?

    首先把什么是拉格朗日乘子法(Lagrange Multiplier) 和KKT条件叙述一下;然后开始分别谈谈为什么要这样求最优值。

    展开全文
  • 支持向量

    千次阅读 多人点赞 2016-07-18 23:04:15
    向量的模 向量的内积 点到平面的距离 最优间隔分类器与支持向量 函数间隔几何间隔 如何确定这个超平面 最大间隔划分超平面 对偶问题 对偶问题转化 对偶问题求解 拉格朗日乘子法KKT条件 拉格朗日乘子法等式约束...

    支持向量机

    点到平面的距离

    平面的一般式方程

    w1x1+w2x2+w3x3+b=wTx+b=0

    其中w=(w1,w2,w3) 是平面的法向量,b 是将平面平移到坐标原点所需距离(所以 b=0 时,平面过原点)

    向量的模

    给定一个向量 w=(w1,w2,w3), 则 |w|=sqrt(w21+w22+w23)

    向量的内积

    给定两个向量 w=(w1,w2,w3)x=(x1,x2,x3) 则他们的内积是

    wx=w1x1+w2x2+w3x3

    点到平面的距离

    !Alt text

    最优间隔分类器与支持向量

    函数间隔和几何间隔

    令划分超平面的线性方程为

    wTx+b=0

    假设超平面能正确分类,当 wTx+b>0 的点对应 y=1 的数据点, wTx+b<0 的点对应 y=1 的点。
    给定一个训练样本 (x(i),y(i))。我们定义函数间隔如下:
    γ(i)=y(i)(wTx(i)+b)

    实际上
    γ(i)=wTx(i)+b

    为了使函数间隔最大(更大的信心确定该例是正例还是反例),当y(i)=1 时,wTx(i)+b 应该是个大正数,反之是个大负数。因此函数间隔代表了我们认为特征是正例还是反例的确信度。

    继续考虑 wb,如果同时加大wb,比如在 wTx(i)+b 前面乘个系数比如2,那么所有点的函数间隔都会增大二倍,这个对求解问题来说不应该有影响,因为我们要求解的是 wTx(i)+b=0 ,同时扩大 wb对结果是无影响的。这样,我们为了限制 wb,可能需要加入归一化条件

    现在我们定义全局样本上的函数间隔

    γ=mini=1,...,mγ(i)

    说白了就是在训练样本上分类正例和负例确信度最小那个函数间隔。

    样本空间任意点 x(i) 到超平面的几何间隔为

    r(i)=wTx(i)+bw=γ(i)w

    函数间隔归一化结果就是几何间隔。同时扩大 wbw 扩大几倍,w 就扩大几倍,结果无影响。
    定义全局的几何间隔
    r=mini=1,...,mr(i)

    分类学习最基本的想法就是基于给定训练集在样本空间中找到一个划分超平面,将不同的类别样本分开。但满足这种要求的划分超平面有很多。
    !Alt text

    如何确定这个超平面

    直观上讲,这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是寻找一个超平面,使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面,我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。

    形式化表示为

    maxr,w,bγws.t.y(i)(wTx(i)+b)γ,i=1,2,...,m

    前面说到同时扩大 wb 对结果没有影响,但我们最后要求的仍然是 wb 的确定值。因此,我们需要对 γ 做一些限制,以保证我们解是唯一的。这里为了简便我们取 γ=1 。这样的意义是将全局的函数间隔定义为1。即将离超平面最近的点的距离定义为1w
    即令

    {wTxi+b+1,yi=+1wTxi+b1,yi=1

    如下图所示
    Alt text

    上式使得等号成立的几个样本点被称为支持向量

    两个异类支持向量到超平面距离之和为:

    γ=2w

    被称为间隔

    最大间隔划分超平面

    欲找到最大间隔的划分超平面,我们得到改写后的目标函数为

    maxw,b2ws.t.yi(wTxi+b)1,i=1,2,...,m

    我们在优化时喜欢求最小值,将上式转化正等价的求最小值如下

    minw,b12w2s.t.yi(wTxi+b)1,i=1,2,...,m

    这就是支持向量机的基本型

    对偶问题

    对偶问题转化

    上式是一个凸二次规划问题,我们可以使用拉格朗日乘数法进行优化,对每个约束添加拉格朗日乘子 αi0。则问题的拉格朗日函数可写为

    L(w,b,α)=12w2+i=1mαi(1yi(wTxi+b))

    式中 αi是拉格朗日乘子.
    我们令
    θ(w)=maxαi0L(w,b,α)

    如果约束条件都满足,θ(w) 的最优值就是 12w2,和目标函数一样。

    因此我们可以直接求 θ(w) 的最小值,等价于求原目标函数。因此目标函数变成如下

    minw,bθ(w)=minw,bmaxαi0L(w,b,α)=p

    将求最大值和最小值交换位置,得到原始问题的对偶问题

    maxαi0minw,bL(w,b,α)=d

    满足

    dp

    在满足某些条件的情况下(满足KKT条件),这两者相等,这个时候就可以通过求解对偶问题来间接地求解原始问题。

    对偶问题求解

    分别求 Lw,b 的导数,并令其为0,得如下结果

    Lw=0w=i=1mαiyixiLb=0i=1mαiyi=0

    带入 L(w,b,α) 得到 minw,bL(w,b,α)

    minw,bL(w,b,α)=12i,j=1mαiαjyiyjxTixji,j=1mαiαjyiyjxTixjbi=1mαiyi+i=1mαi=i=1mαi12i,j=1mαiαjyiyjxTixj

    然后求最大值,从上面的式子得到对偶问题

    maxαi0i=1mαi12i,j=1mαiαjyiyjxTixjs.t.i=1mαiyi=0,αi0,i=1,2,...,m

    上式是关于 α 的式子,如果能求出 α ,则通过 w=i=1mαiyixi 可以求出 w,再根据前面函数距离等于1的假设求出 b

    得到模型

    f(x)=wTx+b=i=1mαiyixTix+b=i=1mαiyixi,x+b

    对于新点 x 的预测,只需计算它与训练数据点的内积即可。且所有非支持向量所对应的系数 α 都等于零(这里为满足 maxαi0L(w,b,α) 最大化必须等于0),因此对于内积计算只针对支持向量即可。

    拉格朗日乘子法和KKT条件

    拉格朗日乘子法和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法,在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。

    前提:只有当目标函数为凸函数时,使用这两种方法才保证求得的是最优解。

    最优化问题分类:
    1). 如果目标函数和约束条件都为变量的线性函数, 称该最优化问题为线性规划;
    2). 如果目标函数为变量的二次函数, 约束条件为变量的线性函数, 称该最优化问题为二次规划;
    3). 如果目标函数或者约束条件为变量的非线性函数, 称该最优化问题为非线性规划.

    拉格朗日乘子法–等式约束问题

    对于等式约束问题

    x=argminxf(x)subject to hi(x)=0,i=1,..,m

    利用拉格朗日乘子法,原问题转换为
    x=argmin xL(x,λ)=argmin xf(x)+mi=1λihi(x),

    其中 λi0,称为拉格朗日乘子,这样我们有了 k+m 个变量。

    通过对 x 求偏导,找最优解,得到最优的条件

    xL(x,λ)=xf(x)+iλixhi(x)=0

    我们得到了 k 个方程式。进一步对拉格朗日乘子求偏导,得到另外 m 个方程式

    L(x,λ)λi=hi(x)=0,

    这里通过强制偏导数为零,我们同样可以限制可能的解满足原始约束条件。现在变量数与方程数相同,使得方程解唯一。

    等式约束问题的合理性

    举个二维最优化的例子

    minf(x,y)s.t.g(x,y)=c

    我们可以画图来辅助思考
    !Alt text这里写图片描述

    蓝线是 f(x,y) 的等高线。箭头表示斜率,和等高线的法线平行。从梯度的方向上来看,显然有 d1>d2
    绿线标出的是约束 g(x,y)=c 的点的轨迹,也就是说,只要正好落在这条绿线上的点才可能是满足要求的点。

    最小值点应该在哪里呢?显然应该是在 f(x,y) 的等高线正好和约束线相切的位置,因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值。

    很容易看出来,要想让目标函数 f(x,y) 的等高线和约束相切,则他们切点的梯度一定在一条直线上。即在最优解处,fg 的斜率平行。
    因此,我们通过观察可以得到优化取到最小值时满足

    [f(x,y)+λ(g(x,y)c)]=0λ0

    这个结果正好等价于方程 F(x,y)=f(x,y)+λ(g(x,y)c)x 求偏导。方程 F(x,y) 在达到极值时与 f(x,y) 相等,因为F(x,y)达到极值时g(x,y)c总等于零。

    拉格朗日乘子法–不等式约束问题

    当同时存在不等式约束时,新的问题描述为

    x=argminxf(x)

    subject to hi(x)=0,i=1,..,msubject to gi(x)0,i=1,..,n

    此时不等式约束下的最优化问题描述为

    x=argmin xL(x,λ,μ)=argmin xf(x)+mi=1λihi(x)+ni=1μigi(x)

    其中 L(x,λ,μ) 为拉格朗日函数,λi 对应等式约束系数,μk 对应不等式约束系数。现在总共有 k+m+n个变量。

    跟等式约束一样,我们想通过对 xλ 求偏导,得到 k+m 个方程式。接下来的问题是怎么通过不等式约束得到更多的 n 个方程式。

    对于不等式约束,当极值点存在 gi(x)<0 区域,那么这个约束不影响极值的取值,等同于没有约束。因此它的系数 μi 可以设置为0。另一方面,如果极值在约束边界上,此时,gi(x)=0。如下图所示
    Alt text
    综合可得到

    μigi(x)=0

    为问题的必要条件。至此,我们得到了 n 个方程式通过不等式约束。系数 λi 可以为任意值,没有符号的限制。然而 μk0 ,下图解释说明。
    Alt text

    假设 xgi(x)=0 区域内,那么 μi 可以不为零。

    {x^*} = \underset{{x}}{\textrm{argmin }} f({x})  + \mu_i g_i({x})
    \\0 = \nabla f({x})  + \mu_i \nabla g_i({x})
    \\\begin{equation}\mu_i = -\frac{\nabla f({x})}{\nabla g_i({x})}\label{eq:signofmu}\end{equation}

    x 点处,f(x)gi(x) 的梯度方向像相反。所以 μi0

    KKT条件

    对于一个标准形式的最优化数学模型

    x=argminxf(x)

    subject to hi(x)=0,i=1,..,msubject to gi(x)0,i=1,..,n

    KKT条件是一个非线性规划问题能有最优化解法的必要和充分条件。KKT条件就是指上面最优化问题中的最小点 x 必须满足下面的条件:
    Stationarity:Primalfeasibility:Dualfeasibility:Complementaryslackness:0=f(x)+iλihi(x)+iμigi(x)hi(x)=0,i=1,..,mgi(x)0,i=1,..,nμi0,i=1,..,nμigi(x)=0,i=1,..,m

    不等式约束问题的合理性

    为什么可对偶问题求解

    L(x,μ)=f(x)+k=1qμkgk(x)μk0gk(x)0

    μk0gk(x)0}=>μg(x)0

    \therefore \begin{equation}\max_{\mu}L(x,\mu)=f(x)\label{a}\end{equation}

    \therefore\begin{equation}\min_{x}f(x)=\min_{x}\max_{\mu}L(x,\mu)\label{firsthalf}\end{equation}

    maxμminxL(x,μ)=maxμ[minxf(x)+minxμg(x)]=maxμminxf(x)+maxμminxμg(x)=minxf(x)+maxμminxμg(x)

    μk0gk(x)0}=>minxμg(x)={0ifμ=0org(x)=0ifμ>0andg(x)<0

    maxμminxμg(x)=0

    此时 μ=0org(x)=0
    \begin{equation}\therefore \max_{\mu}\min_{x}L(x,\mu)=\min_{x}f(x)+\max_{\mu}\min_{x}\mu{g(x)}=\min_{x}f(x)\label{secondhalf}\end{equation}

    此时 μ=0org(x)=0
    联合(???),(???)我们得到 >
    minxmaxμL(x,μ)=maxμminxL(x,μ)

    L(x,μ)=f(x)+k=1qμkgk(x)μk0gk(x)0
    =>
    minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)

    我们把 maxμminxL(x,μ) 称为原问题 minxmaxμL(x,μ) 的对偶问题,上式表明当满足一定条件时原问题、对偶的解、以及 minxf(x) 是相同的,且在最优解 xμ=0org(x)=0。把 x 代入 (???)maxμL(x,μ)=f(x) ,由 (???)maxμminxL(x,μ)=f(x) ,所以 L(x,μ)=minxL(x,μ) ,这说明 x 也是 L(x,μ) 的极值点,即 L(x,μ)x|x=x=0

    最后总结一下:

    L(x,μ)=f(x)+k=1qμkgk(x)μk0gk(x)0
    =>
    minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)=f(x)μkgk(x)=0L(x,μ)x|x=x=0

    KKT条件是拉格朗日乘子法的泛化,如果我们把等式约束和不等式约束一并纳入进来则表现为:

    L(x,λ,μ)=f(x)+i=1nλihi(x)+k=1qμkgk(x)λi0hi(x)=0μk0gk(x)0

    =>
    minxmaxμL(x,λ,μ)=maxμminxL(x,λ,μ)=minxf(x)=f(x)μkgk(x)=0L(x,λ,μ)x|x=x=0

    L(x,λ,μ)x|x=x=0 表明f(x)在极值点x 处的梯度是各个 hi(x)gk(x) 梯度的线性组合。

    核函数

    支持向量机是建立在统计学习理论基础之上的新一代机器学习算法,支持向量机的优势主要体现在解决线性不可分问题,它通过引入核函数,巧妙地解决了在高维空间中的内积运算,从而很好地解决了非线性分类问题。

    特征空间的隐式映射

    前面的讨论中,我们假设训练样本是线性可分的,即存在一个划分超平面能将训练样本正确分类。事实上大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在。

    对于非线性的情况,SVM 的处理方法是选择一个核函数 κ(,) ,通过将数据从原始空间映射到一个更高维的特征空间,使得样本在特征空间内线性可分,来解决在原始空间中线性不可分的问题。

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

    ϕ(x) 表示将 x 映射后的特征向量,于是,在特征空间中的划分超平面所对应的模型可表示为

    f(x)=wTϕ(x)+b

    这意味着建立非线性学习器分为两步:首先使用一个非线性映射将数据变换到一个特征空间。然后在特征空间使用线性学习器分类

    类似于原始空间线性可分的问题,可以得到特征空间的SVM基本型

    minw,b12w2s.t.yi(wTϕ(xi)+b)1,i=1,2,...,m

    其对偶问题是

    maxαi0i=1mαi12i,j=1mαiαjyiyjϕ(xi)Tϕ(xj)s.t.i=1mαiyi=0,αi0,i=1,2,...,m

    求解上式涉及到计算 ϕ(xi)Tϕ(xj),这是样本在特征空间的内积。

    ϕ(xi)Tϕ(xj) 可以有两种方法
    1、先找到这种映射,然后将输入空间中的样本映射到新的空间中,最后在新空间中去求内积
    2、或者是找到某种方法,它不需要显式的将输入空间中的样本映射到新的空间中,而能够在输入空间中直接计算出内积,这就是传说中的核函数方法

    由于特征空间维数可能很高,直接计算通常困难。为了避开障碍,可以设想一个这样的函数

    k(xi,xj)=ϕ(xi),ϕ(xj)=ϕ(xi)Tϕ(xj)

    即特征空间的内积等于在原始空间中通过函数 k(.,.) 计算而得。这样就不必直接去计算高维特征空间的内积。于是上式可重写为

    maxαi0i=1mαi12i,j=1mαiαjyiyjk(xi,xj)s.t.i=1mαiyi=0,αi0,i=1,2,...,m

    求解后可得到

    f(x)=wTϕ(x)+b=i=1mαiyiϕ(xi)Tϕ(x)+b=i=1mαiyik(xi,x)+b

    这里的函数 k(.,.) 就是核函数。

    定义:核是一个函数 K,对于所有的 x1,x2X 满足,K<x1,x2>=<Φ(x1),Φ(x2)>,这里的 Φ 为从 X 到内积特征空间 F 的映射。

    核函数有效性判定

    先看一个例子,假设 xz 都是 n维的 K(x,z)=(xTz)2 展开后,得

    k(x,z)=(xTz)2=(i=1nxizi)j=1nxjzj=i=1nj=1n(xixj)(zizj)=ϕ(x)Tϕ(z)

    现在看一下映射函数(n=3时),根据上面的公式,得到
    ϕ(x)=[x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3]T

    这个时候发现我们可以只计算原始特征 xz 内积的平方,就等价与计算映射后特征的内积。也就是说核函数 K(x,z)=(xTz)2 只能在选择这样的 ϕ 作为映射函数时才能够等价于映射后特征的内积。

    我们再看一个核函数

    k(x,z)=(xTz+c)2=(i=1nxizi+c)j=1nxjzj+c=i=1nj=1n(xixj)(zizj)+(i=1n(2cxi)(2czi))+c2

    对应的映射函数(n=3时)是

    ϕ(x)=[x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x32cx12cx22cx3c]T

    半正定矩阵

    实对称矩阵:如果有 n 阶矩阵 A,其各个元素都为实数,矩阵A的转置等于其本身,则称 A 为实对称矩阵。
    主要性质
    1.实对称矩阵 A 的不同特征值对应的特征向量是正交的。
    2.实对称矩阵 A 的特征值都是实数,特征向量都是实向量。
    3.n 阶实对称矩阵 A 必可对角化,且相似对角阵上的元素即为矩阵本身特征值。

    埃尔米特矩阵n 阶复方阵 A 的对称单元互为共轭,即 A 的共轭转置矩阵等于它本身,则 A 是埃尔米特矩阵。显然它是实对称阵的推广。

    半正定矩阵:一个 n×n 的埃尔米特矩阵 M 是正定的当且仅当对于每个非零的复向量 z,都有 zMz>0,则称M 为正定矩阵,其中z 表示z 的共轭转置。当zMz>0弱化为 zMz0 时,称 M 是半正定矩阵。
    判定:所有主子式大于或等于零

    问题描述与分析

    给定一个函数 K,我们能否使用 K 来替代计算 ϕ(x)Tϕ(z),也就说,是否能够找出一个 ϕ,使得对于所有的 xz,都有 k(x,z)=ϕ(x)Tϕ(z)。 比如给出了 k(x,z)=(xTz)