第八章 集成学习

8.1 个体与集成

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

  

  • 先产生一组“个体学习器”（individual learner），再用某种策略将它们结合起来。
  • 个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5决策树算法、BP神经网络算法等。
  • 同质（homogeneous）集成：集成中只包含同种类型的个体学习器（亦称“基学习器”base learner），例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络。相应的学习算法称为“基学习算法”（base learning algorithm）
  • 异质（heterogeneous）集成：集成中包含不同类型的个体学习器（称为“组件学习器”component learner）。

• 集成学习通过将多个学习器进行结合，长可获得比单一学习器显著优越的泛化性能。

• 要获得好的集成效果，个体学习器应“好而不同”，即个体学习器要有一定的准确性，即学习器不能太坏，并且要有多样性（diversity），即学习器之间具有差异。

• 在现实中，个体学习器的“准确性”和“多样性”本身存在冲突。

  • 准确性很高之后，要增加多样性就要牺牲准确性
  • 如何产生“好而不同”的个体学习器，是集成学习研究的核心。

• 集成学习方法大致分为两大类：

  • 序列化方法：个体学习器间存在强依赖关系、必须串行生成。代表为Boosting
  • 并行化方法：个体学习器间不存在强依赖关系，可同时生成。代表为Bagging和“随机森林”（Random Forest）。

8.2 Boosting

• Boosting是一族可将弱学习器提升为强学习器的算法。

  • 先从初始训练集训练出一个基学习器；
  • 根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
  • 基于调整后的训练样本来训练下一个基学习器；
  • 如此重复，直至基学习器书目达到事先指定的值T，最终将T个基学习器进行加权结合。

• AdaBoost算法，基于“加性模型”，即基学习器的线性组合来最小化指数损失函数（exponential loss function）。

  • 基学习器的线性组合：$H(x)=\sum_{t=1}^T\alpha_th_t(x)$
  • 指数损失函数：$l_{exp}(H\mid D)=E_{x\sim D}[e^{-f(x)H(x)}]$

  

  • $sign(H(x))=sign(\frac12ln\frac{P(f(x)=1\mid x)}{P(f(x)=-1\mid x)})=\begin{cases}1,&P(f(x)=1\mid x)>P(f(x)=-1\mid x)\ -1,&P(f(x)=1\mid x)<P(f(x)=-1\mid x)\end{cases}=\mathop{argmax}\limits_{y\in{-1,1}}P(f(x)=y\mid x)$

    • 若指数损失函数最小化，则分类错误率也将最小化。指数损失函数是分类任务原本0/1损失函数的一致的（consistent）替代损失函数。

• Boosting主要关注降低偏差，能给予泛化性能相当弱的学习器构建出很强的集成。

8.3 Bagging与随机森林

• 欲得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立；
• 虽然“独立”在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异。

8.3.1 Bagging

• Bagging是并行式集成学习方法最著名的代表，直接基于自助采样法。
  • 给定包含$m$个样本的数据集
  • 先随机取出一个样本放入采样集
  • 再把该样本放回初始数据集，使得下次采样该样本仍有可能被选中。
  • 经过$m$次随机采样操作，得到含$m$个样本的采样集。初始训练集中有63.2%的样本出现在采样集中。
  • 采样出$T$个含$m$个训练样本的采样集，然后基于每个采样集训练出一个学习器，再将这些基学习器进行结合。
• 在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜者。

8.3.2 随机森林

• 随机森林（Random Forest）是Bagging的一个扩展变体。
  • RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。
  • 传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；
  • 在RF中，对基决策树的每个结点，先从该结点的属性集合中（假定有$d$个属性）随机选择一个包含$k$个属性的子集，然后再从这个子集中选择一个最优属性用于划分。
  • $k$控制了随机性的引入程度：若$k=d$，则基决策树与传统决策树相同；若$k=1$，则是随机选择一个属性用于划分；一般情况下，推荐$k=log_2d$
• 随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
• 随机森林的起始性能往往相对较差。随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差。
  • 随机森林的训练效率常优于Bagging。

8.4 结合策略

• 学习器结合可能带来的好处：

  • 从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器会减小这一风险；
  • 从计算的角度看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟糕，通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险；
  • 从表示的方面看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，通过结合多个学习器，相应的假设空间有所扩大，可能学的更好的近似。

  

• 假定集成包含$T$个基学习器${h_1,h_2,…,h_T}$，其中$h_i$在示例$x$上的输出为$h_i(x)$。

8.4.1 平均法

• 简单平均法（simple averaging）：$H(x)=\frac1T\sum_{i=1}^Th_i(x)$
• 加权平均法（weighted averaging）：$H(x)=\sum_{i=1}^Tw_ih_i(x)$，其中$w_i$是个体学习器$h_i$的权重，通常$w_i\geq 0，\sum_{i=1}^Tw_i=1$
  • 权重一般在训练数据中学习而得。
• 个体学习器性能相差较大时使用加权平均法，个体学习器性能相近时宜使用简单平均法。

8.4.2 投票法

• 将$h_i$在样本$x$上的预测输出表示为一个$N$维向量$(h_i^1(x);h_i^2(x);…;h_i^N(x))$，其中$h_i^j(x)$是$h_i$在类别标记$c_j$上的输出。
• 绝对多数投票法（majority voting）：$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);\ reject,&otherwise\end{cases}$，即若某标记得票超过半数，则预测为该标记；否则拒绝预测。
• 相对多数投票法（plurality voting）：$H(x)=c_{\mathop{arg max}\limits_j\sum_{i=1}^Th_i^j(x)}$，即预测为得票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。
• 加权投票法（weighted voting）：$H(x)=c_{\mathop{arg max}\limits_j\sum_{i=1}^Tw_ih_i^j(x)}$。
• 投票法没有限制个体学习器输出值的类型，现实任务中，根据不同类型的个体学习器产生的$h_i^j(x)$值：
  • 类标记：$h_i^j(x)\in{0,1}$，硬投票；
  • 类概率：$h_i^j(x)\in[0,1]$，软投票。
• 不同类型的$h_i^j(x)$不能混用。

8.4.3 学习法

• 个体学习器为初级学习器；用于结合的学习器称为次级学习器或元学习器（meta-learner）
• Stacking算法先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在新数据集中，初级学习器的输出被当作样例输入特征，初始样本的标记仍被当做样例标记。
  • 在训练阶段，次级训练集是利用初级学习器产生的。若直接用初级学习器的训练集来产生次级训练集，则过拟合的风险比较大。

8.5 多样性

8.5.1 误差—分歧分解

• 构建泛化能力强的集成，个体学习器应“好而不同”。
• 假定我们用个体学习器$h_1,h_2,…,h_r$通过加权平均法结合产生的集成来完成回归学习任务$f:R^d→R$，对示例$x$，定义学习器$h_i$的“分歧”（ambiguity）为：\(A(h_i\mid x)=(h_i(x)-H(x))^2\)，则集成的“分歧”为：\(\bar A(h\mid x)=\sum_{i=1}^Tw_iA(h_i\mid x)=\sum_{i=1}^Tw_i(h_i(x)-H(x))^2\)
• “分歧”项表征了个体学习器在样本$x$上的不一致性，即在一定程度上反映了个体学习器的多样性。
• 个体学习器$h_i$的平方误差：$E(h_i\mid x)=(f(x)-h_i(x))^2$
• 集成$H$的平方误差：$E(H\mid x)=(f(x)-H(x))^2$
• 令$\bar E(h\mid x)=\sum_{i=1}^Tw_i·E(h_i\mid x)$表示个体学习器误差的加权均值，有\(\bar A(h\mid x)=\sum_{i=1}^Tw_iE(h_i\mid x)-E(H\mid x)=\bar E(h\mid x)-E(H\mid x)\)
  • 令$p(x)$表示样本的概率密度，在全样本上有：$\sum_{i=1}^Tw_i\int A(h_i\mid x)p(x)dx=\sum_{i=1}^Tw_i\int E(h_i\mid x)p(x)dx-\int E(H\mid x)p(x)dx$
  • 个体学习器$h_i$在全样本上的泛化误差和分歧项分别为：
    • $E_i=\int E(h_i\mid x)p(x)dx$
    • $A_i=\int A(h_i\mid x)p(x)dx$
  • 集成的泛化误差为：$E=\int E(H\mid x)p(x)dx$
• 误差—分歧分解（error-ambiguity decomposition）：个体学习器准确性越高、多样性越大，则集成越好。
• 现实任务中很难直接对$\bar E-\bar A$进行优化。

8.5.2 多样性度量

• 多样性度量（diversity measure）：是用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度。典型做法：考虑个体分类器的两两相似/不相似性。
• 给定数据集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，对二分类任务，$y_i\in{-1,+1}$，分类器$h_i$与$的预测结果列联表（contingency table）为：

• $a$表示$h_i$与$h_j$均预测为正类的样本数目，$a+b+c+d=m$，基于这个列联表，可以得到：

8.5.3 多样性增强

• 增强多样性的一般思路是在学习过程中引入随机性，常见做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

• 数据样本扰动：

  • 基于采样法。在Bagging中使用自主采样，在AdaBoost中使用序列采样。
  • 数据样本扰动法对“不稳定基学习器”很有效；
  • “稳定基学习器”，例如线性学习期、支持向量机、朴素贝叶斯、k近邻学习器集成时需要使用输入属性扰动等其他机制。

• 输入属性扰动

  • 训练样本通常由一组属性描述，不同的“子空间”（subspace，属性子集）提供了观察数据的不同视角。
  • “随机子空间”（random subspace）依赖输入属性扰动：该算法从初始属性集中抽取若干个属性子集，再基于每个属性子集训练一个基学习器。
  • 若数据只包含少量属性，或者冗余属性很少，不宜用输入属性扰动法。

• 输出表示扰动

  • 对训练样本的标记稍作变动。
  • “输出调制法”（Output Smearing）将分类输出转化为回归输出后构建个体学习器，还可将原任务拆解为多个可同时求解的子任务。
  • ECOC法利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。

• 算法参数扰动

  • 随机设置基学习算法的参数，以产生差别较大的个体学习器。

  • “负相关法”（Negative Correlation）显式地通过正则化项来强制个体神经网络使用不同的参数。

• Previous
  第七章 贝叶斯分类器
• Next
  第九章 聚类