集成学习是使用一系列学习器进行学习,并使用某种规则把各个学习结果进行整合从而获得比单个学习器更好的学习效果的一种机器学习方法。一般情况下,集成学习中的多个学习器都是同质的"弱学习器"。

注脚

展开查看详情

1.马健

2.第八章 : 集成 学习

3.集成学习 个体 与集成 Boosting Adaboost Bagging 与随机森林 结合策略 平均法 投票 法 学习 法 多样性 误差 - 分歧分解 多样性度量 多样性扰动

4.个体与集成 集成学习 (ensemble learning) 通过构建并结合多个学习器来提升性能

5.个体与集成 考虑一个简单的例子,在二分类问题中,假定 3 个分类器在三个样本中的表现如下图所示,其中 √ 表示分类正确, X 号表示分类错误,集成的结果通过投票产生。 集成个体应:好而不同

6.个体与 集成 – 简单分析 考虑二分类问题,假设基分类器的错误率为: 假设集成通过简单投票法结合 分类器,若有超过半数的基分类器正确则分类就正确  

7.个体与 集成 – 简单分析 假设基分类器的错误率相互独立,则由 Hoeffding 不等式可得集成的错误率为: 显示,在一定条件下,随着集成分类器数目的增加,集成的错误率将指数级下降,最终趋向于 0  

8.个体与集成 – 简单分析 上面的分析有一个关键假设:基学习器的误差相互独立 现实任务中,个体学习器是为解决同一个问题训练出来的,显然不可能互相独立 事实上,个体学习器的“准确性”和“多样性”本身就存在冲突 如何产生“好而不同”的个体学习器是集成学习研究的核心 集成学习大致可分为两大类

9.个体与集成 – 简单分析 上面的分析有一个关键假设:基学习器的误差相互独立 现实任务中,个体学习器是为解决同一个问题训练出来的,显然不可能互相独立 事实上,个体学习器的“准确性”和“多样性”本身就存在冲突 如何产生“好而不同”的个体学习器是集成学习研究的核心 集成学习大致可分为两大类

10.Boosting 个体学习器存在强依赖 关系, 串行生成 每次调整 训练数据的 样本分布

11.Boosting - Boosting 算法 Boosting 族算法最著名的代表是 AdaBoost

12.Boosting – AdaBoost 算法

13.Boosting – AdaBoost 推导 基学习器的线性组合 最小化指数损失函数

14.Boosting – AdaBoost 推导 若 能令指数损失函数最小化,则 上式 对 的偏导值为 0 ,即   贝叶斯最优错误率,说明指数损失函数是分类任务原来 0/1 损失函数的一致的替代函数。  

15.Boosting – AdaBoost 推导 当基分类器 分布 ,该基分类器的权重 使得 最小化指数损失函数   令指数 损失函数的导数为 0 ,即

16.Boosting – AdaBoost 推导 在获得 的样本分布进行调整,使得下一轮的基学习器 能纠正 的一些错误,理想的 能纠正全部错误   泰勒展开近似为

17.Boosting – AdaBoost 推导 于是,理想的基学习器: 注意到 是一个常数,令 D t 表示一个分布 :

18.Boosting – AdaBoost 推导 根据数学期望的定义,这等价于令 : 由 :  

19.Boosting – AdaBoost 推导 最终的样本分布更新 公式 则理想的基学习器

20.Boosting – AdaBoost 注意事项 数据分布的学习 重赋权法 重采样法 重启动,避免训练过程过早停止

21.0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 (a) 3 个基学习器 (b) 5 个基学习器 (c) 11 个基学习器 Boosting – AdaBoost 实验 从偏差 - 方差的角度:降低偏差,可对泛化性能相当弱的学习器构造出很强的集成

22.0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 (a) 3 个基学习器 (b) 5 个基学习器 (c) 11 个基学习器 Boosting – AdaBoost 实验 从偏差 - 方差的角度:降低偏差,可对泛化性能相当弱的学习器构造出很强的集成

23.Bagging 与随机森林 个体学习 器不存在 强依赖 关系 并行 化生成 自助采样法

24.Bagging 与随机森林 - Bagging 算法

25.Bagging 与随机 森林 - Bagging 算法特点 时间复杂度低 假定基学习器的计算复杂度为 O(m) ,采样与投票 / 平均过程的复杂度为 O(s) ,则 bagging 的复杂度大致为 T(O(m)+O(s )) 由于 O(s) 很 小且 T 是一个不大的常数 因此训练一个 bagging 集成与直接使用基学习器的复杂度同阶 可使用包外估计

26.Bagging 与随机 森林 - 包外估计 表示对样本 包外预测,即仅考虑那些未使用样本 训练的基学习器在 预测   Bagging 泛化误差的包外估计为:

27.0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 0 0.2 0.4 0.6 0.8 0.2 0.4 0.6 好瓜 坏瓜 密度 含糖率 (a) 3 个基学习器 (b) 5 个基学习器 (c) 11 个基学习器 Bagging 与随机森林 - Bagging 实验 从偏差 - 方差的角度:降低 方差,在不剪枝的决策树、神经网络等易受样本影响的学习器上效果更好

28.Bagging 与随机森林 - 随机森林 随机森林 (Random Forest ,简称 RF) 是 bagging 的一个扩展变种 采样的随机性 属性选择的随机性

29.Bagging 与随机 森林 - 随机森林算法 随机森林算法

30.Bagging 与随机 森林 - 随机森林实验

31.Bagging 与随机 森林 - 随机森林实验

32.(a) 统计的原因 (b) 计算的原因 (c) 表示的原因 同等性能的假设 假设空间 个体假设 真实假设 结合策略 学习器的组合可以从三个方面带来好处

33.结合 策略 – 平均法 简单平均法 加权平均 法

34.结合策略 – 平均法 简单平均法是加权平均法的特例 加权平均法在二十世纪五十年代被广泛使用 集成学习中的各种结合方法都可以看成是加权平均法的变种或特例 加权平均法可认为是集成学习研究的基本出发点 加权平均法未必一定优于简单平均法

35.结合策略 – 投票 法 绝对多数投票法( majority voting ) 相 对多数投票法( plurality voting ) 加权投票法( weighted voting )

36.结合策略 – 学习法 Stacking 是学习法的典型代表 多响 应 线性回归 (MLR) 作为次级学习器的学习算法 效果 较好 贝 叶斯模型 平均 (BMA)

37.结合策略 – 学习法 Stacking 是学习法的典型代表 多响 应 线性回归 (MLR) 作为次级学习器的学习算法 效果 较好 贝 叶斯模型 平均 (BMA)

38.多样性 – 误差 - 分歧分解 定义学习器 分歧 (ambiguity) :   集成的分歧:

39.多样性 – 误差 - 分歧分解 分歧项代表了个体学习器在样本 上的不一致性,即在一定程度上反映了个体学习器的多样性,个体学习器 和集成 的平方误差分别为  

40.多样性 – 误差 - 分歧分解 令 表示个体学习器误差的加权均值,有 上式对所有样本 均成立,令 表示样本的概率密度,则在全样本上有  

41.多样性 – 误差 - 分歧分解 个体 在全样本上的泛化误差和分歧项分别为:   集成的泛化误差为: 令 表示个体学习器泛化误差的加权均值, 表示个体学习器的加权分歧值,有

42.多样性 – 误差 - 分歧分解 这个漂亮的式子显示 : 个体学习器精确性越高、多样性越大,则集成效果越好。称为误差 - 分歧分解 为什么不能直接把 作为优化目标来求解? 现实任务中很难直接对 进行优化, 它们定义在整个样本空间上 不是一个可直接操作的多样性度量 上面的推导过程只适用于回归学习,难以直接推广到分类学习任务上去  

43. 对于二分类问题,分类器 与 的预测结果联立表 ( contingency table ) 为   多样性 – 多样性度量 多样性度量 (diversity measure) 用于度量集成中个体学习器的多样性

44.常见的多样性 度量 不合度量 (Disagreement Measure) 相关系数 (Correlation Coefficient) 多样性 – 多样性度量

45.常见的多样性 度量 Q- 统计量 ( Q-Statistic) K- 统计量 ( Kappa-Statistic) 多样性 – 多样性度量

46.多样性 – 多样性度量 误差图  

47.多样性 – 多样性增强 常见的增强个体学习器的多样性的方法 数据样本扰动 输入属性扰动 输出表示扰动 算法参数扰动

48.多样性 – 多样性增强 - 数据样本扰动 数据样本扰动通常是基于采样法 Bagging 中的自助采样法 Adaboost 中的序列采样 对数据样本的扰动敏感的基学习器 ( 不稳定基学习器 ) 决策树,神经网络等 对数据样本的扰动不敏感的基学习器 ( 稳定基学习器 ) 线性学习器,支持向量机,朴素贝叶斯, k 近邻 等 数据样本扰动对“不稳定基学习器”很 有效

49.随机子空间算法 (random subspace) 多样性 – 多样性增强 – 输入属性扰动

50.翻转法 (Flipping Output) 输出调剂法 (Output Smearing) ECOC 法 多样性 – 多样性增强 – 输出表示扰动

51.负相关法 不同的多样性增强机制同时使用 多样性 – 多样性增强 – 算法参数扰动

52.阅读材料 集成学习方面的主要推荐读物是 [Zhou,2012] ,本章提及的所有内容在该书中都有更深入的详细介绍。 [Kuncheva,2004;Rockach,2010b] 可供参考, [ Schapire and Freund,2012] 则是专门关于 Boosting 的著作,集成学习方面有一些专门性的会议 MCS(International W orkshop on M ultiple Classifier S ystem). Boosting 源于 [Schapire,1990] 对 [Kearns and Valiant,1989] 提出的 ” 弱分类器是否等价于强学习 ” 这个重要理论问题的构造性证明。最初的 Boosting 算法仅有理论意义,经数年努力后 [Freund and Schapire,1997] 提出 Adaboost ,并因此或得理论计算机科学方面的重要奖项 — 哥德尔奖。关于 Boosting 和 Bagging 已有的很多理论研究结果课参阅 [Zhou,2012] 第 2-3 章。