08ensemble_learning.md

集成学习

集成学习（ensemble learning）通过构建并结合多个学习期来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、**基于委员会的学习（committee-based learning）**等。

这一章的内容大致如下：

• 个体与集成：同质集成和异质集成有什么不同？集成学习对个体学习器有什么要求？集成学习研究的核心是什么？集成学习分哪两大类？

• Boosting：Boosting的基本概念？AdaBoost算法的流程？如何基于加性模型最小化指数损失函数来推导？怎样处理基学习算法无法处理带权样本的情况？Boosting的优势是什么？

• Bagging与随机森林：Bagging算法如何获得各个基学习器的训练集？预测时如何进行结合？相比AdaBoost有什么优势？随机森林的核心思想是什么？相比Bagging有什么优势？

• 结合策略：结合多个学习器有什么好处？平均法是怎样的？投票法是怎样的？学习法又是怎样的？

• 多样性：如何进行误差-分歧分解？说明了什么？有哪些多样性度量指标？有哪些增强多样性的手段？

个体与集成

集成学习先产生一组个体学习器（individual learner），再用某种策略将它们结合起来。

当所有个体学习器都由同样的学习算法生成时，也即集成中只包含同种类型的个体学习器时，称为同质（homogeneous）集成，这些个体学习器又被称为基学习器（base learner），相应的学习算法称为基学习算法（base learning algorithm）；

当个体学习器由不同的学习算法生成时，称为**异质（heterogenous）集成，这些个体学习器称为组件学习器（component learner）**或直接称为个体学习器。

集成学习通过结合多个学习器，通常能获得比单一学习器更优越的泛化性能，对**弱学习器（weak learner）**的提升尤为明显。注：弱学习器即略优于随机猜测的学习器，例如二分类任务中精度略高于50%。虽然理论上，集成弱学习器已经能获得很好的性能。但现实任务中，人们往往会使用比较强的学习器。

当我们使用集成学习的时候，我们其实是希望不同的个体学习器产生互补的效果，使得某个学习器错误的地方能有机会被其他学习器纠正过来，这就要求个体学习器应该尽量“不同”，即具有多样性；同时我们希望这种互补不会把正确改为错误，这就要求个体学习器应该尽量“准确”。合起来就是集成学习研究的核心——如何产生并结合“好而不同”的个体学习器。

根据个体学习器的生成方式，集成学习方法大致可分为两个大类：

• 个体学习器间存在强依赖关系，必须串行生成的序列化方法，例如：Boosting算法族；
• 个体学习器间不存在强依赖关系，可同时生成的并行化方法，例如：Bagging，随机森林；

习题

8.1

问：假设抛硬币正面朝上的概率为 $p$，反面朝上的概率为 $1-p$。令 $H(n)$ 代表抛 $n$ 次硬币所得正面朝上的次数，则最多 $k$ 次正面朝上的概率为

$$P(H(n) \leq k) = \sum_{i=0}^k \binom{n}{i} p^i (1-p)^{n-i}$$

对 $\delta > 0,\quad k=(p-\delta)n$，有 Hoeffding 不等式

$$P(H(n) \leq (p-\delta)n) \leq e^{-2\delta^2n}$$

试推导出式（8.3）

8.2

问：对于 0/1 损失函数来说，指数损失函数并非仅有的一直替代函数，考虑式（8.5），试证明：任意损失函数 $\ell(-f(\mathbf{x}H(\mathbf{x})))$，若对于 $H(\mathbf{x})$ 在区间 $-\inf,\delta$ 上单调递减，则 $\ell$ 是 0/1 损失函数的一致替代函数。

8.3

问：从网上下载或自己编程实现 Adaboost，以不剪枝决策树为基学习器，在西瓜数据集 3.0$\alpha$ 上训练一个 AdaBoost 集成，并与图8.4进行比较。

8.4

问：GradientBoosting 是一种常用的 Boosting 算法，试析其与 AdaBoost 的异同。

8.5

问：试编程实现 Bagging，以决策树桩为基学习器，在西瓜数据集 3.0$\alpha$ 上训练一个 Bagging 集成，并与图8.6进行比较。

8.6

问：试析 Bagging 通常为何难以提升朴素贝叶斯分类器的性能。

8.7

问：试析随即森林为何比决策树 Bagging 集成的训练速度更快。

8.8

问：MultiBoosting 算法将 AdaBoost 作为 Bagging 的基学习器，Iterative Bagging 算法则是将 Bagging 作为 AdaBoost 的基学习器，试比较二者的优缺点。

8.9*

问：试设计一种可视的多样性度量，对习题8.3和习题8.5中得到的集成进行评估，并与 $\kappa$-误差图比较。

8.10*

问：试设计一种能提升 $k$ 近邻分类器性能的集成学习算法。