1、第八章 Adaboost 提纲 AdaBoost的起源和基本概念 AdaBoost算法 前向分步训练算法 AdaBoost 编程 AdaBoost实时人脸检测算法 1984，Kearns和Valiant： 强可学习(strongly learnable)和弱可学习(weakly learnable) 在概率近似正确（probably approximately correct, PAC) 学习的框架中，一个概念（类），如果存在一个多项式的学 习算法能够学习它，并且正确率很高，称这个概念是强可学 习的； 一个概念（类），如果存在一个多项式的学习算法能够学习 它，学习的正确率仅比随机猜测略好，则称
2、这个概念是弱可 学习的。 1989, Schapire，证明： 在PAC学习的框架下，一个概念是强可学习的充分必要条件是 这个概念是弱可学习。 Adaboost的起源 问题的提出： 只要找到一个比随机猜测略好的弱学习算法就可以 直接将其提升为强学习算法，而不必直接去找很难 获得的强学习算法。 Adaboost的起源 例如：学习算法A在a情况下失效，学习算法B在b情况下 失效，那么在a情况下可以用B算法，在b情况下可以用A 算法解决。这说明通过某种合适的方式把各种算法组合 起来，可以提高准确率。 为实现弱学习互补，面临两个问题： （1）怎样获得不同的弱分类器？ （2）怎样组合弱分类器？ 怎样实现
3、弱学习转为强学习 使用不同的弱学习算法得到不同基本学习器 参数估计、非参数估计 使用相同的弱学习算法，但用不同的参数 K-Mean不同的K，神经网络不同的隐含层 相同输入对象的不同表示凸显事物不同的特征 使用不同的训练集 装袋（bagging） 提升（boosting） 怎样获得不同的弱分类器 也称为自举汇聚法(boostrap aggregating) 从原始数据集选择S次后得到S个新数据集 新数据集和原数据集的大小相等 每个数据集都是通过在原始数据集中随机选择样本来进 行替换而得到的。 S个数据集建好之后，将某个学习算法分别作用于每个 数据集就得到S个分类器。 选择分类器投票结果中最多的类
4、别作为最后的分类结果。 改进的Bagging算法，如随机森林等。 Bagging 多专家组合 一种并行结构，所有的弱分类器都给出各自的预测结果，通过 “组合器”把这些预测结果转换为最终结果。 eg.投票（voting） 及其变种、混合专家模型 多级组合 一种串行结构，其中下一个分类器只在前一个分类器预测不够准 （不够自信）的实例上进行训练或检测。 eg. 级联算法 （cascading） 怎样组合弱分类器怎样组合弱分类器 1990年，Schapire最先构造出一种多项式级的算法， 即最初的Boost算法; 1993年，Drunker和Schapire第一次将神经网络作为弱 学习器，应用Boos
5、ting算法解决OCR问题; 1995年，Freund和Schapire提出了Adaboost(Adaptive Boosting)算法，效率和原来Boosting算法一样，但是 不需要任何关于弱学习器性能的先验知识，可以非常 容易地应用到实际问题中。 Adaboost的提出 AdaBoost Adaptive A learning algorithm Building a strong classifier a lot of weaker ones Boosting Adaboost基本概念 1 1), 1(h x . . . Weak classifiers slightly better
6、 than random 1 ( )( ) T t tTt h xHxsign 2 1), 1(h x 1(), 1 T hx strong classifier Adaboost基本概念 两个问题如何解决： 每一轮如何改变训练数据的权值或概率分布？ AdaBoost：提高那些被前一轮弱分类器错误分类样本的权值，降低那些 被正确分类样本的权值 如何将弱分类器组合成一个强分类器？ AdaBoost：加权多数表决，加大分类误差率小的弱分类器的权值，使其 在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在 表决中起较小的作用。 Adaboost基本概念 Adaboost基本概念 输入：二
7、分类的训练数据集 ， 输出：最终分类器G(x) 1 初始化训练数据的起始权值分布 AdaBoost算法 2 对m个弱分类器 m=1,2，。M a、在权值Dm下训练数据集，得到弱分类器 b、计算Gm的训练误差 c、计算Gm的系数 d、更新训练数据集的权值分布 Z是规范化因子 AdaBoost算法 3、构建弱分类器的线性组合， 得到最终分类器： AdaBoost算法 步骤 b 步骤 c 步骤 d 误分类的样本权值放大 AdaBoost算法说明 初始化 对m=1 a、在权值分布为D1的数据集上，阈值取2.5，分类误差率最小，基本 弱分类器： b、G1(x)的误差率 ： c、G1(x)的系数： 例子：
8、 d、更新训练数据的权值分布 弱基本分类器G1(x)=signf1(x)在更新的数据集上有3 个误分类点 例子： 对m=2 a、在权值分布D2上，阈值v=8.5时，分类误差率最低 b、误差率 c、计算 d、更新权值分布 分类器G2(x)=signf2(x)有三个误分类点 例子： 对m=3 a、在权值分布D3上，阈值v=5.5时，分类误差率最低 b、误差率 c、计算 d、更新权值分布 分类器G3(x)=signf3(x)误分类点为0 例子： Weak Classifier 1 Boosting illustration Weights Increased Boosting illustratio
9、n Weak Classifier 2 Boosting illustration Weights Increased Boosting illustration Weak Classifier 3 Boosting illustration Final classifier is a combination of weak classifiers Boosting illustration 由： 定理：AdaBoost算法最终分类器的训练误差界为： AdaBoost的训练误差分析 证明： 前面部分很明显， 证后面，由 AdaBoost的训练误差分析 定理：二分类问题AdaBoost的训练误差
10、界为： 证明：前面， AdaBoost的训练误差分析 定理：二分类问题AdaBoost的训练误差界为： 证明：后面， 由ex和 在x=0的泰劳展开得： 进而得证。 AdaBoost的训练误差分析 定理：如果存在 0，对所有的m有 m ，则 即：训练误差为指数下降。 注意：AdaBoost算法不需要知道下界，这正是Freund与Schapire设计 AdaBoost时所考虑的，与一些早期的提升方法不同，AdaBoost具有适 应性，即它能适应弱分类器各自的训练误差率，这也是它的名称(适 应的提升)的由来，Ada是Adaptive的简写 AdaBoost的训练误差分析 AdaBoost 模型：加法
11、模型 损失函数：指数函数 学习算法：前向分步算法的二分类学习算法 AdaBoost算法的解释 加法模型（additive model） 给定训练数据和损失函数 L(y, f(x), 学习加法模型f(x) 成为经验风险极小化即损失函数极小化问题： 基函数的参数 基函数 基函数的系数 复杂的优化问题 前向分步算法 前向分步算法Forward stagewise algorithm 求解思路： 根据学习的是加法模型，如果能够从前向后，每一步只 学习一个基函数及其系数，逐步逼近优化目标函数式， 具体，每步只需优化如下损失函数： 前向分步算法 输入：训练数据集 损失函数 ，基函数集 输出：加法模型f(x
12、) 1 初始化 f0(x)=0 2 对m=1，2，M a、极小化损失函数 得到参数m，m b、 更新 3 得到加法模型 前向分步算法 定理： AdaBoost算法是前向分步加法算法的特例，模型是由基本分类器组成的 加法模型，损失函数是指数函数 证明： 前面部分很明显： 后面部分证明损失函数是指数函数（exponential loss function） 假设经过m-1轮迭代前向分步算法得到fm-1(x): 在第m轮迭代得到 前向分步算法 在第m轮迭代得到 目标： 即： 现证使上式最小的 就是AdaBoost算法得到的 不依赖和G,依赖于fm-1(x),随着每一轮迭代改变 前向分步算法 首先，求
13、 ；对任意 0，使式 最小的G(x)由下式得到 ： 即 为AdaBoost算法的基本分类器 ，为使第 m轮加权训练数据分类误差率最小的基本分类器 前向分步算法 求 由 将已求得的 代入，对求导并使导数为0， 得： 与AdaBoost的m完全一致 前向分步算法 每一轮样本权值的更新，由： 可得： 与AdaBoost的权值更新一致，相差规范化因子，因而等 价。 前向分步算法 提升树是以分类树或回归树为基本分类器的提升方法；提升树被 认为是统计学习中性能最好的方法之一。 提升树模型 (boosting tree) 提升方法实际采用：加法模型(即基函数的线性组合)与前向分步算法，以 决策树为基函数；
14、对分类问题决策树是二叉分类树， 对回归问题决策树是二叉回归树， 基本分类器xv，可以看作是由一个根结点直接连接两个叶结点的简单决策树， 即所谓的决策树桩(decision stump)。 提升树 前向分步算法： 首先确定初始提升树： 第m步的模型： 其中，fm-1(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数m 由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之 间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。 提升树算法 针对不同问题的提升树学习算法，使用的损失函数 不同： 用平方误差损失函数的回归问题， 用指数损失函数的分类问题， 用一般损失函数的一般决
15、策问题。 对二类分类问题：提升树算法只需将AdaBoost算法 中的基本分类器限制为二类分类树即可，这时的提 升树算法是AdaBoost算法的特殊情况。 讨论回归问题提升树： 提升树算法 回归问题提升树： 已知训练数据集： X为输入空间，y为输出空间， 将X划分为J个互不相交的区域R1,R2,.Rj, 并且在每个区域上确定输出的 常量cj，那么，树可表示为： J是回归树的复杂度即叶结点个数 提升树算法 前向分步算法： 在前向分步算法的第m步，给定当前fm-1 需求解 得到第m棵树的参数 采用平方损失函数时： 提升树算法 回归问题的提升树算法 X的取值范围0.5, 10.5,y的取值范围：5.0
16、,10.10,用树 桩做基函数； 求f1(x)回归树T1(x)， 求切分点s： 容易求得在R1,R2内部使平方损失误差达到最小值的 c1,c2: 例： 各切分点： 回归树T1 例： 用f1拟合数据的平方误差： 第二步：求T2， 例： 例： 提升树利用加法模型与前向分步算法实现学习的优化过程，当损 失函数是平方损失和指数损失函数时，每一步优化是很简单的， 但对一般损失函数而言，往往每一步优化并不那么容易。 针对这一问题，Freidmao提出了梯度提升(gradient boosting)算法. 这是利用最速下降法的近似方法，其关键是利用损失函数的负梯 度在当前模型的值 作为回归问题提升树算法中的
17、残差的近似值，拟合一个回归树。 梯度提升 梯度提升算法 Adaboost的实现 单层决策树生成函数 单层决策树生成函数 单层决策树生成函数 单层决策树生成函数 完整AdaBoost算法的实现 完整AdaBoost算法的实现 完整AdaBoost算法的实现 完整AdaBoost算法的实现 基于AdaBoost的分类函数 测试算法 基于AdaBoost的分类函数 测试算法 加载数据 在马疝病数据集上应用Adaboost 在马疝病数据集上应用Adaboost overfitting 在马疝病数据集上应用Adaboost 相似之处 把弱分类器看成SVM的核函数。 按照最大化某个最小间隔的方式重写Ada
18、Boost算法。 不同 二者所定义的间隔计算方式有所不同，导致结果不同。 高维空间下，二者间差异会更加明显。 SVM和AdaBoost的关系 1、马疝病 2、垃圾邮件 3、癌症检测 分类性能度量指标：正确率、召回率、ROC曲线 混淆矩阵 Confusion matrix 非均衡分类问题 二分类问题的混淆矩阵 Precision 正确率=TP/(TP+FP) Recall 召回率=TP/(TP+FN) 假阳率=FP/(FP+TN) 真阳率=TP/(TP+FN) 非均匀分类问题 非均匀分类问题 接收者操作特性（receiver operating Characteristic） 成本效益（cost-versus-benefit） 曲线下面积（Area Unser theCurve，AUC） 非均匀分类问题 基于代价函数的分类器决策控制 欠抽样 （undersampling） 过抽样 （oversampling） 处理非均衡问题的数据抽样方法 END
