支持向量机(SVM)(二)— 拉格朗日对偶(Lagrange duality)

来源:http://blog.csdn.net/u011067360/article/details/25215465

简介:

1、在之前我们把要寻找最优的分割超平面的问题转化为带有一系列不等式约束的优化问题。这个最优化问题被称作原问题。我们不会直接解它,而是把它转化为对偶问题进行解决。

2、为了使问题变得易于处理,我们的方法是把目标函数和约束全部融入一个新的函数,为了使问题变得易于处理,我们的方法是把目标函数和约束全部融入一个新的函数,即拉格朗日函数,再通过这个函数来寻找最优点。即拉格朗日函数,再通过这个函数来寻找最优点。

3、约束条件可以分成不等式约束条件和等式约束条件,只有等式约束条件的问题我们在高等数学课程中已经学习过了,其解决方法是直接将等式约束加入原问题构造出拉格朗日函数,然后求导即可。现在考虑更加一般性的问题:带不等式约束和等式约束的极值问题如何构造拉格朗日函数求解。学习拉格朗日对偶原理重要的是理解构造所得的原始问题和原函数的等价性,以及原始问题和对偶问题解得等价性。

回忆一下之前得到的目标函数

3.2. 拉格朗日对偶  - 图1

要求解这个式子。我们可以通过求解对偶问题得到最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题。

1、我们下看下面的一个式子

3.2. 拉格朗日对偶  - 图2

上面是要求解的目标函数及其条件。我们可以得到拉格朗日公式为

3.2. 拉格朗日对偶  - 图3

在这里3.2. 拉格朗日对偶  - 图4被称为拉格朗日算子。

然后分别对w和求偏导,使得偏导数等于0,然后解出3.2. 拉格朗日对偶  - 图53.2. 拉格朗日对偶  - 图6

3.2. 拉格朗日对偶  - 图7

下面我们将要产生一个既有等式又有不等式条件限制的式子,我们可以叫做原始优化问题,这里简单介绍下拉格朗日对偶的原理。如下式子:

3.2. 拉格朗日对偶  - 图8

上述式子有两个条件(等式条件和不等式条件)

由此我们定义一般化的拉格朗日公式

3.2. 拉格朗日对偶  - 图9

这里的3.2. 拉格朗日对偶  - 图103.2. 拉格朗日对偶  - 图11都是拉格朗日算子。不要忘了我们求解的是最小值。

设如下等式:

3.2. 拉格朗日对偶  - 图12

这里的P代表primal。我们设如下约束条件(primal constraints):

3.2. 拉格朗日对偶  - 图13

如果条件不全部满足的话,我们总可以调整3.2. 拉格朗日对偶  - 图143.2. 拉格朗日对偶  - 图15使最大值出现正无穷,即会出现下面情况:

3.2. 拉格朗日对偶  - 图16

因此我们可以得出如下式子:

3.2. 拉格朗日对偶  - 图17

这样我们原来要求的min f(w)可以转换成求了。

3.2. 拉格朗日对偶  - 图18同时我们设

3.2. 拉格朗日对偶  - 图19

3.2. 拉格朗日对偶  - 图20将问题转化为先求拉格朗日关于3.2. 拉格朗日对偶  - 图21的最小值,这个时候就把3.2. 拉格朗日对偶  - 图223.2. 拉格朗日对偶  - 图23看做常量。之后再求最大值。

如下:

3.2. 拉格朗日对偶  - 图24

这个问题就是原问题的对偶问题,相对于原问题只是更换了min和max的顺序,而一般更换顺序的结果是Max Min(X) <= Min Max(X)。然而在这里两者相等。由此我们可以设如下:

3.2. 拉格朗日对偶  - 图25

所以在一定的条件下我们可以得到:

3.2. 拉格朗日对偶  - 图26

因此我们可以解决原问题的对偶问题,但是我们还要看看条件是什么。

假设f和g都是凸函数,h是仿射的(仿射的含义:存在ai, bi,使得3.2. 拉格朗日对偶  - 图27,并且还要满足存在w使得所有的i都有3.2. 拉格朗日对偶  - 图28

有了以上的假设,那么一定会存在使得3.2. 拉格朗日对偶  - 图29是原问题的解,3.2. 拉格朗日对偶  - 图30是对偶问题的解。同时也满足

3.2. 拉格朗日对偶  - 图31另外,3.2. 拉格朗日对偶  - 图32还满足Karush-Kuhn-Tucker( KKT condition),如下式子:

3.2. 拉格朗日对偶  - 图33

所以3.2. 拉格朗日对偶  - 图34如果满足了KKT条件,那么他们就是原问题和对偶问题的解。

我们从式子3.2. 拉格朗日对偶  - 图35和式子3.2. 拉格朗日对偶  - 图36可以看出如果3.2. 拉格朗日对偶  - 图37那么3.2. 拉格朗日对偶  - 图38

这个也就说明3.2. 拉格朗日对偶  - 图39时,w处于可行域的边界上,这时才是起作用的约束。

而其他位于可行域内部的(3.2. 拉格朗日对偶  - 图40)点都是不起作用的约束,其中也就是3.2. 拉格朗日对偶  - 图41的时候。这个KKT双重补足条件会用来解释支持向量和SMO的收敛测试。

原文: https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-2.html