集成学习：AdaBoost、GBDT、XGBoost、Bagging、RF

发表于 2025-05-29 分类于机器学习本文字数： 5.3k

概论

集成学习（Ensemble Learning）一般结构：产生一组个体学习器（Individual Learner）再用某种策略把他们结合起来。

根据所有个体学习器相同与否分为“同质”（homogeneous）和“异质”（heterogenous）。

根据个体学习器的生成方式，目前的集成学习方法大致分为两大类：

个体学习器之间存在强依赖关系，必须串行生成个体生成器，如 Boosting
不存在强依赖关系，可以并行生成个体生成器，如 Bagging 和 Random Forest

Boosting

Boosting 是指一类将弱学习器提升为强学习器的集成算法：

先从初始训练集训练出一个基学习器；
根据基学习器的表现对训练样本的分布做出调整，使得预测错误的样本得到更多关注；
基于调整后的训练样本训练下一个学习器；

重复训练 $T$ 个学习器，然后再进行加权结合。

从偏差-方差角度来讲，Boosting方法主要关注于降低偏差。

Note

偏差-方差分析

假设目标函数：

$y = f(x) + \varepsilon$

其中：

$f(x)$ 是数据的真实生成过程；
$\varepsilon$ 是观测噪声，满足 $\mathbb{E}[\varepsilon] = 0$ ， $\text{Var}(\varepsilon) = \sigma^2$ ；
我们学习的模型是 $h(x)$ ，依赖于从数据集中学到的模型参数。

对于一个数据点 $(x,y)$ ，泛化误差的期望是：

$\mathbb{E}_{\mathcal{D},\varepsilon}\left[(y - h(x))^2\right] = \mathbb{E}_{\mathcal{D},\varepsilon}\left[(f(x) + \varepsilon - h(x))^2\right]$

展开后得到：

$= \underbrace{( \mathbb{E}_{\mathcal{D}}[h(x)] - f(x) )^2}_{\text{偏差（Bias）}^2} + \underbrace{\mathbb{E}_{\mathcal{D}}[(h(x) - \mathbb{E}[h(x)])^2]}_{\text{方差（Variance）}} + \underbrace{\sigma^2}_{\text{噪声（Noise）}}$

直观地理解：对于一个数据点，我们希望用相同数量的样本集训练这个模型时，能够得到相近的结果，且尽可能地贴合其标签。

	数学形式	含义
偏差 (Bias²)	$(\mathbb{E}[h(x)] - f(x))^2$	模型预测的平均值与真实值（注意不是标签）之间的误差
方差 (Variance)	$\mathbb{E}[(h(x) - \mathbb{E}[h(x)])^2]$	模型预测随不同训练集波动性大小
噪声 (Noise)	$\sigma^2$	数据本身的不可预测性

偏差-方差权衡（Bias-Variance Tradeoff）：提高模型复杂度可以减少偏差，但可能增加方差。

AdaBoost

宏观分析

$H(x) = \sum_{t=1}^T \alpha_t h_t(x)$

$h_t(x)$ 表示一个弱分类器，个体学习器；
$\alpha_t$ 衡量每个弱分类器的重要性；

宏观上看，AdaBoost 所做的是训练 $T$ 个基学习器组成一个集成学习器 $H(x)$ ，在组合过程中不断最小化 $H(x)$ 的指数损失函数：

$\begin{aligned} \mathcal{L}_{exp}(H|\mathcal D) =& \mathbb E_{(x, y) \sim \mathcal D} [e^{-y \cdot H(x)}] \\ =&e^{-H(x)} \cdot P(y=1 \mid x) + e^{H(x)} \cdot P(y = -1 \mid x) \end{aligned}$

使用指数函数是因为将其求关于 $H(x)$ 的偏导并使偏导为 $0$ 时，此时位于最低值位置的 $H(x)$ 有：

$\mathrm{sign}(H(x)) = \mathrm{sign} \left(\frac{1}{2} \log \frac{P(Y=1|x)}{P(Y=-1|x)}\right)$

上面的式子中，当正类概率大于负类时， $\mathrm{sign}(H(x))$ 为 1，反之为 -1，这符合我们想要的预测效果。故最小化指数损失函数，其实也是在寻找一个能够最大化贝叶斯准确率（使用了log-likelihood来近似）的 $H(x)$ 。

实际实现

步骤：

初始化权重
训练分类器
根据分类器的错误率 $\alpha_t = \frac{1}{2} \ln\left(\frac{1 - \varepsilon_t}{\varepsilon_t}\right) $调整该分类器的权重
根据分类器在某个样本上的偏差调整该样本的权重 w_{t+1}^{(i)} = w_t^{(i)} \cdot e^\left(-\alpha_t y_i h_t(x_i)\right)
归一化权重
进行下一个学习器的训练

具体步骤实现：

初始化样本权重 $w$ ，记在训练第 $t$ 个学习器时，第 $i$ 个样本的权重是 $w_{t}^i$ ：

$w_1^{(i)} = \frac{1}{m}, \quad i=1, 2, \dots, m$

训练一个弱分类器 $h_t(x)$ ，使得加权错误率最小，记 $\varepsilon_t$ 为第 $t$ 个基分类器的错误率：

$\varepsilon_t = P(y\neq h_t(x)) = \sum_{i=1}^m w_t^{(i)} \cdot \mathbb{I}(h_t(x_i) \ne y_i)$

计算弱分类器的系数（权重）：

$\alpha_t = \frac{1}{2} \ln\left(\frac{1 - \varepsilon_t}{\varepsilon_t}\right)$

这个更新权重的方式是由指数函数损失对 $\alpha_t$ 的偏导为 0 得到的，使用 $\varepsilon_t$ 计算的 $\alpha_t h_t$ 的指数损失函数如下：

$\begin{aligned} \mathcal{L}_{exp}(\alpha_th_t|\mathcal D) =& \mathbb E_{(x, y) \sim \mathcal D} [e^{-y \cdot \alpha_t h(t)}] \\ =& e^{-\alpha_t} P(h_t(x) = y) + e^{\alpha_t} P(h_t(x) \neq y) \\ \quad &// h_t(x)y \text{ 大于 0 } 说明正确，反之说明错误 \\ =& e^{-\alpha_t} \cdot (1-\varepsilon_t) + e^{\alpha_t} \cdot \varepsilon_t \end{aligned}$

更新样本权重，根据第 $\alpha_t h_t$ 个学习器在该样本上的指数函数损失更新其权重：

$w_{t+1}^{(i)} = w_t^{(i)} \cdot e^{\left(-\alpha_t y_i h_t(x_i)\right)}$

然后归一化使得 $\sum_{i=1}^m w_{t+1}^{(i)} = 1$

梯度提升决策树 GBDT

Gradient Boosting Decision Tree

每个学习器的都是一个CART回归树，前 $t$ 个学习器的集成预测 $H_t(x)$ 的一般形式是前 $t-1$ 个学习器的预测加上第 $t$ 个学习器的预测（ $\gamma$ 是学习率）：

$H_t(x) = H_{t-1}(x) + \gamma h_t(x)$

在第 $t$ 轮，我们要构造一棵树来拟合上一轮损失函数对输出的误差：

$\mathcal{L}^{(t)} = \sum_{i=1}^n \ell(y_i, H_{t-1}(x_i) + h_t(x_i))$

在这里， $H_t(x_i)$ 和 $h_t(x_i)$ 都属于自变量空间，而 $\ell$ 是因变量。这个朴素目标对于决策树来说太难优化了。因为我们要优化的是一个树，无法像神经网络那样计算损失然后求导反向传播来改变树的结构。在构建树的过程中，我们需要知道其目标值是什么，用于监督树的构建。由于在训练 $t$ 个树的时候，前 $t-1$ 的都已经构建完成，于是，把损失函数 $\ell$ 前面的模型 $H_{t-1}(x_i)$ 处泰勒展开为：

$\ell(y_i, H_{t-1}(x_i) + h_t(x_i)) \approx \ell(y_i, H_{t-1}(x_i)) + \frac{\partial \ell}{\partial H_{t-1}(x_i)} h_t(x_i)$

一阶泰勒展开告诉我们， $\ell$ 在 $H_{t-1}$ 处沿着 $\frac{\partial \ell}{\partial H_{t-1}(x_i)}$ 的方向增大，所以我们需要让自变量往这个梯度的相反方向移动，也就是自变量的增值 $h_t(x_i)$ 以负梯度作为其目标值，于是 $h_t(x_i)$ 的目标值为：

$r_i^{(t)} = - \left[ \frac{\partial \ell(y_i, H_{t-1}(x_i))}{\partial H_{t-1}(x_i)} \right]$

当 $h_t(x_i)$ 的目标值是这个的时候，因变量就会在 $H_{t-1}(x_i)$ 沿着负梯度的方向变化，从而降低 $H_t(x_i)$ 时的损失。注意，我们还有学习率的存在，其控制我们具体走多长的步伐。

Note

从优化角度看：GBDT 是在函数空间中做梯度下降。区别于神经网络模型的梯度下降，神经网络模型是在参数空间的梯度下降，即通过修改参数来降低损失函数的值，也就是对参数求偏导。GBDT 在函数空间做梯度下降，是通过构造函数来实现集成模型的损失降低，每一步都在尝试构建一个新的函数去逼近当前损失函数对模型输出的负梯度，进而让整体集成的模型的损失往梯度下降方向走一步；

设损失函数为平方损失 $\ell(y_i, H_{t-1}(x_i)) = \frac{1}{2} (y_i - H_{t-1}(x_i))^2$ ，对 $H_{t-1}(x)$ 求偏导得到 $(y_i - H_{t-1}(x_i))$ ，再对梯度求负得到 $r_i^{(t)} = y_i - H_{t-1}(x_i)$ ，所以很多情况下，第 $t$ 个学习器拟合的是真实值与前面 $t-1$ 个学习器的残差。

XGBoost

XGBoost 是 GBDT 的变种，加入了：

二阶梯度优化：将 $h_t$ 的损失在模型 $h_{t-1}$ 附近做二阶泰勒近似，则其损失函数为：

$\begin{aligned} \mathcal{L}^{(t)} &= \ell(y_i, H_{t-1}(x_i) + h_t(x_i)) \\ &\approx \sum_{i=1}^n \left[ \ell(y_i, H_{t-1}\left(x_i)\right) + \frac{\partial \ell}{\partial H_{t-1}(x_i)} h_t(x_i) + \frac{1}{2} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} h_t^2(x_i) \right] + \Omega(h_t) \end{aligned}$

去除常数项后，我们可以得到其优化目标为

$\begin{aligned} \mathcal{\widetilde L}^{(t)} &= \sum_{i=1}^n \left[ \ \frac{\partial \ell}{\partial H_{t-1}(x_i)} h_t(x_i) + \frac{1}{2} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} h_t^2(x_i) \right] + \Omega(h_t) \end{aligned}$
正则化 $\Omega$ 控制模型复杂度，防止过拟合

$\Omega(h_t) = \gamma Leaves+ \frac{1}{2} \lambda \sum_{j=1}^{Leaves} w_j^2$

$Leaves$ ：树的叶子数
$w_j$ ：第 $j$ 个叶子节点的分数（回归树的预测值）
$\gamma$ 和 $\lambda$ 是两个超参数

推导最优叶子分数：GBDT 直接让叶子来拟合负梯度，因此叶子的分数通常是其内所有样本负梯度的平均值。而 XGBoost 在构建树的结构后，会根据损失函数推导一个最优的叶子分数 $w_j^*$ ，使得损失函数最小。

前面的优化目标中，我们是根据训练样本的损失来构建的，现在，我们可以用所有叶子的损失之和来等价训练样本的损失。舍弃二阶近似中的常数项、展开正则化项、合并同类项后，我们可以得到（ $I_j$ 表示叶子 $j$ 中的样本集合， $w_j$ 表示该叶子输出的分数）：

$\tilde{\mathcal{L}}^{(t)} = \sum_{j=1}^{Leaves} \left[ \left( \sum_{i \in I_j} \frac{\partial \ell}{\partial H_{t-1}(x_i)} \right) w_j + \frac{1}{2} \left( \sum_{i \in I_j} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda \right) w_j^2 \right] + \gamma Leaves$

求该函数的最值点，即求 $w_j$ 的偏导并让导数为 $0$ ，我们可以求得：

$w_j^* = - \frac{\sum_{i \in I_j} \frac{\partial \ell}{\partial H_{t-1}(x_i)}}{\sum_{i \in I_j} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda}$

此即为叶子结点 $j$ 的预测值。
推导树的损失和构建树：将叶子节点的分数代入 $\widetilde{\mathcal L}^{(t)}$ 可得到整个决策树结构的损失：

$\tilde{\mathcal{L}}^{(t)} = -\frac{1}{2} \sum_{j=1}^T \frac{ \left(\sum_{i \in I_j} \frac{\partial \ell}{\partial H_{t-1}(x_i)}\right)^2 } { \sum_{i \in I_j} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda }$

这个损失函数可以用来衡量第 $t$ 个决策树结构的质量，帮助我们构建 $h_t$ 。通常来说，我们无法枚举所有决策树结构来获取最优的 $h_{t}$ ，一般都是在构造 $h_t$ 的每一步贪心地选择分支的属性及其值。有了上面的整棵树的损失函数，对于每次分支，当前节点及其样本集 $I$ 在分支前的损失为：

${\mathcal{L}}_{before} = -\frac{1}{2} \frac{ \left(\sum_{i \in I} \frac{\partial \ell}{\partial H_{t-1}(x_i)}\right)^2 } { \sum_{i \in I} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda }$

在分支后，其分裂成两个节点，包含的样本集分别为 $I_R$ 和 $I_L$ ，两个节点的损失之和为：

${\mathcal{L}}_{after} = -\frac{1}{2} \left[\frac{ \left(\sum_{i \in I_L} \frac{\partial \ell}{\partial H_{t-1}(x_i)}\right)^2 } { \sum_{i \in I_L} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda } + \frac{ \left(\sum_{i \in I_R} \frac{\partial \ell}{\partial H_{t-1}(x_i)}\right)^2 } { \sum_{i \in I_R} \frac{\partial^2 \ell}{\partial H_{t-1}^2(x_i)} + \lambda }\right]$

然而，需要注意的是，相比分裂前，整棵树会多一个叶子节点，所以分裂的损失应该加上一个 $\gamma*1$

$\mathcal L_{splite} = \mathcal L_{after} - \mathcal L_{before} + \gamma$

于是乎，我们在每次选择分裂的属性及根据哪个值进行分裂时，选择的依据为能带来最大的 $\mathcal L_{split}$ 的属性和划分点。
缩减（Shrinkage）与列采样（Column Subsampling）：对于每一步 $h_{t}(x_i)$ 的结果，会乘以一个学习率 $\eta$ 再加上 $H_{t-1}(x_i)$ 。在构建决策树的时候，使用了 Random Forest 的列采样技术，在构建每一棵树或每个节点时，随机选择部分特征用于寻找最佳切分点，从而引入随机性，降低过拟合风险。
近似贪婪：在划分属性时，除了严格地枚举所有可能的枚举点之外，还可以采用近似算法。其先找到候选的分位数，并要求小于分位数的样本的二阶导数之和占全部样本的二阶导数之和的比例的差异不能超过某个阈值 $\epsilon$ ，以此保证分位数之间的样本数量均衡，没有过大或过小的桶。

令 $\mathcal D_k=\{(x_{ik},b_i)\}$ 表示所有样本的第 $k$ 个属性的值及损失对该样本的二阶导数 $b_i$ ， $r_k(z)$ 表示属性值 $k$ 小于 $z$ 的所有样本的二阶导数之和占全部样本的比例：

$r_k(z) = \frac{1}{\sum_{(x, b)\in\mathcal D_k}b} \sum_{(x,b)\in \mathcal D_k, x < z} b$

我们的目标是找到一群切分点 $\{s_{k1}, s_{k2},... s_{kl}\}$ （总共 $l$ 个）使得

$|r_k(s_{k,j}) - r_k(s_{k,j+1})| < \epsilon, s_{k1} = \min_{i}x_{ik}，s_{kl} = \max_i x_{ik}$

也就是下一个被选中的分位数与上一个被选中的分位数之间的差值必须小于 $\epsilon$ ，划分点之间形成的桶总是有着近似相等的Hessian总和。此时 $1/\epsilon$ 表示可能作为候选的划分点的大致数量。
稀疏处理/缺失值处理：在分裂节点时，仅考虑每个特征的非缺失样本中枚举所有可能的切分点。在划分后，考虑分裂特征为缺失值的样本全部默认走左子树或右子树两种情况，分别计算增益，选择增益较大的方向作为该值缺失的样本在当前节点的默认走向。在枚举每个属性的切分点的时候，0 值也会被全部跳过，不会枚举切分点。而且 0 值样本也会被看做是缺失值样本分配一个默认走向。
系统层优化：
1. CSC（compressed column）：在开始训练之前，把每一列排序后存储在一个连续的内存块中，而不是以行为单位存储。这样之后，每个节点分裂后节点内的样本每一列特征仍然会保持有序状态，而且可以并行化地处理多个特征，同时得到多个特征的增益，因为他们的内存完全独立。并且由于每个特征内的每个值是连续内存的，所以CPU读取很快，相比行存储减少了大量的随机读取。
2. 缓存预取 Prefectching：由于 CSC 是连续的，所以我们天然地可以在 CPU 计算某个样本的梯度的时候，提前将下一步样本准备好并放入 CPU 缓存。

Bagging

使用自助采样法将训练集划分为 $T$ 个含有相同数量 $m$ 的采样集，用这 $T$ 个数据集训练 $T$ 个基学习器。

这种方法源自于集成学习的个体学习器互补逻辑：要得到性能更优的预测，集成中的个体学习器应该尽可能相互独立。如果分类器的错误率相互独立，则可以由 Hoeffding 不等式推导出其错误率会随着个体分类器的数量的增大而指数下降。

自助采样法：随机选取一个样本放到采样集，然后将其返回原数据集。

Note

设 $X_1, X_2, \dots, X_n$ 是独立的随机变量，且每个 $X_i$ 的取值区间为 $[a_i, b_i]$ 。定义 $S_n = \sum_{i=1}^n X_i$ ，则对任意 $t > 0$ ，有：

$P\left( S_n - \mathbb{E}[S_n] \geq t \right) \leq \exp\left( -\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),$

$P\left( \mathbb{E}[S_n] - S_n \geq t \right) \leq \exp\left( -\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right).$

随机森林

随机森林可以看作是 Bagging 的一个变体，其在 Bagging 的基础上，根据决策树的特性，引入了随机属性选择。

决策树中：选择划分属性时在当前节点的属性集合中选择一个最优属性进行划分

随机森林：先随机选择一个大小为 $k$ 的属性子集，再从这个子集中选择要一个最优属性进行划分

可以看出，Bagging 试图让各个个体学习尽可能独立的方法是给他们不同的训练集，而随机森林是直接根据决策树的模型特点，从其构建过程中直接引入随机性来增加个体学习器之间的独立性。

模型融合

简单策略

对所有个体学习器的预测结合的方法通常有：

回归
- 简单平均
- 加权平均，权重一般从训练数据中学习而来
分类
- 绝对多数投票：超过半数则作为预测，没有超过半数的则拒绝预测
- 相对多数投票：随机选取一个得票最多的标记
- 加权投票：与加权平均类似

投票可分为：

硬投票：用最终标记投票
软投票：用概率投票

学习法：Stacking 堆叠集成

用交叉验证法分割数据集，对每一折数据的训练集上都训练一个基学习器 $h_{t}^{(j)}$ （在第 $j$ 折训练集上训练的第 $t$ 个模型），并用相应的测试集来输入该学习器得到其输出 $z_i^{(t)}$ （第 $t$ 个学习器对第 $i$ 个样本的预测），组合所有的 $z_{i}^{(t)}$ 形成数据集 $(z_i, y_i)$ 用来训练一个次级学习器 $g$ ， $g$ 将会根据所有的

训练个体学习器：
- 对每个基学习器 $h_j$ ，用 K 折交叉验证生成对每个训练样本的 out-of-fold 预测值：
  
  $z_i^{(t)} = h_t^{(j)}(x_i)$
  
  其中 $h_{t}^{(j)}$ 表示在第 $j$ 折训练集上训练的第 $t$ 个模型；
- 这样可以避免学习器直接输出训练集的标签，导致过拟合，提高泛化能力。
构造新的训练集：
- 组合所有个体学习器的输出，得到新特征：
  
  $z_i = [z_i^{(1)}, z_i^{(2)}, ..., z_i^{(T)}]$
- 对应的标签仍是 $y_i$ 。
训练次级学习器（Meta-Learner）：
- 用 $(z_i, y_i)$ 训练 meta-learner $g(z)$ 。
预测时流程：
- 先用 base learners 对测试集进行预测，得到 $z_{\text{test}}$ ；
- 然后用 meta-learner 对 $z_{\text{test}}$ 输出最终预测。

多样性

误差-分歧分解

构建好的集成学习器应该让所有个体学习器好而不同，下面形式化这一性质。集成分歧是个体学习器与最终集成学习器之间的差异，比如每个学习器的预测和最终集成学习器的预测的加权 MSE。

$\bar A(h | x) = w_i\sum_i^T(h_i(x) - H(x))^2$

其中的累加的每一项称为个体学习器 $h_i$ 的分歧 $(h_i(x) - H(x))^2$ 。

记 $E(h_i|x)$ 为 $h_i$ 的误差，即 $E(h_i|x)=(h_i(x)-y)^2$ ，则个体学习器的误差的加权平均值为：

$\overline E(h|x) = \sum_{i=1}^T w_i(h_i(x)-y)^2$

从上面两条式子中，我们可以推导出分歧与集成学习器的误差之间的关系，即

$\begin{aligned} \overline A(h|x) &= w_i\sum_i^T(h_i(x) - H(x))^2 \\ &= \sum_i^Tw_i \left(h_i(x)^2 - 2h_iH(x) + H(x)^2 \right)\\ &= \sum_i^T w_ih_i(x)^2 - 2H(x)\sum_i^T w_ih_i(x) + H(x)^2 \\ &= \sum_i^T w_ih_i(x)^2 - 2H(x)^2 + H(x)^2 \quad // \sum_{i}^Tw_ih_i(x) = H(x) \\ &= \sum_{i=1}^T w_ih_i(x)^2 - H(x)^2 \\ &= \sum_{i=1}^T w_i(y-h_i(x))^2 - (f(x)-H(x))^2 \quad // \sum_{i}^T2w_ih_i(x)y = 2H(x)y\\ &= \sum_i^T w_i E(h_i|x) -E(H|x) \end{aligned}$

可以推导出 集成学习的泛化误差=个体学习器的误差加权平均值-集成分歧，此即为误差分歧分解：

$E(H|x)=\overline{E}(h|x) - \overline{A}(h|x)$

上式即为误差-分歧分解，可以看到个体误差越低、分歧越高，则集成的误差越低：

个体学习器偏差足够小的情况下，缺少多样性也无所谓；
个体学习器偏差过大但是分歧也比较大，多样性比较好的话也可以弥补。

度量多样性

to be continue…

概论

Boosting

AdaBoost

宏观分析

实际实现

梯度提升决策树 GBDT

XGBoost

Bagging

随机森林

模型融合

简单策略

学习法：Stacking 堆叠集成

多样性

误差-分歧分解

度量多样性

参考资料