梯度提升树

1. 背景概述

假定输入与输出的真实关系为 $\mathbf{y}=g(\mathbf{x})$，对于 $T$ 个不同的模型 $h_1(\mathbf{x}),h_2(\mathbf{x}),\dots,h_T(\mathbf{x})$，每个模型的期望错误为

$\begin{aligned} \mathcal R(h_t)&=E_\mathbf{x}\left[\left(h_t(\mathbf{x})-g(\mathbf{x})\right)^2\right]\\ &=E_\mathbf{x}\left[\epsilon_t(\mathbf{x})^2\right] \end{aligned}$

其中 $\epsilon_t(\mathbf{x})=h_t(\mathbf{x})-g(\mathbf{x})$ 表示模型 $t$ 在样本 $\mathbf{x}$ 上的错误。

因此所有模型的平均错误为

$\mathcal R(h)=\frac{1}{T}\sum^T_{t=1}E_\mathbf{x}\left[\epsilon_t(\mathbf{x})^2\right]$

集成学习（Ensemble Learning）就是通过某种策略将多个模型集成起来，通过群体决策来提高决策准确率。集成学习的首要问题是如何集成多个模型，比较常见的方法有平均法、投票法、学习法等。平均法又有算术平均和加权平均。

基于算术平均的集成模型 $F(\mathbf{x})$ 为

$F(\mathbf{x})=\frac{1}{T}\sum_{t=1}^T h_t(\mathbf{x})$

定理 1. 对于 $T$ 个不同模型 $h_1(\mathbf{x}),h_2(\mathbf{x}),\dots,h_T(\mathbf{x})$，其平均期望错误为 $\overline{\mathcal R}(h)$，基于算术平均的集成模型 $F(\mathbf{x})$ 的期望错误在 $\displaystyle\frac{1}{T}\overline{\mathcal R}(h)$ 和 $\overline{\mathcal R}(h)$ 之间。

证明：集成模型的期望错误为

$\begin{aligned} \mathcal R(h_t)&=E_\mathbf{x}\left[\left(\frac{1}{T}\sum_{t=1}^T h_t(\mathbf{x})-g(\mathbf{x})\right)^2\right]\\ &=E_\mathbf{x}\left[\left(\frac{1}{T}\sum_{t=1}^T\epsilon_t(\mathbf{x})\right)^2\right] \\ &=\frac{1}{T^2}E_\mathbf{x}\left[\sum_{t=1}^T\sum_{r=1}^T\epsilon_t(\mathbf{x})\epsilon_r(\mathbf{x})\right]\\ &=\frac{1}{T^2}\sum_{t=1}^T\sum_{r=1}^TE_\mathbf{x}\left[\epsilon_t(\mathbf{x})\epsilon_r(\mathbf{x})\right] \end{aligned}$

其中 $E_\mathbf{x}\left[\epsilon_t(\mathbf{x})\epsilon_r(\mathbf{x})\right]$ 即为两个不用模型错误的相关性。如果两个模型之间错误是不相关的，则 $E_\mathbf{x}\left[\epsilon_t(\mathbf{x})\epsilon_r(\mathbf{x})\right]=0$；如果两个模型之间的错误是相同的，则 $\epsilon_t(\mathbf{x})=\epsilon_r(\mathbf{x})$。因此，可以得到

$\displaystyle\frac{1}{T}\overline{\mathcal R}(h)\le \overline{\mathcal R}(h) \le \overline{\mathcal R}(h)$

从上述公式中可以看出，为了得到更好的集成效果，要求每个模型之间具有一定的差异性，并随着模型数量的增多，其错误率也会下降，并趋于 $0$。

集成学习的方法可以分为两大类 Bagging 和 Boosting。

Bagging 类方法 Bagging 类方法是通过随机构造训练样本、随机选择特征等方法来提高每个基模型的独立性，代表性方法有 Bagging 和随机森林等。

Bagging（Bootstrap Aggregating）是通过不同模型的训练数据集的独立性来提高不同模型之间的独立性。我们在原始训练集上进行有放回的随机采样，得到 $M$ 个比较小的训练集并训练 $M$ 个模型，然后通过投票的方法进行模型集成。
随机森林（Random Forest）[Breiman, 2001] 是在 Bagging 的基础上再引入了随机特征，进一步提高每个基模型之间的独立性。在随机森林中，每个基模型都是一棵决策树。

Boosting 类方法 Boosting 类方法是按照一定的顺序来先后训练不同的基模型，每个模型都针对前序模型的错误进行专门训练。根据前序模型的结果，来调整训练样本的权重，从而增加不同基模型之间的差异性。Boosting 类方法是一种非常强大的集成方法，只要基模型的准确率比随机猜测高，就可以通过集成方法来显著地提高集成模型的准确率。 Boosting 类方法的代表性方法有 AdaBoost[Freund et al., 1996] 等。

2. 梯度提升树

提升树运用了 boosting 的思想，并将弱分类器限制为只使用决策树。提升方法实际采用加法模型(即基函数的线性组合)与前向分步算法。

给定二元分类训练数据集：

$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$

其中，${\displaystyle \mathbf x_i\in \mathcal{X}\subseteq R^n}$ 表示实例的特征向量，$y\in \mathcal{Y}=\{-1,+1\}$ 表示实例的类别，也就是标记（label）。给定实例特征向量$\mathbf x$，输出所属的类 $y$ 。

假设 $T$ 步得到的集成模型为

$f_T(\mathbf{x})=\sum_{t=1}^T h_t(\mathbf{x})$

因此，第 $t$ 步的模型为

$f_t(\mathbf{x})=f_{t-1}(\mathbf{x}) + h_t(\mathbf{x})$

那么第 $t$ 步的总误差为

$Loss_t=\sum_\mathbf{x}L(y,f_{t-1}(\mathbf{x}) + h_t(\mathbf{x}))$

$f_{t-1}(\mathbf{x}) + h_t(\mathbf{x})$ 即相当于损失函数的自变量，每一步为了使总误差下降，只需要使 $f_t$ 向负梯度的方向移动即可。因此，每一个新的模型 $h_t(\mathbf{x})$ 拟合上一步损失函数的负梯度

$h_t(\mathbf{x})=-\frac{\partial L(y,f_{t-1}(\mathbf{x}))}{\partial f_{t-1}(\mathbf{x})}$

这样第 $t$ 步的模型即为

$f_t(\mathbf{x})=f_{t-1}(\mathbf{x}) -\frac{\partial L(y,f_{t-1}(\mathbf{x}))}{\partial f_{t-1}(\mathbf{x})}$

相当于步长为 $1$ 的梯度下降法

$\theta_i = \theta_{i-1} -\rho \frac{\partial J}{\partial \theta_{i-1}}$

2.1 GBDT 回归

如果回归树使用平方误差损失函数

$L(y, f(x))=\frac{1}{2}(y-f(x))^2$

第 $t$ 步的模型为

$f_t(\mathbf{x})=f_{t-1}(\mathbf{x}) + h_t(\mathbf{x})$

损失变为

$L(y, f_{t-1}(\mathbf{x}) + h_t(\mathbf{x}))=(y-f_{t-1}(\mathbf{x}) - h_t(\mathbf{x}))^2$

令

$r=y-f_{t-1}(\mathbf{x})$

$r$ 即为数据的残差，为了使更新后的模型损失尽可能小，$h_t$ 拟合的目标即为数据的残差。

以上其实是提升树的思想，即拟合残差。从梯度提升树的角度思考，平方误差损失函数的负梯度即为

$\frac{\partial L(y, f(\mathbf{x}))}{\partial f(\mathbf{x})}=y-f(\mathbf{x})$

这与残差的结果是一致的。

到底残差是负梯度的特例，还是负梯度是残差的表现形式，还存在疑问

两种解释

本质是使损失函数最小化，拟合负梯度使损失函数下降最快。本质是通过累加各个学习器使损失函数减小，而不是使训练样本拟合的更好。rme 损失函数的负梯度恰好是残差。

本质是拟合残差，减小残差而非拟合负梯度才是求解本质。

更倾向于第一种解释

平方误差对于异常值的鲁棒性不强，过分关注与异常值。因此，在回归问题中，还具有其他损失函数

绝对损失

$L(y,f)=|y-f|$

Huber 损失

${\displaystyle L(y,f)={ \begin{cases} \frac{1}{2}(y-f)^2&|y-f|\le \delta \\ \delta(|y-f|-\delta/2)&|y-f|> \delta \end{cases} } }$

在真值为 $5$，预测为 $1.7$ 的情况下，三种损失值分别为 $5.445$、$3.3$、 $1.525(\delta=0.5)$。

绝对损失的负梯度为

$-g(\mathbf{x})=-\frac{\partial L(y, f(\mathbf{x}))}{\partial f(\mathbf{x})}=\text{sign}(y-f(\mathbf{x}))$

Huber 损失的负梯度为

$\begin{aligned} -g(\mathbf{x})&=-\frac{\partial L(y, f(\mathbf{x}))}{\partial f(\mathbf{x})} \\ &={ \begin{cases} y-f(\mathbf{x})&|y-f|\le \delta \\ \delta\text{sign}(y-f(\mathbf{x}))&|y-f|> \delta \end{cases} } \end{aligned}$

对于每一个实例 $\mathbf{x}$ 都可计算出一个负梯度，然后用一个回归树拟合即可，也就是用负梯度的值取代真实值 $y$，再去做训练得到 $h_t$。

2.1 GBDT 分类

GBDT 的分类算法从思想上和 GBDT 的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。

为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时 GBDT 退化为 Adaboost 算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的 GBDT 分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

分类底层还是用的 CART 回归树，没有用到分类树。

参考

1. 梯度提升树(GBDT)原理小结 - 刘建平
 2. SPECIAL INVITED PAPER ADDITIVE LOGISTIC REGRESSION: A STATISTICAL VIEW OF BOOSTING
3. Greedy Function Approximation: A Gradient Boosting Machine
4. A Gentle Introduction to Gradient Boosting
5. Lecture 17: Gradient Boosting
6. gbdt的残差为什么用负梯度代替？ - zhihu
7. Gradient boosting - wiki

Machine Learning

2022-07-19