提升树与GBDT的详细算法过程（建议收藏版）

GBDT的全称为：梯度提升决策树，英文为：（Gradient Boosting Decison Tree）。

提升树核心思想：拟合残差

怎么拟合残差呢？

首先第一步是使用boosting技术，对残差使用决策树进行拟合，比如我们常用的CART算法。第二步是使用加法模型，将拟合好的决策树相加。

一、提升树算法步骤

输入：$D=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$

（1）初始化$f_0(x)=0$；

（2）对于$m=1,2,\cdots ,M$，针对每一个样本$(x_i,y_i)$，计算残差：
$$r_{mi}=y_i-f_{m-1}(x_i),i=1,2,\cdots ,N$$

（3）利用$\{(x_i,r_{mi}){\}}_{i=1,2,\cdots ,N}$训练一个决策树（回归树），得到$T(x;{\Theta }_m)$

（4）更新$f_m(x)=f_{m-1}(x)+T(x;{\Theta }_m)$

（5）完成以上迭代，得到提升树:
$$f_M(x)=\sum _{i=1}^{M}T(x;{\Theta }_m)$$

其中，$M$表示决策树个数；$R_{mi}$表示残差。

二、GBDT算法步骤

输入：训练数据集$D=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$；损失函数为:$L(y,f(x))$。

（1）初始化:
$$f_0(x)=\arg \underset{c}{\min }\sum _{i=1}^{N}L(y_i,c)$$

（2）对于$m=1,2,\cdots ,M$，针对每一个样本$(x_i,y_i)$，计算残差：
$$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}{]}_{f(x)=f_{m-1}(x)},i=1,2,\cdots ,N$$

（3）利用$\{(x_i,r_{mi}){\}}_{i=1,2,\cdots ,N}$训练出第$m$棵决策树（回归树）$T_m$，其中叶节点划分的区域为:$R_{mj},j=1,2,\cdots ,J$

（4）对于回归树$T_m$的每一个叶结点，计算其输出值：
$$c_{mj}=\arg \underset{c}{\min }\sum _{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c),j=1,2,\cdots ,N$$

（5）更新:
$$f_m(x)=f_{m-1}(x)+\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$$

（6）得到最终提升回归树：
$$\widehat{f(x)}=f_M(x)=\sum _{m=1}^M\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$$

输出：提升回归树$\widehat{f(x)}$

三、两者之间的区别

1.梯度提升回归树的残差使用负梯度来代替；

2.梯度提升回归树多了一步在叶子节点loss求最优值的计算，这里应该是为了降低优化误差，优化回归树的结果。