NO.45.tip：提升法与堆叠法

背景

集成学习（ensemble learning）让人相信"群众的智慧"这一理念，它表明一个更大的群体的决策通常比单个个体的决策要好。集成学习方法使用多种学习模型来获得比使用任何单独的学习模型更好的预测性能。机器集成学习由一组具体的备选模型组成，但通常允许这些备选模型之间存在更灵活的结构。有监督学习算法执行的任务是在一个假设空间中搜索合适的模型或对特定的问题进行良好的预测。即使假设空间中包含了对特定问题非常好的假设，也可能很难找出一个好的假设。集成学习将多个假设结合起来，形成一个（希望是）更好的假设。术语"集成"通常用来描述使用相同的基础学习器生成多个假设的方法，而多分类器系统则广泛得多，它包括不同类别的基础学习器。

评估一个集成学习方法的预测能力，通常比评估单个模型的预测能力需要更多的计算。从某种意义上说，集成学习方法可以被认为是通过执行大量的额外计算来补偿差的学习算法的一种方式。决策树等快速算法通常用于集成学习方法（例如，随机森林），尽管较慢的算法也可以从集成学习技术中获益。集成学习方法也被用于无监督学习场景，例如共识聚类或异常检测等。

经过训练的集成学习模型代表单一的假设，但这个假设不一定包含在它所建立的模型的假设空间中。因此，可以证明集成学习方法在它们所能代表的功能上具有更大的灵活性。理论上，这种灵活性使它们比单个模型更容易过拟合训练数据，但在实践中，一些集成学习方法（尤其是套袋法）往往能克服对训练数据的过拟合而导致的问题。

从经验上讲，当模型之间存在显著的多样性时，集成学习方法往往会产生更好的结果。因此，许多集成学习方法试图增强它们所结合的模型之间的多样性。虽然可能并不直观，但与非常谨慎的算法（如基于熵的决策树）相比，更多的随机算法（如随机决策树）可以用来产生更强的集成学习模型。

虽然集成学习模型中的基础分类器的数量对预测的准确性有很大的影响，但如何确定基础分类器的数量是一个关键但比较困难的问题。大多数情况下是通过统计测试来确定适当的基础分类器的数量。最近，一个理论框架提出，集成学习方法存在一个理想的基础分类器的数量，多于或少于这个数量的基础分类器都会降低集成学习方法的精度。这就是所谓的"集成构建中的收益递减法则"。他们的理论框架表明，使用与类标签相同数量的独立的基础分类器可以获得最高的准确率。

常见的集成学习方法有贝叶斯最优分类器（bayes optimal classifier）、套袋（bagging）法、提升（boosting）法、桶模型（bucket of models）以及堆叠（stacking）模型。贝叶斯模型组合（Bayesian model combination）、贝叶斯参数平均（Bayesian model averaging）以及堆叠（stacking）模型。下面重点介绍提升法和堆叠法。

源与流

提升法

Kearns 和 Valiant 首先提出了强可学习（strongly learnable）和弱可学习（weakly learnable）的概念，并曾经提出过这样一个问题：一组弱学习器能否创造出一个强学习器？弱学习器一般是指一个分类器，它的分类结果只比随机分类好一点点；强学习器指分类器的分类结果与真实分类非常接近。Robert Schapire 在 1990 年的一篇论文中对 Kearns 和 Valiant 的问题做出了肯定的回答。最先构造出一种多项式级的算法，这就是最初的提升算法。该论文在机器学习理论方面产生了重大的影响。一年后，Freund 开发了效率更高的提升算法。关于这些早期提升算法的实践上的缺陷，那就是都是要求事先知道弱学习器的下限。1995 年，Freund 和 Schapire 改进了提升算法，提出了 AdaBoost（Adaptive Boosting）算法，该算法的效率和 Freund 于 1991 年提出的提升算法几乎相同，但不需要任何关于弱分类器的先验知识，因而更容易应用到实际问题当中。

提升算法是过去 30 年中开发的最有前途的数据分析方法之一，其基本思想是反复应用简单的分类器，并结合其解决方案的结果，以获得更好的预测结果。提升法通过训练每个新的模型实例来更注重先前模型错误分类的实例来增量构建集成模型。在某些情况下，提升法已被证明可比套袋法更好的准确性，但它也往往更容易过拟合训练数据。

影响提升法的两个核心问题是：

在每一轮中如何改变训练数据的权值或概率分布？提高上一个弱分类器分错的样本的权值，减小前一轮中分类正确的样本的权值，让误分类的样本在后续受到更多的关注。
如何将弱分类器组合成为一个强分类器？通过加法模型将弱分类器进行线性组合。比如 AdaBoost 通过加权多数表决的方式，即增大错误率较小的分类器的权值，同时减小错误率较大的分类器的权值；提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

我们首先介绍 AdaBoost 算法以了解提升法的精髓。

AdaBoost 算法

AdaBoost 是 Adaptive Boosting 的简称，是由 Yoav Freund 和 Robert Schapire 提出的一种机器学习算法，他们的工作获得了 2003 年哥德尔奖。AdaBoost 算法可以和许多其他类型的学习算法一起使用，以提高性能。其他学习算法（"弱学习器"）的输出被组合成一个加权和，代表提升分类器的最终输出。AdaBoost 是自适应的，即后续的弱学习器会被调整，以支持那些被之前的分类器错误分类的实例。各个学习器可以很弱，但只要每个学习器的性能比随机猜测好，就可以证明最终的模型收敛到一个强学习器。

以决策树为弱学习器的 AdaBoost 通常被称为最好的开箱即用的分类器。AdaBoost 算法的每个阶段收集的关于每个训练样本分类的相对"难度"的信息被反馈给树生长算法，这样以后树就会倾向于关注更难分类的样本。

机器学习中的问题常常受到维度灾难问题的影响，评估每个特征不仅会降低分类器的训练和执行速度，事实上还会降低预测能力。与神经网络和 SVM 不同，AdaBoost 训练过程只选择那些已知能提高模型预测能力的特征，减少了维度，并可能提高执行速度，因为不相关的特征不需要计算。

原理

假设有一个数据集 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})$ ，其中每个样本 $x_{i}$ 是一个 $n$ 维向量， $y_{i} \in {- 1, 1}$ 。在第 $m - 1$ 次迭代后，AdaBoost 提升分类器是弱分类器的线性组合，其形式为：

$C_{(m - 1)} (x_{i}) = α_{1} k_{1} (x_{i}) + \dots + α_{m - 1} k_{m - 1} (x_{i}) (1)$

其中，类取值将是 $C_{(m - 1)} (x_{i})$ 的符号。在第 $m$ 次迭代时，我们希望通过增加另一个弱学习器 $k_{m}$ ，再加一个权重 $α_{m}$ ，将其扩展为一个更好的提升分类器：

$C_{m} (x_{i}) = C_{(m - 1)} (x_{i}) + α_{m} k_{m} (x_{i}) (2)$

所以，剩下的就是确定哪种弱分类器是 $k_{m}$ 的最佳选择，以及它的权重 $α_{m}$ 应该是多少。我们将 $C_{m}$ 的总误差 $E$ 定义为其在每个数据点上的指数损失之和：

$E = i = 1 \sum N e^{- y_{i} C_{m} (x_{i})} = i = 1 \sum N e^{- y_{i} C_{(m - 1)} (x_{i})} e^{- y_{i} α_{m} k_{m} (x_{i})} (3)$

定义 $w_{i}^{(m)} = e^{- y_{i} C_{(m - 1)} (x_{i})}$ （当 $m > 1$ 时），且 $w_{i}^{(1)} = 1$ ，则：

$E = i = 1 \sum N w_{i}^{(m)} e^{- y_{i} α_{m} k_{m} (x_{i})} (4)$

$w_{i}^{(m + 1)} = e^{- y_{i} C_{(m)} (x_{i})} = e^{- y_{i} [C_{(m - 1)} (x_{i}) + α_{m} k_{m} (x_{i})]} = w_{i}^{(m)} e^{- y_{i} α_{m} k_{m} (x_{i})}$

然后对 $w_{i}^{(m + 1)}$ 进行归一化处理，即：

$归一化 w_{i}^{(m + 1)} = \frac{w _{i}^{(m + 1)}}{\sum _{j = 1}^{N} w _{j}^{(m + 1)}} (5)$

然后将此归一化后的值作为 $w_{i}^{(m + 1)}$ 的新值。

我们可以将这个和值分成按 $k_{m}$ 正确分类的数据点（所以 $y_{i} k_{m} (x_{i}) = 1$ ）和分类错误的数据点（所以 $y_{i} k_{m} (x_{i}) = - 1$ ）：

$E = y_{i} = k_{m} (x_{i}) \sum w_{i}^{(m)} e^{- α_{m}} + y_{i} \neq = k_{m} (x_{i}) \sum w_{i}^{(m)} e^{α_{m}} = e^{- α_{m}} y_{i} = k_{m} (x_{i}) \sum w_{i}^{(m)} + e^{α_{m}} y_{i} \neq = k_{m} (x_{i}) \sum w_{i}^{(m)} (6)$

由于该等式右侧唯一依赖于 $k_{m}$ 的部分是 $\sum_{y_{i} \neq = k_{m} (x_{i})} w_{i}^{(m)}$ ，因此我们看到最小化 $E$ 的 $k_{m}$ 是最小化 $\sum_{y_{i} \neq = k_{m} (x_{i})} w_{i}^{(m)}$ 的 $k_{m}$ （假设 $α_{m} > 0$ ），即加权误差最小的弱分类器。

为了确定使带有 $k_{m}$ 的总误差 $E$ 最小化的期望权重 $α_{m}$ ，我们对其进行微分：

$\frac{d E}{d α _{m}} = \frac{d ( \sum _{y_{i} = k_{m} (x_{i})} w _{i}^{(m)} e ^{- α_{m}} + \sum _{y_{i} \neq = k_{m} (x_{i})} w _{i}^{(m)} e ^{α_{m}} )}{d α _{m}}$

将其设为零并求解（具体的推导过程在此省略）：

$α_{m} = \frac{1}{2} ln (\frac{\sum _{y_{i} = k_{m} (x_{i})} w _{i}^{(m)}}{\sum _{y_{i} \neq = k_{m} (x_{i})} w _{i}^{(m)}}) (7)$

我们计算出弱分类器的加权错误率为：

$ε_{m} = \frac{\sum _{y_{i} \neq = k_{m} (x_{i})} w _{i}^{(m)}}{\sum _{i = 1}^{N} w _{i}^{(m)}} (8)$

由此可知：

$α_{m} = \frac{1}{2} ln (\frac{1 - ε _{m}}{ε _{m}}) (9)$

这样就得出了 AdaBoost 算法。在每次迭代时，选择分类器 $k_{m}$ ，使总加权误差 $\sum_{y_{i} \neq = k_{m} (x_{i})} w_{i}^{(m)}$ 最小化，用它来计算误差率 $ε_{m}$ 和权重 $α_{m}$ ，最后改进提升分类器 $C_{m - 1}$ 为：

$C_{m} = C_{(m - 1)} + α_{m} k_{m} (10)$

在分类问题中，AdaBoost 算法通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。AdaBoost 算法的伪代码如下。

输入： 训练数据集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})}$ ， $x_{i} \in L \subseteq R^{n}$ ， $y_{i} \in Υ = {- 1, 1}$ ，一组弱分类器 ${k_{1}, k_{2}, \dots, k_{L}}$ （例如决策树）。

输出： 最终分类器 $C (x)$ 。

过程：

初始化训练数据的权值分布：

$w_{i}^{(1)} = \frac{1}{N}, i = 1, 2, \dots, N$

训练 $L$ 个弱分类器 ${k_{1}, k_{2}, \dots, k_{L}}$ 。

(a) 使用具有权值分布 $w^{(m)}$ 的训练数据集学习（$1 \leq m < L$），取下一个弱分类器：

$k_{m} : L \to {- 1, 1}, u = 1, 2, \dots, L$

(b) 计算 <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8444em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1514em;"><span style="top:-2.55em;margin-left:-0.0315em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">m</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 在训练数据集上的分类误差率：

$ε_{m} = i = 1 \sum N e^{- y_{i} k_{m} (x_{i})}$

累加每个样本的预测误差。

(c) 计算 <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8444em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1514em;"><span style="top:-2.55em;margin-left:-0.0315em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">m</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 的系数：

$α_{m} = \frac{1}{2} ln (\frac{1 - ε _{m}}{ε _{m}})$

(d) 更新训练数据集的权值分布：

$w_{i}^{(m + 1)} = e^{- y_{i} C_{(m)} (x_{i})} = e^{- y_{i} [C_{(m - 1)} (x_{i}) + α_{m} k_{m} (x_{i})]} = e^{- y_{i} C_{(m - 1)} (x_{i})} e^{- y_{i} α_{m} k_{m} (x_{i})} = w_{i}^{(m)} e^{- α_{m} k_{m} (x_{i})}, i = 1, 2, \dots, N$

然后归一化，得到：

$w_{i}^{(m + 1)} = \frac{w _{i}^{(m + 1)}}{\sum _{j = 1}^{N} w _{j}^{(m + 1)}}, i = 1, 2, \dots, N$

(e) 构建新的基本分类器：

$C_{m} (x_{i}) = C_{(m - 1)} (x_{i}) + α_{m} k_{m} (x_{i}) = j = 1 \sum m α_{j} k_{j} (x_{i}), m \geq 2$

如果 <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span>，则 <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.07153em;">C</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0715em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3117em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0037em;">α</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0037em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0315em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3117em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>。

然后继续利用下一个弱分类器，重复步骤 (a) ~ (e)，直到遍历所有的弱分类器。

继续得到最终的分类器：

$C (x) = sign (C (x)) = sign (j = 1 \sum L α_{j} k_{j} (x))$

提升法的分类、优点和挑战

提升法的重点是迭代组合弱学习器，以建立一个能够预测更准确结果的强学习器。提升算法创建和聚集弱学习器的方式可能有所不同，四种流行的提升法包括：

自适应提升或 AdaBoost。 Yoav Freund 和 Robert Schapire 被认为是 AdaBoost 算法的创造者。这种方法以迭代的方式运行，识别错误分类的数据点，并调整其权重以最小化训练误差。该模型以一种连续的方式持续优化，直到产生最强的预测器。它采用指数损失函数，上一节已经对此做了详细介绍。
梯度提升。 在 Leo Breiman 的基础上，Jerome H. Friedman 开发了梯度提升法，其工作原理是依次将预测器添加到一个集合体中，每个预测器都会纠正其前辈的错误。然而，梯度提升不是像 AdaBoost 那样改变数据点的权重，而是对前一个预测器的剩余误差进行训练。它采用残差或绝对损失函数。由于结合了梯度下降算法和提升法，所以使用了梯度提升这个名称。
极端梯度提升或 XGBoost。 XGBoost 是梯度提升的一种实现方式，旨在提高计算速度和规模。XGBoost 允许在训练过程中进行并行学习。
自然梯度提升或 NGBoost。 它利用自然梯度将不确定性估计引入梯度增强中，是一种用于概率预测的模块化提升算法。该算法由基学习器、参数概率分布和评分规则组成。

提升法的主要优点包括：

易于实施。 提升法以一种连续的方式将多个弱学习器结合起来，在观察的基础上反复改进。在 Python 中，sklearn 的集合方法（sklearn ensemble）可以很容易地实现流行的提升方法，包括 AdaBoost、XGBoost、LightGBM 等，而且提升法可以使用几个超参数调整选项来改善拟合，不需要对数据进行归一化。
减少偏差。 提升法可以帮助减少高偏差，常见于浅层决策树和逻辑回归模型。
计算效率。 由于提升算法在训练过程中只选择能提高其预测能力的特征，因此可以帮助降低维度，并提高计算效率。

提升法也存在一些争议，主要在于提升法是否能帮助减少过拟合或加剧过拟合。

过拟合。 研究中存在一些争议，主要在过拟合确实发生的情况下，预测不能被泛化到新的数据集上，所以提升模型的计算成本很高。尽管 XGBoost 试图解决其他类型的提升计算中的巨大计算量。提升中的顺序训练很难扩大规模。由于每个估计器都是建立在其前辈的集合上。
可扩展性问题。 与套袋法相比，提升法的训练速度会更慢，因为大量的参数也会影响模型的行为。

梯度提升法的原理

提升法的主要思想是将新的模型依次加入集合中。在每个特定的迭代中，新的弱基础学习器模型被训练成与到目前为止所学的整个集合的误差相关。第一项突出的提升技术是纯粹算法驱动的，这使得对其属性和性能的详细分析相当困难。这导致了一些猜测：为什么这些算法要么优于其他所有的方法，要么由于严重过拟合而不适用。

梯度提升（gradient boosting = gradient descent + boosting）的思想起源于 Leo Breiman 的观点，即提升可以解释为一个合适的代价函数上的优化算法，随后 Jerome H. Friedman、Llew Mason、Jonathan Baxter、Peter Bartlett 和 Marcus Frean 也提出了更为普遍的函数梯度提升观点，即通过迭代选择一个指向负梯度方向的函数（弱假设），在函数空间上优化代价函数。这种函数梯度的提升观点使得提升算法在回归和分类之外的许多机器学习和统计学领域得到了发展。损失函数描述的是模型的不可靠程度，损失函数的结果越大，说明模型越容易出错（其实这里有一个方差、偏差均衡的问题，但是我们暂不考虑）。如果模型能够让损失函数在其梯度下降的方向上下降，则说明模型在不断改进，而最好的方式就是让损失函数在其梯度的方向上下降。

在梯度提升机（Gradient Boosting Machine，GBM）中，学习过程连续拟合新的模型，提供对响应变量更准确的估计。这种算法的原理是构建新的基础学习器，使其与损失函数的负梯度最大程度地相关，从而与整个集合相关。损失函数可以任意选择，但如果误差函数是经典的平方误差损失，学习过程将导致连续的错误拟合。一般来说，损失函数的选择是由研究者设定的，到目前为止，既有广泛适用的损失函数，也有可实现特定任务的损失函数。这种高度的灵活性使得 GBM 对于任何特定的数据驱动的任务都可以高度可定制的。它的实现相对简单，这使得人们可以尝试不同的模型设计。此外，GBM 不仅在实际应用中，而且在各种机器学习和数据挖掘的挑战中也获得了成功。

梯度提升法是非常经典而又重要的提升方法，它与 AdaBoost 一样都是将弱分类器合成强分类器。它们的主要区别是：

梯度提升法通过变量的残差来改变错误分类的权重，而 AdaBoost 则直接修改分类错误的训练权重。
梯度提升法中的分类器一般是完整的决策树，但是 AdaBoost 一般使用二层决策树，可以参见 5.1.1 节的例子。

与其他提升方法一样，梯度提升法以迭代的方式将弱学习器组合成一个强学习器。在最小二乘回归的环境中最容易解释，其目标是通过最小化均方误差 $\frac{1}{n} \sum_{i} (\overset{y}{^}_{i} - y_{i})^{2}$ （其中 $y_{i}$ 为样本的实际观测值， $\overset{y}{^}_{i}$ 为样本的预测值）一个模型 $F$ 预测 $\overset{y}{^} = F (x)$ 的值。

现在，考虑一个有 $M$ 个阶段的梯度提升算法。在梯度提升的每个阶段 $m$ （ $1 \leq m \leq M$ ），假设有一些不完美的模型 $F_{m}$ 。对于早期阶段（即 $m$ 较小时），这个模型可能只是返回 $\overset{y}{^}_{i} = \overset{y}{ˉ}$ ，即 $y$ 的平均值。为了提升 $F_{m}$ ，算法应该增加一些新的估计器 $h_{m} (x)$ 。因此，

$F_{m + 1} (x) = F_{m} (x) + h_{m} (x) = y (11)$

即

$h_{m} (x) = y - F_{m} (x) (12)$

与其他提升法一样，每个 $F_{m + 1}$ 都试图修正其前一个模型 $F_{m}$ 之间的误差。观察到给定模型的残差 $h_{m} (x)$ 是均方误差损失函数的负梯度[相对于 $F (x)$ ]，可以将这一思想推广到平方误差以外的其他损失函数：

$L_{MSE} = \frac{1}{2} (y - F (x))^{2} (13)$

$h_{m} (x) = - \frac{\partial L _{MSE}}{\partial F} = y - F (x) (14)$

因此，梯度提升可以是专门的梯度下降算法，而泛化则需要"适配"不同的损失函数及其梯度。

梯度提升决策树

梯度提升决策树（或梯度提升树，GBT）将提升看作为一个数值优化问题，其目标是使用类似梯度下降的过程来增加弱学习器，从而最小化模型的损失。这类算法被描述为一个阶段性的加法模型，这是因为每次增加一个新的弱学习器，而模型中现有的弱学习器被冻结并保持不变。

请注意，这种分阶段（stagewise）的策略与逐步式（stepwise）的方法不同，后者是在加新项时重新调整先前输入的项，例如 AdaBoost 算法。

梯度提升决策树可以被认为是一种贪婪的函数逼近，允许使用任意可微分的损失函数，该技术扩展到二元分类、回归、多分类等问题。从这个角度看，基于梯度提升的决策树已经与各类神经网络学习方法融合。

梯度提升决策树涉及三个要素：

一组进行预测的 CART 决策树作为弱学习器。
一个待优化的损失函数。
一个加法模型，用来增加弱学习器，使损失函数最小化。

CART 决策树被用作梯度提升中的弱学习器。具体来说，回归树被用于输出真实值……并“纠正”预测中的残差。树可以……CART 决策树的输出被添加，并“纠正”预测中的残差。……
损失函数

使用何种损失函数取决于问题的类型。回归可以使用平方误差，分类可以使用对数损失……损失函数必须是可微分的，目前有许多标准的损失函数可用，也可以自定义损失函数。例如……这是一个足够通用的框架，可以使用任何可微分的损失函数。

梯度提升框架的一个好处是，不必为每个可能使用的损失函数推导新的提升算法，相反，它是一个足够通用的框架，可以使用任何可微分的损失函数。

假设损失函数是 $L (y, F_{k - 1} (x))$ ，迭代的目标是找到一个弱学习器 $F_{m} (x)$ ，让本轮的损失函数 $L (y, F_{k} (x)) = L (y, F_{k - 1} (x) + F_{k} (x))$ 最小。也就是说，要让样本的损失尽量变得……针对损失函数拟合方法的问题，Friedman 提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个 CART 回归树。第 $k$ 轮的第 $i$ 个样本的损失函数的负梯度表示为

$r_{i} = - [\frac{\partial L ( y , F _{k - 1} ( x _{i} ))}{\partial F _{k - 1} ( x _{i} )}] (15)$

利用 $(x_{i}, r_{i}) (i = 1, 2, \dots, n)$ ，我们可以拟合一棵 CART 回归树，得到第 $k$ 棵回归树，其对应的叶子节点区域为 $R_{kj}$ ， $j = 1, 2, \dots, J$ ，其中 $J$ 为叶子节点的个数。

针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的输出值 $c_{kj}$ ：

$c_{kj} = ar g c min x_{i} \in R_{kj} \sum L (y_{i}, F_{k - 1} (x_{i}) + c) (16)$

这样就得到了本轮的决策树拟合函数：

$h_{k} (x) = j = 1 \sum J c_{kj} I (x \in R_{kj}) (17)$

从而本轮最终得到的强学习器的表达式如下：

$F_{k} (x) = F_{k - 1} (x) + η j = 1 \sum J c_{kj} I (x \in R_{kj}) (18)$

通过损失函数的负梯度，我们找到了一种通用的拟合损失误差的方法。这种方法对于分类问题和回归问题均适用，区别仅在于损失函数不同导致的负梯度不同而已。

加法模型

树是一个一个地添加的，模型中现有的树不会被改变。梯度下降过程被用来最小化添加树时的损失。传统的梯度下降是用来最小化一组参数，如回归中的系数或神经网络中的权重。在计算出误差或损失后，权重被更新以最小化该误差。

但是，在梯度提升树中，我们不使用参数，而是使用弱学习器的子模型，或更具体的决策树。在计算损失后，为了执行梯度下降过程，我们必须向模型新添加一棵树，以减少损失（即遵循梯度）。我们需要对树进行参数化，然后修改树的参数，并通过减少残差向正确的方向移动。一般来说，这种方法被称为函数梯度下降或常函数的梯度下降。

然后，新树的输出被添加到现有树序列的输出中，以纠正或改善组合提升模型的最终输出。一旦损失达到可接受的水平或在外部验证数据集上不再有改善，就会停止训练，树的数量不再增加。

综上所述，梯度提升树的优点包括：

它是一种通用的算法，适用于任何可微分的损失函数。
它提供的预测分数通常比其他算法好得多，并且更准确。
它可以处理缺失的数据——不需要归因。
训练速度更快，尤其是在大型数据集上。
它们中的大多数都支持处理分类特征。

梯度提升树的缺点包括：

这种方法对异常值很敏感。离群值比非离群值的残差要大得多，因此梯度提升法会把大量的注意力放在这些点上。使用平均绝对误差（MAE）而不是平均平方误差（MSE）来计算误差，可以帮助减少这些异常值的影响，因为后者对较大的差异给予了更多的权重。
如果树的数量太大，就容易出现过拟合，需要在模型开始过拟合之前停止。可以通过应用 L1 和 L2 正则化惩罚来解决过拟合问题，也可以尝试使用低学习率。
模型的计算成本很高，需要很长的时间来训练，特别是在 CPU 上。
很难解释最终的模型。

尽管梯度提升树现在被广泛使用，但许多人仍然把它当作一个复杂的黑匣子，只是使用预先建立的库运行模型。

梯度提升分类决策树

基于梯度提升树的分类算法预测输出的不是连续的值而是离散的类别，导致我们无法直接利用输出类别拟合误差。为了解决这个问题，主要有两种方法：一种方法是用指数损失函数，此时梯度提升分类决策树（GBDT）退化为 AdaBoost 算法；另一种方法是用类似于逻辑回归的对数似然损失函数，可以参考关于 logistic 回归问题的描述。也就是说，我们用类别的预测概率值和真实概率值的差来拟合损失。本节仅讨论利用对数似然损失函数的 GBDT 分类，又可以进一步分为二元分类和多元分类。

二元 GBDT 分类算法

对于二元 GBDT 分类算法，首先要将预测变量转变为连续值，可以采用类似 logistic 回归中的做法，利用对数概率和相应的计算过程。这里的 $y$ 实际是转换以后的样本的 log(odds)。用类似于逻辑回归的对数似然损失函数，则损失函数为

$L (y, F (x)) = lo g (1 + exp (- y F (x))) (19)$

其中 $y \in {- 1, + 1}$ 。则此时的负梯度误差为

$r_{ki} = - [\frac{\partial L ( y , F _{k - 1} ( x ))}{\partial F _{k - 1} ( x )}] = \frac{y _{i}}{1 + exp ( y _{i} F _{k - 1} ( x _{i} ))} (20)$

对于生成的决策树，各个叶子节点的最佳负梯度拟合值为

$c_{kj} = ar g c min x_{i} \in R_{kj} \sum lo g (1 + exp (- y_{i} F_{k - 1} (x_{i}) + c)) (21)$

由于上式比较难优化，我们一般使用近似值代替：

$c_{kj} = \frac{\sum _{x_{i} \in R_{kj}} r _{ki}}{\sum _{x_{i} \in R_{kj}} ∣ r _{ki} ∣ ( 1 - ∣ r _{ki} ∣ )} (22)$

除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元 GBDT 分类和 GBDT 回归算法过程相同。

多元 GBDT 分类算法

多元 GBDT 比二元 GBDT 复杂一些，主要体现在多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为 $K$ ，则此时的对数似然损失函数为

$L (y, F (x)) = - t = 1 \sum T y_{t} lo g p_{t} (x) (23)$

其中如果样本输出类别为 $t$ ，则 $y_{t} = 1$ 。第 $t$ 类的概率 $p_{t} (x)$ 的表达式为

$p_{t} (x) = \frac{exp ( F _{t} ( x ))}{\sum _{l = 1}^{T} exp ( F _{l} ( x ))} (24)$

结合上面两个公式可以计算出第 $k$ 轮的第 $i$ 个样本对应类别 $t$ 的负梯度误差：

$r_{k t i} = - [\frac{\partial L ( y , F _{k - 1} ( x ))}{\partial F _{k - 1} ( x )}] = y_{t i} - p_{t, k - 1} (x_{i}) (25)$

可以看出，这里的误差就是样本 $i$ 对应类别 $t$ 的真实概率和 $t - 1$ 轮预测概率的差值。对于生成的决策树，各个叶子节点的最佳负梯度拟合值为

$c_{q j l} = ar g c_{j l} min i = 0 \sum m k = 1 \sum K L (y_{k}, f_{t - 1, l} (x) + j = 0 \sum J c_{j l} I (x_{i} \in R_{j l})) (26)$

由于上式比较难优化，我们一般使用近似值代替：

$c_{q j l} = \frac{K - 1}{K} \frac{\sum _{x_{i} \in R_{q j l}} r _{t i l}}{\sum _{x_{i} \in R_{q j l}} ∣ r _{t i l} ∣ ( 1 - ∣ r _{t i l} ∣ )} (27)$

除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元 GBDT 分类和二元 GBDT 分类以及 GBDT 回归算法过程相同。

梯度提升回归决策树

梯度提升法最初提出时是以回归问题和函数逼近为出发点的，因此，理解梯度提升回归决策树（GBRT）相对容易一些，这里给出梯度回归决策树的算法描述。

GBRT 的算法流程如下。

输入：训练数据集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})}$ ， $x_{i} \in L \subseteq R^{n}$ ， $y_{i} \in R$ 。

输出：梯度提升回归树 $F (x)$ 。

过程：

初始化模型 $F_{0} (x_{i}) = \frac{\sum _{i = 1}^{N} y _{i}}{N}$ ，依据 $F_{0} (x)$ 对样本进行预测，并计算残差。

循环训练 $K$ 个模型， $k = 1, 2, \dots, K$ 。

2.1 计算残差， $h_{k} (x_{i}) = y_{i} - F_{k - 1} (x_{i})$ ， $i = 1, 2, \dots, N$ 。

2.2 基于残差和所有特征属性，训练一个回归决策树 $T_{k} (x_{i}, h_{k})$ 。

2.3 更新模型 $F_{k} (x_{i}) = F_{k - 1} (x_{i}) + η \cdot T_{k} (x_{i}, h_{k})$ ， $η$ 为学习速率，然后进入下一次循环。

得到最终的梯度提升回归树 $F (x) = F_{0} (x) + η \sum_{i = 1}^{K} T_{i} (x, h_{i})$ 。

从梯度提升回归树算法流程可以看出，它的弱分类器是依据即时计算的残差值和特征属性训练得到的，而不是像 AdaBoost 那样预先准备好的弱分类器。

随机梯度提升树

对 GBDT 进行正则化可防止过拟合。GBDT 的正则化主要有三种方式：

第一种是学习率，定义为 $η$ ，在前文中已经介绍过。对于前面的弱学习器的迭代， $F_{k} (x) = F_{k - 1} (x) + h_{k} (x)$ 。如果我们加上正则化项，则有 $F_{k} (x) = F_{k - 1} (x) + η \cdot h_{k} (x)$ 。 $η$ 的取值范围为 $[0, 1]$ 。对于同样的训练集学习效果，较小的 $η$ 意味着需要更多的弱学习器的迭代次数。通常我们用学习率和迭代最大次数一起来决定算法的拟合效果。
第二种是对 CART 回归树等弱学习器进行正则化剪枝。这在第 3 章介绍决策树剪枝时已经讲过，这里就不重复了。
第三种是通过子采样（subsample）比例进行正则化，其取值为 $(0, 1]$ 。注意这里的子采样和随机森林不一样，随机森林使用的是放回采样，而这里是不放回采样。如果取值为 1，则全部样本都使用，等于没有使用子采样。如果取值小于 1，则只有一部分样本会做 GBDT 的决策树拟合。选择小于 1 的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在 $[0.5, 0.8]$ 之间。

使用了子采样的 GBDT 有时也称作随机梯度提升树（Stochastic Gradient Boosting Tree, SGBT）。由于使用了子采样，可以通过采样分发到不同的任务去做提升的迭代，最后形成新树，从而减少弱学习器难以并行学习的弱点。

随机梯度提升树是 2002 年 Jerome H. Friedman 在 "Stochastic Gradient Boosting" 这篇论文中提出。Breiman（1996）在套袋法中引入了一个概念：将随机性注入函数估计过程中可以提高它们的性能。Friedman 受此启发，对梯度提升算法进行了小小的改动，即将随机性整合到梯度提升算法中。特别地，在每次迭代中，从所有的训练集中随机地（不重复）进行子采样，然后使用这个随机抽取的子样本而不是全部样本来拟合一个基学习器，并计算模型对当前迭代的更新。

当随机子样本数量 $\hat{N} = N$ 时就没有随机性，这个算法就和之前的 GBDT 一样。比例 $f = \hat{N} / N$ 越小，在连续迭代中的随机样本就会差别越大，因此，整个程序的随机性就越大。 $f = 1/2$ 时，算法大致等价于在每次迭代中使用套袋法。使用 $\hat{N} = f \cdot N$ 也会使得计算量减少为原来的 $1/ f$ 。然而，使用过小的 $f$ 值会减少每次迭代用来训练基学习器的数据量，这会导致单个基学习器的方差增加。

堆叠法

堆叠（stacking）（有时称为堆叠泛化）是指利用多种不同的基分类器或基回归器对样本数据进行预测，基于各个预测结果组合形成新的特征集和样本集，然后用它们来训练和测试元（meta）学习器，最终实现预测的集成学习方法。

如何组合成为关键，这里涉及模型的组合以及样本的划分与组合问题。堆叠一般采用异构的基学习器，例如同时采用线性模型、决策树模型甚至各类深度学习模型等，并对这些基学习器的预测输出进行组合。如果采用等权重的组合，则不需要对预测结果做进一步的处理，但是这样效果并不好，因为我们不知道哪个基学习器更优秀，这也失去了使用各种异构基学习器的优势。如果采用不同权重的组合，那么问题是各个基学习器的权重该如何确定。办法依然是有监督的训练。因此，在堆叠法中，需要对样本数据进行有效划分，以支持多层次的训练同时防止过拟合出现。

首先看模型如何堆叠。如图 5.16 所示，使用多个模型（例如 KNN、决策树或 SVM）的预测结果来建立一个新的模型，这个最终的模型被用来对测试数据集进行预测。因此，我们在堆叠中所做的是，将训练数据通过多个模型来运行。这些模型通常被称为基学习器、基础学习器或基础模型，我们从这些模型中产生预测结果。然后，这些预测值被作为输入送到下一级或者基础模型，而不是进行投票或者聚合。该模型将给出最后的预测。根据所要处理的是回归问题还是分类问题，可以选择不同的模型。堆叠的概念是非常有趣的，它开辟了很多的可能性。但是，以这种方式做堆叠会带来一个巨大的风险，那就是模型的过拟合，因为正在使用整个训练数据来创建模型，并由此进行预测。

因此，样本数据的划分变得非常重要。依据交叉验证的思想，在基学习器的训练中，采用 K 折交叉验证的思想，这些样本数据在第二阶段被用作训练样本集依然作为第二阶段的测试样本，从而获得最终的预测结果。

堆叠集成学习方法主要关注两个方面：

模型的组合，包括各种基学习器的选择和训练过程，以及后续阶段会利用前面阶段的预测结果进行集成模型的训练。
模型的过拟合问题的解决，主要依托交叉验证等思想，对样本集进行划分，并改进训练过程。在此过程中，需要生成新的训练样本和测试样本数据。根据处理方式的不同，堆叠法衍生出了几种变种。下面首先从二阶段堆叠模型开始介绍。

简单的二阶段堆叠算法

首先介绍一种最简单的二阶段堆叠算法。基学习器的训练作为第一阶段，这一阶段与各个基学习器的特征有关。如果有 $T$ 个基学习器，则分别使用训练数据集 $D$ 对它们进行训练，获得 $T$ 个预测结果，将这些预测结果组合成一个特征向量，即 $(h_{1} (x_{i}), h_{2} (x_{i}), \dots, h_{T} (x_{i}))$ ，其与实际目标变量值 $y_{i}$ 构成一条新的训练数据。对于原始的 $m$ 个样本数据，可以产生新的 $m$ 个训练数据，构成数据集 $D_{1}$ ，新的训练数据的特征属性全部发生了变化，且只有 $h_{i} (x_{i})$ 以及最后的模型 $H (x)$ 。在这个过程中， $T$ 个基学习器（集成模型）进行训练，获得新的模型选择。算法描述如下。

输入：训练数据 $D = {x_{i}, y_{i}}_{i = 1}^{m}$ ， $x_{i} \in R^{n}$ ， $y_{i} \in Y$ 。

输出：一个集成分类器 $H$ 。

步骤1：训练第一级分类器

for $t \leftarrow 1$ to $T$ do

　基于数据集 $D$ ，训练一个基分类器 $h_{t}$

end for

步骤2：从数据集 $D$ 中构建新数据

for $i \leftarrow 1$ to $T$ do

　构建包含 $(x_{i}^{'}, y_{i})$ 新数据集，其中 $x_{i}^{'} = (h_{1} (x_{i}), h_{2} (x_{i}), \dots, h_{T} (x_{i}))$

end for

步骤3：训练第二级分类器

基于新构建的数据集训练一个新的分类器 $h^{'}$

return $H (x) = h^{'} (h_{1} (x), h_{2} (x), \dots, h_{T} (x))$

基于 K 折交叉验证的二阶段堆叠法

上文介绍的简单的二阶段堆叠算法容易出现过拟合问题，为此可以使用交叉验证来准备二级分类器的输入数据。因此，需要对输入数据进行划分：样本数据集被分成 $K$ 个折，在连续的 $K$ 轮中， $K - 1$ 个折被用来训练第一阶段的基学习器；在每轮的第一阶段的基学习器进行验证，每个基学习器使用的训练集和验证集都有一些差异。然后，所得的预测结果被组合起来，并作为输入数据提供给第二阶段的元学习器。

基于 K 折交叉验证的堆叠法的算法流程如下：给定样本数据集 $D$ ，特征向量为 $x_{i}$ ，目标变量为 $y$ ，假设有 $m$ 个样本，每个样本的特征向量 $x_{i}$ 有 $n$ 个特征属性， $T$ 个基学习器。

步骤1：首先将样本数据集 $D$ 划分为 $K$ 个大小相等的折（子集） $D_{1}, D_{2}, \dots, D_{K}$ ，类似于 K 折交叉验证过程，然后开始训练 $T$ 个基学习器，执行 $K$ 轮训练。每轮训练中，选取除 $D_{k}$ 折以外的其他 $K - 1$ 个折作为训练数据，迭代训练各个基学习器 $h_{t}$ 。把 $D_{k}$ 折作为验证集，利用该轮更新的每一个基学习器 $h_{t}$ 对 $D_{k}$ 折中的每一个样本 $x_{i}$ ，得到一组预测值 $h_{1} (x_{i}), h_{2} (x_{i}), \dots, h_{T} (x_{i})$ ，将这些预测值构成一个特征向量，联合原来的实际目标变量值 $y_{i}$ ，构成一个新的训练数据。这样每轮实际获得了 $∣ D_{k} ∣$ 个新的训练数据。经过 $K$ 轮，实际获得的新训练数据为 $m$ 个。

步骤2：利用新创建的训练数据对元学习器进行训练。

步骤3：在整个数据集 $D$ 上重新训练生成基学习器。然后利用更新后的基学习器对测试集进行预测，并形成新的测试数据集供元学习器作为测试集使用。或者，可以尝试在一开始就把 $D$ 分成训练和测试集。在训练部分进行步骤1和步骤2，然后只在测试集上重新训练基学习器。这样做的一个好处是可以减少时间，因为它不需要在全部数据上工作。

K 折交叉验证的堆叠法的伪代码描述如下。在整个过程中的训练样本和测试样本的派生过程见图 5.19。

输入：训练数据集 $D = {x_{i}, y_{i}}_{i = 1}^{m}$ ， $x_{i} \in R^{n}$ ， $y_{i} \in Y$ 。

输出：一个集成分类器 $H$ 。

步骤1：采用交叉验证的方式为第 2 级分类器准备一个训练集

随机将数据 $D$ 分割为 $K$ 个等大小的子数据集： $D = {D_{1}, D_{2}, \dots, D_{K}}$

for $k \leftarrow 1$ to $K$ do

　步骤1.1：训练第 1 级分类器

　for $t \leftarrow 1$ to $T$ do

　　从 $D ∖ D_{k}$ 中训练分类器 $h_{k t}$

　end for

　步骤1.2：为第 2 级分类器构建一个训练集

　for $x_{i} \in D_{k}$ do

　　获得一个记录 ${x_{i}^{'}, y_{i}}$ ，其中 $x_{i}^{'} = (h_{k 1} (x_{i}), h_{k 2} (x_{i}), \dots, h_{k T} (x_{i}))$

　end for

end for

步骤2：训练第 2 级分类器

基于集合 ${x_{i}^{'}, y_{i}}$ 训练一个新的分类器 $h^{'}$

步骤3：重新训练第 1 级分类器

for $t \leftarrow 1$ to $T$ do

　基于 $D$ 训练一个分类器 $h_{t}$

end for

return $H (x) = h^{'} (h_{1} (x), h_{2} (x), \dots, h_{T} (x))$

概率统计100问

NO.45.tip： 提升法与堆叠法

背景

源与流

NO.45.tip：提升法与堆叠法