机器学习技法-lecture2：Dual Support Vector Machine

Dual Support Vector Machine

课程回顾

lecture1中我们主要介绍了最简单的线性的SVM，包括标准的数学形式、QP的解法和其背后的理论保证，本节课我们进一步研究非线性的SVM。

Motivation of Dual SVM

我们的目的是做一个非线性的SVM，其中的一个步骤是我们需要将原始的特征空间(X空间)通过一个非线性变换映射至一个更高维的空间(Z空间),于是一个很现实的问题摆在眼前，如果Z空间的特征维度过高甚至是无穷维，那么我们使用二次规划解决这个问题将会付出过多的计算成本，于是我们需要改进这个问题的解决方案。

我们的一个思路是把原来的比较复杂的SVM的问题转化成一个对偶的SVM的问题，转化的主要思路是我们之前在做正则化时，将带条件的Ein最小化问题转化成最小化Eaug的思路，使用的工具主要为：Lagrange Multipliers。

实际上我们这么做的目的是将限制条件加入我们的目标函数，我们采用分类讨论的方法容易证明我们得到相应的Lagrange function先对α取最大值再对b,w取最小值的解与原始的SVM问题的解是一致的，其中α需要大于等于0。

Lagrange Dual SVM

我们容易证明原始的问题是大于等于其对偶问题的，然后我们发现对偶问题相对而言容易解答（因为后者的括号里面是求解b,w的无条件限制问题），于是我们的目的是寻求建立两者的联系从而达到转化的目的，在前辈的研究下，发现当如下条件成立时，二者的解是等价的。具体的三个条件是：问题是凸函数、问题有解及问题的限制条件是线性的，而SVM恰好是满足的。

于是我们顺利将问题转化为求解对偶问题，我们着眼于内部的无条件的最小化问题，我们容易知道最低点在梯度为零的位置取得，我们对w和b求梯度可以化简得到如下结果：

此外，求解该类问题需要满足的条件也被总结成KKT条件，主要如下：

Solving Dual SVM

解决对偶的SVM的问题，我们使用的方法还是QP方法，等价于求解α的最优解问题，在求解出α以后结合KKT条件我们可以求解出相应的w和b。

Messages behind Dual SVM

结合上节课的内容，我们给出support vector的定义：那些对应α大于0的点。大于0的α都对应着一个sv,我们还发现w能被这些sv唯一表示，进而可以唯一求解出b，也就是说决定这个边界分类器的只是sv。

结合前面学过的PLA，容易发现二者的表现形式是相似的，这似乎揭示了两者的某种联系。

最后需要指出的是我们本节课的推导并没有解释如何化解高维度计算量，这部分的内容将在接下来的课程讨论。

小结

本节课我们主要建立了SVM的对偶问题，推导了其数学形式，重点关注其成立的条件，解决的方法还是QP方法，最后我们给出了support vector的定义，分析了其背后的理论依据。