Dual Support Vector Machine《机器学习技法》学习笔记(2.1、2.2、2.3、2.4)

第1周的课里面主要讲的是线性SVM,包括如何让线性SVM的线性分割的线更加鲁棒以及如何用二次规划(QP)求解,我也用Matlab实践了一下。
这一周主要讲的是SVM的对偶问题,或者说是SVM的另一种表示形式。

预备知识1:对偶问题

本科的时候学过运筹学,里面使用线性规划讲解的对偶问题,跟这个很相似,目的就是最大问题的对偶问题是最小化问题(对偶具有对称性,所以反过来也对),而且可以解决原问题无可行解,但对偶问题具有可行解的情况或者对偶问题比原问题好计算。
而且对偶问题的一个性质就是两个问题都有可行解的话,最优解就是一样的。SVM的对偶问题是两个问题都可行解的,而且对偶问题更容易计算。

原问题

假如现在问题是有a,b,c三种资源分别可以生产出甲乙两种产品,什么时候利润最大,大概就是下面这张图:

该问题其实是资源有限条件下的最优生产决策问题,这个问题是最简单的,原问题和对偶问题都有可行解
目标函数:

    maxz=50x1+100x2;

约束条件:

    x1+x2<=300;
    2x1+x2<=400;
    x2<=250;
    x1,x2>=0

二维可以使用图解法求解,高维使用单纯性法(简单的说:添加非基变量化为标准型,然后从有限的基可行解寻找最优解,最优解的非基变量系数都为负)求解。
算法时间复杂度:迭代次数n小于或者等于约束条件的个数m(最大为m)。

对偶问题

首先说一句,线性规划的对偶问题主要可以用来解释资源的影子价格、线性规划问题的灵敏度分析。
上面是一个把资源创造出产品,产品最大利润问题,你可以把这个问题反过来想,产品折算成资源去卖成钱(影子价格),这个问题就变成了我怎么利用这三种资源赚的更多,对于每个产品来说就是用的资源转让出去要比这个产品挣的多,这时候资源转让的价格也可以算出来,原问题的话就可以变成300y1+400y2+250y3。

但这时候如果算转让各种资源什么时候最挣钱,因为资源只要越贵越好,整体肯定更贵,无最优解们也没什么意义,但是如果算什么时候赚的最少,说明我产品拆成资源赚的钱少不值得,我反过来资源变成产品利润就是高的很值,于是就通过资源的影子价格算出来了最大的利润。
目标函数:

    minw=300y1+400y2+250y3

约束条件::

    y1+2y2>=50;
    1y1+1y2+1y3>=100; 

具体对偶问题反映了经济学上的边际效益什么、或者更普遍的“灵敏度”的我就不说了。

预备知识2:拉格朗日乘子法

这个方面百度百科就有,但是推荐看这个博客。这个的讲解主要来自于推荐的博客。wiki的定义,拉格朗日乘数法是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法。基本思路就是把约束条件放进损失函数。
定义凸优化问题:

从数学角度看,凸优化问题又可以分为以下三种情况:
1. 无约束优化问题:min L(x);
2. 等式约束优化问题:min L(x);s.t. h_i(x) = 0,i =1, …, n;
3. 不等式约束优化问题:min L(x);s.t. g_i(x) <= 0,h_i(x) = 0,i =1, …, n。

第一种情况,无约束优化问题,minf=2x2 +3y2 +7z2 ,最小应该直接求一阶偏导,然后就是都等于0,最后最小值等于0.
第二种情况,等式约束优化,用拉格朗日乘子法解决。
问题:

然后拉格朗日会变成:

继续求偏导换元:

然后将x都变成α的最小化,此时就是无约束优化问题,然后直接求偏导就行了。

KKT条件定理

任何原始问题约束条件无非最多3种,等式约束,大于号约束,小于号约束,而这三种最终通过将约束方程化简化为两类:约束方程等于0和约束方程小于0。

都变成等号与小于号,方便后面的,反正式子的关系没有发生任何变化就行了。
新的目标函数:

新的约束条件就是KKT条件,下面是KKT条件定理:
如果一个优化问题在转变完后变成下面这样:

其中g是不等式约束,h是等式约束(像上面那个只有不等式约束,也可能有等式约束)。那么KKT条件就是函数的最优值必定满足下面条件:

具体为什么对,我觉得结合SVM的很好懂,先说到这,SVM的KKT那会进行证明。

回到SVM的对偶问题

这一周主要四课,动机,拉格朗日对偶,解决对偶,对偶SVM后面是什么意思。

Motivation

线性变成非线性,只需要加上非线性的特征转换,这个很简单。
在第一周的时候已经用过二次规划解决问题,Q的纬度=d+1 因为w的纬度和x的纬度是一样的d,再加上b的纬度是1,所以是d+1,所以当非线性转换后的zn纬度很大,那这个Q就很大,计算就很麻烦

现在的问题,是如果d是无限大怎么办?

重新梳理一下思路

现在求w和b就是d+1的变量,N个限制条件。d无穷大我们没法做,把d给去掉,然后我们就去找他的对偶函数,新的问题没有d

怎么变,用拉格朗日乘子法结合KKT


首先这个min,max要先看懂,因为
都是小于等于0的,α又等大于等于0,如果最大化后面那一部分就应该等于0,此时后面那一坨最大就是0,就和原始的min问题等同了。
如果不满足上面的限制条件,就是有大于等于0的,那么最大就是无限大,那么问题就变了。
所以想要保证问题不变,而且问题满足原始条件,那就是上面KKT说的第三个条件。

拉格朗日对偶

上面只是感性的说了KKT的第三个条件,现在重头来一遍:

max大于等于any,又大于等于any就是大于等于最好的(最大的)。所以max、min反过来,注意α变成了α',不过由于条件都是所有的α大于等于0,所以连个没什么区别。
这样的好处在于min问题终于和目标函数放在一起了。


大于等于是弱对偶,等于才是强对偶问题
因为我们现在要解右边的问题(min问题和目标函数放在一起),如果我们还是希望用原来的二次规划算法,那应该是强对偶问题。
强对偶就意味着b,w,α对原问题和对偶问题都是最优解。
所以现在就是要添加限制条件是两者变成强对偶问题。

最小里面的肯定对b的偏导要等于0,可以推出来,因为b就是一次项,所以可以添加条件消掉b。

刚才对b偏导,现在对w偏导,消掉w,最后化简之后已经没有w了,w在限制条件里,所以里面的min也可以消掉了,只剩α的问题。

上面推导过程中需要满足的事情有:
两边化等号变成强对偶的条件,就是KKT第三条件;
两个问题的原始条件;
还有为了简化推到的条件,就是dual-inner optimal。

解决对偶问题

还是要一步一步化成QP问题

首先max问题乘-1变成最小化问题,然后平方展开写成向量相乘,又因为w暂时跟问题没关系,先不管。所以就是求解α了。

二次规划完美转换。
但是新的问题来了。上面的那个z的纬度如果很大,Q是很大的,所以不能使用标准的QP算法。


α出来以后怎么算w,b?
w直接算出来,b通过找到α不等于0的里面任意找一个找就行了。
α不等于0,那就是后面的等于0,其实就是找到了支撑向量。

总结:对偶SVM后面是什么意思


只有α>0才是有意义的样本。

现在真的和d没有关系了吗?q可是d2的矩阵,仍然有关系,而且d无穷大还是没解决,下周解决这个问题。

发表评论

电子邮件地址不会被公开。