梯度提升决策树(Gradient Boosting Decision Tree, GBDT)是一种基于提升决策树(Boosting Tree)的模型以分类回归决策树（Classification and Regression Tree, CART)作为基本分类器的模型。
Bossting Tree
提升树(Bosting Tree)其实就是把分类回归决策树（Classification and Regression Tree, CART)直接进行线性组合的决策树模型，在处理分类问题的时候是二叉分类树，在处理回归问题的时候就是二叉回归树。用公式可以作如下表达：
\(\mathcal{f}_M(x)=\sum_{m=1}^{M}T(x;\theta_{m})\)
\(T(x;\theta_{m})\)表示决策树，\(\theta_{m}\)是决策树的参数，\(M\)是树的个数。
第m步的模型是：
\(f_{m}(x)=f_{m-1}(x)+T(x;\theta_{m})\)
\(f_{m-1}(x)\)是当前模型，通过最小化的方法确定下一棵决策树的参数\(\theta_{m}\)：
\(\hat{\theta_{m}}=\mathop{\arg\min}_{\theta_{m}} \sum_{i=1}^{N}\mathcal{L}(y_{i}, f_{m-1}(x_{i})+T(x;\theta_{m}))\)
一般对于的回归问题采用的损失函数是平方误差损失函数，对于分类问题则使用的是的指数损失函数。以回归问题为例，采用平凡误差损失函数时：
\(\mathcal{L}(y,f(x))=(y-f(x))^2\)
故其损失变成：
\(\begin{aligned} \mathcal{L}(y,f_{m-1}(x)+T(x;\theta_{m})) &= [y-f_{m-1}(x)-T(x;\theta_{m})]^2 \\ &= [r-T(x;\theta_{m})]^2\end{aligned}\)
这里：
\(r=y-f_{m-1}(x)\)
即当前模型拟合的残差(residual)。
Gradient Boosting
提升树算法利用加法模型与前向分布算法实现学习的优化过程，当损失函数是平方损失和指数损失函数的时候，每一步优化比较简单，但是对一般损失函数而言，往往每一步算法优化并不是那么容易，所以就有了梯度提升( Gradient Boosting)算法，主要是利用损失函数的负梯度在当前模型的值：
\(-[\frac{\partial L(y, f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}\)
具体算法流程如下：
输入： 训练数据集\(T={(x_1, y_1), (x_2, y_2), … , (x_N, y_N)}\), \(x_i \in \mathcal{X} \subset \mathcal{R}^{n}\), \(y_i \in \mathcal{Y} \subset \mathcal{R}\); 损失函数 \(L(y, f(x))\) ;
输出：回归树 \(\hat{f}(x)\)
- 初始化: \(f_{0}(x) = \mathop{\arg\min}_c \sum^{N}_{I=1}L(y_i, c)\)
- 对\(m=1, 2, …, M\)
(a). 对\(i=1,2, … ,N\)，计算\(r_{mi}=-[\frac{\partial L(y, f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}\)
(b). 对\(r_{mi}\)拟合一个回归树，得到第m棵树的叶结点区域\(R_{mj}\)，\(j=1,2, …, \mathcal{J}\)
(c). 对\(j=1,2, …, \mathcal{J}\)，计算\(c_{mj}=\mathop{\arg\min}_{c} \sum_{x_{i} \in R_{mj}} L(y_i, f_{m-1}(x_i)+c)\)
(d) 更新\(f_{m}(x) = f_{m-1}(x)+\sum^{\mathcal{J}}_{j=1} c_{mj}I(x \in R_{mj})\) - 得到回归树
\(\hat{f}(x) = f_{M}(x) = \sum^{M}_{m=1} \sum^{J}_{j=1} c_{mj} I(x \in R_{mj})\)
算法第一步初始化，估计使损失函数极小化的常数值，只是一个有根节点的树，第2(a)计算损失函数负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数，它就是通常所说的残差，对于一般损失函数，它就是残差的近似值。第2(b) 步估计回归树的结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计该结点区域的值，使损失函数极小化，第2(d)步更新回归树，第3步得到输出的最终模型 \(\hat{f}(x)\)。
以上便是经典的GBDT模型。
XGBoost
XGBoost则是GBDT的一个优化版实现，主要优化点如下：
- 传统GBDT在loss里面只用到了一阶导，XGBoost则在loss里面基于泰勒展开用到了二阶导，用了牛顿法来迭代。
- XGBoost在代价函数里面添加了正则项，正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合。
- 借鉴随机森林的思想，添加了列抽样以降低过拟合和减少计算。
- 最重要的：支持并行。并行是特征粒度上的，XGBoost在训练之前预先对数据进行排序，然后保存为block结构，后面的迭代重复使用这个结构减少计算量。也是这个block结构使得并行变成了可能，可以在计算特征增益的时候并行。
- 支持运行在MPI，YARN上。
References
- 李航 《统计学习方法》
-
机器学习算法中 GBDT 和 XGBOOST 的区别有哪些？