机器学习技法

机器学习技法第1讲支持向量机SVM在机器学习基石介绍的基本工具（主要围绕特征转换FeatureTransform）的基础上，延伸成为复杂而实用的模型。1)一方面，如何更好地运用现有的features以及控制复杂度的问题，产生了SVM（支持向量机）模型；2)再者，如何构造或者结合出一些具有预测性的feature让整个模型有更好的表现，产生了AdaBoost（逐步增强法）模型；3)另外，如何学习出隐含的features，这样的想法刺激了早年的神经网络近年发展成为DeepLearning的模型。1最大边界间隔超平面在Perceptron中，针对如下图所示线性可分的训练数据，有可能会得到左/中/右这样的三条分隔线，而且Perceptron无法确定这三条线哪一条更好。凭直觉而言，最右边是最好的，因为其对噪声的容忍度最高。从点的角度来看，测试模型的时候由于测量误差或者收集的条件不同，即便应该与训练数据一模一样的数据在收集时也可能出现误差，图中圆形区域为噪声，区域越大表示能够容忍的噪声越大；另一方面，从线的角度来看，超平面分别向正负样本方向扩展到最近的正负样本得到的间隔，代表了超平面的鲁棒性，最右边的线得到的间隔也最大。图都线性可分,那么那条直线是最好的2问题标准化描述为了得到上一小节中提到的最大边界间隔的超平面，可以将问题形式化为如下的优化问题，其中margin(b,w)表示超平面wx+b离样本点的最小距离，而优化问题的目标则是让这个最小距离最大化：图问题的描述图X/W的定义问题来了,如何描述距离呢?图距离的描述,图中灰色代表超平面,x’和x’’是平面的两个向量，经过推导知w即为超平面的法向量图距离推导过程推导的结果是：问题转化为：为了进一步简化这个问题，考虑到w和b同时成倍的放缩不会影响超平面位置的变化，所以总可以找到一组w*和b*，使得miny(w*x+b*)=1，那么有：进一步地，为了简化最优化约束中的最小化条件，我们来证明一下是否能够转化为不等式的形式。假设转换后得到的解中最小的y(wx+b)不再=1，而是一个比1大的数，显然我们可以通过同时放缩w，b得到一个更优化的解，因此约束条件中最小化的等式与下图中的不等式是等价的。那么最后的最后，就简化成为了如下图的优化问题。3支持向量机SVM其实就是一种找出上述优化问题中最大边界间隔的超平面的方法。那如何解这个优化问题呢，幸运的是，这个问题形式和二次规划(线性规划的进阶版)一致，因此只要将我们的优化问题表示成为二次规划的标准形式，然后就可以使用二次规划的方法求解。二次规划的一般形式如下：图二次规划问题的标准形式QuadraticProgramming那么只要将我们的优化问题表示为上述的二次规划的一般形式，找出其中变量Q，p，A，c分别的映射关系即可，如下图所示。接下来就可以通过任何实现QP解法的工具计算求解。经过对比，不难得出相应参数：这里解的优化问题严格来说叫做LinearHard-MarginSVMAlgorithm，Hard-Margin代表训练数据一定线性可分；Linear则表示我们寻找的超平面是原来空间的x，对于非线性问题，可以通过对x做二次转化或其他转化，然后求解。4SVM可行的理论依据之前我们提到一个形象化的解释是SVM对噪声的容忍性更强。那么从VCbound的角度来说（超平面到底能够产生多少圈圈叉叉分类的组合），例如对于PLA来说，可以shatter三个训练点的所有可能组合（8种，下图仅画出4种）；但是对于SVM来说，会对margin有所限制，那么就有可能无法做出所有的排列组合了，因为对margin的宽度有要求。linearhardSVM不能shatter任意3个inputs，这说明有更少的dichotomies，更小的VC维度，也就有更好的泛化效果（E_in与E_out更接近）。同时，如果使用特征转换，可以使linearhardSVM进行一些更精细的分类。总结：LinearHardSVM的解法中需要训练数据线性可分，然后通过缩放平面和等价转换，将原始问题转成QP问题求解。数据线性可分在实际情况中很难出现，所以linearhardSVM的应用价值比较有限。同时，在特征转换时，将原始数据映射到其他空间的计算复杂度在很大情况下也很大。第2讲DualSupportVectorMachine1拉格朗日乘子上一讲中讲了LinearSVM的模型，我们讲述了如何用QP的方法来寻找出最大间隔的超平面的问题。这一讲中我们把同样的问题转换成另外的一种形式，以求将其更容易地延伸到各式各样不同的应用中去。线性约束很烦，不方便优化，是否有一种方法可以将线性约束放到优化问题本身，这样就可以无拘无束的优化，而不用考虑线性约束了。这里用到的基本工具在机器学习基石课程中讲解Regularization时已经讲到了，通过拉格朗日算子可以将约束条件加入到目标方程中。将之前SVM有约束问题，转化为无约束问题，如右图所示：经过引入拉格朗日乘子后，原来的优化问题可以写成下面的等效形式：见证奇迹的时刻到了：针对无约束的拉格朗日目标函数进行如上图的优化后得到的结果与原来的SVM的解是一致的。为什么呢？分析如下：a)对于坏的解b和w，也就是至少违反了某一个约束条件，那么1-y_n(w^T*z_n+b)肯定会0，乘上一个同样大于0的alpha，对其求解max肯定会得到正无穷；b)对于可行的解b和w，符合所有的约束条件，那么所有的1-y_n(w^T*z_n+b)都会为负，对其求解max时所有的alpha为0即可；c)最后，通过min淘汰不符合约束条件的解，并且在所有符合约束条件的解中选取最大边界间隔的超平面作为最终的解，因此约束条件现在已经包含在了max中。2SVM的拉格朗日对偶形式经过上一小节对SVM问题的转换，min(max)的形式仍然不方便求解。不过可以经过一系列的变换得到其与对偶形式max(min)的关系，最大值中的最小值显然要大于等于最小值中的最大值：右边的形式通常叫做拉格朗日对偶问题，这里大于等于的关系告诉我们：如果拉格朗日对偶问题解决了，我们就得到原来SVM问题中解的下限，不完全是原来问题的解但是能够知道原来问题至少能做到多好的程度。在最佳化问题中，大于等于的关系被称为弱对偶。实际上，对于这里的二次规划问题，等于=的强对偶问题满足如下的条件时会成立。原始问题是凸问题原始问题线性可分约束条件是线性的很幸运的，上面的三个条件对于原始的SVM问题都是满足的。因此，接下来我们详细来看一下如何求解原始SVM的拉格朗日对偶问题。对于里面的min问题是没有条件的最佳化问题，那么对变量的微分应该要等于0的结果。首先对b进行微分，得到如下图的结果。可见如果达到最优，必须满足上面的条件，那么不妨把这个条件代入原式，应该不影响最优解：简化为后成为：接着对W进行微分：对于后面约束项展开：∑(())∑∑∑代入⇒∑于是得到：执行到这里，现在目标函数只与alpha有关，形式满足QP，可以轻易得到最优化的alpha，也就是得到w。现在只剩下最后一个问题，如何计算b?在之前的简化过程中消去了b，上面的QP解与b无关。KKT条件帮助我们解决这个问题。如果原始问题和对偶问题都有最优解，且解相同，那么会满足KKT条件，这也是一个充分必要条件。第一：需要满足原始问题的条件，这个理所当然这样才是左边问题的可行解；第二：需要满足对偶问题的条件；第三：需要满足对偶问题最佳化理念也就是分别对w和b微分的结果；第四：需要满足原始问题做最佳化的理念，如果不违反原始问题的约束条件，最佳化的时候会让alpha为0，也就是满足条件的w和b，alpha要满足如下乘积为0的条件。最后一点也是最重要的一点，通常称为complementaryslackness(互补松弛性)。所以，根据KKT条件中的互补松弛性，alpha与原始问题的约束条件等式两者有一个不为0时，另外一个必然为0。所以，只要找到一个alpha不为0，则包含w与b的等式一定为0，于是就可以利用这个性质计算出b，实际操作中为了减少误差可能会计算所有的b然后求平均得到。并且值得注意的是，alpha0时，这些可以计算出b的点，满足了原始问题中关于支持向量的定义，那么这些点都是支持向量。3SVM对偶形式的求解针对上一小结推导出的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问题的求解。4SVM对偶问题背后的哲学一般情况下，我们将解完SVM对偶问题后alpha0的点称为支撑向量，这些点肯定是在最大间隔的边界上的。对于在最大间隔边界上但是alpha为0的点，则称之为候选支撑向量supportvectorcandidate。支撑向量有什么重要的呢？计算w，b都只需要支撑向量就够了。因此可以将SVM看成是一种通过对偶问题找到支撑向量来学习出最大间隔的边界超平面的一种机制。通过上面我们知道，SVM中w的计算其实是yz对于alpha的线性组合，alpha由对偶问题得到。其实我们早就看过这件事了，PLA针对w的更新也是类似的机制。同理，逻辑回归，线性回归最后得到的关于w的解都会是原始资料的线性组合，称为w可以通过数据表示出来。SVM神奇的地方在于只需要训练数据中的支撑向量即可表示出来，PLA则使用犯错的点表现出来。图w的数据表示总结:还记得我们最初延伸出对偶问题的初衷吗，我们想要求解SVM但是计算复杂度不想与d_telta有关系，因为d_telta可能为无穷大。看起来SVM的对偶问题只与N有关系，实际上不然，d_telta隐藏在了计算Q矩阵的地方，计算Q中每个元素的时候有两个z向量的内积，而z向量的长度就是d_telta。因此接下来的问题是如何避开Q矩阵中这一步的计算。第3讲KernelSupportVectorMachine上一讲中我们将对偶SVM问题转换成了一个标准的二次规划问题，似乎问题变得简单了，但是我们需要计算Q，Q中的每一项涉及z向量的内积，由于特征变换，z空间维度可能很大，有没有一个办法解决这个问题呢？这里用到核技巧。1KernalTrick回忆之前的求解：我们真的可以这样做吗？事实上不可以。因为先转换到z空间，然后再做内积，耗费很大。那我们自然而然的想法是：能不能两步同时完成，省去中间的环节。下面考虑一个2阶的多项式变换：在z空间做内积：可见，结果只需要计算在x空间两个向量内积，算量减少了。我们将这个结果定义为核函数：对于之前的对偶SVM问题的QP用核函数替换，如下：经过替换后的方法我们称为核支持向量机，算法的计算过程如下：总结如下：第一步，计算Q矩阵；第二步，通过Qp求解器，得到系数α；第三步，求解b，根据∑()的下标索引withSV(),这里只需要一个支持向量就能计算b，也可以用多个支持向量求平均值；第四步，返回支持向量机模型，用于预测，x是输入测试样本；()(∑()的下标索引)2通用二次多项式