# 集成学习

## 第8章 集成学习

* Page171: 多分类器系统(multi-classifier system)

  即集成学习。
* Page171: 个体学习器（individual learner）

  集成学习的一般结构是：先产生一组“个体学习器”，再用某种策略将它们结合起来，个体学习器通常由一个现有的学习算法从训练数据产生。
* Page171: 基学习器(base learner)

  集成中只包含同种类型的个体学习器，这样的集成是同质的。同质集成中的个体学习器亦称“基学习器”，相应的学习算法称为“基学习算法”。
* Page171: 基学习算法(base learning algorithm)

  见基学习器。
* Page171: 集成学习(311)(ensemble learning)

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

  集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能，这对弱学习器尤为明显，基学习器有时也被直接称为弱学习器。
* Page172: AdaBoost

  AdaBoost算法有多种推导方式，比较容易理解的是基于“加性模型”，即基学习器的线性组合

  $$H(x) = \sum\_{t=1}^T \alpha\_t h\_t (x)$$

  来最小化指数损失函数（exponential loss function）

  $$l\_{exp}(H|D) = \mathbb{E}\_{x\~D}\[e^{-f(x)H(x)}]$$
* Page172: 多样性(diversity)

  学习器之间具有差异。
* Page172: 投票法(225)(voting)

  少数服从多数。
* Page173: Boosting(page139)

  Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本在后续收到更多关注，然后基于调整后的样本分布来训练下一个基学习器，如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
* Page173: 加性模型

  见AdaBoost
* Page177: 重采样（re-sampling）

  在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。
* Page177: 重赋权（re-weighting）

  在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重，对无法接受带权样本的基学习算法，则可通过重采样法处理，两种做法没有显著的优劣差别。
* Page178: Bagging（Boostrap AGGregatING）

  Bagging是并行式集成学习方法最著名的代表，基于自助采样法，给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的从未出现。采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这就是Bagging的基本流程。
* Page178: 自助采样法(Boostrap sampling)

  见Bagging。
* Page179: 随机森林（Random Forest，RF）

  是Bagging的一个扩展变体，RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有d个属性）中选择一个最优属性，，而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分，这里的参数k控制了随机性的引入程度：若令k=d，则基决策树的构建与传统决策树相同；若令k=1，则是随机选择一个属性用于划分；一般情况下，推荐$$k=log\_2d$$。
* Page182: 加权平均(225)(weighted averaging)

  假定集成包含T个基学习器$${h\_1,h\_2,...h\_T}$$，其中$$h\_i$$在示例$$x$$上的输出为$$h\_i(x)$$，加权平均结合$$h\_i$$： $$H(x)=\sum\_{i=1}^Tw\_ih\_i(x)$$

  其中$$w\_i$$是个体学习器$$h\_i$$的权重，通常要求$$w\_i\geqq0, \sum\_{i=1}^T=1$$
* Page182: 简单平均(simple averaging)

  $$H(x)=\frac{1}{T}\sum\_{i=1}^Th\_i(x).$$

  符号含义见加权平均。
* Page182: 绝对多数投票(majority voting) 对分类任务来说，学习器$$h\_i$$将从类别标记集合$${c\_1,c\_2,...,c\_N}$$中预测出一个标记，最常见的结合策略是使用投票法，将$$h\_i$$在样本$$x$$上的预测输出表示为一个N维向量$$(h\_i^1(x);h\_i^2(x);...;h\_i^N(x))$$，其中$$h\_i^j(x)$$是$$h\_i$$在类别标记$$c\_j$$上的输出。

  绝对多数投票法: $$\begin{eqnarray}H(x)= \begin{cases} c\_j, \&if \sum\_{i=1}^Th\_i^j(x)>0.5\sum\_{k=1}^N\sum\_{i=1}^Th\_i^k(x)\cr reject, otherwise\end{cases} \end{eqnarray}$$

  即若某标记得票过半数，则预测为该标记；否则拒绝预测。
* Page183: 加权投票(225)（weighted voting）

  $$H(x)=c\_{argmax\_j\sum\_{i=1}^Tw\_ih\_i^j(x)}$$

  与加权平均法类似，$$wi$$是$$h\_i$$的权重，通常$$wi\geq0, \sum\_{i=1}^Tw\_i=1$$.
* Page183: 相对多数投票（plurality votiing）

  $$H(x) = c\_{argmax\_j\sum\_{i=1}^Th\_i^j(x)}$$

  即预测为得票最多的标记，若同时又多个标记获得最高表，则从中随机选取一个，绝对多数投票和相对多数投票统称为多数投票法。
* Page184: Stacking

  一种集成学习方法，先从初始数据集训练出初级学习器，然后生成一个新数据集用于训练次级学习器，在新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当做样例标记。
* Page185: 贝叶斯模型平均（Bayes Model Averaging）

  基于后验概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现，理论上，若数据生成模型恰在当前考虑的模型中，且数据噪声少，则BMA不差于Stacking；然而，在现实应用中无法确保数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来进行近似，因此，Stacking通常优于BMA，更鲁棒，BMA对模型近似误差更敏感。
* Page185: 分歧(304)（ambiguity）

  假定我们用个体学习器$$h\_1,h\_2,...,h\_T$$通过加权平均法结合产生的集成来完成回归学习任务$$f:\mathbb{R}^d\mapsto\mathbb{R}$$，对示例$$x$$，定义学习器$$h\_i$$的“分歧”为：

  $$A(h\_i|x)=(h\_i(x)-H(x))^2$$

  则集成的“分歧”是 $$\overline{A}(h|x) = \sum\_{i=1}^Tw\_iA(h\_i|x) = \sum\_{i=1}^Tw\_i(h\_i(x)-H(x))^2$$

  这里的分歧表征了个体学习器在样本x上的不一致性，在一定程度上反映了个体学习器的多样性。
* Page185: 误差-分歧分解（error-ambiguity decomposition）

  $$E=\overline{E}-\overline{A}$$

  $$E$$: 集成泛化误差，$$\overline{E}$$: 个体学习器泛化误差的加权均值，$$\overline{A}$$表示个体学习器的加权分歧值。这个分解明确提出：个体学习器准确性越高，多样性越大，集成越好。
* Page187: 差异性度量

  同多样性度量。
* Page187: 多样性度量（diversity measure）

  度量集成中个体分类器的多样性，估算个体学习器的多样化程度，典型做法是考虑个体分类器的两两相似/不相似性，常用度量有不合度量，相关系数，Q-统计量，K-统计量
* Page189: 属性子集

  训练样本通常由一组属性描述，不同的子空间（即属性子集）提供了观察数据的不同视角。
* Page189: 随机子空间（random subspace）

  依赖输入属性扰动产生随机的属性子集。
* Page189: 稳定基学习器(stable base learner)

  对数据样本扰动不敏感的学习器，例如线性学习器、支持向量机、朴素贝叶斯，k近邻学习器。
* Page189: 子空间(227)(subspace)

子空间一般指从初始的高维属性空间投影产生的低维属性空间，描述低维空间的属性是通过初始属性投影变换而得，未必是初始属性。

* Page191: 集成修剪(ensemble pruning)

  集成产生之后再视图通过去除一些个体学习器来获得较小的集成，称为集成修剪，有助于减小模型的存储开销和预测时间开销，减小集成规模常导致泛化性能下降，并行化集成进行修剪能在减小规模的同时提升泛化性能，并催生了基于优化的集成修剪技术。
* Page191: 选择性集成(selective emsemble)

  对并行化集成的修剪亦称“选择性集成”，但现在一般将选择性集成用作集成修剪的同义语，亦称集成选择(ensemble selection)。