集成学习

第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)。