集成学习笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  本文做一些关于集成学习的的笔记,包括了Boosting算法,Bagging和随机森林。

集成学习(Ensemble Learning)

  所谓的集成学习通过构建并结合多个学习器来完成学习任务,先产生一组个体学习器(individual learner)。如果个体学习器只包含同种类型的个体学习器,称这样的集成是同质的(homogeneous)。反之称为异质的(heterogenous)。同质集成中的个体学习器亦称基学习器(base learner),相应的学习算法称为基学习算法(base learning algorithm),异质集成中的个体学习器常称为组件学习器(component learner)。
  要获得好的集成,个体学习器应“好而不同”,即个体学习器要有一定的“准确性”,学习器不能太坏,并且要有“多样性”(diversity),即学习器间具有差异。
  然而在现实任务中,个体学习器是为解决同一个问题训练出来的,它们显然不可能相互独立,个体学习器的“准确性”和“多样性”本身就存在冲突。一般的,准确性很高之后,要增加多样性就需牺牲准确性。
  如何产生并结合“好而不同”的个体学习器,正是集成学习研究的核心。根据个体学习器的生成方式,目前的集成学习方法大致可分为两大类,即:

  • 个体学习器间存在强依赖关系,必须串行生成的序列化方法,代表是Boosting。
  • 个体学习器间不存在强依赖关系,可同时生成的并行化方法,代表是Bagging和随机森林。

  我们接下来简单的介绍下Boosting和随机森林。

Boosting

  Boosting可将弱学习器提升为强学习器,它先从初试训练集中训练出基学习器,再根据基学习器的表现对训练样本进行调整,使得先前基学习器做错的训练样本在后续受到更多关注,然后基于调整后的样本分布来训练下一个基学习器,最终将这些基学习器进行加权结合。
  Boosting算法要求基学习器能对特定的数据分布进行学习,可通过两种方法:

  • 重赋权法(re-weighting),即在训练过程的每一轮中,根据样本分布为每个训练样本重新赋予一个权重。
  • 重采样法(re-sampling),这种方法针对无法接受带权样本的基学习算法,即在每一轮学习中,根据样本分布对训练集重新进行采样,再用重采样而得的样本集对基学习器进行训练。

  一般而言,这两种做法没有显著的优劣差别。需注意的是,Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件(检查当前基分类器是否是比随机猜测好),一旦条件不满足,则当前基学习器即被抛弃,且学习过程停止。在这种情况下,初始设置的学习轮数也许还远未到,可能导致最终集成中只包含很少的基学习器而性能不佳。若采用重采样法,则可获得重启动机会以避免训练过程过早停止,即在抛弃不满足条件的当前基学习器之后,可根据当前分布重新对训练样本进行采样,再基于新的采样结果重新训练出基学习器,从而使得学习过程可以持续到预设轮次完成。
  从偏差-方差分解的角度看,Boosting主要关注降低偏差,因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

AdaBoost

  Boosting族算法最出名的是AdaBoost,伪代码如下,其中\(y_{i} \in\{-1,+1\}\)

  我们简单的来推导一下,采取加型模型(additive model)的思路来推导一下,即基学习器的线性组合: \[ H(\boldsymbol{x})=\sum_{t=1}^{T} \alpha_{t} h_{t}(\boldsymbol{x}) \]   损失函数采用指数损失函数: \[ \ell_{\exp }(H | \mathcal{D})=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right] \]   对\(H(\boldsymbol{x})\)求偏导,令损失函数最小化: \[ \frac{\partial \ell_{\exp }(H | \mathcal{D})}{\partial H(\boldsymbol{x})}=-e^{-H(\boldsymbol{x})} P(f(\boldsymbol{x})=1 | \boldsymbol{x})+e^{H(\boldsymbol{x})} P(f(\boldsymbol{x})=-1 | \boldsymbol{x}) \]   令偏导为0得: \[ H(\boldsymbol{x})=\frac{1}{2} \ln \frac{P(f(x)=1 | \boldsymbol{x})}{P(f(x)=-1 | \boldsymbol{x})} \]   因此: \[ \begin{aligned} \operatorname{sign}(H(\boldsymbol{x}))&=\operatorname{sign}\left(\frac{1}{2} \ln \frac{P(f(x)=1 | \boldsymbol{x})}{P(f(x)=-1 | \boldsymbol{x})}\right) \\ &=\left\{\begin{array}{ll}{1,} & {P(f(x)=1 | \boldsymbol{x})>P(f(x)=-1 | \boldsymbol{x})} \\ {-1,} & {P(f(x)=1 | \boldsymbol{x})<P(f(x)=-1 | \boldsymbol{x})}\end{array}\right.\\ &=\underset{y \in\{-1,1\}}{\arg \max } P(f(x)=y | \boldsymbol{x}) \end{aligned} \]   因此\(\operatorname{sign}(H(\boldsymbol{x}))\)也达到了贝叶斯最优错误率,也就是说,若指数损失函数最小,则分类错误也将最小。因此指数损失函数是分类任务中原本的0/1损失函数的一致性替代损失函数,而指数损失函数连续可微,具有更好的数学性质,因此我们用指数损失函数来代替0/1损失函数。
  AdaBoost是一个迭代式的算法,不断的迭代生产\(\alpha_t\)\(h_t\),当基学习器\(h_t\)基于分布\(\mathcal{D}_t\)产生后,该基分类器的权重\(\alpha_t\)应使得\(\alpha_t h_t\)最小化指数损失函数: \[ \begin{aligned} \ell_{\exp }\left(\alpha_{t} h_{t} | \mathcal{D}_{t}\right) &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left[e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x})}\right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left[e^{-\alpha_{t}} \mathbb{I}\left(f(\boldsymbol{x})=h_{t}(\boldsymbol{x})\right)+e^{\alpha_{t}} \mathbb{I}\left(f(\boldsymbol{x}) \neq h_{t}(\boldsymbol{x})\right)\right] \\ &=e^{-\alpha_{t}} P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(f(\boldsymbol{x})=h_{t}(\boldsymbol{x})\right)+e^{\alpha_{t}} P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(f(\boldsymbol{x}) \neq h_{t}(\boldsymbol{x})\right) \\ &=e^{-\alpha_{t}}\left(1-\epsilon_{t}\right)+e^{\alpha_{t}} \epsilon_{t} \end{aligned} \]   其中\(\epsilon_{t}=P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(h_{t}(\boldsymbol{x}) \neq f(\boldsymbol{x})\right)\),对损失函数求导: \[ \frac{\partial \ell_{\mathrm{exp}}\left(\alpha_{t} h_{t} | \mathcal{D}_{t}\right)}{\partial \alpha_{t}}=-e^{-\alpha_{t}}\left(1-\epsilon_{t}\right)+e^{\alpha_{t}} \epsilon_{t} \]   令导数为0得: \[ \alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right) \]   在获得\(H_{t-1}\)之后样本分布将进行调整,使下一轮的基学习器\(h_t\)能纠正\(H_{t-1}\)的一些错误,理想的\(h_t\)能纠正\(H_{t-1}\)的所有错误,即最小化: \[ \begin{aligned} \ell_{\exp }\left(H_{t-1}+h_{t} | \mathcal{D}\right) &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x})\left(H_{t-1}(\boldsymbol{x})+h_{t}(\boldsymbol{x})\right)}\right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} e^{-f(\boldsymbol{x}) h_{t}(\boldsymbol{x})}\right] \end{aligned} \]   我们使用泰勒展开式近似为: \[ \begin{aligned} \ell_{\exp }\left(H_{t-1}+h_{t} | \mathcal{D}\right) & \simeq \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h_{t}(\boldsymbol{x})+\frac{f^{2}(\boldsymbol{x}) h_{t}^{2}(\boldsymbol{x})}{2}\right)\right] \\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h_{t}(\boldsymbol{x})+\frac{1}{2}\right)\right](因为f^{2}(\boldsymbol{x})=h_{t}^{2}(\boldsymbol{x})=1) \end{aligned} \]   所以理想的基学习器为: \[ \begin{aligned} h_{t}(\boldsymbol{x}&=\underset{h}{\arg \min } \ell_{\exp }\left(H_{t-1}+h | \mathcal{D}\right) \\ &=\underset{h}{\arg \min } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\left(1-f(\boldsymbol{x}) h(\boldsymbol{x})+\frac{1}{2}\right)\right] \\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \end{aligned} \]   其中\(\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]\)是一个常数,\(\mathcal{D}_{t}\)可表示为一个分布: \[ \mathcal{D}_{t}(\boldsymbol{x})=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} \]   根据数学期望的定义, \[ \begin{aligned} & \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \\=& \sum_{i=1}^{|D|} \mathcal{D}\left(\boldsymbol{x}_{i}\right) \frac{e^{-f\left(\boldsymbol{x}_{i}\right) H_{t-1}\left(\boldsymbol{x}_{i}\right)}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}\left(\boldsymbol{x}_{i}\right)}\right.} f\left(x_{i}\right) h\left(x_{i}\right) \\=& \sum_{i=1}^{|D|} \mathcal{D}_{t}\left(\boldsymbol{x}_{i}\right) f\left(\boldsymbol{x}_{i}\right) h\left(\boldsymbol{x}_{i}\right) \\ =&\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \end{aligned} \]   所以\(h_{t}(\boldsymbol{x})\)等价于: \[ \begin{aligned} h_{t}(\boldsymbol{x}) &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[\frac{e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]} f(\boldsymbol{x}) h(\boldsymbol{x})\right] \\ &=\underset{h}{\arg \max } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \end{aligned} \]   因为\(f(\boldsymbol{x}), h(\boldsymbol{x}) \in\{-1,+1\}\),有: \[ f(\boldsymbol{x}) h(\boldsymbol{x})=1-2 \mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x})) \]   所以理想的基学习器为: \[ h_{t}(\boldsymbol{x})=\underset{h}{\arg \min } \mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[\mathbb{I}(f(\boldsymbol{x}) \neq h(\boldsymbol{x}))] \]   理想的\(h_t\)将在分布\(\mathcal{D}_{t}\)下最小化分类误差,弱分类器将基于分布\(\mathcal{D}_{t}\)来训练,且针对\(\mathcal{D}_{t}\)的分类误差应小于0.5。\(\mathcal{D}_{t}\)\(\mathcal{D}_{t+1}\)的关系有: \[ \begin{aligned} \mathcal{D}_{t+1}(\boldsymbol{x}) &=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \\ &=\frac{\mathcal{D}(\boldsymbol{x}) e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})} e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \\ &=\mathcal{D}_{t}(\boldsymbol{x}) \cdot e^{-f(\boldsymbol{x}) \alpha_{t} h_{t}(\boldsymbol{x})} \frac{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]} \end{aligned} \]   因此AdaBoost的简单推导结束。

Bagging

  Bagging(Bootstrap AGGregatING)是并行式集成学习方法最著名的代表。它基于自助采样法(bootstrap sampling)。给定包含\(m\)个样本的数据集,我们先随机取出一个样本放入采样集中,再把该样本放回初始数据集,使得下次采样时该样本仍有可能被选中,这样,经过\(m\)次随机采样操作,我们得到含\(m\)个样本的采样集,初始训练集中有的样本在采样集里多次出现,有的则从未出现。初始训练集中约有63.2%的样本出现在采样集中。
  因此按照自主采样法的思想,我们可采样出\(T\)个含\(m\)个训练样本的采样集,然后基于每个采样集训练出一个基学习器,再将这些基学习器进行结合。在对预测输出进行结合时,Bagging通常对分类任务使用简单投票法,对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形,最简单的做法是随机选择一个,也可进一步考察学习器投票的置信度来确定最终胜者。算法流程如下:

   与标准AdaBoost只适用于二分类任务不同,Bagging能不经修改地用于多分类、回归等任务。自助采样过程带来的一个优点是:由于每个基学习器只使用了初始训练集中约63.2%的样本,剩下约36.8%的样本可用作验证集来对泛化性能进行包外估计(out-of-bag estimate)。令\(D_t\)表示\(h_t\)实际使用的训练样本集,令\(H^{oob}(\boldsymbol{x})\)表示对样本\(\boldsymbol{x}\)包外预测: \[ H^{o o b}(\boldsymbol{x})=\underset{y \in \mathcal{Y}}{\arg \max } \sum_{t=1}^{T} \mathbb{I}\left(h_{t}(\boldsymbol{x})=y\right) \cdot \mathbb{I}\left(\boldsymbol{x} \notin D_{t}\right) \]   泛化误差的包外估计为: \[ \epsilon^{o o b}=\frac{1}{|D|} \sum_{(\boldsymbol{x}, y) \in D} \mathbb{I}\left(H^{o o b}(\boldsymbol{x}) \neq y\right) \]   从偏差-方差分解的角度看,Bagging主要关注降低方差,因此它在不剪枝见决策树、神经网络等易受样本扰动的学习器上效用更为明显。

包外样本还有许多其他用途。例如当基学习器是决策树时,可使用包外样本来辅助剪枝,或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理。当基学习器是神经网络时,可使用包外样本来辅助早期停止以减小过拟合风险。

随机森林(Random Forest, RF)

  RF是Bagging的一个扩展变体.RF在以决策树为基学习器构建Bagging集成的基础上,进一步在决策树的训练过程中引入了随机属性选择。传统决策树在选择划分属性时是在当前结点的属性集合(假定有\(d\)个属性)中选择一个最优属性,而在RF中,对基决策树的每个结点,先从该结点的属性集合中随机选择一个包含\(k\)个属性的子集,然后再从这个子集中选择一个最优属性用于划分。参数\(k\)控制了随机性的引入程度,一般情况下推荐值\(k = log_2d\)
  随机森林对Bagging只做了小改动,但是与Bagging中基学习器的多样性仅通过样本扰动(通过对初始训练集采样)而来不同,随机森林中基学习器的多样性不仅来自样本扰动,还来自属性扰动,这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
  随机森林的起始性能往往相对较差,特别是在集成中只包含一个基学习器时,因为通过引入属性扰动,随机森林中个体学习器的性能往往有所降低。然而,随着个体学习器数目的增加,随机森林通常会收敛到更低的泛化误差。
  值得一提的是,随机森林的训练效率常优于Bagging,因为在个体决策树的构建过程中,Bagging 使用的是“确定型”决策树,在选择划分属性时要对结点的所有属性进行考察,而随机森林使用的“随机型”决策树则只需考察一个属性子集。

结合策略

  集成学习,也就是结合学习器,学习器结合可能会从三个方面带来好处:

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

  假定集成包含\(T\)个基学习器\(\{h_1,h2,\cdots,h_T\}\),其中\(h_i\)在示例二上的输出为\(h_i(\boldsymbol{x})\),接下来我们介绍几种对\(h_i(\boldsymbol{x})\)进行结合的常见策略。

平均法

  对于数值型输出\(h_{i}(\boldsymbol{x}) \in \mathbb{R}\),最常用平均法。

  • 简单平均法: \[ H(\boldsymbol{x})=\frac{1}{T} \sum_{i=1}^{T} h_{i}(\boldsymbol{x}) \]
  • 加权平均法: \[ H(\boldsymbol{x})=\sum_{i=1}^{T} w_{i} h_{i}(\boldsymbol{x})(通常用求w_{i} \geqslant 0, \sum_{i=1}^{T} w_{i}=1) \]   加权平均法的权重一般是从训练数据中学习而得,现实任务中的训练样本通常不充分或存在噪声,这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说,要学习的权重比较多,较容易导致过拟合.因此,实验和应用均显示出加权平均法未必一定优于简单平均法区。一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近时宜使用简单平均法。

投票法

  对分类任务来说,学习器\(h_i\)将从类别标记集合\(\{c_1,c_2,\cdots,c_N\}\)中预测出一个标记,最常见的结合策略是投票法。记\(h_i\)在样本\(\boldsymbol{x}\)上的预测输出表示为一个\(N\)维向量\(\left(h_{i}^{1}(\boldsymbol{x}) ; h_{i}^{2}(\boldsymbol{x}) ; \ldots ; h_{i}^{N}(\boldsymbol{x})\right)\),其中\(h_i^j(\boldsymbol{x})\)\(h_i\)从在类别标记\(c_j\)上的输出。

  • 绝对多数投票法,若某标记得票过半数,则预测为该标记,否则拒绝预测: \[ H(\boldsymbol{x})=\left\{\begin{array}{ll}{c_{j},} & {\text { if } \sum_{i=1}^{T} h_{i}^{j}(\boldsymbol{x})>0.5 \sum_{k=1}^{N} \sum_{i=1}^{T} h_{i}^{k}(\boldsymbol{x})} \\ {\text { reject, }} & {\text { otherwise. }}\end{array}\right. \]
  • 相对多数投票法,预测为得票最多的标记,若同时有多个标记获最高票,则从中随机选取一个: \[ H(\boldsymbol{x})=c_{\mathrm{arg} \max } \sum_{i=1}^{T} h_{i}^{j}(\boldsymbol{x}) \]
  • 加权投票法 \[ H(\boldsymbol{x})=c_{\underset{j}{\arg \max } \sum_{i=1}^{T} w_{i} h_{i}^{j}(\boldsymbol{x})}(通常用求w_{i} \geqslant 0, \sum_{i=1}^{T} w_{i}=1) \]

  上面三式没有限制个体学习器输出值的类型,而在现实任务中,不同类型个体学习器可能产生不同类型的值,常见的有:

  • 类标记,硬投票,\(h_{i}^{j}(\boldsymbol{x}) \in\{0,1\}\),预测为类别\(c_j\)取值为1,否则为0。
  • 类概率,软投票,\(h_{i}^{j}(\boldsymbol{x}) \in[0,1]\),相当于对后验概率\(P\left(c_{j} | x\right)\)的一个估计。

  不同类型的\(h_i^j(\boldsymbol{x})\)值不能混用.对一些能在预测出类标记的同时产生分类置信度的学习器,其分类置信度可转化为类概率使用。若此类值未进行规范化,例如支持向量机的分类间隔值,则必须使用一些技术如Platt缩放(Platt scaling),等分回归(isotonic regression)等进行校准(calibration)后才能作为类概率使用。虽然分类器估计出的类概率值一般都不太准确,但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。
  需注意的是,若基学习器的类型不同,则同类其类概率值不能直接进行比较。在此种情形下,通常可将类概率输出转化为类标记输出然后再投票。

学习法

  当训练数据很多时,一种更为强大的结合策略是使用学习法,即通过另一个学习器来进行结合。Stacking是学习法的典型代表。我们把个体学习器称为初级学习器,用于结合的学习器称为次级学习器或元学习器(meta-learner)。
  Stacking先从初始数据集训练出初级学习器,然后生成一个新数据集用于训练次级学习器。在这个新数据集中,初级学习器的输出被当作样例输入特征,而初始样本的标记仍被当作样例标记。Stacking的算法描述如下图所示,这里我们假定初级学习器使用不同学习算法产生,即初级集成是异质的。

  在训练阶段,次级训练集是利用初级学习器产生的,若直接用初级学习器的训练集来产生次级训练集,则过拟合风险会比较大。因此,一般是通过使用交叉验证或留一法这样的方式,用训练初级学习器未使用的样本来产生次级学习器的训练样本。以\(k\)折交叉验证为例,初始训练集\(D\)被随机划分为\(k\)个大小相似的集合\(D_1,D_2,\cdots,D_k\)。令\(D_j\)\(\overline{D}_{j}=D \backslash D_{j}\)分别表示第\(j\)折的测试集和训练集。给定\(T\)个初级学习算法,初级学习器\(h_t^{(j)}\)通过在\(\overline{D}_{j}\)上使用第\(t\)个学习算法而得。对\(D_j\)中每个样本\(\boldsymbol{x}_i\),令\(z_{i t}=h_{t}^{(j)}\left(\boldsymbol{x}_{i}\right)\),则由\(\boldsymbol{x}_i\)所产生的次级训练样例的示例部分为\(\boldsymbol{z}_{i}=\left(z_{i 1} ; z_{i 2} ; \ldots ; z_{i T}\right)\),标记部分为\(y_i\)。于是,在整个交叉验证过程结束后,从这\(T\)个初级学习器产生的次级训练集是\(D^{\prime}=\left\{\left(\boldsymbol{z}_{i}, y_{i}\right)\right\}_{i=1}^{m}\),然后\(D^{\prime}\)将用于训练次级学习器。
  次级学习器的输入属性表示和次级学习算法对Stacking集成的泛化性能有很大影响。有研究表明,将初级学习器的输出类概率作为次级学习器的输入属性,用多响应线性回归(Multi-response Linear Regression, MLR)作为次级学习算法效果较好,在MLR中使用不同的属性集更佳。

贝叶斯模型平均(Bayes Model Averaging, BMA)基于后验概率来为不同模型赋予权重,可视为加权平均法的一种特殊实现。理论上来说,若数据生成模型恰在当前考虑的模型中,且数据噪声很少,则BMA不差于Stacking,然而,在现实应用中无法确保数据生成模型一定在当前考虑的模型中,甚至可能难以用当前考虑的模型来进行近似,因此,Stacking通常优于BMA,因为其鲁棒性比BMA更好,而且BMA对模型近似误差非常敏感。

多样性

误差-分歧分解

  假定我们用个体学习器\(h_1,h_2,\cdots,h_T\)通过加权平均法结合产生的集成来完成回归学习任务\(f : \mathbb{R}^{d} \mapsto \mathbb{R}\),对样本\(\boldsymbol{x}\),定义学习器从的分歧(ambiguity)为: \[ A\left(h_{i} | \boldsymbol{x}\right)=\left(h_{i}(\boldsymbol{x})-H(\boldsymbol{x})\right)^{2} \]   则集成的分歧是 \[ \begin{aligned} \overline{A}(h | \boldsymbol{x}) &=\sum_{i=1}^{T} w_{i} A\left(h_{i} | \boldsymbol{x}\right) \\ &=\sum_{i=1}^{T} w_{i}\left(h_{i}(\boldsymbol{x})-H(\boldsymbol{x})\right)^{2} \end{aligned} \]   这里的分歧项表征了个体学习器在样本\(\boldsymbol{x}\)上的不一致性,即在一定程度上反映了个体学习器的多样性。个体学习器\(h_i\)从和集成\(H\)的平方误差分别为: \[ \begin{aligned} E\left(h_{i} | \boldsymbol{x}\right) &=\left(f(\boldsymbol{x})-h_{i}(\boldsymbol{x})\right)^{2} \\ E(H | \boldsymbol{x}) &=(f(\boldsymbol{x})-H(\boldsymbol{x}))^{2} \end{aligned} \]   令\(\overline{E}(h | \boldsymbol{x})=\sum_{i=1}^{T} w_{i} \cdot E\left(h_{i} | \boldsymbol{x}\right)\)表示个体学习器误差的加权均值,有: \[ \begin{aligned} \overline{A}(h | \boldsymbol{x}) &=\sum_{i=1}^{T} w_{i} E\left(h_{i} | \boldsymbol{x}\right)-E(H | \boldsymbol{x}) \\ &=\overline{E}(h | \boldsymbol{x})-E(H | \boldsymbol{x}) \end{aligned} \]   令\(p(x)\)表示样本的概率密度,则在全样本上有: \[ \sum_{i=1}^{T} w_{i} \int A\left(h_{i} | \boldsymbol{x}\right) p(\boldsymbol{x}) d \boldsymbol{x}=\sum_{i=1}^{T} w_{i} \int E\left(h_{i} | \boldsymbol{x}\right) p(\boldsymbol{x}) d \boldsymbol{x}-\int E(H | \boldsymbol{x}) p(\boldsymbol{x}) d \boldsymbol{x} \]   类似的,个体学习器\(h_i\)从在全样本上的泛化误差和分歧项分别为: \[ \begin{aligned} E_{i} &=\int E\left(h_{i} | \boldsymbol{x}\right) p(\boldsymbol{x}) d \boldsymbol{x} \\ A_{i} &=\int A\left(h_{i} | \boldsymbol{x}\right) p(\boldsymbol{x}) d \boldsymbol{x} \end{aligned} \]   集成的泛化误差为: \[ E=\int E(H | \boldsymbol{x}) p(\boldsymbol{x}) d \boldsymbol{x} \]   令\(\overline{E}=\sum_{i=1}^{T} w_{i} E_{i}\)表示个体学习器泛化误差的加权均值,令\(\overline{A}=\sum_{i=1}^{T} w_{i} A_{i}\)表示个体学习器的加权分歧值,将前三式代入上式有: \[ E=\overline{E}-\overline{A} \]   上式也表现出个体学习器准确性越高、多样性越大,则集成越好。上面这个分析也称为误差-分歧分解(error-ambiguity decomposition)。需注意的是,上面的推导过程只适用于回归学习,难以直接推广到分类学习任务上去。

在现实任务中很难直接对\(E=\overline{E}-\overline{A}\)进行优化,不仅由于它们是定义在整个样本空间上,还由于\(\overline{A}\)不是一个可直接操作的多样性度量,它仅在集成构造好之后才能进行估计。

多样性度量(Diversity Measure)

  多样性度量是用于度量集成中个体分类器的多样性,即估算个体学习器的多样化程度。典型做法是考虑个体分类器的两两相似和两两不相似性。
  给定数据集\(D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}\),对二分类任务\(有y_i \in \{-1,1\}\),分类器\(h_i\)\(h_j\)的预测结果列联表(contingency table)为:

  \(h_i=+1\) \(h_i=-1\)
\(h_j=+1\) a c
\(h_j=-1\) b d

  其中\(a+b+c+d=m\),基于这个列联表,给出以下常见的多样性度量。

  • 不合度量(disagreement measure),值域为\([0,1]\),值越大则多样性越大。 \[ d i s_{i j}=\frac{b+c}{m} \]
  • 相关系数(correlation coefficient),值域为\([-1,1]\),若\(h_i\)\(h_j\)无关,为0,正相关值为正,否则为负。 \[ \rho_{i j}=\frac{a d-b c}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} \]
  • \(Q\)-统计量(\(Q\)-statistic),与相关系数\(\rho_{ij}\)的符号相同,且\(|Q_{ij}| \ge |\rho_{ij}|\) \[ Q_{i j}=\frac{a d-b c}{a d+b c} \]
  • \(\kappa\)-统计量(\(\kappa\)-statistic) \[ \kappa=\frac{p_{1}-p_{2}}{1-p_{2}} \]   其中,\(p_1\)是两个分类器取得一致的概率,\(p_2\)是两个分类器偶然达成一致的概率,它们可由数据集\(D\)估算: \[ \begin{aligned} p_{1} &=\frac{a+d}{m} \\ p_{2} &=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^{2}} \end{aligned} \]   若分类器\(h_i\)\(h_j\)\(D\)上完全一致,则\(\kappa=1\)。若它们仅是偶然达成一致则\(\kappa=0\)\(\kappa\)通常为非负值,仅在\(h_i\)\(h_j\)达成一致的概率甚至低于偶然性的情况下取负值。

  以上介绍的都是成对型多样性度量,它们可以容易地通过二维图绘制出来.例如\(\kappa\)-误差图,就是将每一对分类器作为图上的一个点,下图给出了一个例子。显然,数据点云的位置越高,则个体分类器准确性越低。点云的位置越靠右,则个体学习器的多样性越小。

多样性增强(Diversity Enhance)

  在集成学习中需有效地生成多样性大的个体学习器。与简单地直接用初始数据训练出个体学习器相比,如何增强多样性呢?一般思路是在学习过程中引入随机性,常见做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。

  • 数据样本扰动。给定初始数据集,可从中产生出不同的数据子集,再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法,例如在Bagging中使用自助采样,在AdaBoost中使用序列采样。此类做法简单高效,使用最广。对很多常见的基学习器,例如决策树、神经网络等,训练样本稍加变化就会导致学习器有显著变动,数据样本扰动法对这样的不稳定基学习器很有效。然而,有一些基学习器对数据样本的扰动不敏感,例如线性学习器、支持向量机、朴素贝叶斯、\(k\)近邻学习器等,这样的基学习器称为稳定基学习器(stable base learner),对此类基学习器进行集成往往需使用输入属性扰动等其他机制。

  • 输入属性扰动。训练样本通常由一组属性描述,不同的子空间(即属性子集)提供了观察数据的不同视角。显然,从不同子空间训练出的个体学习器必然有所不同。著名的随机子空间(random subspace)算法就依赖于输入属性扰动,该算法从初始属性集中抽取出若干个属性子集,再基于每个属性子集训练一个基学习器,算法描述下图所示。对包含大量冗余属性的数据,在子空间中训练个休学习器不仅能产生多样性大的个体,还会因属性数的减少而大幅节省时间开销,同时,由于冗余属性多,减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性,或者冗余属性很少,则不宜使用输入属性扰动法。

  • 输出表示扰动。此类做法的基本思路是对输出表示进行操纵以增强多样性,可对训练样本的类标记稍作变动,如翻转法(Flipping Output),随机改变一些训练样本的标记。也可对输出表示进行转化,如输出调制法(Output Smearing)将分类输出转化为回归输出后构建个体学习器。还可将原任务拆解为多个可同时求解的子任务,如ECOC法利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。

  • 算法参数扰动。基学习算法一般都有参数需进行设置,例如神经网络的隐层神经元数、初始连接权值等,通过随机设置不同的参数,往往可产生差别较大的个体学习器。例如负相关法(Negative Correlation)显式地通过正则化项来强制个体神经网络使用不同的参数。对参数较少的算法,可通过将其学习过程中某些环节用其他类似方式代替,从而达到扰动的目的,例如可将决策树使用的属性选择机制替换成其他的属性选择机制。使用单一学习器时通常需使用交叉验证等方法来确定参数值,这事实上已使用了不同参数训练出多个学习器,只不过最终仅选择其中一个学习器进行使用,而集成学习则相当于把这些学习器都利用起来。由此也可看出,集成学习技术的实际计算开销并不比使用单一学习器大很多。

  不同的多样性增强机制可同时使用,例如随机森林中同时使用了数据样本扰动和输入属性扰动。

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 集成学习(Ensemble Learning)
  3. 3. Boosting
    1. 3.1. AdaBoost
  4. 4. Bagging
  5. 5. 随机森林(Random Forest, RF)
  6. 6. 结合策略
    1. 6.1. 平均法
    2. 6.2. 投票法
    3. 6.3. 学习法
  7. 7. 多样性
    1. 7.1. 误差-分歧分解
    2. 7.2. 多样性度量(Diversity Measure)
    3. 7.3. 多样性增强(Diversity Enhance)
  8. 8. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...