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_MR1,R2,...,RM ，生成决策树：
Boosting Decision Tree
迭代地使用多棵回归决策树，每一颗树的学习目标，是最小化上一棵树的残差
残差=真实值-预测值
这是一种加法模型，模型预测值等于所有子树输出值的累加
其中 T表示决策树，Θm\Theta_mΘm 表示决策树的参数，MMM 树的个数。
用前向分布算法训练决策树：
(1) 令 f0(x)=0
(2) m=1,2,...,M 时，
其中 fm−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)
- 初始化
f_0(x)=\arg \underset{c}{\min} \sum_{i=1}^{N}L(y_i,c)
- 对 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