支持向量机对偶形式例题,感知机对偶算法

　　机器学习技术简介(二):双支持向量机(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的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。