Machine Learning

集成学习介绍

集成学习介绍

Posted by Jinliang on June 13, 2019

1. 集成学习介绍

集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统、基于委员会的学习等。

首先介绍集成学习的组成结构：

image-20190609220937186

如上图所示，先产生一组个体学习器，然后基于某种策略将他们组合起来。

根据个体学习器之间的关系可以将集成学习分成两类：

  • 同质

    个体学习器属于同一种类型

    其中的个体学习器称为基学习器，相应的学习算法称为基学习算法

  • 异质

    个体学习器属于不同类型

    相应的个体学习器称为组件学习器。

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

下面我们来探究集成学习是如何获得比个体学习器更好的性能的：

首先对我们的个体学习器提出要求，我们的个体学习器最起码不差于弱学习器(正确率略高于50%)，并且要有多样性(一模一样的学习器对于集成学习来说没有效果)

通过公式进行简单的分析：

目前有一个二分类问题$y\in {-1,1}$和真是函数f，假定基分类器的错误率是$\epsilon$，对每个分类器$h_i$有：

\[P(h_i(x)\neq f(x))=\epsilon \tag{1-1}\]

假设我们集成学习器采取的策略是简单投票发(少数服从多数)，我们现在有T个基分类器，若产过半数的基分类器判别正确，那么集成分类判别就为正确：

\[H(x)=sign\left(\sum_{i=1}^Th_i(\textbf x)\right)\tag{1-2}\]

假定我们的基分类器的错误率是相互独立的，通过Hoeffding不等式得出，集成的错误率为：

\[\begin{align} P(H(x)\neq f(x))&=\sum_{k=0}^{\lfloor T/2 \rfloor}\begin{pmatrix}T\\ k\end{pmatrix} (1-\epsilon)^k\epsilon^{T-k}\\ &\leq\exp\left(-\frac{1}{2}T(1-2\epsilon)^2\right) \end{align}\tag{1-3}\]

证明如下：

由基分类器相互独立，设X为T个基分类器分类正确的次数，因此$\mathrm{X} \sim \mathrm{B}(\mathrm{T}, 1-\mathrm{\epsilon})$，则：

\[\begin{aligned} P(H(x) \neq f(x))&= P(X \leq\lfloor T / 2\rfloor) \\ & \leqslant P(X \leq T / 2) \\ & =P\left[X-(1-\varepsilon) T \leqslant \frac{T}{2}-(1-\varepsilon) T\right] \\ & =P\left[X- (1-\varepsilon) T \leqslant -\frac{T}{2}\left(1-2\varepsilon\right)]\right] \end{aligned}\tag{1-4}\]

根据Hoeffding不等式: \(P(X-(1-\epsilon)T\leqslant -kT) \leq \exp (-2k^2T)\tag{1-5}\) 令$k=\frac {(1-2\epsilon)}{2}$，公式1-4为：

\[\begin{aligned} P(H(\boldsymbol{x}) \neq f(\boldsymbol{x})) &=\sum_{k=0}^{\lfloor T / 2\rfloor} \left( \begin{array}{c}{T} \\ {k}\end{array}\right)(1-\epsilon)^{k} \epsilon^{T-k} \\ & \leqslant \exp \left(-\frac{1}{2} T(1-2 \epsilon)^{2}\right) \end{aligned} \tag{1-6}\]

公式1-3显示，随着集成中个体分类器数目T的增大，集成的错误率将成指数级下降，最终趋近于0.

貌似上面的结论很好，但是不要忘记了我我们最初的假设：基学习器的误差相互独立。

但是在现实任务中，个体学习器是为解决同一问题训练出来的，它们显然不可能相互独立。实际上，个体学习器的准确性和多样性本身存在冲突，准确性很高，想要增加多样性势必要牺牲准确性。

因此集成学习的核心是：如何产生并结合好而不同的个体学习器

前面根据个体学习器之间关系我们将集成学习进行了分类，现在我们根据个体学习器的生成方式，将集成学习从不同的角度分类：

  • 序列化方法

    个体学习器存在强依赖关系、必须串行生成的序列化方法

    代表是Boosting

  • 并行化方法

    个体学习器间不存在强依赖关系、可同时生成的并行化方法

    代表是”随机森林”

2. Boosting

Boosting是一族可将弱学习器提升为强学习器的算法(当然如此了，这是集成学习的概念，Boosting是集成学习的一种)

工作机制：

先从初始训练集训练处一个基学习器，再根据基学习器对训练样本进行调整，使得先前基学习器做错的训练样本在后续训练中更受关注，然后基于调整后的训练样本训练下一个基学习器；重复上述步骤，直至基学习器的数量达到指定值，最终将所训练的基学习器进行加权结合。

通过上述工作步骤，可以发现基学习器的训练时串行的，即后面的基学习器的训练时依赖先前基学习器的训练的。

Boosting算法中最著名的是AdaBoost，算法伪代码如下：

image-20190610212402663

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

\[H(\textbf x)=\sum_{t=1}^Ta_th_t(\textbf x)\tag{2-1}\]

来最小化指数损失函数：

\[\begin{aligned} \ell_{\mathrm{exp}}(H | \mathcal{D})=&\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right] \\ =&P(f(x)=1|x)*e^{-H(x)}+P(f(x)=-1|x)*e^{H(x)} \end{aligned} \tag{2-2}\]

若$H(x)$可以使损失函数最小化，首先计算损失函数对$H(x)$的偏导：

\[\frac{\partial \ell_{\exp}(H \mid D)}{\partial H(\textbf x)}=-e^{-H(\textbf x)}p(f(\textbf x)=1 \mid \textbf x)+e^{H(\textbf x)}p(f(\textbf x)=-1 \mid \textbf x)\tag{2-3}\]

令偏导为0，即公式2-3为0可解的：

\[H(\textbf x)=\frac{1}{2}\ln\frac{p(f(\textbf x)=1 \mid \textbf x)}{p(f(\textbf x)=-1 \mid \textbf x)}\tag{2-4}\]

最终的集合分类器为：

\[\begin{align} \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) \\ & = \begin{cases} {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{cases}\\ & =\underset{y \in{-1,1}}{\arg \max } P(f(x)=y | \boldsymbol{x}) \end{align}\tag{2-5}\]

根据贝叶斯最优错误率公式，可知$\operatorname{sign}(H(\boldsymbol{x}))$达到了贝叶斯最优错误率。即损失函数最小，则分类错误率也将最小。

根据以上证明，我们来分析AdaBoost的伪代码：

首先在AdaBoost算法中，第一个基分类器$h_1$直接通过初始训练集训练基学习算法；此后迭代的生成$h_t$和$a_t$，当基分类器$h_t$基于分布$D_t$产生后，该基分类器的权重$a_t$应该使$a_th_t$最小化指数损失函数(可以理解为找到一个合适的权值，使得$a_th_t$能够达到贝叶斯最优分类器的效果)

\[\begin{align} \ell_{\exp}(a_th_t \mid D_t)&=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right]\\ &=\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-a_t}\Bbb I(f(x)=h_t(x))+e^{a_t}\Bbb I(f(x)\not=h_t(x))\right]\\ &=e^{-a_t}P_{\textbf x \sim D_t}(f(x)=h_t(x))+e^{a_t}P_{\textbf x \sim D_t}(f(x)\not=h_t(x))\\ &=e^{-a_t}(1-\epsilon _t)+e^{a_t}\epsilon_t \end{align}\tag{2-6}\]

公式2-6中，$\epsilon t=P{\textbf x \sim D_t}(f(x)\not =h_t(x))$.

计算此时指数损失函数的导数：

\[\frac{\partial \ell_{\exp}(a_th_t \mid D)}{\partial a_t}=-e^{-a_t}(1-\epsilon _t)+e^{a_t}\epsilon_t \tag{2-7}\]

令导数2-7为0，可得：

\[a_t=\frac{1}{2}\ln \frac{1-\epsilon_t}{\epsilon_t}\tag{2-8}\]

公式2-8求得的a_t即使能够使h_t满足最小化指数损失函数的公式，在AdaBoost的伪代码中，权重也是这样计算的。

下面来分析怎样对样本分布进行调整。

AdaBoost算法在获得$H_{t-1}$之后样本分布将进行调整，使下一轮的基学习器$h_t$能纠正$H_{t-1}$的错误。理想情况下，$h_t$能纠正$H_{t-1}$的全部错误，即最小化：

\[\begin{aligned} \ell_{\mathrm{exp}}(H_{t-1}+h_t | \mathcal{D})=&\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) (H_{t-1}(\boldsymbol{x})+h_t(\boldsymbol{x}))}\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} \tag{2-9}\]

因为预测结果和真实结果为$y\in {-1,1}$，因此$f^2(\textbf x)=h_t^2(\textbf x)=1$，对公式2-9中$e^{-f(\textbf x) h_t(\textbf x)}$的泰勒展开近似为：

\[\begin{aligned} \ell_{\mathrm{exp}}(H_{t-1}+h_t | \mathcal{D})&\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]\\ \end{aligned} \tag{2-10}\]

因此，理想的学习器：

\[\begin{align} h_t(\textbf x)&=\underset h{\arg\max}\ell_{\mathrm{exp}}(H_{t-1}+h | \mathcal{D})\\ &=\underset h{\arg\max}\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{align}\tag{2-11}\]

公式2-11中，$\mathbb{E}{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H{t-1}(\boldsymbol{x})}\right]$是一个常数。

我们令$\cal D_t$表示一个分布:

\[\tag{2-12} \cal D_t=\frac{\cal D(\textbf x)e^{-f(\textbf x) H_{t-1}(\boldsymbol{x})}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}\right]}\]

假设$x$的概率分布是f(x) (注:本书中概率分布全都是)$\mathcal{D(x)}$:

\[\mathbb{E(g(x))}=\sum_{i=1}^{|D|}f(x)g(x)\tag{2-13}\]

因此：

\[\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H(\boldsymbol{x})}\right]=\sum_{i=1}^{|D|} \mathcal{D}\left(\boldsymbol{x}_{i}\right) e^{-f\left(\boldsymbol{x}_{i}\right) H\left(\boldsymbol{x}_{i}\right)}\tag{2-14}\]

根据上述公式，继续对2-11进行求解：

\[\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}(\boldsymbol{x}) }] \right.}f(x_i)h(x_i) \\ =& \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}\tag{2-15}\]

完整的公式为：

\[h_t(\textbf x)=\underset h{\arg\max}\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[f(\boldsymbol{x}) h(\boldsymbol{x})] \tag{2-16}\]

又因为$f(\textbf x),h(\textbf x)\in {-1,+1}$，于是：

\[f(\textbf x)h(\textbf x)=1-2\Bbb I(f(\textbf x) \not=h(\textbf x))\tag{2-17}\]

进一步化简公式2-16：

\[h_t(\textbf x)=\underset h{\arg\min}\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}_{t}}[\Bbb I(f(\textbf x) \not=h(\textbf x))] \tag{2-18}\]

通过公式2-18，可以发现理想的$h_t$将在分布$\cal D_t$下最小化分类误差。

因此，弱分类器将基于分布 $\cal D_t$来训练，且针对$cal D_t$的分类误差应小于0.5，这在一定程度上类似”残差逼近”的思想。

我们来计算一下$\cal D_t$和$\cal D_{t+1}$的关系：

\[\begin{align} \cal D_{t+1}(\textbf x)&=\frac{\cal D(\textbf 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{\cal D(\textbf x)e^{-f(\boldsymbol{x}) H_{t-1}(\boldsymbol{x})}e^{-f(\textbf x)a_th_t(\textbf x)}}{\mathbb{E}_{\boldsymbol{x} \sim \mathcal{D}}\left[e^{-f(\boldsymbol{x}) H_{t}(\boldsymbol{x})}\right]}\\ &= \cal D_t(x)\cdot e^{-f(\textbf x)a_th_t(\textbf 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{align}\tag{2-19}\]

公式2-19就是AdaBoost伪代码中的样本分布更新公式。

以上，通过公式2-8和公式2-19，我们从基于加性模型迭代式优化指数损失函数的角度推导出AdaBoost算法的伪代码流程。

根据基学习器能够对特定的数据分布进行学习，将Boosting分为两种：

  • 重赋权法

    根据样本分布为每个训练样本重新赋予权重

  • 重采样法

    根据训练分布对训练样本进行采样，适应采样的样本对训练集进行训练

上述两种方法没有明显的优劣差别(实现方式不一样而已)。

但是在训练过程中，会判断当前的基学习器是否满足条件(例如AdaBoosting算法判断是否比随机的好)，不满足条件则停止训练，这种情况下，因为基学习器较少使得集成学习器性能不佳。但是采用重采样法则可获得”重启动”的机会以避免训练过早停止(因为重采样没有改变训练集，所以可以实现continue的效果)

从偏差-方差的角度来看，Boosting方法关注降低偏差，因此它能够基于泛化能力弱的学习器构建出很强的集成。

3. Bagging

第二小节讲了Boosting算法，即串行式集成学习。本小节我们讲并行式集成学习。

Bagging是并行式集成学习方法最著名的代表，它是基于自助采样法实现的。

看一下Bagging的简单流程：给定包含m个样本的训练集，我们首先随机选择一个样本放入采样集中，再把样本放回训练集中，使得下次采样仍有可能被选择到，经过m次随机选择，获取到包含m个样本的采样集（有重复的样本）。我们按照上述方法采样T个采样集，然后基于每个采样集进行基学习器的训练，最后将这些基学习器结合。

在对预测输出进行结合时，即集成的策略，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。

下面看一下Bagging的伪代码：

image-20190612001508062

假设基学习器的计算复杂度为$O(m)$，那么Bagging的复杂度大致为$T(O(m)+O(s))$，$O(s)$代表采样与投票/平均的时间复杂度，由于$O(s)$很小，T通常不是很大，因此，训练一个Bagging算法与直接使用基学习算法训练一个学习器的复杂度同阶，所以Bagging是一个很高效的集成学习算法。

Boosting算法与AdaBoost算法的不同在于Boosting算法能直接用于多分类和回归任务，AdaBoost仅适用于二分类。

由于我们的基学习器学习时，采样集仅使用了训练集中63.2%的样本，剩下的样本可以用作验证集对泛化性能进行”包外估计”

我们使用验证样本对基学习器进行包外估计：

\[H^{oob}(\textbf x)=\underset {y\in \cal Y}{\arg\max}\sum_{t=1}^T\Bbb I(h_t(\textbf x)=y) \cdot \Bbb I(\textbf x \notin D_t) \tag{3-1}\]

则包外估计的泛化误差为：

\[\epsilon ^{oob}=\frac{1}{\mid D\mid}\sum_{(\textbf x,y)\in D}\Bbb I(H^{oob}(\textbf x)\notin y)\tag{3-2}\]

包外估计除了计算泛化误差外，还有其他的用途：

  • 当基学习器是决策树时，使用包外估计辅助剪枝
  • 当基学习器是神经网络时，使用包外估计早期停止防止过拟合

从偏差-方差的角度来看，Bagging主要用于降低方差，因此在不剪枝决策树、神经网络等易受样本扰动的学习器效果更明显。

4. 随机森林

随机森林(Random Forst，简称RF)是Bagging的一个扩展变体。

RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体来说，传统的决策树在选择划分属性时，是在当前节点的属性集合中选择最优属性；但是在RF中，对基学习器的每个节点，先从该节点的属性集合中随机选择一个包含$k$个属性的子集，然后从子集中选择一个最优属性用于划分。

这里的参数$k$控制了随机性的引入程度：若$k=d$，则基决策树的构建与传统决策树相同；若$k=1$，则基学习器完全是随机选择最优属性；一般情况下，推荐值$k=\log _2d$。

通过上述的描述，随机森林简单、容易实现、计算开销小。但是效果却很好，被誉为”代表集成学习技术水平的方法”。

随机森林在Bagging算法上做了一个小改动，但是在Bagging算法通过样本扰动多样性之外，随机森林增加了属性扰动，是的基学习器的多样性进一步增加。

由于Bagging算法是在样本的所有属性中选择最优属性，但是随机森林在属性子集中选择最优属性，所以通常来说，随机森林的训练效率要高于Bagging算法。

5. 结合策略-平均法

对数值类型的输出，即$h_i(\textbf x)\in \Bbb R$，最常见的结合策略是使用平均法。

  • 简单平均法

    \[H(\textbf x)=\frac{1}{T}\sum_{i=1}^Th_i(\textbf x) \tag{5-1}\]

  • 加权平均法

​ \(H(\textbf x)=\frac{1}{T}\sum_{i=1}^Tw_ih_i(\textbf x) \tag{5-2}\)

公式5-2中，$w_i$表示基学习器的权重，通常要求$w_i \geq 0$，$\sum_{i=1}^T=1$

简单平均法是加权平均法的特例，加权平均法的权重一般从训练数据中学习而得，但是由于训练样本不充分或存在噪声，使得学习的权重不可靠，而且在规模比较大的集成中，要学习的权重很多，容易导致过拟合，所以有时候，简单平均法的性能会优于加权平均法。

一般来说，在个体学习器相差较大的时候宜使用加权平均法，在相差不大时宜使用简单平均法。

6. 结合策略-投票法

对分类任务来说，最常见的结合策略是投票法。

  • 绝对多数投票法

​ \(H(\textbf x)= \begin{cases} c_j, \qquad \qquad if \; \sum_{i=1}^Th_i^j(\textbf x) > 0.5\sum_{k=1}^N\sum_{i=1}^Th_i^k;\\ reject \qquad \qquad otherwise. \end{cases}\tag{6-1}\) ​

​ 公式6-1所示，得票数过所有票数的一半，则预测为该标记，否则拒绝预测

  • 相对多数投票法

​ \(H(\textbf x)=c_{\underset j {\arg\max}\sum_{i=1}^Th_i^j(\textbf x)}\tag{6-2}\)

​ 公式6-2所示，票数最多的类别即为预测类别，如果票数最多的同时有多个，那么随机选择一个。

  • 加权投票法

​ \(H(\textbf x)=c_{\underset j {\arg\max}\sum_{i=1}^Tw_ih_i^j(\textbf x)}\tag{6-3}\)

​ 相当于将相对多数投票法与加权平均法结合，通常要求$w_i \geq 0$，$\sum_{i=1}^T=1$。

绝对多数投票法可能会出现拒绝预测的情况，这对于可靠性要求高的学习任务中是一个很好的机制，但是如果学习任务要求必须提供预测结果，那么绝对多数投票法会退化成相对多数投票法。因此，在不允许拒绝预测的任务之中，绝对多数和相对多数统称为多数投票法。

在分类任务中，个体学习器的输出类型可能为以下两种：

  • 类标记

    $h_i^j \in {0,1}$，即预测的值为类别代表的数字。

    使用类标记的投票为硬投票

  • 类概率

    $h_i^j \in [0,1]$，即输出的是对后验概率$P(c_j \mid \textbf x)$的一个估计

    使用类概率的投票为软投票

一般来说，基于类概率将个体学习器进行结合往往比直接使用类标记的个体学习器进行结合的性能更好。

7. 组合策略-学习法

当训练数据很多时，一种更加强大的结合策略是使用学习法，即通过另一个学习器进行结合。

Stacking是学习法中的典型代表，我们把个体学习器称作初级学习器，用于结合的学习器叫做次级学习器或者元学习器。

Stacking先从初始训练集训练处初级学习器，然后生成一个新的数据集用于训练次级学习器。生成的新数据集中，初级学习器的输出被当做输入特征，初始样本的标记仍然作为杨丽标记。

下面来看一下Stacking算法的伪代码，我们假设初级学习器是异质的：

image-20190613221322933

次级训练集是通过初级学习器产生的，但是直接使用初级训练机来产生次级训练集，过拟合风险比较大，因此一般使用交叉验证或者留一法这种方式减小过拟合的风险。

次级学习器的输入属性和次级学习器的算法对次级学习器的性能影响很大。一般来说，使用多响应线性回归(MLR)作为次级学习器的算法，在MLR中使用不同的属性集产生的次级学习器性能很比较好。

8. 多样性增强

在第一小节中，我们就得出了要生成多样性大的个体学习器，但是怎样增强个体学习器之间的多样性呢，我们有下面几种办法：

  • 数据样本扰动

    从初始训练集中产生不同的数据子集，通常使用采样法。

    例如Bagging算法中的自助采样、AdaBoost算法中的序列采样等。

    数据样本扰动方法适用于不稳定学习器，即训练样本稍加变化就会对学习器造成很大影响，包括决策树、神经网络等。

    对稳定学习器的效果并不好，例如线性学习器、支持向量机、朴素贝叶斯、$k$近邻学习器等。

  • 输入属性扰动

    从不同的子空间，即属性子集训练的学习器会获得观察数据的不同视角。

    著名的有随机子空间算法，该算法从初始属性集抽取出若干属性子集，然后基于每个属性子集训练一个基学习器。

    image-20190613223358575

    对数据冗余属性少、或者属性少的数据不宜使用属性扰动法

  • 输出表示扰动

    对输出表示进行操纵以增强多样性。

    • 可对训练样本的类别标记变动，如翻转法：随机改变一些训练样本的输出标记

    • 对输出表示进行转换，如输出调制法：将分类输出改为回归输出

    • 将原任务拆解成多个可同时求解的子任务，如EOOC法：将多分类拆解成一系列二分类

  • 算法参数扰动

    基学习算法一般有参数进行设置，例如神经网络的隐层神经元数、初始连接权值等，通过随机设置不同的参数，产生个体差异较大的个体学习器。

    • 负相关法显式的通过正则化项强制个体神经网络使用不同的参数
    • 对于参数较少的算法，可以将算法的某个环节使用其他方法代替，例如决策法，可使用不同的属性选择机制达到扰动的目的

以上介绍的4中扰动方法可同时使用，例如随机森林同时使用了数据扰动和属性扰动。

上述学习笔记主要参考周志华的《机器学习》一书。

CATALOG
    FEATURED TAGS
    Linux Java Algorithm ML100Days Machine Learning Deep Learning K8s Reinforcement Learning Yan Zaizai Big Data
    FRIENDS