支持向量机对偶形式例题,感知机对偶算法
机器学习技术简介(二):双支持向量机(DSVM)_wx5d44d4866b864的技术博客_博客
特别注意:
微信官方账号原名“红石机器学习之路”即将更名为“AI算法实践”。请关注本微信官方账号!谢谢你
上次主要介绍了线性支持向量机(Linear Support Vector Machine)。线性SVM的目标是找到最胖的分割线,将正负类分开。方法是用二次规划求分类线。本课将从另一个方面入手,研究对偶支持向量机,尝试从新的角度计算分类线,推广SVM的应用范围。
3354前言
一个
双重SVM的动因
首先我们来回顾一下,对于非线性SVM,我们通常可以用非线性变换将变量从X域变换到Z域。然后在Z域,根据上节课的内容,用线性SVM解题。上节课我们说过,用SVM来获得大利润,降低了有效VC的维数,限制了模型的复杂度;另一方面,利用特征变换使模型更加复杂,减少Ein。因此,非线性SVM结合了这两个目的,平衡了两者之间的关系。然后在特征变换下,将Z域求解QP问题的维数设为D 1。如果模型越复杂,D 1就越大,相应地解决这个QP问题就很困难。当d为无穷大时,问题会变得难以解决,那么有什么办法解决这个问题呢?一种方法是使SVM的求解过程独立于D,这是我们这节课要讨论的主要内容。
作为对比,上节课我们讲的原SVM二次规划问题的变量个数是d^ 1,有n个约束;在这一课中,我们将问题转化为一个对偶问题(“等价”SVM),这也是一个二次规划,只是变量的数量变为N,并且有N-1个约束。这种对偶SVM的好处是问题只与N有关,与D无关,这样上面提到的D为无穷大时很难解决的情况就不存在了。
如何将一个问题转化为“等价的”SVM?数学推导很复杂。本文不做详细的数学论证,从概念和原理上做简单的推导。
所以在正则化问题中,是一个已知常数,求解过程就变得容易了。那么对于对偶SVM问题,也可以引入,将条件问题转化为无条件问题,只是是未知参数,个数为n,需要求解。
这个函数右边的第一项是SVM的目标,第二项是SVM和拉格朗日因子 n的条件的乘积,我们把这个函数叫做拉格朗日函数,它包含三个参数:b,w, n
接下来,我们用拉格朗日函数把SVM构造成一个无条件问题:
2
拉格朗日对偶SVM
现在,我们把SVM问题转化为与拉格朗日因子 n有关的最大最小形式,给定n0,那么对于任意固定的,且n0,必然存在如下不等式:
取上述不等式右边的最大值,不等式也成立:
上面的不等式说明我们把SVM的最小值和最大值对调了,满足这个关系,这就是所谓的拉格朗日对偶问题。不等式的右边是SVM问题的下界。我们的下一个目标是找到这个下限。
已知是弱对偶关系。在二次规划的QP问题中,如果满足以下三个条件:
函数是凸的,函数有解,条件是线性的。然后,上面的不等式关系变成强对偶关系,变成=,即一定有满足条件的解(b,w,),这样方程左右两边都成立,SVM的解就转化为右形式。
经过推导,SVM对偶问题的解已经转化为无条件形式:
其中拉格朗日函数L(b,w,)的最小值在上式的括号内计算。然后按照梯度下降算法的思路:最小位置满足梯度为零。首先,设L(b,w,)对参数b的梯度为零:
这样,SVM表达式消除了B,问题就简化了。然后按照最小值的思想,设L(b,w,)对参数w的梯度为零:
也就是说,得到:
这样,SVM表达式去掉了W,问题就更简化了。此时有三个条件:
综上所述,SVM的优化形式转化为只与n有关:
其中,满足最优化的条件被称为卡鲁什-库恩-塔克(KKT):
下一部分,我们将利用KKT条件计算优化问题中的,进而得到B和w
三
求解双重SVM
我们已经得到了简化版的双SVM以上。接下来我们会继续优化。首先将max问题转化为min问题,然后整理并推导出一些条件,得到:
显然,这是一个凸的QP问题,有N个变量n和N-1个约束。然后根据上节课提到的QP解,求出Q,P,A,C的对应值,再用软件工具包求解。
四
双重SVM背后的信息
回想一下,在上一课中,我们将分类线边界上的点称为支持向量(候选)。在本课的前面,介绍了n 0的点必须落在分类线的边界上。这些点称为支持向量(注意没有候选)。也就是说,分类线上所有点不一定是支持向量,但满足n 0的点一定是支持向量。
SV只由n 0的点决定。根据上一部分推导出的W和B的计算公式,我们发现W和B只由SV即n 0的点决定,简化了计算。这与上一课中介绍的分类线仅由“胖”边界上的点确定的原因相同。也就是说,样本点可以分为两类:一类是支持向量,通过它得到最胖的超平面;可以获得;另一种不是支持向量,对我们最胖的超平面没有影响。
回过头来,让我们比较一下SVM和解放军的W公式:
综上所述,这节课和上节课主要介绍了SVM的两种形式,一种是原始硬边际SVM,另一种是双重硬边际SVM。Primhard-margin SVM具有d^ 1参数和n个约束。当d^ 1很大时,很难求解。而双硬边界SVM有N个参数和N-1个约束。当数据量n很大时,也会增加计算难度。两种形式都能得到W和B,得到最胖的超平面。通常,如果n不是很大,通常使用对偶SVM来解决问题。
五
摘要
这节课主要介绍SVM的另一种形式:双重SVM。这样做的出发点是为了去除计算过程对d的依赖,对偶SVM的推导过程是通过引入拉格朗日因子,将SVM变换成新的无条件形式。然后,利用QP求出最佳解的拉格朗日因子。然后通过KKT条件,计算出相应的W和B。最终得到最胖的超平面。在下一课中,我们将解决计算对偶SVM时对D的依赖性问题。
长按二维码扫描关注。
人工智能算法实践
版权归作者所有:原创作品来自博主wx5d44d4866b864,转载请联系作者授权,否则将追究法律责任。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。