本文将简要介绍 Boosting 这一集成学习方法，主要包括 Gradient Boost ，XGBoost ，以及对 Adaboost 的详细建模和收敛性分析。

Boosting

• Boosting 的优化方向与 bagging 截然不同，此处我们关注的是优化偏差，也就是更侧重于模型能力。简单的说，boosting 可以概括为通过给数据点加权或是修改损失函数训练出侧重点不同的模型，再将它们结合起来，以期整合弱模型的能力达到强模型水平。以下我们将介绍 Gradient boost 、Adaboost 和 XGBoost 。

Gradient Boost

• 尽管 Adaboost 实际上更早发明，但我们还是要先介绍 Gradient boost ，因为 ababoost 的理论框架不如 Gradient boost 漂亮，可以被后者包含。尽管如此我们还是要介绍 adaboost 的原因是 gradient boost 的理论细节难以分析，而 ababoost 作为一个特例可以给出漂亮的收敛性证明。

• 总的来说，Gradient Boost 这一方法，顾名思义，其动机来源于直接在函数空间中做梯度下降。在一般的集成学习框架中，我们希望学习一系列模型 ，并以某种方式组合得到最终假设： 现在假设所有的假设都落在一定的函数空间 中¹，从 开始，对于给定的损失函数 ，我们希望优化： 对此我们希望采取某种类似于梯度下降的方式。然而函数空间的梯度甚至是难以定义的，遑论解析解。²所以此处我们要采取折衷的方式。具体的，令向量 ， ，将损失写成 ，则可以对于 定义梯度： 我们希望找到一个函数，使其可以在各个数据点处拟合这些梯度值，并期待该函数真的可以代表损失下降的方向。具体的，假设已经得到 ，对于下一个假设 ，选择损失函数： 是为对于梯度诱导的新数据集的 MSE 。优化上式得到 后选择一定的学习率 并迭代得到： 然后重复该过程直到达到 次的上限为止，这便是 Gradient Boost 。

• 特别的，尽管我没做过严格推导，我非常怀疑以上的框架仅限于动机而难以严格化。恐怕 Gradient Boost 的收敛性证明需要细致的个例分析吧。

Adaboost

• Adaboost 的思想是通过弱学习器（Weak Learner）得到的多个弱假设（Weak Hypothesis）整合得到一个强假设（Strong hypothesis）。在 Gradient Boost 的框架中，其等于说每一次都只能使用弱学习器产生的弱假设来拟合梯度。

弱学习器

• 我们要先严格定义弱学习器。

  • 【定义 1. 弱学习器】给定训练集 ，称 弱学习器存在，当且仅当对于 的 个数据点上的任何分布 ，都存在一个弱假设 使得在 上：

  • Remark. 弱学习器的存在性在实践中一般作为前提假设。这是因为实践中的数据集多少是有点规律可以学的；另一方面，我们也不可能证明 弱学习器的广泛存在，因为至少在均匀随机的分布上不可能存在任何学习器能做到正确率好于 。

Adaboost 的理论框架

• 现在我们先介绍 Adaboost 本身的理论建模。假定存在一个 弱学习器，使得对于任意训练集 上的分布，都可以找到一个假设 ，使得： 现在我们期望通过组合若干个弱假设 ，得到强假设： 并定义预测为 ，我们期待强假设的分类错误率趋于 。为了优化 ，采取 ERM ： 直接优化 是一件困难的事，因此我们期望通过某种贪心的方式来逐步优化 的每一项。在一开始设定 ，进行总共 轮优化，每一轮基于先前的 来优化 ，并迭代： 这便是 adaboost 的主要框架。具体的，在第 轮时，优化目标为： 令 ，则上式等价于： 同时优化 和 是一件困难的事，因此先优化 ，再优化 。注意到 的值域为 ，因此： 固定 时，显然上式取得最小值时有： 现在考虑如何优化 。由于 ，显然优化式 等价于使得满足 （即预测正确）的权重之和最大。将 归一化得到 ，则得到： 按照【定义 1. 弱学习器】，我们可以找到一个相对好的弱假设 ，使用该弱假设即可。以上即为 adaboost 的完整框架。

• 我们希望将 adaboost 规约为某种 gradient boost 。为此，选择式 作为 gradient boost 的损失函数，其关于 的梯度为（丢弃 ）： 按照 gradient boost ，在 MSE 度量下使用 来拟合负梯度： 从而最小化 MSE 等价于最大化： 显然等价于最大化分类正确的权重之和，即： 这样，我们就说明了 adaboost 选择弱假设的一步本质上等价于拟合 的梯度。然而 adaboost 还需要优化 ，而 gradient boost 则设置了固定的学习率。这在经验上有一些区别，导致：

  1. adaboost 可能在训练集上收敛更快，但是泛化误差较大。
  2. gradient boost 的训练更慢，但是泛化性更好。

  特别的，现在的 boost 模型一般都在 gradient boost 的框架下，选择设置固定学习率。

Adaboost 的收敛性证明

• Adaboost 作为早期的模型，其相对简单的形式和优美的理论建模保证了其简单优雅的收敛性分析。具体的，我们有如下引理：

  • 【引理 1. Exponential Decay】即第 轮迭代结束后的强假设 为 ，则有：

  证明：[Admitted]³

  现在分析强假设的（训练）错误率，注意到： 因此： 若令分类错误率小于 ，则显然不可能有任何一个训练集中的数据点分类错误。由于： 有： 做泰勒展开得到 ，因此： 因此组合 个弱假设就可以达到零训练错误率了。

弱学习器的实现

• 首先需要说明的是，我们并不能证明弱学习器的广泛存在，因为这和数据的分布相关，因此往往要假设在给定的数据集上存在某个 弱学习器。弱学习器的选择比较广泛，例如决策树桩（decision stump），是为一层的决策树，比较简单，这里就不介绍了。值得一提是 boosting 选择的基模型一般要做强正则化，这可能是为了避免基模型本身的倾向导致集中效果不佳。
• 一个有趣的看法是，既然 boosting 针对偏差优化，bagging 又针对方差优化，那能不能对 boosting 做 bagging ？一般来说，不建议这样做，因为算力开销太大。而且一个更好的选择是在 boosting 的基模型中引入 bagging 的技巧作为强正则化，例如自助采样和特征采样，这样便可（一定程度上）集中 boosting 和 bagging 的优点。

XGBoost

• 尽管本文中介绍的绝大部分方法的表现都与业界真实使用的方法具备较大差距，本篇介绍的 Gradient Boost 实际上已经距离 Boosting 方法使用情景下的 SOTA 很近了。因此以下我们将要介绍实践中广泛使用的方法，XGBoost 。具体的，相比采用 Gradient Tree Boosting ，XGBoost 采用了以下改进：

  1. 对损失函数做额外的正则化。 其中 是决策树的叶子数目， 是每个叶子的预测标签， 是额外的超参数。

  2. 仿照随机森林，在构建决策树做节点的分划时使用随机取样的标签集。

  3. 不再仅使用梯度，而使用基于 Hessian Matrix 的二阶优化方法。

  关于 XGBoost 的详细介绍，参见 https://github.com/dmlc/xgboost 。

---

1. 对于 没什么要求，毕竟这只是动机。↩︎

2. 在性质足够好的函数空间（例如 RKHS ）中，确实可以定义 Frechet 导数，并使用再生核定义梯度。但是都有 RKHS 了为什么不做 Kernel Trick 啊，更别说后者的效果好不好还另说。↩︎

3. 感觉证明比较繁琐，意思不大，有时间再补。↩︎