机器学习技法

1、机器学习技法第1讲 支持向量机SVM在机器学习基石介绍的基本工具（主要围绕特征转换Feature Transform）的基础上，延伸成为复杂而实用的模型。1) 一方面，如何更好地运用现有的features以及控制复杂度的问题，产生了SVM（支持向量机）模型；2) 再者，如何构造或者结合出一些具有预测性的feature让整个模型有更好的表现，产生了AdaBoost（逐步增强法）模型；3) 另外，如何学习出隐含的features，这样的想法刺激了早年的神经网络近年发展成为Deep Learning的模型。1 最大边界间隔超平面在Perceptron中，针对如下图所示线性可分的训练数据，有可能会得到

2、左/中/右这样的三条分隔线，而且Perceptron无法确定这三条线哪一条更好。凭直觉而言，最右边是最好的，因为其对噪声的容忍度最高。从点的角度来看，测试模型的时候由于测量误差或者收集的条件不同，即便应该与训练数据一模一样的数据在收集时也可能出现误差，图中圆形区域为噪声，区域越大表示能够容忍的噪声越大；另一方面，从线的角度来看，超平面分别向正负样本方向扩展到最近的正负样本得到的间隔，代表了超平面的鲁棒性，最右边的线得到的间隔也最大。图 都线性可分,那么那条直线是最好的2问题标准化描述为了得到上一小节中提到的最大边界间隔的超平面，可以将问题形式化为如下的优化问题，其中margin(b, w)表示

3、超平面wx + b离样本点的最小距离，而优化问题的目标则是让这个最小距离最大化：图 问题的描述图 X/W的定义问题来了,如何描述距离呢?图 距离的描述,图中灰色代表超平面,x和x是平面的两个向量，经过推导知w即为超平面的法向量图 距离推导过程推导的结果是：问题转化为：为了进一步简化这个问题，考虑到w和b同时成倍的放缩不会影响超平面位置的变化，所以总可以找到一组w*和b*，使得min y(w*x+b*) = 1，那么有：进一步地，为了简化最优化约束中的最小化条件，我们来证明一下是否能够转化为不等式的形式。假设转换后得到的解中最小的y(wx + b)不再=1，而是一个比1大的数，显然我们可以通过同

4、时放缩w，b得到一个更优化的解，因此约束条件中最小化的等式与下图中的不等式是等价的。那么最后的最后，就简化成为了如下图的优化问题。3支持向量机SVM其实就是一种找出上述优化问题中最大边界间隔的超平面的方法。那如何解这个优化问题呢，幸运的是，这个问题形式和二次规划(线性规划的进阶版)一致，因此只要将我们的优化问题表示成为二次规划的标准形式，然后就可以使用二次规划的方法求解。二次规划的一般形式如下：图 二次规划问题的标准形式Quadratic Programming那么只要将我们的优化问题表示为上述的二次规划的一般形式，找出其中变量Q，p，A，c分别的映射关系即可，如下图所示。接下来就可以通过任何

5、实现QP解法的工具计算求解。经过对比，不难得出相应参数：这里解的优化问题严格来说叫做Linear Hard-Margin SVM Algorithm，Hard-Margin代表训练数据一定线性可分；Linear则表示我们寻找的超平面是原来空间的x，对于非线性问题，可以通过对x做二次转化或其他转化，然后求解。4 SVM可行的理论依据之前我们提到一个形象化的解释是SVM对噪声的容忍性更强。那么从VC bound的角度来说（超平面到底能够产生多少圈圈叉叉分类的组合），例如对于PLA来说，可以shatter三个训练点的所有可能组合（8种，下图仅画出4种）；但是对于SVM来说，会对margin有所限制，

6、那么就有可能无法做出所有的排列组合了，因为对margin的宽度有要求。linear hard SVM不能shatter任意3个inputs，这说明有更少的dichotomies，更小的VC维度，也就有更好的泛化效果（E_in与E_out更接近）。同时，如果使用特征转换，可以使linear hard SVM进行一些更精细的分类。总结：Linear Hard SVM的解法中需要训练数据线性可分，然后通过缩放平面和等价转换，将原始问题转成QP问题求解。数据线性可分在实际情况中很难出现，所以linear hard SVM的应用价值比较有限。同时，在特征转换时，将原始数据映射到其他空间的计算复杂度在很大

7、情况下也很大。第2讲 Dual Support Vector Machine1 拉格朗日乘子上一讲中讲了Linear SVM的模型，我们讲述了如何用QP的方法来寻找出最大间隔的超平面的问题。这一讲中我们把同样的问题转换成另外的一种形式，以求将其更容易地延伸到各式各样不同的应用中去。线性约束很烦，不方便优化，是否有一种方法可以将线性约束放到优化问题本身，这样就可以无拘无束的优化，而不用考虑线性约束了。这里用到的基本工具在机器学习基石课程中讲解Regularization时已经讲到了，通过拉格朗日算子可以将约束条件加入到目标方程中。将之前SVM有约束问题，转化为无约束问题，如右图所示：经过引入拉格

8、朗日乘子后，原来的优化问题可以写成下面的等效形式：见证奇迹的时刻到了：针对无约束的拉格朗日目标函数进行如上图的优化后得到的结果与原来的SVM的解是一致的。为什么呢？分析如下：a) 对于坏的解b和w，也就是至少违反了某一个约束条件，那么1 - y_n(wT*z_n + b) 肯定会 0，乘上一个同样大于0的alpha，对其求解max肯定会得到正无穷；b) 对于可行的解b和w，符合所有的约束条件，那么所有的1 - y_n(wT*z_n + b)都会为负，对其求解max时所有的alpha为0即可；c) 最后，通过min淘汰不符合约束条件的解，并且在所有符合约束条件的解中选取最大边界间隔的超平面作为最

9、终的解，因此约束条件现在已经包含在了max中。2 SVM的拉格朗日对偶形式经过上一小节对SVM问题的转换，min(max)的形式仍然不方便求解。不过可以经过一系列的变换得到其与对偶形式max(min)的关系，最大值中的最小值显然要大于等于最小值中的最大值：右边的形式通常叫做拉格朗日对偶问题，这里大于等于的关系告诉我们：如果拉格朗日对偶问题解决了，我们就得到原来SVM问题中解的下限，不完全是原来问题的解但是能够知道原来问题至少能做到多好的程度。在最佳化问题中，大于等于的关系被称为弱对偶。实际上，对于这里的二次规划问题，等于=的强对偶问题满足如下的条件时会成立。 原始问题是凸问题 原始问题线性可分

10、 约束条件是线性的很幸运的，上面的三个条件对于原始的SVM问题都是满足的。因此，接下来我们详细来看一下如何求解原始SVM的拉格朗日对偶问题。对于里面的min问题是没有条件的最佳化问题，那么对变量的微分应该要等于0的结果。首先对b进行微分，得到如下图的结果。可见如果达到最优，必须满足上面的条件，那么不妨把这个条件代入原式，应该不影响最优解：简化为后成为：接着对W进行微分：对于后面约束项展开：n=1Nn1-ynwTzn=n=1Nn-wTn=1Nnynznw=n=1Nnynzn代入n=1Nn-wTw于是得到：执行到这里，现在目标函数只与alpha有关，形式满足QP，可以轻易得到最优化的alpha，也

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

12、ry slackness (互补松弛性)。所以，根据KKT条件中的互补松弛性，alpha与原始问题的约束条件等式两者有一个不为0时，另外一个必然为0。所以，只要找到一个alpha不为0，则包含w与b的等式一定为0，于是就可以利用这个性质计算出b，实际操作中为了减少误差可能会计算所有的b然后求平均得到。并且值得注意的是，alpha 0时，这些可以计算出b的点，满足了原始问题中关于支持向量的定义，那么这些点都是支持向量。3 SVM对偶形式的求解针对上一小结推导出的SVM对偶问题进行一下调整，可以得到SVM对偶问题的标准形式，如下图所示。总共有N个alpha的变量，每个alpha有一个条件，所有的a

13、lpha合在一起有一个条件，因此总共是N个变量和N+1个约束条件。我们大费周章地把原来SVM的QP问题转化成为一个相对应的QP问题。那么如何求解这个QP问题呢？之前已经讲到过只要按照QP求解程序给定正确的参数Q, p, A, c就可以了，具体到这里如下图所示。值得注意的是，QP的标准形式是大于等于的形式而左边的条件是等号的形式，因此等号的条件拆解为同时满足大于等于与小于等于的两个条件。实际上，很多QP程序可以直接表示等式或者可以指定条件的上限或者下限bound，因此可能不需要针对等号作拆解这么复杂的操作。看起来好像蛮轻松，实际则不然。Q是一个NN的矩阵，而且Q不是稀疏矩阵，假设有N=3w笔训练

14、资料那么Q都需要花费超过3G的存储空间。看起来好像没有原来的SVM问题那么好求解，对于原始的SVM问题因为Q的形式十分简单只有在对角线的位置才有值。因此这里不太能使用一般的QP程序来求解，往往都需要特别为SVM设计的QP程序。一方面不把整个Q矩阵存下来，需要用到某个元素的时候再计算；另一方面，利用SVM特殊的条件来加速QP问题的求解。4 SVM对偶问题背后的哲学一般情况下，我们将解完SVM对偶问题后alpha 0 的点称为支撑向量，这些点肯定是在最大间隔的边界上的。对于在最大间隔边界上但是alpha为0的点，则称之为候选支撑向量support vector candidate。支撑向量有什么重

15、要的呢？计算w，b都只需要支撑向量就够了。因此可以将SVM看成是一种通过对偶问题找到支撑向量来学习出最大间隔的边界超平面的一种机制。通过上面我们知道，SVM中w的计算其实是yz对于alpha的线性组合，alpha由对偶问题得到。其实我们早就看过这件事了，PLA针对w的更新也是类似的机制。同理，逻辑回归，线性回归最后得到的关于w的解都会是原始资料的线性组合，称为w可以通过数据表示出来。SVM神奇的地方在于只需要训练数据中的支撑向量即可表示出来，PLA则使用犯错的点表现出来。图 w的数据表示总结: 还记得我们最初延伸出对偶问题的初衷吗，我们想要求解SVM但是计算复杂度不想与d_telta有关系，因

16、为d_telta可能为无穷大。看起来SVM的对偶问题只与N有关系，实际上不然，d_telta隐藏在了计算Q矩阵的地方，计算Q中每个元素的时候有两个z向量的内积，而z向量的长度就是d_telta。因此接下来的问题是如何避开Q矩阵中这一步的计算。第3讲 Kernel Support Vector Machine上一讲中我们将对偶SVM问题转换成了一个标准的二次规划问题，似乎问题变得简单了，但是我们需要计算Q，Q中的每一项涉及z向量的内积，由于特征变换，z空间维度可能很大，有没有一个办法解决这个问题呢？这里用到核技巧。1 Kernal Trick回忆之前的求解：我们真的可以这样做吗？事实上不可以。因

17、为先转换到z空间，然后再做内积，耗费很大。那我们自然而然的想法是：能不能两步同时完成，省去中间的环节。下面考虑一个2阶的多项式变换：在z空间做内积：可见，结果只需要计算在x空间两个向量内积，算量减少了。我们将这个结果定义为核函数：对于之前的对偶SVM问题的QP用核函数替换，如下：经过替换后的方法我们称为核支持向量机，算法的计算过程如下：总结如下：第一步，计算Q矩阵；第二步，通过Qp求解器，得到系数；第三步，求解b，根据b=ys-SV的下标索引nnynK(xn,xs) with SV (xS,ys),这里只需要一个支持向量就能计算b，也可以用多个支持向量求平均值；第四步，返回支持向量机模型，用于

18、预测，x是输入测试样本；gsvm(x)=signSV的下标索引nnynKxn,x+b2 通用二次多项式核可见,对于特征变换我们加上一个系数,可能会得到更简单的形式,但是z空间不变，即他们的表达能力不变，为了得到更一般的形式，在一次项前面加上2，在二次项前面乘上2，就到了一般形式的二次多项式核：K2x,x=1+2xTx+2(xTx)2=1+xTx2, 0这样的转换有什么区别，或者说有什么好处？1）更容易计算，2）具有相同的能力，3）由于内积不容，可能有不同的几何特性。作为一个参数，它的大小会对分类边界产生什么影响呢？看看下面不同的情况：图 对分类边界的影响可见，越大，边界越复杂，支持向量也会发生

19、变化。一般来说，取值不易过大，具体问题，具体对待。将多项式核推广到更一般的情况，主要有两方面：1）常数项用参数替代，2）不仅仅局限于二阶的，推广到高阶的情况。于是得到不同的多项式核。Figure 10-th order polynomial with margin 0:1如上图，当用到10阶多项式核时，边界曲线可以很复杂。说明表达能力很强。并且这个计算完全不受限于z空间的VC维。我们把SVM+多项式核称为多项式SVM。3 高斯核我们有了多项式核，这些核其实都是特征变换到一个有限维度的z空间上，然后做内积。如果分两步求解我们是不可能处理无限维度的计算的，现在我们有了核的概念，直接通过原来空间计算

20、内积，而不需要z空间，此时我们是否能处理无限维的情况呢？高斯核提供了这种可能。如上面的推导过程，高斯核定义为：Kx,x=e-x-x2最终我们得到了Kx,x可以写成x的内积的形式，说明了它是一个核，x的表达式是无限维的，说明z空间是无限维的，因此我们得到了一个无限维的核，由于这个核函数是高斯函数的形式，我们称之为高斯核，有的地方也叫RBF核。更一般的高斯核函数形式：用高斯核推导SVM得：高斯核的选择不同，同样也会影响边界。一般来说，越大意味着高斯函数越瘦，可能会导致过拟合。4 各种核的比较线性kernel不做feature转换，直接使用。不需要使用对偶技巧，直接使用linear hard SVM

21、解。优点：计算效率高；结果解释性好。缺点：需要数据线性可分多项式核对x进行多项式展开，一般的形式为其中a，b，Q为常量。优点：相比线性kernel，对数据要求没有那么严格缺点：需要选择的系数较多；Q太大会超出一些计算机的精度，一般Q0)是常量。高斯kernel厉害的地方是可以将原始数据x映射到无线维度空间中，x下面取a=1的例子上面的变化采用了Taylor展开，接着其中特征转化为这样，就完成了向无线维度转换，RBF是不是很厉害！优点：调试的系数较少；比线性和多项式更强大，几乎可以适应所有数据；不容易出现计算精度问题缺点：无线维度无法解释；太强大，容易过拟合；计算开销大。上面讲了几种常用的核函数

22、，可见核函数需要具备一定的特性才能成为核函数。necessary & sufficient conditions for valid kernel:Mercers condition：两个条件：1) 对称性；2) 构成的矩阵半正定。第4讲 Soft-Margin Support Vector Machine1 Motivation and Primal Problems之前推导的Kernal SVM算法带来了很多好处，但是存在过拟合问题。分析这个问题产生的原因有2个：1) 核函数表达能力太强，too powerful2) 我们坚持要求每个样本点都要分对，不允许有错误，这样一些噪音样本会导致过拟

23、合。如上图，虽然第一个分类有某些点分类错误，但直觉上我们认为这是一种更合理的方式，而第二个图坚持分类正确，但是边界太复杂。如和解决这个问题，自然而然的想法是容许一些错误，也就是我们放弃一些噪音点。寻找一个次优解。以前是怎么解决的。回想PLA算法，当数据线性不可分的时候，我们有Pocket PLA算法，寻求误差最小的解。将这个思想和hard SVM结合起来，或许就能解决这个问题。可见最小化目标变成了2项，第一项是力求margin最大化，第二项是我们犯错的大小，C这是权衡二者的权重。C很大，最小化的话第二项必须很小，说明我们力求少犯错，反之，这是力求margin最大。注意在条件中我们把样本分成了两

24、部分。正确的和不正确的。为了方便我们将上面的最优化问题换个表达方式，如下：我们称这样的模型为：soft SVM。观察上面的模型，它是非线性的，也不是一个Qp问题，没办法求解。还有一个问题是，对于犯错误的我们就定义误差为1，否则为0，不能表达误差的大小。比如举例margin越近的误差值应该越小，反之越大。于是我们引入一个新的变量n表示第n个样本引入的误差，替换掉原来error count的方式。于是Soft SVM为题变为：这样就变成了一个含有二次项和线性项的二次目标。2 Dual Problem为了消除最优化问题对于d的依赖，回想以前是怎么做的，没错通过朗格朗日乘子引出对偶问题。不同的是，这里

25、约束表达式有2个，所以有2个乘子，分别是n和n.转化后的等价问题是：为了简化n和n ，推导如下：简化后为题变为：这个表达式我们很熟悉，没错，就是前面的Hard SVM，用和前面相同的推导有：将这些条件代入就得到了标准的Soft SVM Dual:唯一不同的是n的上限为C，因为n+n=C,并且n0，n0，很容易得到n的范围是：0nC。3 Kernel Soft-Margin SVM引入Kernal并运用二次规划问题得到Kernel Soft-Margin SVM的算法步骤如下：基本上和Hard SVM相同，注意还有第三步没有解决，之前我们求解b是根据互补松弛性，推出只需要一个SVs就可以计算出b

26、。可见对于s0的支持向量，推出b=ys-yss-wTzs。里面含有s我们不知道，似乎只有知道b才能知道s。这好像成了一个鸡生蛋和蛋生鸡的问题。注意还有个条件C-ns=0，所以当Cn时s=0，那么b=ys-wTzs。Soft-Margin Gaussian SVM的实例：n的物理意义：我们通过n把所有向量分为3部分：1) 不是支持向量，图中的和，对应于n=0；2) Free SV，这些向量处于margin的边界上，图中用表示，对应0n0，如果WSVM比较合理；B=0，如果bsvm取到比较好的值。新的回归问题变为：注意上面的式子中，先用了SVM得到w和b，其实这一步可以看成是一个特征转换，把x多维

27、的情况转换成z空间一维的情况，然后再用LogReg。如何求解上面的问题？Platts Model of Probabilistic SVM for Soft Binary Classification可以总结为下面步骤：总结如下：1) 运行SVM算法得到w和b，或者等价的得到，然后利用得到的SVM模型进行特征转换；2) 在转换的z空间上用LogReg得到参数A、B；3) 返回g(x)。4 Kernal Logistics Regression之前讲的把svm用于Logistics Regression，其实是先用SVM进行特征变换，然后在变换后的空间使用LogReg，那么能不能直接在z空间做变

28、换，而省去SVM的步骤呢？回想前面的怎么直接在z空间做变换，可以想到的是用kernal，什么情况下才能使用kernal技巧呢？可见要用kernal需要在z空间做内积，怎么能在z空间形成内积，那就是我们的最优的w能够表示成z的线性组合。如上面所示。问题是什么情况下我们的最优化的解是z的线性组合呢？定理证明了：对于任何L2-regularized linear model问题最优解是z的组合。怎么理解这个定理呢？思路是：问题是要把w表示成z空间的线性组合，那么我们不妨把z分解成两部分，平行于z空间的部分和垂直的部分。用反证法，假设w*是一个最优解，按照假设我们得到w|是一个更优的解，所以矛盾，说明

29、w*必然只有平行分量。也即w*必须是z空间的线性组合。经过证明我们声称任何L2-regularized linear model都可以被核化。对于核的Logistics Regression问题可以表述如下：怎么求解这个问题？不妨把w*带进去，变成了一个求解的问题。这样问题变成了一个无约束的最优化问题，我们可以使用一切可以求解优化问题的方法，比如GD/SGD等。怎么看待KLR问题？图 KLR的解释第6讲 支持向量回归SVR1 核线性回归回顾前面我们声称任何L2-Regression问题可以有个最优解如下：如果我们把误差项换成平方误差，那么就得到了regularized的线性回归问题：erryn

30、，wTzn=yn-wTzn2再线性回归中我们直接在x空间做回归，而且求得解析解。那么现在我们是否可以利用核技巧在z空间做线性回归并且求得解析解呢？Kernel Ridge Regression Problem表示如下：不失一般性我们求解代替求解w，把w=n=1Nnzn代入上面的问题并化简得：注意两个的项可以写成上面矩阵的形式，后一项求和可以做下面变换：如何求解上面问题最小化解，当然是求导，求导得：注意技巧的使用，K是一个对称阵，而且K是半正定的。令导数等于0得到一个解析解：上面的求逆是一定存在的。有了这个我们就可轻松的求解非线性的回归问题。线性回归和核线性回归比较可见线性回归结果是线性的，表达

31、能力有限，但是当Nd时，效率更高；利用核的脊回归由于核的选择，使得表达更灵活，能表示复杂曲线，但是当训练数据很大时，效率很低。二者的选择其实是效率和灵活性的权衡。2 支持向量回原型归SVR Primalleast-squares SVM (LSSVM)= kernel ridge regression for classification,LSSVM就是以最小二乘为误差的SVM算法. soft-margin Gaussian SVM Gaussian LSSVM可以看出用两种方法能够得到相似的分类边界,但是LSSVM具有以下特点:1) 支持向量个数多,由于往往非0;2) 预测慢, 数据大的时候

32、效率低.3) 对于标准的SVM算法,是稀疏的,我们能不能也得到稀疏的呢?4) 对于原来的误差是一条线为基准,偏离就产生误差,类比之前的SVM算法,误差其实是到边界的距离。因此我们也把回归误差定义为到某一边界的距离，称之为tube Regression。图 tube Regression，在tube之内，没有误差，tube之外误差为到tube的距离用数学表述为：把这种误差称之为-insensitive error 。图Tube versus Squared Regression图 tube和squared的曲线图中可以看出，当s-y很小的时候，二者的曲线接近重合，tubesquared。当s-y

33、较大，tube增长缓慢。这说明tube更不容易受到outliers的影响，因为所谓的outliers就是s-y较大，此时带来的误差小，所以不明感。有了tube误差，我们可以利用tube误差构造L2-Regularized Tube Regression：对比一下：为了和standard SVM保持一致，我们将优化目标改写为：因为max函数不可微，所以我们按照之前的思路，直接用一个变量来代表误差，然后加上相应约束条件，构造成下面的模型：这里把误差分成了上下偏差,分别表示上面和下面违背的误差。这样问题就变成了一个二次规划问题。Yn(实际值)上偏差对于上面的二次规划问题，C用来权衡规则项和误差的权重

34、。是一个选择参数，用来表管子的宽度。模型中共有d+1+2N个变量。2N+2N个约束。问题来了，特征被转换到Z空间时变成d维的，如何消除模型对于d的依赖呢？之前的做法是寻找这个问题的对偶问题。如下：3 SVR dual支持向量回归的对偶问题二次规划的对偶问题首先是引入一个拉格朗日乘子，将约束问题转换为无约束问题。对于该模型的约束条件可以分成两部分，所以引入两个因子对于每个样本点。根据一些条件我们能推导上面的结论。注意互补松弛型的条件。把推导的条件代入模型中，化简就能得到上面最终的模型表达式。这个过程和SVM dual是类似的。最后考虑一下SVR解的松弛性。当点位于tube之内时，可以得到=0，此

35、时时稀疏的。3 核模型的总结线性模型第二行的方法比较常用，有专门的库叫LIBLINEAR。线性或者核模型第四行常用，在LIBSVM中第一行由于表现效果不好（线性不可分），所以不常用；第三行由于通常不是稀疏的，也不常用。第7讲 Blending and Bagging（混合封装）1 Motivation of Aggregation举个例子，你的t个朋友对股票是否上涨分别作了预测，相当于每个人有一个gt(x)，那么你有这些意见，到底该如何决策呢？几种合理的选择：a) 选择你最信赖的朋友validation表现最好的b) 让所有朋友均匀投票，然后根据投票结构预测c) 让他们投票，但是不同人不同的票

36、数，表现好的比重大一些d) 结合一些条件，在某种情况下某个人的票数1，另外情况不是1Aggregation的意思就是结合所有的假设得到更优的决策！把上述的文字描述转换成数学语言描述：Why Might Aggregation Work? 图 左图中如果只用水平或垂直线，无论怎么样都不能得到好的效果。如果混合起来，构成图示形状，效果好得多。对于右图，灰色线条都是无错误的解，我们把所有最优解融合，得到中间的直线，类似于SVM算法的解，由于单个解。2 Uniform Blending (Voting) for Classificationa) 当所有gt都一样的时候（类似独裁），融合的结果和原来相同

37、； b) very different gt (diversity + democracy):majority can correct minority当每个gt相差比较大的时候，显然更加民主，G(x)能够有好的表现；c) 同样可以用于多分类问题，每个人对于某个类别给分，选择最大的即可。这是讲aggregation用于分类，那么对于回归问题呢？Gx=1Tt=1Tgt(x)even simple uniform blending can be better than any single hypothesisUniform Blending的理论分析？右边表示随便选一个gt得到的误差=一个非负数

38、+用G得到的误差，显然说明经过blend aggregation后的效果更好。所以为了实现aggregation首先要得到不同的gt，总结下来可以变为一下步骤：经过上面的理论分析：performance of consensus: called biasexpected deviation to consensus: called varianceuniform blending的目标就是尽量减小variance。3 linear and any Blending问题描述为：目标是：4 Bagging (Bootstrap Aggregation)Blending的策略是得到每个g t，后再聚

39、合，那么我自然的想到能不能二者同时进行？之前说到在进行聚合时，每个g t的差别越大越好，这样能保证Gt具有很好的效果，那么怎么g t的多样性意味着什么呢？a) 不同的模型；h1,h2,h3b) 不同的参数，例如GD算法中的步长，SVM算法中的C等；c) 算法的随机性；d) 样本的随机性回想之前学习的blending技巧：显而易见，consensus的效果要好于直接选择一个g t,但是G来自于很多Dt，而不是我们手中的一个样本集。如何得到很多个样本 Dt from D 呢，如果能做到这样我们就可以用有限的T个样本获得很多g t，然后再得到G。统计学上有个工具叫bootstrapping，通过对样

40、本D采取再采样的方法获得Dt。bootstrap sample Dt: re-sample N examples from D uniformly with replacement（有放回的抽样）can also use arbitrary N instead of original N。通过bootstrap进行聚合的思路Bagging Pocket in Actionbagging works reasonably well if base algorithm sensitive to data randomness第8讲 Adaptive Boosting一个问题：如何认识一个苹果，如何

41、描述它，如下图：如上图，前10张图片是苹果，后面的不是，看了这些图片我们能怎么分辨是不是苹果呢？也许可以描述为苹果是圆的。这样大多数对了，但是有一些错了，如图中放大的图片所示。将注意力集中在犯错的图片上总结一下，我们也许可以说苹果是红色的。这样不停的继续下去，也许我们就能学到怎么分辨苹果。回想一下我们是怎么做到的，没错我们先得到一条规则，然后将注意力集中在犯错的点上，再找出新的规则。直到达到满意的结果。1 Motivation of Boosting总结一下Boosting的思想可以类比成一个班级系统：学生：对应简答的假设gt，比如垂直或者水平线；班级：对应更高级复杂的假设G，如上如中的黑线；

42、老师：教导我们学习方法指导学生专注于关键的实例。2 Diversity by Re-weighting之前讲道可以利用bootstrap的重新抽样得到不同的样本，如上图。由于每次抽到的样本概率不一样，那么这个样本带来的错误或者说权重是不一样的。引入样本权重更为合理。可见我们抽到了两次x1,所以权重为2，相应的没抽到的可以定义为0 。对于每次抽样样本不一样，对应就是权重不一样，引入不同的权重系数就可以训练出不同的gt。模型如下：之前的SVM模型中加入权重，其实也就是调整每个样本的C值，Logistics回归加入权重等价于以和权重成比例的概率取样。之前讲过指纹分类系统的两种错误，由于导致的后果不一

43、样，所以我用带权重分类学习，其实和这个原理是一样的。上面讲了如何得到gt，我们知道gt差别越大，后面做blending或者aggregation的效果就越好，那么怎么通过re-weight构造出diversity的gt呢？首先看如何得到不同的gt，假设我们有gt 和gt+1，如何让二者不一样呢？如果gt 和gt+1，很不一样，也就是把Ut+1用在gt上效果很不好，效果很不好什么意思呢？就就用gt来分类的时候，就像掷硬币一样，完全没有把握，它的概率是1/2。用数学表达：为了使图一表达式成立，一种可能的方式就是给每一个U乘以一个因子，使得最后U of incorrent=U of coeerct。3 Adaptive Boosting Algorithm上一节课讲道了一个放缩因子，从而以此更新权值，为了表达方便我们重新改写等式，得到如下：当错误率小于1/2，也