Bagging & Boosting

分类 决策树分类: ID3 C4.5 贝叶斯分类 后向传播分类 其它分类

分类法的准确性 评估分类法的准确率 提高分类法的准确率 保持（holdout） K-次交叉验证（k-fold cross validation） 提高分类法的准确率 bagging boosting

评估分类法的准确率 保持（holdout） 划分为两个独立的数据集： 通常:训练集 (2/3),测试集(1/3) 变形：随机子选样 划分为两个独立的数据集： 通常:训练集 (2/3),测试集(1/3) 变形：随机子选样 评估准确性 导出分类法 训练集 数据 测试集

评估分类法的准确率 ··· K-次交叉验证 将数据集分为k个子集； 用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证； S1 Sk

提高分类法的准确率 Bagging Boosting 新数据 样本 C1 数据 C2 类预测 组合得票 ··· Ct

Bagging 基本思想: 给定一个弱学习算法,和一个训练集; 单个弱学习算法准确率不高; 将该学习算法使用多次,得出预测函数序列,进行投票; 最后结果准确率将得到提高.

Bagging 算法: For t = 1, 2, …, T Do 从数据集S中取样（放回选样） 训练得到模型Ht 对未知样本X分类时,每个模型Ht都得出一个分类，得票最高的即为未知样本X的分类 也可通过得票的平均值用于连续值的预测

Bagging … … C* c*(x) = maxcntt ct(x) x C1 C2 CT train c1(x) c2(x) S1 S2 ST

Bagging Bagging要求“不稳定”的分类方法； 比如：决策树，神经网络算法 不稳定：数据集的小的变动能够使得分类结果的显著的变动。 “The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.” (Breiman 1996)

Boosting原理及在分类上的应用 背景 Boosting原理 Boosting算法 Boosting应用 总结

背景 游戏理论（Game theory） R P S 锤子 布 剪子 锤子 ½ 1 0 布 0 ½ 1 剪子 1 0 ½ 锤子 布 剪子 锤子 ½ 1 0 布 0 ½ 1 剪子 1 0 ½ 游戏者1（row player)： RSPPSRS… （损失最小化） 游戏者2（column player）： SRRPSRP… （损失最大化）

三个臭皮匠，胜过诸葛亮 背景 Boosting思想源于 Finding many rough rules of thumb can be a lot easier and more effective than finding a single, highly prediction rule.

Boosting—concepts(1) 机器学习（Machine Learning)：将一些已知的并已被成功解决的问题作为范例输入计算机,机器通过学习这些范例总结并生成相应的规则,这些规则具有通用性,使用它们可以解决某一类的问题 。 人脸识别 文本分类 网络安全 生物信息工程 学习机（learner)：机器学习得到的规则或者模型。 样本：所研究问题的实例，一般在训练集中包括正样本和负样本。 一张人脸图像，一篇文章，一个病毒代码，一个生物的遗传编码 训练：采用某种方法，用已知属性的样本作为输入，得到相应规则的过程。 训练集：由已知属性的样本组成的集合，作为训练过程的输入数据。 测试集：由已知属性的样本组成的集合，作为测试过程的输入数据。 假设：学习机对样本做出的判断，即是否符合需要判定的事实。 某张脸是否是张三的，某篇文章是否属于新闻类别

Boosting—concepts(2) 特征选取：从实际数据中抽取反映其本质规律的属性。 人脸图像向量做PCA变换得到特征向量的投影系数 对文本进行语法分析后表示成关于词的特征向量 机器学习系统结构表示

Boosting—concepts(3) 弱学习机（weak learner): 对一定分布的训练样本给出假设（仅仅强于随机猜测） 根据有云猜测可能会下雨 强学习机（strong learner): 根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert) 根据CNN,ABC,CBS以往的预测表现及实际天气情况作出综合准确的天气预测 弱学习机 强学习机 Boosting

Boosting流程(loop1) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 X>1?1:-1 加权后的假设

Boosting流程(loop2) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 Y>3?1:-1 加权后的假设

Boosting流程(loop3) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 Z>7?1:-1 加权后的假设

流程描述 Step1: 原始训练集输入，带有原始分布 Step2: 给出训练集中各样本的权重

核心思想 样本的权重 弱学习机的权重 循环控制：损失函数达到最小 没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N 每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大， 使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。 弱学习机的权重 准确率越高的弱学习机权重越高 循环控制：损失函数达到最小 在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。

简单问题演示（Boosting训练过程）

算法—问题描述 训练集 { (x1,y1), (x2,y2),…, (xN,yN) } xi Rm, yi {-1,+1} Dt 为第t次循环时的训练样本分布（每个样本在训练集中所占的概率， Dt总和应该为1） ht:X{-1,+1} 为第t次循环时的Weak learner，对每个样本给出相应的假设，应该满足强于随机猜测： wt为ht的权重 为t次循环得到的Strong learner

算法—样本权重 思想：提高分错样本的权重 反映了strong learner对样本的假设是否正确 采用什么样的函数形式？

算法—弱学习机权重 思想：错误率越低，该学习机的权重应该越大 为学习机的错误概率 采用什么样的函数形式？ 和指数函数遥相呼应：

算法--Adaboost

理论分析--最优化 如何求弱学习机的权重？ 最基本的损失函数表达形式 为了便于计算，采用以下的目标函数 Boosting的循环过程就是沿着损失函数的负梯度方向进行最优化的过程。通过调整样本的分布Dt和选择弱学习机的权重wt来达到这个目的。每循环一次，增加一项 ，使损失函数以最快速度下降。

总结 Boosting的思想源泉： Boosting的数学实质： Boosting的理论联系： Boosting的应用 三个臭皮匠，胜过诸葛亮 将一系列粗略的规则加权组合起来得到高度精确的规则。 Boosting的数学实质： 对目标函数（损失函数）的最优化问题。 Boosting的理论联系： 最优化 熵映射 Boosting的应用 人脸识别 文本分类

参考资料 Internet站点 推荐论文 www.boosting.org http://mathworld.wolfram.com A Brief Introduction to Boosting Experiments with a New Boosting Algorithm Additive Logistic Regression: a Statistical View of Boosting The Boosting Approach to Machine Learning: an overview Game Theory, On-line Prediction and Boosting Boosting as Entropy Projection Logistic Regression, AdaBoost and Bregman Distances 以上论文均可在www.boosting.org下载

研究方向 Bagging和boosting非常相似,是否存在统一的理论框架. Boosting发生overfit的条件.

Thank you! Have a good supper! End  Thank you! Have a good supper!