SVM学习——求解二次规划问题

       上一篇最后提到要解决最优化问题 :SVM学习——求解二次规划问题

                                                        SVM学习——求解二次规划问题SVM学习——求解二次规划问题

稍微对它做一下改动,如下:

                                       SVM学习——求解二次规划问题

                                       SVM学习——求解二次规划问题  SVM学习——求解二次规划问题  SVM学习——求解二次规划问题

这是一个约束优化问题,更进一步说是一个二次规划问题,复习一下约束优化问题:

     定义1:约束非线性问题是,

                                            SVM学习——求解二次规划问题

                                            SVM学习——求解二次规划问题

                                                   SVM学习——求解二次规划问题

其中SVM学习——求解二次规划问题SVM学习——求解二次规划问题都是定义在SVM学习——求解二次规划问题上的实值连续函数,且至少有一个是非线性的(反之为线性约束优化问题),m是一个正整数,SVM学习——求解二次规划问题叫做目标函数,SVM学习——求解二次规划问题叫做约束函数,如果目标函数是二次函数则叫做二次规划问题,由同时满足所有约束方程的点组成的集合叫做可行域,这些点叫可行点。

      定义2:Farkas引理,对于给定的n维向量SVM学习——求解二次规划问题SVM学习——求解二次规划问题与b,对于任意满足SVM学习——求解二次规划问题  SVM学习——求解二次规划问题的向量P,必有SVM学习——求解二次规划问题的充要条件是:b在向量SVM学习——求解二次规划问题SVM学习——求解二次规划问题所形成的凸锥内,即成立:SVM学习——求解二次规划问题SVM学习——求解二次规划问题  SVM学习——求解二次规划问题

怎么理解“某个向量在若干其它向量形成的凸锥内”这个描述呢?可以看下图,SVM学习——求解二次规划问题

利用平行四边形法则,可以看到向量b处于由SVM学习——求解二次规划问题形成的凸多边形内,发挥一下想象力,在空间中这不就像是一个凸的锥状体嘛。

       定义3:对于约束问题,如果有一个可行点SVM学习——求解二次规划问题,存在SVM学习——求解二次规划问题且满足

                                                 SVM学习——求解二次规划问题

                                                SVM学习——求解二次规划问题 这里SVM学习——求解二次规划问题都是有效约束。

SVM学习——求解二次规划问题叫做K-T点。

      K-T点的几何意义可以从下图看出:

SVM学习——求解二次规划问题

      显然x1是K-T点而x2则不是。在一般非线性规划中,K-T条件是最优解的必要条件但不是它的充分条件,此时K-T点不一定是最优点,但对于凸规划问题,K-T条件是最优解的充要条件;顺便说下,凸规划是个好同志,它的局部最优解就是全局最优解,所以它的K-T点就是全局最优点。

      定理1:设SVM学习——求解二次规划问题是约束问题的局部极小点,SVM学习——求解二次规划问题点处的线性化可行方向的集合等于其序列可行化方向的集合,则必存在SVM学习——求解二次规划问题 SVM学习——求解二次规划问题使得:

                            SVM学习——求解二次规划问题

                            SVM学习——求解二次规划问题 这里SVM学习——求解二次规划问题都是有效约束。

SVM学习——求解二次规划问题点处的线性化可行方向的集合等于其序列可行化方向的集合”这个条件怎么满足呢?只要所有有效约束都是线性函数即可,此时SVM学习——求解二次规划问题必是一个K-T点。

      定理2:一阶最优性条件:对于可行点SVM学习——求解二次规划问题,如果目标函数和所有有效约束在SVM学习——求解二次规划问题处可微,且任意、非零的,在SVM学习——求解二次规划问题处的序列可行化方向向量d满足:SVM学习——求解二次规划问题,则SVM学习——求解二次规划问题为严格局部极小点。这意味着,当向某一点处的任意方向移动都将导致目标函数值上升,那么这个点不就是一个局部极小点嘛。

      定理3:二阶最优性条件:设SVM学习——求解二次规划问题为K-T点,SVM学习——求解二次规划问题是相应的拉格朗日乘子,如果SVM学习——求解二次规划问题,其中d为非零的、SVM学习——求解二次规划问题处的线性化零约束方向,则SVM学习——求解二次规划问题为严格的局部极小点。

      推论1:设SVM学习——求解二次规划问题为K-T点,SVM学习——求解二次规划问题是相应的拉格朗日乘子,如果对一切满足SVM学习——求解二次规划问题的非零向量d都有SVM学习——求解二次规划问题,则SVM学习——求解二次规划问题为严格的局部极小点。                                     

      对于前面的约束非线性规划问题,如果SVM学习——求解二次规划问题是二次函数且所有约束是线性函数的时候就变成了二次规划问题,这一写成以下形式:

                              SVM学习——求解二次规划问题

                              SVM学习——求解二次规划问题

                                   SVM学习——求解二次规划问题

       定理4:如果SVM学习——求解二次规划问题是二次规划问题的可行点,则SVM学习——求解二次规划问题是局部极小点的充要条件是:当且仅当存在拉格朗日乘子SVM学习——求解二次规划问题,使得:     

                              SVM学习——求解二次规划问题

                             SVM学习——求解二次规划问题   SVM学习——求解二次规划问题

                             SVM学习——求解二次规划问题SVM学习——求解二次规划问题

成立,(即SVM学习——求解二次规划问题是K-T点)且对于一切满足

                            SVM学习——求解二次规划问题

                            SVM学习——求解二次规划问题

                           SVM学习——求解二次规划问题(其中E为等式的有效约束,I(SVM学习——求解二次规划问题)为不等式的有效约束)

的向量d都有:SVM学习——求解二次规划问题

        定理5:设H为半正定矩阵(所有特征值大于等于0),则SVM学习——求解二次规划问题二次规划问题的全局极小点当且仅当它是一个局部极小点或者K-T点。

      当H为半正定矩阵,目标函数为凸函数时,该二次规划被叫做凸二次规划,它的任何K-T点都是极小点。回想我们开篇要解决的那个问题,目标函数显然是一个凸函数,所以它是一个凸二次规划问题,所以一定存在全局极小点(真好!)。

      到此,我们就可以开始解决开篇的那个问题:

                                       SVM学习——求解二次规划问题

                                               SVM学习——求解二次规划问题  SVM学习——求解二次规划问题

已经确定它是一个凸二次规划问题了,那么可以利用其拉格朗日函数:SVM学习——求解二次规划问题

通过对SVM学习——求解二次规划问题SVM学习——求解二次规划问题求偏导数后得到:

                                           SVM学习——求解二次规划问题

                                           SVM学习——求解二次规划问题 

带入原始拉格朗日函数,转化为对偶问题:

                             SVM学习——求解二次规划问题

                                           SVM学习——求解二次规划问题

                                           SVM学习——求解二次规划问题

这样就把带不等式约束的优化问题通过其对偶形式转化为只带等式约束的优化问题,即下面的最优化问题W:

                            SVM学习——求解二次规划问题

                             SVM学习——求解二次规划问题

                                    SVM学习——求解二次规划问题

求得SVM学习——求解二次规划问题后就得到了SVM学习——求解二次规划问题,它使得几何间隔SVM学习——求解二次规划问题取最大值,从而得到最优分类超平面。

      K-T点要满足的条件还有一个是:SVM学习——求解二次规划问题,这个式子说明了什么问题呢?

      1、显然,函数间隔不等于1的那些输入点的拉格朗日系数必为0(这些点是非积极因素),而函数间隔恰好为1的输入点的拉格朗日系数则不为0(这些点是积极因素),这说明确定最终分类超平面的就是这些函数间隔为1的边界点,所以这些输入点就是支持向量(Support Vector)。从这里也能看出支持向量机的抗干扰能力比较强,对非积极因素的扰动对于最优化解没有影响;

      2、SVM学习——求解二次规划问题,其中i为支持向量,因为:SVM学习——求解二次规划问题

,我们的目标函数SVM学习——求解二次规划问题

                                     SVM学习——求解二次规划问题

                                     SVM学习——求解二次规划问题

                                     SVM学习——求解二次规划问题(注意这里SVM学习——求解二次规划问题为常数,且有约束条件SVM学习——求解二次规划问题

于是通过这样的对偶转化,我们得到了实现几何间隔为SVM学习——求解二次规划问题的最大间隔超平面。

     通过上面的推导也可以看出将二次规划转化为其对偶问题可以简化约束条件,让我们记住最优化问题W吧,这是一个很牛逼的转化,这个式子还有个特点,就是“数据仅出现在内积中”。

     前面的讨论都是说输入样本是线性可分的时候怎么找到最大间隔超平面来划分两类数据,那么如果输入样本是线性不可分的,那可怎么办呀,前面的那些讨论不就成徒劳的了么?学习SVM后才知道它牛的地方,如果我们可以通过某种函数映射将输入样本映射到另外一个高维空间并使其线性可分的话,前面的讨论结果不就都可以用到了么,还记得“数据仅出现在内积中”吧,假设这个映射关系是:SVM学习——求解二次规划问题,这时候的内积SVM学习——求解二次规划问题就变成了SVM学习——求解二次规划问题,如果有方法能够将内积SVM学习——求解二次规划问题直接算出,就将把输入样本“从低维空间向高维空间映射”和“求映射后的内积”这两步合并成了一步,这样直接计算的方法就是核函数方法,下篇学习核函数吧,SVM的理论部分还是很数学的啊!

                                    

转载于:https://www.cnblogs.com/vivounicorn/archive/2010/12/06/1897702.html

上一篇:输出100~1之间能被3或5整除的数字,每行输出5个数字


下一篇:2021-05-21 GOOGLENET重点