《SVM学习的对偶算法.docx》由会员分享，可在线阅读，更多相关《SVM学习的对偶算法.docx（11页珍藏版）》请在三一文库上搜索。
1、SVM 学习的对偶算法2013.3.23最近课上要求讲一讲关于 SVM 的内容，我被分到了对偶算法这一块，就顺便把这部分知识整理了一下，并加上了一些个人的理解。至于 SVM 有多重要，曾经的研究有多么热这里就不再重提了。一、 问题的引出SVM 的目的非常直接：分类的间隔最大化。由此，得到了非常简洁的最优化模型（这里仅以线性可分 SVM 为例）：min1| w |22w , bs.t .yi ( w x + b ) 1, i =1, 2,., N在这个问题中，x 和 y 是输入的样本点，都是已知的数据，并不是未知数。实际的自变量是w，目标函数是 w 的二次函数，所有的约束条件都是关于 w 的线性
2、函数，这种规划问题叫做二次规划（Quadratic Programming，QP），而且由于它的可行域是一个凸集，因此它是一个凸二次规划。对于一个规划问题，我们最喜欢问的问题就是：“是不是有解？如果有解，是否能找到？”而这样的问题一般很难回答。但是，对于凸二次规划问题，可以证明，总是有唯一的最优解，即全局最优解。然而，有解不等于容易求出来。在这个问题中，虽然目标函数是极其简单的二次函数，但是约束条件并不简单，特别是将 N 个线性约束条件加上去之后可行域边界极其复杂，直接求解几乎是不可能的。那么，我们该如何处理呢？带约束的优化问题，我们一般的求解策略就是将其转化为无约束优化问题，这让我们很容易想
3、到 Lagrange 乘子法：L ( w, b, a ) = 1 | w |2 + Nai yi ( w xi + b) -12i=1令 L 对其 3 个参数的偏导数值分别等于 0，得到的解便是最优解。问题似乎轻而易举地解决了。但是仔细想想，Lagrange 乘子法中要求约束条件是等式，而这里是不等式，所以这种解法并不正确。虽然这么做不正确，但是多少也给了我们一点启发，至少这种转化的方向应该是对的。所以，就有人提出了利用 Lagrange 对偶性进行求解的算法。二、Lagrange 对偶性为了便于更好地描述 Lagrange 对偶性的原理，我们先把上面的问题放在一边，看一个最典型的凸优化模型：
4、minf ( x)xRns.t .g i ( x ) 0,i =1, 2,., kh j ( x ) = 0,j =1, 2,., l这里我们对这个模型做一些限制：1） f ( x )和g i ( x )，i =1, 2,., k均为凸函数 ；2） h j ( x ), j =1, 2,., l 均为仿射函数，即有 Ax +b 的形式。第一个限制不难理解，但是为什么要求 h j ( x) 是仿射函数呢？事实上，为了统一凸优化问题的形式，我们可以这样表述约束条件：g i ( x ) 0,i =1, 2,., kh j ( x ) 0,j =1, 2,., l- h j ( x ) 0,j =1,
5、 2,., l即全部的约束条件都能写成小于等于 0 的形式。同时，还要求它们全部是凸函数。这样一来， h j ( x )和-h j ( x) 都是凸函数，那只能取直线（直线也是一种比较特殊的凸函数）了，高维空间的直线，其表示形式就是仿射函数。明确了模型的要求之后，我们可以仿照之前的 Lagrange 乘子法也写出这样的形式klL ( x, a , b ) = f ( x ) + a i g i ( x ) + b j h j ( x ),ai 0, i =1, 2,., ki =1j =1这里的a i 和b j 都是拉格朗日乘子。如果我们对这个 L 求最小值，马上就会发现，在可行域内，h j
6、( x ) = 0, j =1, 2,., l ，第三项等于零，不会对结果产生影响，而 g i ( x ) 0, i =1, 2,., k 和ai 0, i =1, 2,., k 决定了第二项不会是正数，要想取得 L 的最小值，我们令某个 g i ( x) 0或者h j ( x) 0 的情况，只需令对应的乘子取无穷大，qP ( x) 就可以取到无穷大，以此来表明超出了可行域范围。既然有上面的关系，那么自然就有min f ( x ) = min q P ( x) = min max L( x, a , b)xxxa , b ;ai 0这个问题称为广义 Lagrange 函数的极小极大问题。记p
7、* = min qP ( x)x为原始问题的最优值毫无疑问，此时的最优解与原始问题的解相同，但是：1、这个“新”的问题仅仅是原始问题在形式上的一个重写，本质上并没有转换成新的问题，仍是原始问题；2、正因如此，这个形式上的新问题，并没有给问题的求解带来更大的便利，而且 Lagrange 乘子有两组，其中关于的约束仍为不等式，特别是，复杂度没有降低不说，一旦试着求解一下就会发现，求完极大值之后又回到原来的问题了，徒劳一场。极小极大问题给了我们一个提示，可否尝试着换成极大极小的形式，而且能得到相同的解？下面，我们就来看一下这种思路是否可行。定义q D (a , b ) = min L ( x, a
8、, b )x其中 D 表示对偶问题。再对结果关于，求极大值，得到max q D (a , b ) = max min L ( x, a , b )a , ba , bxs.t .ai 0 , i =1, 2,., k这个问题叫做广义 Lagrange 函数的极大极小问题，这里我们称它为原始问题的对偶问题，记d * = min qD ( x)x为对偶问题的最优值。现在，我们将问题转化成先将a i 和b j 看作固定值，关于 x 求无约束的极小值，然后再对a i 和b j 求极大值。可以看出，此时问题的约束条件变得简单了，极有可能更容易求解一些，所以我们可能更愿意处理这样的问题。现在急需明确的是，
9、原始问题与对偶问题是否完全等价呢？形式上，它们只是交换了求极大和极小的顺序，那么本质上是否如此呢？很遗憾，答案是否定的，这是因为L ( x , a , b ) min L ( x, a , b ) = qD ( x)xL ( x , a , b ) maxL ( x, a , b ) = qP ( x)a , b ;ai 0所以q D ( x ) qP ( x)继而d * = max qD( x ) min qP( x) = p*a , b ;ai 0x即它们的最优解存在着不等关系，而不是我们期望的相等关系。但是，细心的朋友可能就会发现，两个解是有可能取到等号的，我们如果能找出取等条件，那么，
10、当满足这个条件时，相等关系恒成立，那么不就是我们最想要的结果吗？那么，我们就来看看是否存在这样的取等条件。假设 ( x* , a * , b* ) 是对偶问题的最优解，那么d * = q D (a * , b * ) = min L ( x, a * , b * )x= min f ( x ) + a i* g i ( x ) + b *j h j ( x)x i =1j =1kl显然klklmin f ( x ) + a i* g i ( x ) + b *j h j ( x ) f ( x ) + a i* g i ( x ) + b*j h j ( x)xi=1j =1i =1j =1当
11、 x*是最优解时，上式得等号成立klklmin f ( x ) + a i* g i ( x ) + b *j h j ( x ) = f ( x * ) + a i* g i ( x * ) + b*j h j ( x* )xi =1j=1i =1j =1与原始问题的最优解 p* = f ( x* ) 相比，差了后面kl a i* g i ( x * ) + b*j h j ( x* )i =1j =1这两项。由于最优解 x*肯定在可行域内，h j ( x* ) = 0, j =1, 2,., l ，所以关于 b * 的那一个求和项全部为零，现在，只差关于a* 这个求和项了，我们只要能让它等
12、于零，那么就有f ( x * ) + a i* g i ( x * ) + b*j h j ( x * ) = f ( x* )kli =1j =1这样就得到了我们想要的 d * = p* 了！所以，上面提到的我们最想看到的取等条件就是kai* g i ( x* ) = 0i=1而求和项中每一项都是非正数，求和结果为零，那么只能是ai* g i ( x* ) = 0，i =1, 2,., k这就是著名的互补对偶条件。有了它，我们就可以放心地去求解对偶问题了。在开始求解之前，可能有人会有疑问，这个互补对偶条件的意义是什么？我们可以换种写法a i* 0, g i ( x* ) = 0g i ( x
13、 * ) 0 时，必须有 g i ( x* ) = 0 ；当 g i ( x* ) 0 的样本点，分离超平面只是这样的点支持的，故称这样的样本点为支持向量。换个角度来看，根据 KKT 条件，ai yi ( w xi + b) - 1 = 0，i=1,2,.,N对于ai* 0的样本点，一定有yi ( w* xi + b* ) -1=0即w* xi + b* = 1由此可知，这样的样本点都在间隔边界上，同样说明训练数据中ai 0 的样本点是支持向量。至此，可以总结出利用对偶问题求解一般流程：1、构造优化问题的对偶形式；2、求解对偶问题（具体求解用到了 SMO 算法）；3、计算 w；4、选择不为零的
14、a j 对应的 j 计算 b；5、得到分离超平面和分类决策函数；这样，我们就完美地解决了线性可分 SVM 的求解问题。四、软间隔 SVM 的对偶问题从原始问题到对偶问题的转化与前面的处理基本一致，得到对偶问题N1NNmaxa a i-a ia j yi y j ( xi x j )i =12 i =1j =1Ns.t .ai yi = 0i=10 ai C ,i = 1, 2,., N其中,由于mi 与C和ai线性相关，可以消去。直接给出该问题的 KKT 条件： w L ( w* , b* , x * , a * , m * ) = w* - ai* yi xi = 0i=1NN b L (
15、w* , b* , x * , a * , m * ) = ai* yi = 0i=1 x L ( w* , b* , x * , a * , m * ) = C - a * - m* = 0yi ( w* xi + b* ) - 1 + xi* 0，i=1,2,.,Nxi* 0，i=1,2,.,Na i* yi ( w* xi + b* ) - 1 = 0，i=1,2,.,N mi*xi* =0，i=1,2,.,N (互补对偶条件)最终求解出的参数与线性可分 SVM 的对偶问题完全相同（这样说不完全准确，因此此时的b*取值不唯一，需要采取特定的措施确定），可以参照第三部分，此处不予列出。根据
16、 KKT 条件可以得出软间隔的支持向量的分布情况五、利用对偶问题进行求解的优点经过上面的证明和推导，我们发现利用对偶问题对 SVM 问题进行求解有很多优点，主要几点如下;1、原始问题中复杂的约束条件在对偶问题中变得简单，并且仍是凸优化问题从下面的关系图可以看出，线性可分 SVM 和软间隔 SVM 在变成对偶问题之后约束条件都变简单了，特别是，在原始问题形式下，软间隔问题要复杂很多，但是在对偶问题形式下，差别仅仅体现在对ai 的约束上多了一个常数上界 C，这最直接的优点就是两个问题的求解过程十分相似，几乎可以完全像处理线性可分 SVM 问题那样处理软间隔 SVM 问题。2、对偶问题中只涉及到了样本的内积，容易过渡到核技巧核技巧是 SVM 问题中最重要的内容之一，借助对偶问题，可以直接过渡到核技巧，实现原空间的内积到特征空间的内积之间的映射。3、对偶问题的形式便于用 SMO 算法求解对偶问题将对 w 和 b 的求解转化为对一组ai 的求解，可以通过类似于坐标轮换法的SMO 算法来求解。