梯度提升决策树——GBDT(Gradient Boosting Decision Tree)

1 前向分布算法

梯度提升决策树GBDT算法的整体框架逻辑用到了前向分布算法。这里首先来看前向分布算法是什么。其实，在Adaboost传送门的算法中我们已经接触了它：

(1) 加法模型

在Adaboost算法中，每个基学习器(基分类器)合成一个复杂的学习器(分类器)的方式是通过对每个基学习器进行加权求和，即： \[f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)\]

其中，\(b\left(x ; \gamma_{m}\right)\)为即基分类器，\(\gamma_{m}\)为基分类器的参数，\(\beta_m\)为基本分类器的权重。从形式上很容易看出，这是一个加法模型。

给定了训练数据\(x\)以及损失函数\(L(y, f(x))\)的条件下，已知加法模型:\(f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)\)，那么该任务的优化问题便是求解下面函数的最优解： \[ \min _{\beta_{m}, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right) \]

上面函数最优解的求解是一个复杂的优化问题，很难通过简单的凸优化求解的方式来解决。所以对于上面的加法模型的优化函数，我们可以使用前向分布算法来求解：从前往后，每一步只优化一个基函数及其系数(也就是一个基学习器)，逐步逼近目标函数，这样就能降低优化的复杂度。通过前向分布算法，我们最后需要关注的就只是每一步的优化函数： \[ \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right) \]

(2) 前向分布算法

上面介绍了加法模型，那么我们这部分来看用前向分布算法来求解最优的加法模型。

任务设定

给定二分类任务的数据集\(T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}\)，\(x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}\)，\(y_{i} \in \mathcal{Y}=\{+1,-1\}\)。损失函数\(L(y, f(x))\)，基函数集合\(\{b(x ; \gamma)\}\)。

前向分布算法的输出

加法模型(函数)\(f(x)\)。

算法流程

初始化：\(f_{0}(x)=0\)
对m = 1,2,...,M(M是基学习器的个数):
- 极小化损失函数：\(\left(\beta_{m}, \gamma_{m}\right)=\arg \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)\)，得到参数\(\beta_{m}\)与\(\gamma_{m}\)
- 更新：\(f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)\)
得到加法模型：
\[ f(x)=f_{M}(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right) \]

这样，前向分步算法将同时求解从m=1到M的所有参数\(\beta_{m}\)，\(\gamma_{m}\)的优化问题简化为逐次求解各个\(\beta_{m}\)，\(\gamma_{m}\)的问题。

Adaboost算法是前向分布算法的一种应用。Adaboost是由基学习器组成的加法模型，优化函数(损失函数)为指数损失函数。

2 提升决策树——BDT(Boosting Decision Tree)

提升决策树BDT是指以CART回归树(二叉树)为基学习器，利用上一基学习器预测值和真实值之间的差值(残差)作为输入进行训练。从框架上看，提升树算法是依靠加法模型+前向分布算法框架的解决问题的算法。

BDT算法流程

初始化\(f_0(x) = 0\)
对m = 1,2,...,M(M是CART回归树的个数)：
- 计算每个样本的残差:\(r_{m i}=y_{i}-f_{m-1}\left(x_{i}\right), \quad i=1,2, \cdots, N\)
- 拟合残差\(r_{mi}\)学习一棵回归树(最小化平方误差)，得到\(T\left(x ; \Theta_{m}\right)\)
- 更新\(f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)\)
得到最终的回归问题的提升树：\(f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)\)

BDT案例

案例来源：《统计学习方法》李航

问题描述：学习下面训练数据表中回归问题的提升树模型。考虑只用树桩(只有一个分叉，而且因为是CART回归树，所以分叉是二叉，也就是只选择一个分裂点)作为基函数。

3 梯度提升决策树——GBDT

3.1 什么是GBDT？

提升树利用加法模型+前向分步算法实现学习的过程，当损失函数为平方损失和指数损失时，每一步优化是相当简单的，也就是前面探讨的提升树算法和Adaboost算法。但是对于一般的损失函数而言，往往每一步的优化不是那么容易。梯度提升决策树算法利用损失函数的负梯度在当前模型的值\(-\left[\frac{\partial L\left(y, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{m-1}(x)}\)作为回归问题提升树算法中的残差的近似值，拟合回归树。

与其说负梯度作为残差的近似值，不如说残差是负梯度的一种特例。

GBDT算法流程

输入训练数据集\(T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}, x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}, y_{i} \in \mathcal{Y} \subseteq \mathbf{R}\)和损失函数\(L(y, f(x))\)，输出回归树\(\hat{f}(x)\)。
- 初始化\(f_{0}(x)=\arg \min _{c} \sum_{i=1}^{N} L\left(y_{i}, c\right)\)

对于m=1,2,...,M(M是基学习器的个数)：
- 对i = 1,2,...,N计算：\(r_{m i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{m-1}(x)}\)
- 对\(r_{mi}\)拟合一个回归树，得到第m棵树的叶结点区域\(R_{m j}, j=1,2, \cdots, J\)
- 对j=1,2,...J，计算：\(c_{m j}=\arg \min _{c} \sum_{x_{i} \in R_{m j}} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+c\right)\)
- 更新\(f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)\) (I为指示函数，括号里条件满足为1，不满足为0)
得到回归树：\(\hat{f}(x)=f_{M}(x)=\sum_{m=1}^{M} \sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)\)

3.2 基于sklearn的GBDT的使用

from sklearn.metrics import mean_squared_error
from sklearn.datasets import make_friedman1
from sklearn.ensemble import GradientBoostingRegressor

X, y = make_friedman1(n_samples=1200, random_state=0, noise=1.0)
X_train, X_test = X[:200], X[200:]
y_train, y_test = y[:200], y[200:]
est = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1,
    max_depth=1, random_state=0, loss='ls').fit(X_train, y_train)
mean_squared_error(y_test, est.predict(X_test))

输出：5.009154859960321

from sklearn.datasets import make_regression
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split
X, y = make_regression(random_state=0)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, random_state=0)
reg = GradientBoostingRegressor(random_state=0)
reg.fit(X_train, y_train)
reg.score(X_test, y_test)

输出：0.440031029624667

补充：GradientBoostingRegressor与GradientBoostingClassifier函数各个参数的含义如下。

GradientBoostingRegressor参数及其含义
1. loss：{ls,lad,huber,quantile}, default=ls。其中，
  - ls：指最小二乘回归；
  - lad：(最小绝对偏差)是仅基于输入变量的顺序信息，具有高度鲁棒的损失函数；
  - huber：上述两者的结合；
  - quantile：允许分位数回归（用于alpha指定分位数）。
2. learning_rate：学习率用于缩小每棵树的贡献learning_rate，在learning_rate和n_estimators之间需要权衡。
3. n_estimators：执行迭代次数。
4. subsample：用于拟合各个基学习器的样本比例。如果小于1.0，将使得随机梯度增强。subsample与参数n_estimators有关联，选择subsample<1.0会导致方差减少和偏差增加。
5. criterion：{friedman_mse，mse，mae}，默认为friedman_mse：mse是均方误差，mae是平均绝对误差。默认值friedman_mse通常是最好的，因为在大多情况下可以提供更好的近似值。
6. min_samples_split：默认为2，拆分内部节点所需的最少样本数。
7. min_samples_leaf：默认为1，在叶节点处需要的最小样本数。
8. min_weight_fraction_leaf：默认为0.0，在所有叶节点处（所有输入样本）的权重总和中的最小加权数。如果未提供sample_weight，则样本的权重相等
9. min_impurity_decrease：如果节点拆分会导致不纯度大于或等于该值，则该节点将被拆分。
10. min_impurity_split：提前停止树生长的阈值。如果节点的不纯度高于该值，则该节点将拆分。
11. max_depth：默认为3，各个回归模型的最大深度。最大深度限制了树中节点的数量。调整此参数以获得最佳性能；最佳值取决于输入变量。
12. max_features {auto, sqrt, log2}，int或float：寻找最佳切分点时要考虑的特征个数。其中，
  - 如果是int，则表示节点切分的特征个数；
  - 如果是float，max_features则为小数，根据公式int(max_features * n_features)确定节点切分的特征个数；
  - 如果是auto，则max_features=n_features；
  - 如果是sqrt，则max_features=sqrt(n_features)；
  - 如果为log2，则为max_features=log2(n_features)；
  - 如果没有，则max_features=n_features。
GradientBoostingClassifier参数及其含义
1. loss：{deviance,exponential}, default=deviance。deviance是指对具有概率输出的分类（等同于logistic回归）；对于exponential梯度提升方法，可等同于AdaBoost算法。
2. learning_rate：学习率用于缩小每棵树的贡献learning_rate，在learning_rate和n_estimators之间需要权衡。
3. n_estimators：执行迭代次数
4. subsample：用于拟合各个基学习器的样。本比例。如果小于1.0，将使得随机梯度增强。subsample与参数n_estimators有关联，选择subsample<1.0会导致方差减少和偏差增加。
5. criterion：{friedman_mse，mse，mae}，默认为friedman_mse：mse是均方误差，mae是平均绝对误差。默认值friedman_mse通常是最好的，因为在大多情况下可以提供更好的近似值。
6. min_samples_split：默认为2，拆分内部节点所需的最少样本数。
7. min_samples_leaf：默认为1，在叶节点处需要的最小样本数。
8. min_weight_fraction_leaf：默认为0.0，在所有叶节点处（所有输入样本）的权重总和中的最小加权数。如果未提供sample_weight，则样本的权重相等。
9. max_depth：默认为3，各个回归模型的最大深度。最大深度限制了树中节点的数量。调整此参数以获得最佳性能；最佳值取决于输入变量。
10. min_impurity_decrease：如果节点拆分会导致不纯度大于或等于该值，则该节点将被拆分。
11. min_impurity_split：提前停止树生长的阈值。如果节点的不纯度高于该值，则该节点将拆分。
12. max_features {auto, sqrt, log2}，int或float：寻找最佳切分点时要考虑的特征个数。其中，
  - 如果是int，则表示节点切分的特征个数；
  - 如果是float，max_features则为小数，根据公式int(max_features * n_features)确定节点切分的特征个数；
  - 如果是auto，则max_features=n_features；
  - 如果是sqrt，则max_features=sqrt(n_features)；
  - 如果为log2，则为max_features=log2(n_features)；
  - 如果没有，则max_features=n_features。