说到GBDT，很多人都熟悉，那么我为什么还要在这里编写这篇文章呢？原因很简单，对我来说，在算法学习过程中，喜欢探究算法背后的公式推导，有时候自己也是一头雾水，但目的就是把每个步骤弄清楚，而每次重新回顾算法的时候，或多或少都会领悟到一些与之前不一样的东西，然后惊叹：噢，原来这里是这样，之前怎么就没领悟到，“书读百遍其义自见”大概就是这个道理！这篇文章其实很早之前就写了一部分，只是一直没有完整的整理出来，每次看到这篇文章放到draft里面，就总觉得有种有始无终的感觉。这回，在文章后面引入了实例解析部分，主要是希望后续回来温习的时候，能够快速地理解。
引文
在李航博士的《统计学习方法》里面讲到统计学习方法由三要素组成：模型、策略和算法。细的来讲，模型就是所要学习的条件概率分布或决策函数；策略指的是按照什么样的准则进行学习或者选择最优的模型；算法是学习模型的具体计算方法，本质上属于最优化问题。那么，对于GBDT算法来说，三要素又是什么呢？笔者的理解是（此处请读者保留自己的观点，如有误导，还请大神赐教）：模型表示的是Boosting模型，加法模型；策略指的是通过迭代来近似拟合残差以达到降低模型偏差的目的，算法则是基于梯度（一阶倒数）进行优化。
GBDT是基于决策树的，各类算法的大致时间线如下（从CART开始）：
- 1984：CART “Classification & Regression Trees” (Breiman)
- 1986：ID3（Quinlan）
- 1993：C4.5（Quinlan）
- 1995：Adaboost（Freund and Schapire）
- 1996：Bagging（Freund and Schapire）
- 2001：Random Forests（Breiman）
- 2001：Freund 在“Greedy function approximation: A gradient boosting machine”中，提出了Gradient Boosting 思想。
- 2014: XGBoost是陈天奇于2014年提出的一套并行boost算法工具库，2016年发表论文“XGBoost: A Scalable Tree Boosting System”。
- 2016：LightGBM是微软推出的boosting框架，并与2017年发表论文“LightGBM: A Highly Efficient Gradient Boosting Decision Tree”。
从CART算法到boosting思想的提出，历时约11年，而从boosting思想到现在的lightGBM转眼又是21年，加起来都超出了我的年纪了呐。好了，闲话少说，直奔主题吧，这篇文章介绍的就是GBDT，对于xgboost和lightGBM，暂且不表。说到底，GBDT也是xgboost和lightGBM的基础中的基础，核心中的核心。
GBDT三大核心
GBDT这个名字非常有深意：G-gradient（表示该算法是基于梯度的），B-Boosting（表示该算法是boosting模型），DT-decision tree（表示算法内部使用的是决策树）。在这篇文章，主要也是从这三个要点进行细化：
- 提升方法（加法模型+前向分步算法）；
- 梯度提升：梯度与残差；
- 决策树：CART回归树。
Boosting
在进入GBDT理论推导之前，必须得聊聊Boosting思想。Boosting方法本质上属于加法模型$\eqref{1}$（各个基分类器的线性组合），同时属于前向分步算法，它每轮训练的模型都是在上一个模型的基础上进行进一步优化，通过不断迭代来降低整个模型的偏差，所以Boosting模型的一个特点就是低偏差、高方差，最典型的代表就是Adaboost算法。与其相反的就是Bagging算法，最典型的代表就是RF。Bagging模型的各个子模型之间互不影响，最后通过加权的方式组合到一起，以达到降低方差的效果，所以说Bagging是高偏差、低方差的模型。
$$
f_M(x)=\sum^M_{m=1}T(x,θ_m)
\tag{1}\label{1}
$$
对Boosting和Bagging模型原理模糊的童鞋可以参阅下笔者几年前的文章机器学习-组合算法总结。
下面来看看梯度提升过程中的梯度和残差。
梯度与残差
在RF、Adaboost等加法模型中，都是通过直接拟合真实值来构建模型的，而在GBDT里面（下面这句话是重点，认真理解，并且多读几遍）：非首轮迭代的模型拟合的目标值不再是真实值，而是一个梯度值，主要是通过拟合损失函数的负梯度值在当前模型的值来构建模型。其梯度值表达式如下：
$$
\large {r_{mi}} = -\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1}(x)}
\tag{2}\label{2}
$$
当损失函数为平方损失的时候，损失函数可以表示为：$L(y_i,f(x_i)) = \frac{1}{2}(y_i - f(x_i))^2$，此时当前模型下损失函数的负梯度值正好等于残差：$r_{mi} = y_i - f(x_i)$。了解到GBDT的这一特性之后，下面我们来看看第三个要点：CART决策树。
DT：CART
GBDT属于Boosting模型，对于boosting模型而言，都存在基模型，那么GBDT的基模型是什么呢？CART。CART分类回归树，是决策树的一种，它即可用于分类也可用于回归。在分类任务中，树的分裂准则采用Gini index（基尼指数），而在回归任务中采用MSE（均方误差）。关于Gini Index的描述如下：
在分类任务中，假设当前样本集中有$k$个类别，样本点属于第$k$类的概率为$p_k$,那么样本概率分布的基尼指数为：
$$
Gini(p) = 1-\sum_{k=1} p_{k}^2
\label{3}\tag{3}
$$
原理剖析
在2001年的论文Greedy function approximation: A gradient boosting machine中，介绍了梯度提升的基本思想，本文仅仅摘录了论文gradient boosting思想部分（如果想要全面了解GBDT，还请读者移步到原始paper中），梯度提升的算法流程如下：
算法解析：
- 第1行初始化模型，估计损失函数极小化的常数值；
- 第2行迭代的训练M个子模型；
- 第3-6行为子模型的训练细节，
- 首先第3行是计算损失函数$L(y_i, F(x_i))$在当前模型$F(x_i)$的负梯度值，将其作为残差的估计值；
- 第4行是使用负梯度值$\hat{y}_i$作为目标值，拟合一颗回归树模型$h(x_i;a)$，从而得到当前模型的参数$a_m$。
- 第5行是一个线性搜索过程，论文中将其成为Shrinkage($ρ_m$,学习率)。
- 第6行是利用加法模型，更新回归树，得到$F_m(x)$；
对于上面的算法，损失函数不一样就会产生不同变形算法，具体内容读者可以参考原paper，这里暂且举一个例子来说明一下。当损失函数为平方损失时，各个阶段的变换为：
当$L(y,F) = \frac{1}{2}(y-F)^2$，Algorithm 1中第3行的$\hat{y}_i = y_i - F_{m-1}(x_i)$，即残差（真实值-当前模型的值）。那么，第4行就相当于用一个回归树模型来拟合残差。第5行的参数$ρ_m$即为第4行的$\beta$，即$ρ_m=\beta_m$。由此，便得出基于平方损失函数的gradient boosting算法模型。
Algorithm 2只提及了整个算法的过程，细节如何呢？前面说到GBDT采用的是CART算法来拟合模型（损失函数在当前模型的负梯度值），既然如此，每次拟合之后每颗树叶子节点的取值是多少呢？Algorithm 3中展示的是LAD（Least-absolute-deviation）回归的regression tree的具体原理。在LAD_TreeBoost里面，算法的第4行表示的是以$(\hat{y}_i,x_i)^N_1$为训练样本来拟合一颗回归树模型，最终得到叶子节点区域。第5行则表示如何计算第$m$轮迭代中，第$j$个叶子节点的值$\gamma_{jm}$。其值与损失函数有关，不同的损失函数，会致使叶子节点的值也不一样。当损失函数为MSE时，$\gamma_{jm}=ave_{x_i \in R_{jm}} \hat{y}_i$，其中$\hat{y}_i$为负梯度值。下图为LAD损失函数的梯度提升回归树模型算法思想。
实例解析
上面对原理进行了分析之后，大致对GBDT有了进一步的认识，为了更加形象的解释GBDT的内部执行过程，这里引用《统计学习方法》里面的数据来进行进一步分析。
假设有数据集如下：
| $xi$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y_i$ | 5.56 | 5.7 | 5.91 | 6.4 | 6.8 | 7.05 | 8.9 | 8.7 | 9. | 9.05 |
采用GBDT进行训练，为了方便，我们采用MSE作为损失函数，并且将树的深度置为1
根据Algorithm 2，首先初始化$F_{0}(x)$,可以计算出$F_{0}(x)=7.307$.其次，计算出损失函数在当前模型的负梯度值: $\hat{y}_i = y_i - F_{m-1}(x_i)$，结果如下：
| $xi$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y_i$ | -1.747 | -1.607 | -1.397 | -0.907 | -0.507 | -0.257 | 1.593 | 1.393 | 1.693 | 1.743 |
接下来，通过构建回归树来拟合损失函数在当前模型的负梯度值$\hat{y}_i$。
对于决策树来说，最关键的步骤就是如何选择最优的划分标准，在回归树里面，我们采用MSE来进行评估，通过对比不同切分点两个分支的MSE加和，来选择最优的切分点（加和MSE最小的点）。根据所给的数据，可以考虑的切分点为1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5.分别计算$y_i - F_{0}(x_i)$的值，并计算出切分后的左右两侧加和MSE最小的切分，最后得到的是6.5，此时的MSE=0.3276.找到最佳的切分点之后，我们可以得到各个叶子节点区域，并计算出$R_{jm}$和$\gamma_{jm}$.此时，$R_{11}$为x小于6.5的数据，$R_{21}$为x大于6.5的数据。同时，
$$r_{11} = \frac{1}{6} \sum_{x_i \in R_{11}} y_{i}=−1.0703$$
$$r_{21} = \frac{1}{4} \sum_{x_i \in R_{21}} y_{i}=1.6055$$
最后，更新$F_{1}(x_i)$的值，$F_1(x_i)=F_{0}(x_i)+ \rho_m \sum^2_{j=1} \gamma_{j1} I(x_i \in R_{j1})$，其中$\rho_m$为学习率，或称shrinkage，目的是防止预测结果发生过拟合。
至此第一轮迭代便完成，后面的迭代方式与上面一样，迭代$m$次后，第$m$次的$F_{m}(x)$即为最终的预测结果。
$$
F_{m}(x) = F_{m-1}(x) + \rho_{m} h(x; a_m)
\label{4}\tag{4}
$$
总结
写到这里，关于GBDT的文章也算结束了，在RS或者CTR预估中，GBDT也曾占据一席之地，至今也留有使用GBDT+LR来构建排序模型。感兴趣的可以看看Facebook发出的这篇paper: Practical lessons from predicting clicks on ads at facebook。
最后的最后，小小的感叹一下，对于工作后的自己来说，写一片质量略好的文章真的并非一朝一夕之事。从最初的构思到组织语言，每个句子每行公式都离不开精心的编纂和检查。读者如果觉得这篇文章对您有作用，欢迎多来光顾；如果觉得文章中理解不对，存在误人子弟之处，还望能在评论区中指出文中不足，笔者在此深表感谢。
参考文献
- 统计学习方法，第二版，李航
- Friedman, Jerome H. “Greedy function approximation: a gradient boosting machine.” Annals of statistics (2001): 1189-1232.
- Freund, Yoav, and Robert E. Schapire. “Experiments with a new boosting algorithm.” icml. Vol. 96. 1996.
- Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learningand an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, August 1997.
- 2001：Random Forests（Breiman），Breiman, L. (2001). Random forests. Machine learning, 45(1), 5-32.
- He, Xinran, et al. “Practical lessons from predicting clicks on ads at facebook.” Proceedings of the Eighth International Workshop on Data Mining for Online Advertising. ACM, 2014.