机器学习技法——第1-2讲.Linear Support Vector Machine

本栏目（机器学习）下机器学习技法专题是个人对Coursera公开课机器学习技法（2015）的学习心得与笔记。所有内容均来自Coursera公开课Machine Learning Techniques中Hsuan-Tien Lin林轩田老师的讲解。（https://class.coursera.org/ntumltwo-001/lecture）

第1讲-------Linear Support Vector Machine

在机器学习基石介绍的基本工具（主要围绕特征转换Feature Transform）的基础上，延伸成为复杂而实用的模型。一方面，如何更好地运用现有的features以及控制复杂度的问题，产生了SVM（支持向量机）模型；再者，如何构造或者结合出一些具有预测性的feature让整个模型有更好的表现，产生了AdaBoost（逐步增强法）模型；另外，如何学习出隐含的features，这样的想法刺激了早年的神经网络近年发展成为Deep Learning的模型。

一、最大边界间隔超平面

在Perceptron中，针对如下图所示线性可分的训练数据，有可能会得到左/中/右这样的三条分隔线，而且Perceptron无法确定这三条线哪一条更好。凭直觉而言，最右边是最好的，因为其对噪声的容忍度最高。从点的角度来看，测试模型的时候由于测量误差或者收集的条件不同，即便应该与训练数据一模一样的数据在收集时也可能出现误差，图中圆形区域为噪声，区域越大表示能够容忍的噪声越大；另一方面，从线的角度来看，超平面分别向正负样本方向扩展到最近的正负样本得到的间隔，代表了超平面的鲁棒性，最右边的线得到的间隔也最大。

二、问题标准化描述

为了得到上一小节中提到的最大边界间隔的超平面，可以将问题形式化为如下的优化问题，其中margin(b, w)表示超平面wx + b离样本点的最小距离，而优化问题的目标则是让这个最小距离最大化：

为了进一步简化这个问题，考虑到w和b同时成倍的放缩不会影响超平面位置的变化，所以总可以找到一组w*和b*，使得min y(w*x+b*) = 1，那么有：

进一步地，为了简化最优化约束中的最小化条件，我们来证明一下是否能够转化为不等式的形式。假设转换后得到的解中最小的y(wx + b)不再=1，而是一个比1大的数，显然我们可以通过同时放缩w，b得到一个更优化的解，因此约束条件中最小化的等式与下图中的不等式是等价的。那么最后的最后，就简化成为了如下图的优化问题。

三、支持向量机

SVM其实就是一种找出上述优化问题中最大边界间隔的超平面的方法。那如何解这个优化问题呢，幸运的是，这个问题形式和二次规划(线性规划的进阶版)一致，因此只要将我们的优化问题表示成为二次规划的标准形式，然后就可以使用二次规划的方法求解。二次规划的一般形式如下：

那么只要将我们的优化问题表示为上述的二次规划的一般形式，找出其中变量Q，p，A，c分别的映射关系即可，如下图所示。接下来就可以通过任何实现QP解法的工具计算求解。

这里解的优化问题严格来说叫做Linear Hard-Margin SVM Algorithm，Hard-Margin代表训练数据一定线性可分；Linear则表示我们寻找的超平面是原来空间的x，对于非线性问题，可以通过对x做二次转化或其他转化，然后求解。

四、SVM可行的理论依据

之前我们提到一个形象化的解释是SVM对噪声的容忍性更强。那么从VC bound的角度来说（超平面到底能够产生多少圈圈叉叉分类的组合），例如对于PLA来说，可以shatter三个训练点的所有可能组合（8种，下图仅画出4种）；但是对于SVM来说，会对margin有所限制，那么就有可能无法做出所有的排列组合了，因为对margin的宽度有要求。

linear hard SVM不能shatter任意3个inputs，这说明有更少的dichotomies，更小的VC维度，也就有更好的泛化效果（E_in与E_out更接近）。同时，如果使用特征转换，可以使linear hard SVM进行一些更精细的分类。

Linear Hard SVM的解法中需要训练数据线性可分，然后通过缩放平面和等价转换，将原始问题转成QP问题求解。数据线性可分在实际情况中很难出现，所以linear hard SVM的应用价值比较有限。同时，在特征转换时，将原始数据映射到其他空间的计算复杂度在很大情况下也很大。

第2讲-------Dual Support Vector Machine

一、拉格朗日乘子

上一讲中讲了Linear SVM的模型，我们讲述了如何用QP的方法来寻找出最大间隔的超平面的问题。这一讲中我们把同样的问题转换成另外的一种形式，以求将其更容易地延伸到各式各样不同的应用中去。

线性约束很烦，不方便优化，是否有一种方法可以将线性约束放到优化问题本身，这样就可以无拘无束的优化，而不用考虑线性约束了。这里用到的基本工具在机器学习基石课程中讲解Regularization时已经讲到了，通过拉格朗日算子可以将约束条件加入到目标方程中。

类似地，引入拉格朗日算子，将如下图中左边原来有约束条件的优化问题转换为右边的看似没有约束条件的问题。

见证奇迹的时刻到了：针对无约束的拉格朗日目标函数进行如下的优化后得到的结果与原来的SVM的解是一致的。其实，仔细分析起来也不难证明。

• 对于坏的解b和w，也就是至少违反了某一个约束条件，那么1 - y_n(w^T*z_n + b) 肯定会 > 0，乘上一个同样大于0的alpha，对其求解max肯定会得到正无穷；
• 对于可行的解b和w，符合所有的约束条件，那么所有的1 - y_n(w^T*z_n + b)都会为负，对其求解max时所有的alpha为0即可；
• 最后，通过min淘汰不符合约束条件的解，并且在所有符合约束条件的解中选取最大边界间隔的超平面作为最终的解，因此约束条件现在已经包含在了max中。

最后，奉上一道练习题，拉格朗日做的事情就是将原来我们想要最小化的事情以及各个约束条件通通都加起来：

二、SVM的拉格朗日对偶形式

经过上一小节对SVM问题的转换，min(max)的形式仍然不方便求解。不过可以经过一系列的变换得到其与对偶形式max(min)的关系，最大值中的最小值显然要大于等于最小值中的最大值：

右边的形式通常叫做拉格朗日对偶问题，这里大于等于的关系告诉我们：如果拉格朗日对偶问题解决了，我们就得到原来SVM问题中解的下限，不完全是原来问题的解但是能够知道原来问题至少能做到多好的程度。

在最佳化问题中，大于等于的关系被称为弱对偶。实际上，对于这里的二次规划问题，等于=的强对偶问题满足如下的条件时会成立。

• 原始问题是凸问题
• 原始问题线性可分
• 约束条件是线性的

很幸运的，上面的三个条件对于原始的SVM问题都是满足的。因此，接下来我们详细来看一下如何求解原始SVM的拉格朗日对偶问题。

对于里面的min问题是没有条件的最佳化问题，那么对变量的微分应该要等于0的结果。首先对b进行微分，得到如下图的结果。

那么，将这个结果带入到原来问题中，可以化简消去b的部分得到如下的问题。进一步地，对w进行微分，可以得到如下的结果。

同样地，把这个结果带入到目标函数中，化简可以得到如下的形式。因为带入后的结果已经不包含w和b了，因此可以去掉min这个优化符号了。

执行到这里，现在目标函数只与alpha有关，形式满足QP，可以轻易得到最优化的alpha，也就是得到w。

现在只剩下最后一个问题，如何计算b? 在之前的简化过程中消去了b，上面的QP解与b无关。KKT条件帮助我们解决这个问题。如果原始问题和对偶问题都有最优解，且解相同，那么会满足KKT条件，这也是一个充分必要条件。第一：需要满足原始问题的条件，这个理所当然这样才是左边问题的可行解；第二：需要满足对偶问题的条件；第三：需要满足对偶问题最佳化理念也就是分别对w和b微分的结果；第四：需要满足原始问题做最佳化的理念，如果不违反原始问题的约束条件，最佳化的时候会让alpha为0，也就是满足条件的w和b，alpha要满足如下乘积为0的条件。最后一点也是最重要的一点，通常称为complementary slackness (互补松弛性)。

所以，根据KKT条件中的互补松弛性，alpha与原始问题的约束条件等式两者有一个不为0时，另外一个必然为0。所以，只要找到一个alpha不为0，则包含w与b的等式一定为0，于是就可以利用这个性质计算出b，实际操作中为了减少误差可能会计算所有的b然后求平均得到。并且值得注意的是，alpha > 0时，这些可以计算出b的点，满足了原始问题中关于支持向量的定义，那么这些点都是支持向量。接下来针对KKT问题看一下如下的练习题，稍微分析一下便知正确答案为4，值得注意的是第二个选项的推导。

三、SVM对偶形式的求解

针对上一小结推导出的SVM对偶问题进行一下调整，可以得到SVM对偶问题的标准形式，如下图所示。总共有N个alpha的变量，每个alpha有一个条件，所有的alpha合在一起有一个条件，因此总共是N个变量和N+1个约束条件。我们大费周章地把原来SVM的QP问题转化成为一个相对应的QP问题。

那么如何求解这个QP问题呢？之前已经讲到过只要按照QP求解程序给定正确的参数Q, p, A, c就可以了，具体到这里如下图所示。值得注意的是，QP的标准形式是大于等于的形式而左边的条件是等号的形式，因此等号的条件拆解为同时满足大于等于与小于等于的两个条件。实际上，很多QP程序可以直接表示等式或者可以指定条件的上限或者下限bound，因此可能不需要针对等号作拆解这么复杂的操作。

看起来好像蛮轻松，实际则不然。Q是一个N×N的矩阵，而且Q不是稀疏矩阵，假设有N=3w笔训练资料那么Q都需要花费超过3G的存储空间。看起来好像没有原来的SVM问题那么好求解，对于原始的SVM问题因为Q的形式十分简单只有在对角线的位置才有值。因此这里不太能使用一般的QP程序来求解，往往都需要特别为SVM设计的QP程序。一方面不把整个Q矩阵存下来，需要用到某个元素的时候再计算；另一方面，利用SVM特殊的条件来加速QP问题的求解。

四、SVM对偶问题背后的哲学

一般情况下，我们将解完SVM对偶问题后alpha > 0 的点称为支撑向量，这些点肯定是在最大间隔的边界上的。对于在最大间隔边界上但是alpha为0的点，则称之为候选支撑向量support vector candidate。支撑向量有什么重要的呢？计算w，b都只需要支撑向量就够了。因此可以将SVM看成是一种通过对偶问题找到支撑向量来学习出最大间隔的边界超平面的一种机制。

通过上面我们知道，SVM中w的计算其实是yz对于alpha的线性组合，alpha由对偶问题得到。其实我们早就看过这件事了，PLA针对w的更新也是类似的机制。同理，逻辑回归，线性回归最后得到的关于w的解都会是原始资料的线性组合，称为w可以通过数据表示出来。SVM神奇的地方在于只需要训练数据中的支撑向量即可表示出来，PLA则使用犯错的点表现出来。

总结一下，这两讲讲了两种SVM的解法，原始问题与对偶问题。原始SVM中变量的个数与映射到哪一个空间有关，如果d_telta很大甚至无穷的话就不好求解，通过一定的自由放缩来优化求解b和w；SVM对偶问题变量的个数就是训练数据的数量N，通过找出支撑向量和相对应的alpha来求解b和w。

那这样就够了吗？还记得我们最初延伸出对偶问题的初衷吗，我们想要求解SVM但是计算复杂度不想与d_telta有关系，因为d_telta可能为无穷大。看起来SVM的对偶问题只与N有关系，实际上不然，d_telta隐藏在了计算Q矩阵的地方，计算Q中每个元素的时候有两个z向量的内积，而z向量的长度就是d_telta。因此接下来的问题是如何避开Q矩阵中这一步的计算，且听下回分解。

关于Machine Learning Techniques更多的学习资料将继续更新，敬请关注本博客和新浪微博Sheridan。

原创文章如转载，请注明本文链接: http://imsheridan.com/mlt_1st_lecture.html