中国科学院大学机器学习——AdaBoost(共12页)

1、 Boosting主要(zhyo)内容：AdaBoost简介(jin ji)训练误差(wch)分析测试误差分析贝叶斯最大后验前向递增建模一、AdaBoost简介：1.1 算法简介给定训练集：，其中，表示的正确的类别标签，训练集上样本的初始分布：对，计算弱分类器，该弱分类器在分布上的误差为：计算该弱分类器的权重：更新训练样本的分布：，其中为归一化常数。最后的强分类器为：.1.2. AdaBoost过程举例因为权重更新依赖于,而又依赖于,所以我们直接将权重更新公式用表示。样本权重更新公式：，其中，当样本分错时，当样本(yngbn)分对时，错误(cuw)分类样本更新因子：正确分类样本(yngbn)更

2、新因子：例：给定如图1所示的样本，弱分类器采用平行于坐标轴的直线 （1）得到第一个弱分类器：正确分类样本权重：（7个）错误分类样本权重：(3个)此时强分类器的训练错误为：0.3（2）继续计算第二个弱分类器：正确(zhngqu)分类样本权重：（7个）又分为(fn wi)两种： 第一轮正确(zhngqu)：（4个）第一轮错分：（3个）错误分类样本权重：(3个)第一轮正确: (3个)：此时强分类器的训练错误为：0.3（3）继续计算第三个弱分类器： 正确(zhngqu)分类样本权重：（7个）又分为(fn wi)三种情况： 前两轮(lin ln)都正确：（1个）第一轮错分、第二轮正确：（3个）第一轮正确

3、、第二轮错分：（3个）错误分类样本权重：(3个)前两轮正确: (3个)：此时强分类器的训练错误为：0二、训练误差分析记，由于弱分类器的错误率总是比随机猜测（随机猜测的分类器的错误率为0.5），所以，则训练误差为：。记，则。证明：1、对进行迭代展开令。由于(yuy)是一个(y )分布，所以(suy)：所以。训练误差为 * 。所以，为训练误差的上界。相当于损失(snsh)函数取，则经验(jngyn)风险/训练(xnlin)误差为，使该经验风险最小的估计为。该风险称为指数风险。*当样本分对时，所以，是一个较小的正数。当样本分错时，所以。所以将变为，相当于对上述两种错误率都放大了，这样不等式成立。证明

4、；问题：给定弱分类器的集合：，确定弱分类器及其权重。具体实现时，首先选一个错误率最小的弱分类器，然后确定其权重，所以是一个贪心算法。（相当于对，前向逐步递增特征选择，后面再详细描述），因为即为分类正确(zhngqu)的样本的集合，为分类(fn li)错误的样本的集合。，两边(lingbin)同乘以正确率=，错误率=，所以所以。当很小时，很大，即错误率很小的弱分类器的权重很大。训练误差令（t = “edge”），由于弱分类器的错误率总是比随机猜测（随机猜测的分类器的错误率为0.5），所以，所以（不等式可利用(lyng)在处Taylor展开(zhn ki)得到(d do)）令，即为所有中最小的一个

5、。则训练误差的上界为：。所以，当，即训练误差的上界随T的增加指数减小。三、测试误差分析最终的强分类器为：。T为算法中唯一需要调整的参数，那么T该取多大值？初步猜测：T太大，模型会变得很复杂，会发生过拟合。但实际的运行结果为当训练误差已经等于0后，测试误差仍然没有增加，即使T已经达到1000。更好的解释：Margin训练误差只考虑了分类是否正确，还应该(ynggi)考虑分类的信度。由于为弱分类器的投票权重，可将定义(dngy)为Margin，表示分类的信度。上述实验(shyn)Margin的累积分布：可以证明，随着T的增加，训练样本的Margin会增大（证明过程类似训练误差的证明）；而大的Mar

6、gin会带来更好的泛化性能（如果所有样本的Margin都很大，可以用一个很简单的分类器实现分类）理论上，测试误差的界：，其中D为弱分类器的复杂度。事实上，AdaBoost也可能发生过拟合（如下图所示）。通常(tngchng)当满足下述条件时，发生过拟合的可能性很小：弱分类器的(edge)较大(jio d)（），即弱分类器不太弱，错误率不太低，从而(cng r)Margin较大；弱分类器相对样本规模不太复杂。事实上上述heart-disease dataset就是数据规模太小，弱分类器的edge也较小。四、AdaBoost相当于最大贝叶斯后验，当损失函数取时，则上述表达式为经验风险，当样本很多时

7、，样本均值趋近于期望，即期望风险/测试误差为。对上述风险，我们在每个样本点(x)上最小化， 我们目标是风险最小的，即所以，即所以(suy)，为最大贝叶斯后验。四、AdaBoost相当于前向逐步(zhb)递增(dzng)建模，可视为基展开，其中为基函数，为对应基函数的权重。对基展开，通常是给定基函数，一次联合求出所有的基函数中的参数及其权重（如用最小二乘法或极大似然估计方法）。而AdaBoost可视为一个逐步递增的方式增加基函数，并计算其权重，不调整已添加的基函数中的参数及其权重。因此亦被称为前向逐步递增建模（forward stagewise additive modeling）.假设第步的模

8、型为：当损失函数取时，则第T步新增加的基函数及其权重要使得训练误差/经验风险最小，即， ，其中。因为每个不依赖于，所以可以看作是应用于每个观测的权值，该权值依赖于，所以，每个样本的权值随每次迭代改变。上述问题可以分两步实现：第一步：首先选一个错误率最小的弱分类器，。第二步：然后确定(qudng)其权重， 因为(yn wi)将代入，即可得到(d do)，其中表示错误率。指数损失对outliers比较敏感，且也不是任何二值变量y的概率密度取log后的表示。因此另一种选择是损失函数取负log似然损失，得到logitBoost （算法16.3）.对回归问题，损失函数可取L2，得到L2boosting.图：不同损失函数的比较。内容总结（1）Boosting主要内容：AdaBoost简介训练误差分析测试误差分析贝叶斯最大后验