8 集成学习

集成学习(Ensemble Learning)：是一种机器学习范式，它通过构建并结合多个学习器（也称为基学习器或组件学习器）来完成学习任务。这些学习器可以是从同一种学习算法产生的同质学习器，也可以是从不同学习算法产生的异质学习器。集成学习的核心思想是“好而不同”，即基学习器应该具有好的性能，并且它们之间的预测结果应该具有差异性，以提高整体的泛化性能。一般来讲，集成学习结合后的“学习器”的泛化性能要由于任何一个学习器。

集成学习有时也被称为多分类器系统(Multi-classifier System)、基于委员会的学习(Committee-based Learning)等。

8.1 个体与集成

个体与集成

集成学习的基本结构：先产生一组个体学习器，再使用某种策略将它们结合在一起。若所有的个体学习器都属于同一类别，则称该集成为同质的(Homogeneous)；若个体学习器包含多种类型的学习算法，则称该集成为异质的(Hetergenemous)。

同质集成和异质集成：在同质集成中，个体学习器被称为“基学习器”(Base Learner)，对应的学习算法为“基学习算法”(Base Learning Algorithm)。而在异质集成中，个体学习器称为“组件学习器”(Component Learner)，或直称为“个体学习器”。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”(Weak Learner)尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的。

准确性和多样性

如何获得比最好的单一学习器更好的性能呢？这里，引出了集成学习的两个概念：准确性和多样性。准确性指的是个体学习器不能太差，要有一定的准确度；多样性则是个体学习器之间的输出要具有差异性。一般来说，准确度和差异度都较高的情况下，可以较好地提成集成性能。

分析：

考虑二分类问题$y\in \{-1,+1\}$和真实函数$f$，假定基分类器的错误率为$ϵ$，则对每一个基分类器$h_i$，有：

$$P(h_i(x)\ne f(x))=ϵ$$

假设集成通过简单投票法结合T个基分类器（假设T为奇数），若有超过半数的基分类器正确，则集成分类就正确，即

$$H(x)=\text{sign}(\sum _{i=1}^T{h}_i(x))$$

如果再假设基分类器的错误率互相独立，则由Hoeffding不等式得，集成的错误率为：

$$\begin{array}{rl}P(H(x)\ne f(x))& =\sum _{k=0}^{\lfloor T/2\rfloor }(\genfrac{}{}{0ex}{}{n}{k})(1-e{)}^k{ϵ}^{T-k}\\ & \le \exp (-\frac{1}{2}T(1-2ϵ{)}^2)\end{array}$$

此时，集成器错误率随着基分类器的个数的增加呈指数下降。但前提是基分类器之间相互独立，在实际情形中显然是不可能的，因为这一系列的分类器都是为了解决相同问题而进行训练的，因此在预测新样本时存在着很大的联系。

因此，个体学习器的“准确性”和“差异性”本身就是一对矛盾的变量，准确性高意味着牺牲多样性，所以产生“好而不同”的个体学习器正是集成学习研究的核心。

主流集成学习方法

Boosting, Bagging, 随机森林。

8.2 Boosting

什么是Boosting？

Boosting是一种串行的工作机制，即个体学习器的训练存在依赖关系，必须一步一步序列化进行。其基本思想是：增加前一个基学习器在训练训练过程中预测错误样本的权重，使得后续基学习器更加关注这些打标错误的训练样本，尽可能纠正这些错误，一直向下串行直至产生需要的T个基学习器，Boosting最终对这T个学习器进行加权结合，产生学习器委员会。

AdaBoost: Boosting族的著名算法

• AdaBoosting算法的推导：其有多种推导方式，比较容易理解的是基于“加法模型”，即基学习器的线性组合来最小化指数损失函数。

  $$\begin{array}{rl}H(x)& =\sum _{t=1}^T{\alpha }_t{h}_t(x)\\ {\text{Loss}}_{exp}(h)& ={\mathbb{E}}_{x\sim D,y}\left[e^{-yh(x)}\right]\end{array}$$

  其中，对于指数部分，若打标正确，则为负；反之，则为正。

• 具体来说，整个Adaboost迭代算法分为3步：

  1. 初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。

  2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

  3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。

---

• 流程图如下所示：

8.3 Bagging与随机森林

简介

Bagging和随机森林都是并行式的集成学习方法，即基学习器的训练之间没有前后顺序可以同时进行。上面已经提到，产生“好而不同”的个体学习器是集成学习研究的核心，即在保证基学习器准确性的同时增加基学习器之间的多样性。而这两种算法的基本思想，都是通过“自助采样”的方法来增加多样性。

Bagging

• Bagging (Bootstrap Aggregating)由Breiman在1996年提出，是并行式集成学习方法最著名的代表。这个方法基于自助采样法。

• Bagging使用“有放回”采样的方式选取训练集。对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中有接近36.8%的样本没有被采到。按照相同的方式重复进行，我们就可以采集到T个包含m个样本的数据集，从而训练出T个基学习器，最终对这T个基学习器的输出进行结合。

  为什么是36.8%？

  $$\underset{m\to \mathrm{\infty }}{lim}{(1-\frac{1}{m})}^m=\frac{1}{\mathrm{e}}\approx 0.368$$

• Bagging算法流程如下：

  

  可以看出：

  • Bagging主要通过样本的扰动来增加基学习器之间的多样性，因此Bagging的基学习器应为那些对训练集十分敏感的不稳定学习算法，例如：神经网络与决策树等。
  • 从偏差-方差分解来看，Bagging算法主要关注于降低方差，即通过多次重复训练提高稳定性。
  • 同于AdaBoost的是，Bagging可以十分简单地移植到多分类、回归等问题。总的说起来则是：AdaBoost关注于降低偏差，而Bagging关注于降低方差。

随机森林

• 随机森林 (Random Forest, RF)是由Breiman于2001年提出的一个Bagging的扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

• RF的基学习器固定为决策树，多棵树也就组成了森林，而“随机”则在于选择划分属性的随机，随机森林在训练基学习器时，也采用有放回采样的方式添加样本扰动，同时它还引入了一种属性扰动，即在基决策树的训练过程中，在选择划分属性时，RF先从候选属性集中随机挑选出一个包含K个属性的子集，再从这个子集中选择最优划分属性，一般推荐$K={\log }_{2}d$。

• 这样，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，从而进一步提升了基学习器之间的差异度。相比决策树的Bagging集成，随机森林的起始性能较差（由于属性扰动，基决策树的准确度有所下降），但随着基学习器数目的增多，随机森林往往会收敛到更低的泛化误差。同时不同于Bagging中决策树从所有属性集中选择最优划分属性，随机森林只在属性集的一个子集中选择划分属性，因此训练效率更高。

  

8.4 结合策略

简介

• 学习器结合的好处：
  1. （统计方面）结合多个学习器可以在很大的假设空间上的学习中减小导致泛化性能不佳的风险；
  2. （计算方面）通过多次运行，可以降低陷入比较糟糕的局部极小点的风险；
  3. （表示方面）某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，使用结合多个学习器，有可能学到更好的近似。
• 以下的介绍，都是建立在假定集成包含$T$个基学习器$\{h_1,h_2.\dots ,h_r\}$，其中，$h_i$在示例$x$上的输出为$h_i(x)$的基础上的。

常见策略

平均法（回归问题）

• 对数值型输出$h_i(x)\in \mathbb{R}$，最常见的结合策略是使用平均法(averaging)。其中，有简单平均法和加权平均法。

$$H(x)=\sum _{i=1}^T{w}_i{h}_i(x),w_i\ge 0,\sum w_i=1$$

• 易知简单平均法是加权平均法的一种特例，加权平均法可以认为是集成学习研究的基本出发点。由于各个基学习器的权值在训练中得出，一般而言，在个体学习器性能相差较大时宜使用加权平均法，在个体学习器性能相差较小时宜使用简单平均法。（现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。）

投票法 （分类问题）

• 绝对多数投票法 (Majority Voting)：

$$H(x)=\{\begin{array}{ll}{c}_j,& \text{ if }\sum _{i=1}^T{h}_i^j(x)>0.5\sum _{k=1}^N\sum _{i=1}^T{h}_i^k(x)\\ \text{ reject, }& \text{ otherwise. }\end{array}$$

• 绝对多数投票法提供了拒绝选项，这在可靠性要求很高的学习任务中是一个很好的机制。
• 相对多数投票法 (Plurality Voting)：

$$H(x)=c\arg \underset{j}{max}\sum _{i=1}^T{h}_i^j(x)$$

• 加权投票法 (Weighted Voting)：（其中，$w_i$是权重。）

$$H(x)=c\arg \underset{j}{max}\sum _{i=1}^T{w}_i{h}_i^j(x)$$

• 对于分类任务，各个基学习器的输出值有两种类型，分别为类标记和类概率。
  • 类标记：$h_i^j(x)=\{0,1\}$，若$h_i$将样本$x$预测为$c_j$则取值为1，否则为0。使用此类型的投票方法称为“硬投票”。
  • 类标记：$h_i^j(x)=(0,1)$，相当于对后验概率$P(c_j\mid x)$的一个估计使用此类型的投票方法称为“软投票”。
• 一些在产生类别标记的同时也生成置信度的学习器，置信度可转化为类概率使用，一般基于类概率进行结合往往比基于类标记进行结合的效果更好，需要注意的是对于异质集成，其类概率不能直接进行比较，此时需要将类概率转化为类标记输出，然后再投票。

学习法

学习法是一种更高级的结合策略，即学习出一种“投票”的学习器，Stacking是学习法的典型代表。Stacking的基本思想是：首先训练出T个基学习器，对于一个样本它们会产生T个输出，将这T个基学习器的输出与该样本的真实标记作为新的样本，m个样本就会产生一个$m\times T$的样本集，来训练一个新的“投票”学习器。投票学习器的输入属性与学习算法对Stacking集成的泛化性能有很大的影响，书中已经提到：投票学习器采用类概率作为输入属性，选用多响应线性回归（MLR）一般会产生较好的效果。

8.5 多样性

误差——分歧分解

• 然而，我们很难甚至不能对$E=\bar{E}-\bar{A}$作为优化目标来求解，不仅由于于它们是定义在整个样本空间上，还由于$\bar{A}$不是一个可直接操作的多样性度量，它仅在集成构造好之后才能进行估计。
• 此外，上述的内容只能用在回归学习上，不能推广到分类学习任务上去。

多样性度量

• 多样性度量(Diversity Measure)是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度。典型做法是考虑个体分类器的两两相似/不相似性。
• 常见的“成对型”多样性度量：
  • 不合度量
  • 相关系数
  • Q-统计量
  • $\kappa$-统计量

多样性增强

在集成学习中，基学习器之间的多样性是影响集成器泛化性能的重要因素。因此增加多样性对于集成学习研究十分重要，一般的思路是在学习过程中引入随机性，常见的做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

数据样本扰动，即利用具有差异的数据集来训练不同的基学习器。例如：有放回自助采样法，但此类做法只对那些不稳定学习算法十分有效，例如：决策树和神经网络等，训练集的稍微改变能导致学习器的显著变动。

输入属性扰动，即随机选取原空间的一个子空间来训练基学习器。例如：随机森林，从初始属性集中抽取子集，再基于每个子集来训练基学习器。但若训练集只包含少量属性，则不宜使用属性扰动。

输出表示扰动，此类做法可对训练样本的类标稍作变动，或对基学习器的输出进行转化。

算法参数扰动，通过随机设置不同的参数，例如：神经网络中，随机初始化权重与随机设置隐含层节点数。