GBDT (Gradient Boosting Decision Tree)
Table of Contents
1. 梯度提升简介(GBDT, MART, GTB, GBT, GBRT)
梯度提升树(GBDT, 全称为 Gradient Boosting Decision Tree)。它还有其它一些名字,如 Multiple Additive Regression Tree(MART), Gradient Tree Boosting(GTB), Gradient Boosting Tree(GBT), Gradient Boosting Regression Tree(GBRT).
注: “梯度提升”是集成学习 Boosting 家族的成员。 “梯度提升”是一个通用的框架,我们往往使用 CART 回归树作为“基本回归算法”,这时梯度提升称为梯度提升决策树(GBDT)。GBDT 是回归树,更适合做回归,当然也可以用作分类(如二分类时设定一个阈值即可)。GBDT 几乎可用于所有回归问题(线性/非线性),相对于 Logistic Regression 仅能用于线性回归,GBDT 的适用面更广。
参考:
梯度提升原始论文:Jerome H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine: http://statweb.stanford.edu/~jhf/ftp/trebst.pdf
统计学习方法,李航著
1.1. 梯度提升基本思想
下面通过一个例子来说明梯度提升的基本思想。
有数据
假设你朋友提供了一个现成的模型
一个简单的想法是:你在
上面式子等价于:
也就说,
我们把
对于新的模型
这就是梯度提升的基本思路。但这和“梯度”(Gradient)有什么关系呢?下面的分析将说明:采用平方损失函数时,残差就是负梯度。
在数据拟合过程中,采用平方损失函数
注意到
上式表明, 采用平方误差时,残差就是负梯度 :
参考:
A Gentle Introduction to Gradient Boosting: http://www.chengli.io/tutorials/gradient_boosting.pdf
1.2. 采用“负梯度”,而非“残差”
平方损失函数(Square loss)有一个缺点:它对异常点(outliers)比较敏感。其它一些损失函数,如绝对损失函数(Absolute loss),Huber loss 函数能更好地处理异常点。 表 1 是三种损失函数 Square loss/Absolute loss/Huber loss 对异常点的处理情况。
0.5 | 1.2 | 2 | ||
0.6 | 1.4 | 1.5 | 1.7 | |
Square loss | 0.005 | 0.02 | 0.125 | 5.445 |
Absolute loss | 0.1 | 0.2 | 0.5 | 3.3 |
Huber loss( |
0.005 | 0.02 | 0.125 | 1.525 |
在前面的介绍中,我们知道 采用 Square loss 为损失函数时,负梯度和残差相等。不过,当我们采用 Absolute loss/Huber loss 等其它损失函数时,负梯度只是残差的近似。
GBDT 算法用“负梯度”来取代“残差”。不过需要说明的是,这时新模型不再是
为什么不直接使用“残差”,而使用“负梯度”呢(注:也有一些实现直接使用“残差”)?因为使用“负梯度”有时能够减小异常点的影响。 下面以 Huber loss 函数以例进行说明。
Huber loss 定义如下:
如果采用“残差”的话,则有:
如果采用“负梯度”的话,则有:
对比上面两式,可以发现,采用“负梯度”时异常点(会满足
2. 梯度提升算法
前面从“残差”的角度介绍了梯度提升算法的基本思想(动机)。
梯度提升算法可以看作是“最速下降方法(Steepest Descent Method)”。 不过,和普通的最速下降方法(定义域为
设损失函数为
总损失
上式很难求解。取近似,把
每次迭代过程中(假设当前是第
则
使用“line search”(一维搜索,即求解单变量函数的极小化问题),可以求得步长
2.1. Generic Gradient Boosting
下面是“梯度提升算法”的总结。
输入:训练数据
输出:训练数据对应的回归模型
算法步骤:
第 1 步:初始化
第 2 步:令
(a) 计算“伪残差”:
(b) 使用“基本回归算法”拟合数据
(c) 计算
(d) 更新
第 3 步:训练数据对应的回归模型即为
说明:当我们选择
2.2. GBDT
前面介绍的是通用的梯度提升算法。不过,实践中往往 采用 CART 回归树(参见附录)作为其基本回归算法,这时,梯度提升算法称为“梯度提升决策树”(GBDT, Gradient Boosting Decision Tree)。
GBDT 算法(“梯度提升算法+CART 回归树作为基本回归算法”)描述如下:
输入:训练数据
输出:训练数据对应的回归模型
算法步骤:
第 1 步:初始化
第 2 步:令
(a) 计算“伪残差”:
(b) 使用 CART 回归树拟合数据
(c) 对
(d) 更新
第 3 步:训练数据对应的回归模型即为
说明 1:假设第
说明 2:其它细节,比如为什么有
3. 梯度提升的高效实现
3.1. XGBoost
XGBoost(eXtreme Gradient Boosting)是梯度提升的高效实现(且有很多改进),它是 Kaggle 比赛冠军选手最常用的工具。
参考:
XGBoost: A Scalable Tree Boosting System
Complete Guide to Parameter Tuning in XGBoost (with codes in Python)
3.2. LightGBM
LightGBM 是微软推出的比 XGBoost 更快的梯度提升工具包。
4. 附录:CART 回归树(最小二乘回归树)
这里简单地介绍一下 CART 回归树。为了简单起见,假设数据只有二个维度(即两个特征,用
CART 的思路是把特征空间分为多个区域(后文将介绍具体如何划分,现在假定划分已经完成)。例如图 1 所示,特征空间分为了 5 个区域
Figure 1: CART Regions
这时,我们把 CART 回归模型写为:
其中,
其中,
总结: 对于 CART 回归树,新输入数据
如果通过训练数据我们求得
Figure 2: 图 1 对应的一个 CART 回归树的直观展示
Figure 3: 图 1 对应的一个 CART 回归树
图 4 (摘自 https://support.sas.com/resources/papers/proceedings13/089-2013.pdf )演示了一个更复杂的 CART 回归树。
Figure 4: CART 回归树实例
4.1. 叶结点区域划分规则(递归二分分割)
前面还未介绍如何把特征空间划分为多个区域(称为叶结点区域)。CART 采用迭代方式(每次迭代把一个区域分为两个子区域)来划分特征空间。描述如下:
选择第
如何找到当前迭代中的最优切分变量
怎么求解呢?首先,固定切分变量
通过上面过程,我们把输入特征空间划分为了两个区域。接着,对每个区域重复上述划分过程,直到满足停止条件为止,这样就生成了 CART 回归树的各个 Regions。
注 1:图 3 所示 CART 回归树中,第一次迭代求得的切分变量为
注 2:迭代求解 Regions 的过程每次会把一个区域一分为二,所以图 5 所示分割肯定不会是 CART 分割过程的结果。
Figure 5: 这肯定不会是 CART 分割过程的结果
4.2. CART 回归树实例
下面通过一个 CART 回归树实例(摘自《统计学习方法,李航著》例 8.2)来重点描述下前面介绍的叶结点区域划分规则。
例子:给定表 2 所示训练数据,
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|
5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05 |
求 CART 回归树,重点是求解叶结点区域划分。
这个例子中特征空间是一维的,无需寻找最优切分变量。
设
通过以下优化问题:
可以求得训练数据的最优切分点
步骤如下:
容易求得,
这里
根据所给数据,考虑如下切分点:
对于各个切分点,不难求出相应的
显然原优化问题,就是最小化
当
类似地,对应其它切分点,我们都可以求得相应的
1.5 | 2.5 | 3.5 | 4.5 | 5.5 | 6.5 | 7.5 | 8.5 | 9.5 | |
---|---|---|---|---|---|---|---|---|---|
15.72 | 12.07 | 8.36 | 5.78 | 3.91 | 1.93 | 8.01 | 11.73 | 15.74 |
从表 3 中可知,当
注 1:为简单起见,例子中特征空间是一维的(如果是多维的,步骤也类似,只是求最优切分变量时,还需遍历一下其它特征)。
注 2:为简单起见,我们限制叶结点区域个数为 2,这样只用进行一次迭代就得到 CART 回归树。当叶结点区域个数大于 2 时,步骤是类似的。比如叶结点区域个数为 3 时,我们可以按照同样的步骤在生成的两个区域中寻找另外一个最优切分点(由于只有一个特征,不用寻找最优切分变量了)。
4.3. CART 回归树 vs. 线性回归
假设输入变量(特征空间)是二维的,图 6 (摘自 https://rafalab.github.io/pages/649/section-11.pdf )演示了 CART 回归树和线性回归的区别。
Figure 6: CART 回归树(右边两个图) vs. 线性回归(左边两个图)