Boosting模型:GBDT原理介绍

说到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(表示算法内部使用的是决策树)。在这篇文章,主要也是从这三个要点进行细化:

  1. 提升方法(加法模型+前向分步算法);
  2. 梯度提升:梯度与残差;
  3. 决策树: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. 第1行初始化模型,估计损失函数极小化的常数值;
  2. 第2行迭代的训练M个子模型;
  3. 第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

最后的最后,小小的感叹一下,对于工作后的自己来说,写一片质量略好的文章真的并非一朝一夕之事。从最初的构思到组织语言,每个句子每行公式都离不开精心的编纂和检查。读者如果觉得这篇文章对您有作用,欢迎多来光顾;如果觉得文章中理解不对,存在误人子弟之处,还望能在评论区中指出文中不足,笔者在此深表感谢。

参考文献

  1. 统计学习方法,第二版,李航
  2. Friedman, Jerome H. “Greedy function approximation: a gradient boosting machine.” Annals of statistics (2001): 1189-1232.
  3. Freund, Yoav, and Robert E. Schapire. “Experiments with a new boosting algorithm.” icml. Vol. 96. 1996.
  4. 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.
  5. 2001:Random Forests(Breiman),Breiman, L. (2001). Random forests. Machine learning, 45(1), 5-32.
  6. 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.