All About GBDT (1)

GBDT(Gradient Boosting Decision Tree) 从名字上理解包含三个部分:提升、梯度和树。它最早由 Freidman 在 greedy function approximation :a gradient boosting machine 中提出。很多公司线上模型是基于 GBDT+FM 开发的,我们 Leader 甚至认为 GBDT 是传统的机器学习集大成者。断断续续使用 GBDT 一年多后,大胆写一篇有关的文章和大家分享。

朴素的想法

假设有一个游戏:给定数据集 (x1,y1),(x2,y2),...,(xn,yn){(x_1,y_1),(x_2,y_2),...,(x_n,y_n)},寻找一个模型y^=F(xi){\hat y=F(x_i)},使得平方损失函数 12(y^iyi)2{\sum \frac{1}{2}(\hat y_i - y_i)^2} 最小。

如果你的朋友提供一个可以使用但是不完美的模型,比如

F(x1)=0.8,y1=0.9F(x_1)=0.8,y_1=0.9

F(x2)=1.4,y2=1.3F(x_2)=1.4,y_2=1.3

在如何不修改这个模型的参数情况下,提高模型效果?

一个简单的思路是:重新训练一个模型实现

F(x1)+h(x1)=y1F(x_1)+h(x_1)=y_1

F(x2)+h(x2)=y2F(x_2)+h(x_2)=y_2

......

F(xn)+h(xn)=ynF(x_n)+h(x_n)=y_n

换一个角度是用模型学习数据 (x1,y1F(x1)),(x2,y2F(x2)),...,(xn,ynF(xn)){(x_1,y_1-F(x_1)),(x_2,y_2-F(x_2)),...,(x_n,y_n-F(x_n))}。得到新的模型 y^=F(xi)+h(xi){\hat y=F(x_i)+h(x_i)}

其中 yiF(xi){y_i-F(x_i)} 的部分被我们称之为残差,即之前的模型没有学习到的部分。重新训练模型 h(x){h(x)}正是学习残差。如果多次执行上面的步骤,可以将流程描述成:

F0(x){F_0(x)}

F1(x)=F0(x)+h1(x){F_1(x)=F_0(x)+h_1(x)}

F2(x)=F1(x)+h2(x){F_2(x)=F_1(x)+h_2(x)}

...{...}

Ft(x)=Ft1(x)+ht(x){F_t(x)=F_t-1(x)+h_t(x)}

F(x;w)=t=1Tht(x;w){F(x;w)=\sum^T_{t=1}h_t(x;w)},这也就是 GBDT 。

如何理解 Gradient Boosting Decision Tree ?

Gradient Boosting Decision Tree 简称 GBDT,最早由 Friedman 在论文《Greedy function approximation: a gradient boosting machine》中提出。简单从题目中理解包含三个部分内容:Gradient Descent、Boosting、Decision Tree。

Decision Tree 即决策树,利用超平面对特征空间划分来预测和分类,根据处理的任务不同分成两种:分类树和回归树。在 GBDT 算法中,用到的是 CART 即分类回归树。用数学语言来描述为 F={f(x)=wq(x)}{F=\{f(x)=w_{q(x)}\}},完成样本 x{x} 到决策树叶子节点 q(x){q(x)} 的映射,并将该叶子节点的权重 wq(x){w_{q(x)}} 赋给样本。CART 中每次通过计算 gain 值贪心来进行二分裂。

Boosting 是一种常用的集成学习方法(另外一种是 Bagging)。利用弱学习算法,反复学习,得到一系列弱分类器(留一个问题,为什么不用线性回归做为弱分类器)。然后组合这些弱分类器,构成一个强分类器。上面提到的模型 F(x;w)=t=1Tht(x){F(x;w)=\sum^T_{t=1}h_t(x)} 即是一种 boosting 思路,依次训练多个 CART 树 hi{h_i},并通过累加这些树得到一个强分类器 F(x;w){F(x;w)}

为什么 GBDT 可行?

在 2 中我提到 GBDT 包括三个部分并且讲述了 Boosting 和 Decison Tree。唯独没有提到 Gradient Descent,GBDT 的理论依据却恰恰和它相关。

回忆一下,Gradient Descent 是一种常用的最小化损失函数 L(θ){L(\theta)} 的迭代方法。

  • 给定初始值 θ0{\theta_0}
  • 迭代公式:θt=θt1+Δθ{\theta ^t = \theta ^{t-1} + \Delta \theta}
  • L(θt){L(\theta ^t)}θt1{\theta ^{t-1}} 处进行一阶泰勒展开:L(θt)=L(θt1+Δθ)L(θt1)+L(θt1)Δθ{L(\theta ^t)=L(\theta ^{t-1} + \Delta \theta) \approx L(\theta ^{t-1}) + L^\prime(\theta ^{t-1})\Delta \theta}
  • 要使 L(θt)<L(θt1){L(\theta ^t) < L(\theta ^{t-1}) },取 Δθ=αL(θt1){\Delta \theta = -\alpha L^\prime(\theta ^{t-1})}
  • 其中 α{\alpha} 是步长,可以通过 line search 确定,但一般直接赋一个很小的数。

在 1 中提到的问题中,损失函数是 MSE L(y,F(x))=12(yif(xi))2{L(y, F(x))=\frac{1}{2}(y_i - f(x_i))^2}

我们的任务是通过调整 F(x1),F(x2),...,F(xn){F(x_1), F(x_2), ..., F(x_n)} 最小化 J=iL(yi,F(xi)){J=\sum_i L(y_i, F(x_i))}

如果将 F(xi){F(x_i)} 当成是参数,并对损失函数求导得到 JF(xi)=iL(yi,F(xi))F(xi)=L(yi,F(xi))F(xi)=F(xi)yi{ \frac{\partial J}{\partial F(x_i)} = \frac{\partial \sum_i L(y_i, F(x_i))}{\partial F(x_i)} = \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} = F(x_i)-y_i}

可以发现,在 1 中提到的模型 h(x){h(x)} 学习的残差 yiF(xi){y_i-F(x_i)}正好等于负梯度,即 yiF(xi)=JF(xi){y_i-F(x_i)=-\frac{\partial J}{\partial F(x_i)}}

所以,参数的梯度下降和函数的梯度下降原理上是一致的:

  • Ft+1(xi)=Ft(xi)+h(xi)=F(xi)+yiF(xi)=Ft(xi)1JF(xi){F_{t+1}(x_i)=F_t(x_i)+h(x_i)=F(x_i)+y_i-F(x_i)=F_t(x_i)-1\frac{\partial J}{\partial F(x_i)}}
  • θt=θt1+αL(θt1){\theta ^t = \theta ^{t-1} + \alpha L^\prime(\theta ^{t-1})}

GBDT 算法流程

模型 F 定义为加法模型:

F(x;w)=m=1Mαmhm(x;wm)=m=1Mft(x;wt){F(x;w)=\sum^{M}_{m=1} \alpha_m h_m(x;w_m) = \sum^{M}_{m=1}f_t(x;w_t)}

其中,x 为输入样本,h 为分类回归树,w 是分类回归树的参数,α{\alpha} 是每棵树的权重。

通过最小化损失函数求解最优模型:F=argminFi=1NL(yi,F(xi)){F^* = argmin_F \sum^N_{i=1}L(y_i, F(x_i))}

输入: (xi,yi),T,L{(x_i,y_i),T,L}

  1. 初始化:f0(x){f_0(x)}
  2. 对于 t=1toT{t = 1 to T}
    1. 计算负梯度(伪残差): yi~=[L(yi,F(xi))F(x)]F(x)=Fm1(x),i=1,2,...,N{ \tilde{y_i} = -[\frac{\partial L(y_i, F(x_i))}{\partial F(x)}]_{F(x)=F_{m-1}(x)} ,i=1,2,...,N}
    2. 根据 yi~{\tilde{y_i}} 学习第 m 棵树: w=argminwi=1N(yi~ht(xi;w))2{w^*=argmin_{w} \sum_{i=1}^N(\tilde{y_i} - h_t(x_i;w))^2}
    3. line searcher 找步长:ρ=argminρi=1NL(yi,Ft1(xi)+ρht(xi;w)){\rho^* = argmin_\rho \sum_{i=1}^{N}L(y_i, F_{t-1}(x_i)+\rho h_t(x_i;w^*))}
    4. ft=ρht(x;w){f_t=\rho^*h_t(x;w*)},更新模型:Ft=Ft1+ft{F_t=F_{t-1}+f_t}
  3. 输出 FT{F_T}

说明:

  1. 初始化 f0{f_0} 方法
    1. 求解损失函数最小
    2. 随机初始化
    3. 训练样本的充分统计量
  2. 每一轮拟合负梯度,而不是拟合残差,是为方便之后扩展到其他损失函数。
  3. 最小化问题中,如果有解析解,直接带入。否则,利用泰勒二阶展开,Newton Step 得到近似解。

这一篇就先到这里,之后还会分享 GBDT 常用损失函数推导以及 XGboost 相关内容。如果有任何想法,都可以在留言区和我交流。

Reference

  1. 李航, 《统计学习方法》8.4 提升树
  2. Freidman,greedy function approximation :a gradient boosting machine
  3. 【19年ML思考笔记】GBDT碎碎念(1)谈回归树的分裂准则 - 知乎
  4. 机器学习-一文理解GBDT的原理-20171001 - 知乎
  5. GBDT入门详解 - Scorpio.Lu|Blog
  6. python - Why Gradient Boosting not working in Linear Regression? - Stack Overflow
  7. GBDT基本原理及算法描述 - Y学习使我快乐V的博客 - CSDN博客
  8. GBDT的那些事儿 - 知乎
作者

Ryen Xiang

发布于

2020-01-26

更新于

2024-07-21

许可协议


网络回响

评论