Gradient Boosted Decision Tree.

梯度提升决策树 (Gradient Boosted Decision Tree, GBDT)是一种把决策树作为基学习器的梯度提升Gradient Boosting算法，适用于任意可微损失函数的各类学习任务(回归，分类，排序等)。

GBDT模型可以表示为决策树的加法模型：

其中$T_m(x)$为决策树，$M$是树的个数。无论对于哪种类型的任务，GBDT总是选择CART回归树作为基学习器。这是一种二叉树，递归地把输入空间划分为$J$个互不相交的子区域$R_1,…,R_J$，计算每个子区域$R_j$上的输出值$c_j$，从而构造回归树模型：

设定损失函数$L(y,f(x))$，GBDT模型采用前向分布算法，首先把第一个弱学习器$f_0(x)$初始化为常数$c$：

依次建立$M$棵决策树，其中第$m$步的GBDT模型是：

其中当前决策树$T_m$通过拟合当前损失函数的负梯度$r_m$（代表损失函数的下降方向）实现：

对于生成的子决策树$m$，计算各个叶结点$j$的最佳拟合值为：

则GBDT模型最终构造的强学习器$f_M(x)$为：

1. 回归GBDT

对于回归任务，损失函数设置为平方误差：

初始化弱学习器$f_0(x)$为所有训练样本标签值的均值：

第$m$棵决策树$T_m$拟合当前损失函数的负梯度$r_m$（当前预测结果与真实标签的残差）：

对于生成的决策树$m$，计算各个叶结点$j$的最佳残差拟合值为：

⚪ 使用sklearn实现GBDT回归算法

使用sklearn.ensemble.GradientBoostingRegressor构造回归GBDT：

import numpy as np
from sklearn.ensemble import GradientBoostingRegressor

gbdt = GradientBoostingRegressor(loss='ls', learning_rate=0.1, n_estimators=100,
                                 subsample=1.0, criterion='friedman_mse', min_samples_split=2, 
                                 min_samples_leaf=1, min_weight_fraction_leaf=0,
                                 max_depth=3, min_impurity_decrease=0,
                                 min_impurity_split=None, init=None, random_state=None,
                                 max_features=None, alpha=0.9, verbose=0, max_leaf_nodes=None, 
                                 warm_start=False, validation_fraction=0.1,
                                 n_iter_no_change=None, tol=1e-4
                                 )
train_feat = np.array() # [N, D]
train_label = np.array() # [N,]
test_feat = np.array() # [M, D]

gbdt.fit(train_feat, train_label)
pred = gbdt.predict(test_feat)

⭐ GBDT回归任务常见的损失函数

① 均方误差损失 loss='ls'

默认损失函数，适用于数据噪声较少的场合。对应的表达式$L$及其负梯度$r$为：

② 绝对值损失 loss='lad'

对应的表达式$L$及其负梯度$r$为：

③ 分位数损失 loss='quantile'

对应分位数回归的损失函数，需要对训练集进行分段预测时使用，其中分位数$\alpha$通过超参数alpha指定。对应的表达式$L$及其负梯度$r$为：

④ Huber损失 loss='huber'

对于远离中心的异常点采用绝对值损失，而中心附近的点采用均方误差损失，界限用分位数点$\alpha$通过超参数alpha指定；适用于噪声较多的场合，对应的表达式$L$及其负梯度$r$为：

⭐ GBDT回归模型的正则化

GBDT模型容易过拟合，需要设定一些正则化策略：

① Shrinkage正则化 learning_rate=0.1

在每次对残差估计进行迭代时，不直接加上当前步所拟合的残差，而是乘以一个学习率$0<\lambda\leq 1$，从而对梯度提升的步长进行调整：

较小的学习率意味着需要更多的弱学习器的迭代次数n_estimators。

② 子采样 subsample=1.0

在训练每一个弱学习器时，对训练数据集进行无放回采样构造子数据集。取值小于$1$时只有一部分样本用于拟合，可以减少方差，即防止过拟合；但会增加样本拟合的偏差，因此取值不能太低。推荐在$[0.5, 0.8]$之间。使用子采样的GBDT有时也称作随机梯度提升树 (Stochastic Gradient Boosting Tree, SGBT)。

③ 剪枝

通过对每一棵子树进行剪枝防止过拟合。min_samples_split=2设置了对内部结点进行划分时的最少样本数量，若不满足则作为叶结点。min_samples_leaf=1设置了划分为叶结点时的最少样本数量，若不满足则对其剪枝。min_weight_fraction_leaf=0设置了划分为叶结点时的所有样本的最小权重和(默认所有样本具有相等的权重)，若不满足则对其剪枝。max_depth=3设置了子树的最大深度。min_impurity_decrease=0设置了内部结点进行划分时的不纯度阈值。max_features=None设置了拆分结点时考虑的最大特征数量，可设置为浮点数或整数，也可设置为{'auto', 'sqrt', 'log2'}。max_leaf_nodes=None设置了子树的最大叶结点数量。

④ Early Stopping n_iter_no_change=None

选择一部分样本作为验证集，在迭代拟合训练集的过程中，如果模型在验证集里错误率不再下降，就停止训练。用validation_fraction设置验证集的比例，用n_iter_no_change($\geq 1$)设置验证损失不变化的轮数，若损失变化不超过tol=1e-4则视为不变化。

⑤ Dropout

[DART: Dropouts meet Multiple Additive Regression Trees]指出GBDT会出现over-specialization的问题：前面迭代的树对预测值的贡献比较大，后面的树会集中预测一小部分样本的偏差。作者通过Dropout来平衡所有树对预测的贡献：每次新加一棵树时，这棵树要拟合的并不是之前全部树集成后的残差，而是随机抽取的一些树集成；同时对新加的树的结果进行规范化。

2. 二分类GBDT

无论是回归任务还是分类任务，GBDT模型都采用回归树作为基学习器。这是因为GBDT模型顺序地使用决策树拟合当前损失函数的负梯度，如果采用硬分类方法（即模型直接输出类别序号），则真实标签减去弱分类器的输出结果是没有意义的。因此对于二分类问题，GBDT模型采用回归的形式拟合事件$y=1|x$的对数几率（把输入$x$预测为正样本的概率）：

因此二元GBDT分类模型的思想和逻辑回归是一致的，相当于线性回归+Sigmoid函数：

二元GBDT分类模型的损失函数采用二元交叉熵损失：

对应损失函数的负梯度$r_m$为：

利用数据集中的先验信息来初始化弱学习器$f_0(x)$：

第$m$棵决策树$T_m$拟合当前损失函数的负梯度：

对于生成的决策树$m$，计算各个叶结点$j$的最佳拟合值为：

对于交叉熵损失，上式没有闭式解。因此采用近似值代替。首先计算交叉熵损失的一阶导数和二阶导数：

对损失函数$L(y,f(x)+c)$在$f(x)$处进行二阶泰勒展开：

当上式取极小值时，存在关系：

因此决策树$m$的叶结点$j$的最佳拟合值为：

⚪ 使用sklearn实现GBDT二分类算法

使用sklearn.ensemble.GradientBoostingClassifier构造二分类GBDT：

import numpy as np
from sklearn.ensemble import GradientBoostingClassifier

gbdt = GradientBoostingClassifier(loss='deviance', learning_rate=0.1, n_estimators=100,
                                  subsample=1.0, criterion='friedman_mse', min_samples_split=2, 
                                  min_samples_leaf=1, min_weight_fraction_leaf=0,
                                  max_depth=3, min_impurity_decrease=0,
                                  min_impurity_split=None, init=None, random_state=None,
                                  max_features=None, verbose=0, max_leaf_nodes=None, 
                                  warm_start=False, validation_fraction=0.1,
                                  n_iter_no_change=None, tol=1e-4
                                  )
train_feat = np.array() # [N, D]
train_label = np.array() # [N,]
test_feat = np.array() # [M, D]

gbdt.fit(train_feat, train_label)
pred = gbdt.predict(test_feat)

其主要超参数与GBDT回归算法类似，主要区别在于损失函数不同。二分类GBDT的损失函数包括：

• 对数损失函数 deviance：即二元交叉熵损失函数，默认设置。
• 指数损失函数 exponential：$L(y,f(x))=\exp(-yf(x))$，此时相当于AdaBoost算法。

3. 多分类GBDT

把二分类GBDT模型推广到多分类GBDT模型的思路是分别对每一个类别$k$训练一个模型$f_k$，采用回归的形式拟合事件$y=k|x$的对数几率（把输入$x$预测为正样本的概率）：

因此多分类GBDT模型相当于线性回归+Softmax函数：

对应的损失函数采用多元交叉熵损失，其中真实标签$y$为one-hot编码形式：

其中预测第$k$个类别的模型$f_k$对应损失函数的负梯度$r_{k,m}$为：

因此每个类别的模型$f_k$的训练过程与二分类GBDT模型相同。本质上相当于把$K$分类的多分类任务转换为$K$个二分类任务。下图给出了把一个三分类任务转换成三个二分类任务的过程：

使用sklearn实现GBDT多分类算法的过程与二分类算法相同，其中损失函数只能选择对数损失函数 deviance。