GBDT

GBDT(Gradient Boosting Descision Tree),梯度提升决策树,又名 MART(Multiple Additive Regression Tree),是由多颗回归决策树组成的 Boosting 算法,常用于 CTR 预估。本文介绍了决策树、Boosting 决策树、Gradient Boosting 决策树的算法原理和实现

Regression Descision Tree

最小二乘回归树生成算法

输入:训练数据集 DD

输出:回归树

算法:在训练集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树:

(1) 选择最优切分变量 j 与切分点 s,求解

minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2]\min_{j,s} \bigg[\min_{c_1} \sum_{x_i \in R_1 (j, s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2) ^2 \bigg]

遍历特征 j,对固定的切分变量 j 扫描切分点,选择使上式达到最小值的对 (j,s)(j,s)

(2) 用选定的对 (j,s)(j,s) 划分区域并决定响应的输出值:

R1(j,s)={xx(j)s},R2(j,s)={xx(j)>s}c^m=1NmxiRm(j,s)yi,xRm,m=1,2\begin{aligned} R_1(j,s)=\{x |x^{(j)} \leq s\}, R_2(j,s)=\{x|x^{(j)}>s\} \\ \hat c_m = \frac{1}{N_m} \sum_{x_i \in R_m (j,s)} y_i, x\in R_m, m=1,2\\ \end{aligned}

(3) 继续对两个子区域调用步骤 (1) (2) ,直值满足停止条件(最大深度、样本数量不足无法细分)

(4) 将输入空间划分为 MM 个区域 R1,R2,...,RMR_1,R_2,...,R_M ,生成决策树:

T(x;Θm)=m=1Mc^mI(xRm)T(x;\Theta_m)=\sum_{m=1}^{M} \hat c_m I(x \in R_m)

Boosting Decision Tree

迭代地使用多棵回归决策树,每一颗树的学习目标,是最小化上一棵树的残差

残差=真实值-预测值

这是一种加法模型,模型预测值等于所有子树输出值的累加

fM(x)=m=1MT(x;Θm)f_M(x)=\sum_{m=1}^M T(x;\Theta_m)

其中 TT 表示决策树,Θm\Theta_m 表示决策树的参数,MM 树的个数。

用前向分布算法训练决策树:

(1) 令 f0(x)=0f_0(x)=0

(2) m=1,2,...,Mm=1,2,...,M 时,

fm(x)=fm1(x)+T(x;Θm)f_m(x)=f_{m-1}(x)+T(x;\Theta_m)

其中 fm1f_{m-1} 是当前树,通过最小化损失函数,确定下一棵树的参数

Θ^m=argmini=1NL(yi,fm1+T(xi;Θm))\hat \Theta_m=\arg \min \sum_{i=1}^{N} L(y_i, f_{m-1} + T(x_i;\Theta_m))

Gradient Boosting Decision Tree

Boosting Tree 用加法模型和前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失时,每一步优化很简单;对一般损失函数而言,如 abs loss 和 Huber-M loss [4], 有时并不容易。针对这个问题, Freidman [3] 提出了梯度提升 Gradient Boost 算法,利用最速下降法的近似方法,其关键是利用损失函数的负梯度 (有别于 Boosting 方法的残差)在当前模型的值

[L(y,f(xi))f(xi)]f(x)=fm1(x)-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}

作为回归问题提升树算法中的残差的近似值, 拟合一个回归树

输入: 训练集 T=\{(x_1,y_1,…,(x_n,y_n)\},x_i \in X \subseteq \mathbb{R}^n,y_i \in Y \subseteq \mathbb{R} ;损失函数 L(y,f(x))L(y,f(x))

输出: 回归树 f^(x)\hat f(x)

  1. 初始化
f_0(x)=\arg \underset{c}{\min} \sum_{i=1}^{N}L(y_i,c)
  1. m=1,2,..,Mm=1,2,..,M

a) 对 i=1,2,…,N 计算

γmi=[L(y,f(xi))f(xi)]f(x)=fm1(x)\gamma_{mi}=-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}

b) 对 γmi\gamma_{mi} 拟合一个回归树, 得到第 mm 棵树的叶节点区域 RmjR_{mj}, j=1,2,…,J

c) 对 j=1,2,…,J 计算

c_{mj}=\arg \underset {c}{\min} \sum_{x_i \in \mathbb{R}_{mj}} L(y_i,f_{m-1}(x_i)+c)

d) 更新

fm(x)=fm1(x)+j=1JcmjI(xRmj)f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J}c_{mj}I(x\in \mathbb{R}_{mj})

3)得到回归树

f^(x)=fM(x)=m=1Mj=1JcmjI(xRmj)\hat f(x)=f_M(x)=\sum_{m=1}^{M}\sum_{j=1}^{J} c_{mj}I(x\in \mathbb{R}_{mj})

其中,当损失函数是 MSE 时,GBDT 与 Boosting Descision Tree 的形式相同。

(XG)Boosted Trees

Boosted Trees 模型定义:

y^i=k=1Kfk(xi),fkF\hat y_i = \sum_{k=1}^K f_k(x_i), f_k \in \mathcal F

其中 K 是树的个数,ff 是属于函数空间 F\mathcal F 的树,F\mathcal F 是所有可能的树集合。

目标函数定义:

obj(θ)=inl(yi,y^i)+k=1KΩ(fk)obj(\theta)=\sum_i^n l(y_i, \hat y_i) + \sum_{k=1}^K \Omega(f_k)

Boosted Trees 定义和 RF 一样,区别是树的训练的方法:增量训练和并行训练。

增量训练过程:

\begin{align} \hat y^{(0)} &= 0 \\ \hat y_i^{(1)} &= f_1(x_i) = \hat y_i^{(0)} + f_1(x_i)\\ &...\\ \hat y_i^{(t)} &= \sum_{k=1}^t f_k (x_i) = \hat y_i^{(t-1)} + f_t(x_i) \end{align}

在训练的每一步 t,最优化目标:

\begin{align} obj^{(t)} &= \sum_{i=1}^n l(y_i, \hat y_i^{(t)}) + \sum_{i=1}^t \Omega(f_i)\\ &= \sum_{i=1}^n l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \sum_{i=1}^t \Omega(f_i) \end{align}

如果 ll 是 MSE,对目标函数 obj(t)obj^{(t)} 用二阶泰勒展开,移除常数项得到:

obj(t)=i=1n[gift(xi)+12hift2(xi)]+Ω(ft)obj^{(t)} = \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)

其中:

g_i = \partial_{\hat y_i^{(t-1)}} l (y_i, \hat y_i ^{(t-1)}) \\ h_i = \partial^2_{\hat y_i^{(t-1)}} l (y_i, \hat y_i ^{(t-1)})

树函数定义:

ft(x)=wq(x),wRT,q:Rd1,2,...,T.f_t(x)=w_{q(x)}, w \in R^T, q:R^d \to {1, 2, ..., T}.

其中 ww 是叶子分数向量 ,qq 是把数据映射到叶子的函数,TT 是树叶个数。

复杂度定义可以是:

Ω(f)=γT+12j=1Twj2\Omega(f) = \gamma T + \frac{1}{2} \sum_{j=1}^T w_j^2

结合 ffΩ\Omega 的定义,更新目标函数:

\begin{align}\\ obj^{(t)} &= \sum_{i=1}^n[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T [(\sum_{j \in I_j} g_i) w_j +\frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_j^2] + \gamma T \end{align}

其中 Ij={iq(xi)=j}I_j= \{i | q(x_i)=j\} 是所有归于 j 叶子的 i 的集合。

代入 Gj=iIjgiG_j=\sum_{i\in I_j} g_iHj=iIjhiH_j=\sum_{i\in I_j} h_i 得到:

obj(t)=j=1T[Gjwj+12(Hj+λ)wj2]+γTobj^{(t)} = \sum_{j=1}^T [G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2] + \gamma T

对于 wjw_j,最优的值取在 Gjwj+12(Hj+λ)wj2G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 导数零点:

\begin{align} w_j^* &= - \frac{G_j}{H_j + \lambda} \\ obj^* &= - \frac{1}{2} \sum_{j=1}^T \frac{G^2_j}{H_j + \gamma} + \gamma T \end{align}

最后一个等式可以衡量树结构函数 q(x)q(x) 的优劣。在分裂节点的时候,可以用 Gain 来衡量分裂节点的好坏:

Gain=12[GL2HL+λ+GR2HR+λ(GL+GR)2HL+HR+λ]γGain = \frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L + G_R)^2 }{H_L+H_R+\lambda}] - \gamma

其中每项含义:1) 新的左叶子分数 2) 新的右叶子分数 3) 原来叶子的分数 4) 新叶子的惩罚项

XGBoost 是基于上述监督规则和正则项(取代 CART 剪枝)的 Boosted Tree 库, 特性有:

  • 支持分类和回归问题
  • shrinkage (衰减因子 η\eta)和列采样
  • Split Finding 算法优化:sklearn的gbdt是贪心算法穷举所有 split 较为耗时,xgboost 通过近似方法加速,通过 weighted quantile sketch 算法划分特征区间,使得搜索空间变小、计算结果 g h 可复用、可并行化;Sparsity-ware split finding,缺失值走节点的默认方向(默认方向学习得到),提速50x;
  • 系统设计优化:特征粒度并行支持,data 预排序以 column block 形式存储;Cache-aware access;可并行的近似直方图算法,用于高效地生成候选的分割点。

Reference

[1] GBDT:梯度提升决策树 http://www.jianshu.com/p/005a4e6ac775

[2] 《统计学习方法》李航

[3] Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of statistics, 2001: 1189-1232. PDF

[4] Wiki https://en.wikipedia.org/wiki/Huber_loss

[5] XGBoost: Intro to boosted trees URL

[6] XGBoost: A Scalable Tree Boosting System PDF

本文有帮助?