Gradient Boosting Decision Tree(GBDT)

GBDT又称梯度提升树，是传统机器学习中效果最好的模型之一。在介绍GBDT之前，我们先来看一下回归问题的提升树算法。

Regression

对于回归任务，我们的基学习器自然也应该设置为适用于回归任务的模型，因此选用CART回归树。并且与用于分类的提升树不同的是，我们的损失函数从指数损失变成了均方误差损失。假设我们的回归树有 J J J个叶子节点 R j R_j Rj​，每个叶子节点的输出值为 c j c_j cj​，那么这棵树可以表示为：
T ( x ; θ )   =   ∑ j = 1 J c j I ( x ∈ R j ) T(x;\theta)\ =\ \sum_{j=1}^{J}c_jI(x \in R_j) T(x;θ) = j=1∑J​cj​I(x∈Rj​)
然后假设我们的损失函数选用均方误差损失，即 L ( y , f ( x ) )   =   ( y   −   f ( x ) ) 2 L(y,f(x))\ =\ (y\ -\ f(x))^2 L(y,f(x)) = (y − f(x))2，于是我们在第 t t t轮迭代所找到的最优的回归树就应该满足：
θ t   =   a r g m i n θ    ∑ i = 1 N L ( y i ,   f t − 1 ( x i ) + T ( x i ; θ ) ) \theta_t\ =\ argmin_{\theta}\ \ \sum_{i=1}^{N}L(y_i,\ f_{t-1}(x_i)+T(x_i;\theta)) θt​ = argminθ​  i=1∑N​L(yi​, ft−1​(xi​)+T(xi​;θ))
以上是我们对每轮迭代单棵回归树拟合的过程。下面看整个算法流程。

具体算法流程如下：

输入：数据集 D D D
输出：提升树 f T ( x ) f_T(x) fT​(x)

(1) 初始化 f 0 ( x ) = 0 f_0(x) = 0 f0​(x)=0
(2) 对于 t = 1 , 2 , . . . , T t=1,2,...,T t=1,2,...,T
(a) 计算残差 r t i   =   y i   −   f t − 1 ( x i ) r_{ti}\ =\ y_i\ -\ f_{t-1}(x_i) rti​ = yi​ − ft−1​(xi​)

​ (b) 用残差代替原来的 y y y，即用 D   =   { ( x i , r t i ) } D\ =\ \{(x_i,r_{ti})\} D = {(xi​,rti​)}来拟合一棵回归树，得到 θ t \theta_t θt​，并得到该回归树的叶节点区域 R t j ,   j = 1 , 2 , … , J R_{tj},\ j=1,2,\dots,J Rtj​, j=1,2,…,J

​ © 对于 j   =   1 , 2 , … , J j \ =\ 1,2,\dots,J j = 1,2,…,J，计算

​ c t j   =   a r g m i n c   ∑ i = 1 N L ( y i ,   f t − 1 ( x i )   +   c ) c_{tj}\ =\ argmin_{c}\ \sum_{i=1}^{N}L(y_i, \ f_{t-1}(x_i)\ +\ c) ctj​ = argminc​ ∑i=1N​L(yi​, ft−1​(xi​) + c)

​ (d) 更新 f t ( x )   =   f t − 1 ( x ) + ∑ j = 1 J c t j I ( x ∈ R t j ) f_t(x) \ =\ f_{t-1}(x) + \sum_{j=1}^{J}c_{tj}I(x \in R_{tj}) ft​(x) = ft−1​(x)+∑j=1J​ctj​I(x∈Rtj​)

(3) 得到提升树模型：

​ f M ( x )   =   ∑ t = 1 T ∑ j = 1 J c t j I ( x ∈ R t j ) f_M(x)\ =\ \sum_{t=1}^T \sum_{j=1}^{J}c_{tj}I(x \in R_{tj}) fM​(x) = ∑t=1T​∑j=1J​ctj​I(x∈Rtj​)

GBDT

下面来看GBDT。对于指数损失函数和均方误差损失来说，优化是比较容易的，但对于一般的损失函数来说，优化并不容易，因此 F r i e d m a n Friedman Friedman提出了一个解决方法，即使用损失函数的负梯度作为残差进行拟合。

具体算法流程如下：

输入：数据集 D D D
输出：提升树 f T ( x ) f_T(x) fT​(x)

(1) 初始化 f 0 ( x ) = a r g m i n c ∑ i = 1 N L ( y i , c ) f_0(x) = argmin_c\sum_{i=1}^{N}L(y_i,c) f0​(x)=argminc​∑i=1N​L(yi​,c)
(2) 对于$t=1,2,\dots,T $
(a) 计算残差 r t i   =   − ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) r_{ti}\ =\ -\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)} rti​ = −∂f(xi​)∂L(yi​,f(xi​))​

​ (b) 用残差代替原来的 y y y，即用 D   =   { ( x i , r t i ) } D\ =\ \{(x_i,r_{ti})\} D = {(xi​,rti​)}来拟合一棵回归树，得到 θ t \theta_t θt​

​ © 更新 f t ( x )   =   f t − 1 ( x ) + T ( x ; θ t ) f_t(x) \ =\ f_{t-1}(x) + T(x;\theta_t) ft​(x) = ft−1​(x)+T(x;θt​)

(3) 得到提升树模型： f M ( x )   =   ∑ t = 1 T T ( x ; θ t ) f_M(x)\ =\ \sum_{t=1}^T T(x;\theta_t) fM​(x) = ∑t=1T​T(x;θt​)

其实这里所展示的GBDT主要适用于回归任务。

Binary classification

我们下面来讲一下分类问题，其实我们仍然可以用残差拟合的办法来做分类，只不过这里的残差是真实类标记与预测概率之间的残差。之前我们说提升树模型本质区别还是体现在损失函数上，那么对于分类问题，我们的损失函数无外乎就那么几种。假如使用的是指数损失函数，那么GBDT就退化到了AdaBoost。这里我们介绍采用对数似然函数作为损失函数的做法。

这里所谓的对数似然函数其实就是 s i g m o i d sigmoid sigmoid取对数，仿照了逻辑回归。
L ( y ,   f ( x ) )   =   l o g ( 1   +   e x p ( − y f ( x ) ) ) L(y,\ f(x))\ =\ log(1\ +\ exp(-yf(x))) L(y, f(x)) = log(1 + exp(−yf(x)))
剩下的步骤其实和我们上面的流程是完全一致的。只不过此时我们的优化会比较困难，即
c t j   =   a r g m i n c   ∑ i = 1 N L ( y i ,   f t − 1 ( x i )   +   c ) c_{tj}\ =\ argmin_{c}\ \sum_{i=1}^{N}L(y_i, \ f_{t-1}(x_i)\ +\ c) ctj​ = argminc​ i=1∑N​L(yi​, ft−1​(xi​) + c)
这一步不好优化，因此通常用近似值代替
c t j   =   ∑ x i ∈ R t j r t j ∑ x i ∈ R t j ∣ r t j ∣ ( 1 − ∣ r t j ∣ ) c_{tj}\ =\ \frac{\sum_{x_i \in R_{tj}}r_{tj}}{\sum_{x_i \in R_{tj}}|r_{tj}|(1-|r_{tj}|)} ctj​ = ∑xi​∈Rtj​​∣rtj​∣(1−∣rtj​∣)∑xi​∈Rtj​​rtj​​

Multi-class

那么对于多分类问题，其实这个规律也就摸索出来了，对症下药，采用的是CrossEntropy作为损失函数
L ( y ,   f ( x ) )   =   − ∑ k = 1 K y i l o g ( p k ( x ) ) L(y,\ f(x))\ =\ -\sum_{k=1}^K{y_ilog(p_k(x))} L(y, f(x)) = −k=1∑K​yi​log(pk​(x))
其中 p k ( x ) p_k(x) pk​(x)表示 x x x输入第 k k k类的概率，用softmax来计算
p k ( x )   =   e x p ( f k ( x ) ) ∑ l = 1 K e x p ( f l ( x ) ) p_k(x)\ =\ \frac{exp(f_k(x))}{\sum_{l=1}^K exp(f_l(x))} pk​(x) = ∑l=1K​exp(fl​(x))exp(fk​(x))​
此时，我们的计算的是第 t t t轮迭代第 i i i个样本对类别 k k k的负梯度，即：
r t i k   =   − ∂ L ( y i , f ( x i ) ) ∂ f ( x i )   =   y i k   −   p k , t − 1 ( x ) r_{tik}\ =\ -\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\ =\ y_{ik}\ -\ p_{k, t-1}(x) rtik​ = −∂f(xi​)∂L(yi​,f(xi​))​ = yik​ − pk,t−1​(x)
对于生成的决策树，我们各个叶子节点的最佳负梯度拟合值为：

由于上式比较难优化，我们一般使用近似值代替

Regularization

GBDT有三种正则化方法：

1. 给单棵决策树输出结果乘一个步长，或者叫学习率 α \alpha α，即把更新公式变成 f t ( x )   =   f t − 1 ( x ) + α T ( x ; θ t ) f_t(x) \ =\ f_{t-1}(x) + \alpha T(x;\theta_t) ft​(x) = ft−1​(x)+αT(x;θt​)
2. 子采样比例(subsample)，训练时不采用全部数据进行训练，而是按一定比例采样部分数据，推荐 [ 0.5 ,   0.8 ] [0.5,\ 0.8] [0.5, 0.8]
3. 对基学习器进行正则化，剪枝等操作