“集成”的思想

本文首先会介绍何谓“集成”、然后会介绍两种常见的集成学习方法：Bagging、AdaBoost 的基本定义。这些概念的背后有着深刻的数学理论，但是它们同时也拥有着很好的直观。获得对它们的直观有助于加深对各种模型的分类性能的理解、同时也有助于根据具体的数据集来挑选相应的、合适的模型来进行学习

众擎易举

集成学习基于这样的思想：对于比较复杂的任务，综合许多人的意见来进行决策会比“一家独大”要更好。换句话说、就是通过适当的方式集成许多“个体模型”所得到的最终模型要比单独的“个体模型”的性能更优。我们可以通过下图来直观感知这个过程：

所以问题的关键转化为了两点：如何选择、生成弱分类器和如何对它们进行提升（集成）。在此基础上，通常有三种不同的思路：

• 将不同类型的弱分类器进行提升
• 将相同类型但参数不同的弱分类器进行提升
• 将相同类型但训练集不同的弱分类器进行提升

其中第一种思路的应用相对来说可能不太广泛，而第二、第三种思路则指导着两种常见的做法，这两种做法的区别主要体现在基本组成单元——弱分类器的生成方式：

第一种做法期望各个弱分类器之间依赖性不强、可以同时进行生成。这种做法又称并行方法，其代表为 Bagging，而 Bagging 一个著名的拓展应用便是本系列的主题之一——随机森林（Random Forest，常简称为 RF）。

第二种做法中弱分类器之间具有强依赖性、只能序列生成。这种做法又称串行方法，其代表为 Boosting，而 Boosting 族算法中的代表即是本系列的另一主题——AdaBoost

Bagging 与随机森林

Bagging 是 1996 年由 Breiman 提出的，它的思想根源是数理统计中非常重要的 Bootstrap 理论。Bootstrap 可以翻译成“自举”，它通过模拟的方法来逼近样本的概率分布函数。可以想象这样一个场景：现在有一个包含 N 个样本的数据集$X = \{ x_{1},\ldots,x_{N}\}$，这 N 个样本是由随机变量$x$独立生成的。我们想要研究$x$的均值估计$\bar{x} = \frac{1}{N}\sum_{i = 1}^{N}x_{i}$的统计特性（误差、方差等等），但由于研究统计特性是需要大量样本的、而数据集$X$只能给我们提供一个$\bar{x}$的样本，从而导致无法进行研究

在这种场景下，容易想到的一种解决方案是：通过$x$的分布生成出更多的数据集$X_{1},\ldots X_{M}$、每个数据集都包含 N 个样本。这 M 个数据集都能产生一个均值估计、从而就有了 M 个均值估计的样本。那么只要 M 足够大、我们就能研究$\bar{x}$的统计特性了

当然这种解决方案的一个最大的困难就是：我们并不知道$x$的真实分布。Bootstrap 就是针对这个困难提出了一个解决办法：通过不断地“自采样”来模拟随机变量真实分布生成的数据集。具体而言，Bootstrap 的做法是：

• 从$X$中随机抽出一个样本（亦即抽出$x_1,...,x_N$的概率相同）
• 将该样本的拷贝放入数据集$X_j$
• 将该样本放回$X$中

以上三个步骤将重复 N 次、从而使得$X_{j}$中有 N 个样本。这个过程将对$j = 1,\ldots,M$都进行一遍、从而我们最终能得到 M 个含有 N 个样本的数据集$X_{1},\ldots X_{M}$

简单来说的话、Bootstrap 其实就是一个有放回的随机抽样过程，所以原始数据$\{ x_{1},\ldots,x_{N}\}$中可能会在$X_{1},\ldots X_{M}$中重复出现、也有可能不出现在$X_{1},\ldots X_{M}$中。事实上，由于$X$中一个样本在 N 次采样中始终不被采到的概率为$\left( 1 - \frac{1}{N} \right)^{N}$、且：

$$\lim_{N\rightarrow\infty}\left( 1 - \frac{1}{N} \right)^{N} \rightarrow \frac{1}{e} \approx 0.368$$

所以在统计意义上可以认为、$X_{j}$中含有$X$中 63.2%的样本$\left( \forall j = 1,\ldots,M \right)$

这种模拟的方法在理论上是具有最优性的。事实上、这种模拟的本质和经验分布函数对真实分布函数的模拟几乎一致：

• Bootstrap 以$\frac 1N$的概率、有放回地从$X$中抽取 N 个样本作为数据集、并以之估计真实分布生成的具有 N 个样本的数据集
• 经验分布函数则是在 N 个样本点上以每点的概率为$\frac 1N$作为概率密度函数、然后进行积分的函数

经验分布函数的数学表达式为：

$$F_{N}\left( x \right) = \frac{1}{N}\sum_{i = 1}^{N}{I_{\left( - \infty,x \right\rbrack}(x_{i})}$$

可以看出、经验分布函数用到了频率估计概率的思想。用它来模拟真实分布函数是具有很好的优良性的，详细的讨论可参见相关数学理论

知道 Bootstrap 是什么之后、我们就可以来看 Bagging 的具体定义了。Bagging 的全称是 Bootstrap Aggregating，其思想非常简单：

• 用 Bootstrap 生成出 M 个数据集
• 用这 M 个数据集训练出 M 个弱分类器
• 最终模型即为这M个弱分类器的简单组合

所谓简单组合就是：

• 对于分类问题使用简单的投票表决
• 对于回归问题则进行简单的取平均

简单组合虽说简单、其背后仍然是有数学理论支撑的。考虑二分类问题：

$$y \in \{ - 1, + 1\}$$

假设样本空间到类别空间的真实映射为$f$、我们得到的 M 个弱分类器模型$G_{1},\ldots,G_{M}$所对应的映射为$g_{1},\ldots,g_{M}$，那么简单组合下的最终模型对应的映射即为：

$$g\left( x \right) = \text{sign}\left( \sum_{j = 1}^{M}{g_{j}\left( x \right)} \right)$$

这里的 sign 是符号函数、满足：

$$\text{sign}\left( x \right) = \left\{ \begin{matrix} - 1,\ \ if\ x < 0 \\ + 1,\ \ if\ x > 0 \\ \end{matrix} \right.\$$

其中，$\text{sign}(0)$则可为$-1$也可为$+1$，令其有 50%的概率输出$-$、$+1$也是可行的

如果我们此时假设每个弱分类器的错误率为$\epsilon$：

$$p\left( g_{i}\left( x \right) \neq f\left( x \right) \right) = \epsilon$$

如果我们假设弱分类器的错误率相互独立，那么由霍夫丁不等式（Hoeffding’s Inequality）可以得知：

$$p\left( G\left( x \right) \neq f\left( x \right) \right) = \sum_{j = 0}^{\left\lfloor \frac{M}{2} \right\rfloor}\left( \frac{M}{j} \right)\left( 1 - \epsilon \right)^{j}\epsilon^{M - j} \leq \exp\left( - \frac{1}{2}M\left( 1 - 2\epsilon \right)^{2} \right)$$

亦即最终模型的错误率随弱分类器的个数 M 的增加、将会以指数级下降并最终趋于 0

虽说这个结果看上去很振奋人心，但需要注意的是、我们做了一个非常强的关键假设：假设弱分类器的错误率相互独立。这可以说是不可能做到的，因为这些弱分类器想要解决的都是同一个问题、且使用的训练集也都源自于同一份数据集

但不管怎么说，以上的分析给了我们这样一个重要信息：弱分类器之间的“差异”似乎应该尽可能的大。基于此，结合 Bagging 的特点、我们可以得出这样一个结论：对于“不稳定”（或说对训练集敏感：若训练样本稍有改变，得到的从样本空间到类别空间的映射 g 就会产生较大的变化）的分类器，Bagging 能够显著地对其进行提升。这也是被大量实验结果所证实了的

正如前文提过的，Bagging 有一个著名的拓展应用叫“随机森林”，从名字就容易想到、它是当个体模型为决策树时的 Bagging 算法。不过需要指出的是，随机森林算法不仅对样本进行 Bootstrap 采样，对每个 Node 调用生成算法时都会随机挑选出一个可选特征空间的子空间作为该决策树的可选特征空间；同时，生成好个体决策树后不进行剪枝、而是保持原始的形式。换句话说、随机森林算法流程大致如下：

• 用 Bootstrap 生成出 M 个数据集
• 用这 M 个数据集训练出 M 颗不进行后剪枝决策树，且在每颗决策树的生成过程中，每次对 Node 进行划分时、都从可选特征（比如说有 d 个）中随机挑选出 k 个（$k\le d$）特征，然后依信息增益的定义从这 k 个特征中选出信息增益最大的特征作为划分标准
• 最终模型即为这 M 个弱分类器的简单组合

注意：有一种说法是随机森林中的个体决策树模型只能使用 CART 树

也就是说，除了和一般 Bagging 算法那样对样本进行随机采样以外、随机森林还对特征进行了某种意义上的随机采样。这样做的意义是直观的：通过对特征引入随机扰动，可以使个体模型之间的差异进一步增加、从而提升最终模型的泛化能力。而这个特征选取的随机性，恰恰被上述算法第二步中的参数k所控制：

• 若$k=d$，那么训练出来的决策树和一般意义下的决策树别无二致、亦即特征选取这一部分不具有随机性
• 若$k=1$，那么生成决策树的每一步都是在随机选择属性、亦即特征选取的随机性达到最大

Breiman 在提出随机森林算法的同时指出，一般情况下、推荐取$k=\log_2{d}$

PAC 框架与 Boosting

虽然同属集成学习方法，但 Boosting 和 Bagging 的数学理论根基不尽相同：Boosting 产生于计算学习理论（Computational Learning Theory）[Valiant, 1984]。一般而言，如果只是应用机器学习的话、我们无需对它进行太多的了解（甚至可以说对它一知半解反而有害），所以本节只打算对其最基本的概率近似正确（PAC）学习理论中的“可学习性（PAC Learnability）”进行简要的介绍

PAC 学习整体来说是一个比较纯粹的数学理论。有一种说法是、PAC 学习是统计学家研究机器学习的方式，它关心模型的可解释性、然而机器学习专家通常更关心模型的预测能力。这也正是为何说无需太过了解它，因为我们的目的终究不是成为统计的专家、而是更希望成为一个能够应用机器学习的人。不过幸运的是，虽然为了叙述 Boosting、PAC 学习中“可学习性”的概念难以避开，但其本身却是具有很直观的解释的。下面我们就来看看这个直观解释：

PAC 提出的一个主要的假设、就是它要求数据是从某个稳定的概率分布中产生。直观地说，就是样本在样本空间中的分布状况不能随时间的变化而变化、否则就失去了学习的意义（因为学习到的永远只是“某个时间”的分布，如果未知数据所处时间的分布状况和该时间数据的分布状况不同的话、模型就直接失效了）。然后所谓的PAC可学习性，就是看学习的算法是否能够在合理的时间（多项式时间）内、以足够高的概率输出一个错误率足够低的模型。由此，所谓的“强可学习”和“弱可学习”的概念就很直观了：

• 若存在一个多项式算法可以学习出准确率很高的模型，则称为强可学习
• 若在在一个多项式算法可以学习但准确率仅仅略高于随机猜测，则称为弱可学习

注意：由于进行机器学习时、我们只能针对训练数据集进行学习、所以和真实情况相比肯定是有偏差的。这正是需要提出 PAC 可学习这个概念的原因之一

虽然我们区分定义了这两个概念，不过神奇之处在于，这两个概念在PAC学习框架下是完全等价的[Schapire, 1990]。这意味着对于一个学习问题，只要我们找到了一个“弱学习算法”，就可以把它变成一个“强学习算法”。这当然是意义深刻的，因为往往比较粗糙的“弱学习算法”比较好找、而相对精确的“强学习算法”却难得一求

那么具体而言应该怎么做呢？这里就需要用到所谓的 Boosting（提升方法）了。提升方法可以定义为用于将由“弱学习算法”生成的“弱模型”、提升成和“强学习算法”所生成的“强模型”性能差不多的模型的方法，它的基本组成单元是许许多多的“弱模型”、然后通过某种手段把它们集成为最终模型。虽然该过程听上去和之前介绍的 Bagging 差不多、但它们的思想和背后的数学理论却有较大区别，加以辨析是有必要的

需要指出的是，Boosting 事实上是一族算法、该族算法有一个类似的框架：

• 根据当前的数据训练出一个弱模型
• 根据该弱模型的表现调整数据的样本权重。具体而言：
  • 让该弱模型做错的样本在后续训练中获得更多的关注
  • 让该弱模型做对的样本在后续训练中获得较少的关注
• 最后再根据该弱模型的表现决定该弱模型的“话语权”、亦即投票表决时的“可信度”。自然、表现越好就越有话语权

可以证明，当训练样本有无穷多时、Boosting 能让弱模型集成出一个对训练样本集的准确率任意高的模型。然而实际任务中训练样本当然不可能有无穷多，所以问题就转为了如何在固定的训练集上应用 Boosting 方法。而在 1996 年，Freund 和 Schapire 所提出的 AdaBoost（Adaptive Boosting）正是一个相当不错的解决方案，在理论和实验上均有优异的表现。虽然 AdaBoost 背后的理论深究起来可能会有些繁复、但它的思想并没有脱离 Boosting 族算法的那一套框架。值得一提的是、Boosting 还有一套比较有意思的解释方法；我们会在后文详细讨论其中的代表性算法——AdaBoost 的解释、这里就先按下不表