GBDT

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

Regression Descision Tree

最小二乘回归树生成算法

输入：训练数据集 DDD

输出：回归树

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

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

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

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

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

(4) 将输入空间划分为 MMM 个区域 R1,R2,...,RMR_1,R_2,...,R_MR​1​​,R​2​​,...,R​M​​ ，生成决策树：

Boosting Decision Tree

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

残差=真实值-预测值

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

其中 T表示决策树，Θm\Theta_mΘ​m​​ 表示决策树的参数，MMM 树的个数。

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

(1) 令 f0(x)=0

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

其中 f​m−1​​ 是当前树，通过最小化损失函数，确定下一棵树的参数

Gradient Boosting Decision Tree

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

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

输入: 训练集 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))L(y,f(x))

输出: 回归树 f^(x)\hat f(x)​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,..,Mm=1,2,..,M

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

b) 对 γmi 拟合一个回归树, 得到第 m棵树的叶节点区域 Rmj, 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) 更新

3)得到回归树

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

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