提升树

提升树是以回归树或分类树为基学习器的提升算法，它使用加法模型

其中$T(x; \Theta_m)$表示单棵决策树，$\Theta_m$表示决策树的参数，$M$为树的个数；同时使用前向分步算法，首先确定初始提升树为$f_0(x) = 0$，则第$m$步的模型为

其中$f_{m-1}(x)$为当前模型，通过损失函数极小化确定下一棵决策树的参数$\Theta_m$

由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂，因此提升树被认为是统计学习中性能最好的方法之一。对于二分类问题，当使用指数损失函数时，此时为AdaBoost算法的特殊情况。对于回归问题，已知一个训练集$D = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，$x_i \in \chi \sube \R^N$，$\chi$为输入空间，$y_i \in \gamma \sube \R$，$\gamma$为输出空间。如果将输入空间$\chi$划分为$J$个互不相交的区域$R_1, R_2, …, R_J$，并且在每个区域上确定输出的常量$c_j$，那么有$J$个叶节点的树可以表示为

当使用平方误差损失函数时

有

其中$r_m = y - f_{m-1}(x)$表示当前模型拟合数据的残差，因此对于回归问题的提升树，只需要拟合当前模型的残差。

输入：

训练集$D = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，$x_i \in \chi \sube \R^N$，$y_i \in \gamma \sube \R$

过程：

1. $f_0(x) = 0$;
2. for m = 1, 2, …, M do
3. ​ $r_m = y - f_{m-1}(x)$;
4. ​ 拟合残差$r_m$学习一个回归树$T(x; \Theta_m)$;
5. ​ $f_m(x) =f_{m-1}(x) + T(x; \Theta_m)$;
6. end for

输出：$f_M(x) = \sum_{m=1}^M T(x; \Theta_m)$

梯度提升

回归提升树在损失函数为平方损失时，可以方便地直接优化残差即可，但对于一般的损失函数，有梯度提升的算法。梯度提升（Gradient Boosting）实际就是利用了函数在负梯度方向上下降最快的性质对损失函数进行优化，从而使得集成的泛化性能得到提升。

输入：

训练集$D = {(x_1, y_1), (x_2, y_2), …, (x_N, y_N)}$，$x_i \in \chi \sube \R^N$，$y_i \in \gamma \sube \R$

过程：

1. $f_0(x) = \mathop{\arg \min} \limits_c \sum_{i=1}^N \ell (y_i, c)$;
2. for m = 1, 2, …, M do
3. ​ for i = 1, 2, …, N do
4. ​ $r_{im} = - {\bigg[ \frac {\partial \ell (y_i, f(x_i))} {\partial f(x_i)} \bigg]} _ {f=f_{m-1}}$;
5. ​ end for
6. ​ 对$r_{im}$拟合一个回归树，得到第m棵树的叶节点区域$R_{jm} \quad j = 1, 2, …, J_m$;
7. ​ for j = 1, 2, …, $J_m$ do
8. ​ $c_{jm} = \mathop{\arg \min} \limits_c \sum_{x_i \in R_{jm}} \ell(y_i, f_{m-1}(x_i) + c)$;
9. ​ end for
10. ​ $f_m(x) =f_{m-1}(x) + \sum_{j=1}^{J_m} c_{jm} \Bbb{I} (x \in R_{jm})$;
11. end for

输出：$\hat f(x) = f_M(x)$

GBDT

GBDT(Gradient Boosting Decision Tree)叫做梯度提升决策树，是一种Boosting集成学习算法，它使用CART回归树为基学习器。基于梯度提升算法的学习器叫做GBM(Gradient Boosting Machine)，理论上GBM可以选择不同的算法作为基学习器，GBDT只是GBM的一种情况。那么为什么梯度提升算法要使用决策树作为基学习器呢？因为决策树具有解释性强、预测速度快、不需要特征标准化、可以处理缺失值等优点，但单棵树很容易过拟合，通过一系列办法限制单棵树的复杂度，再使用梯度提升算法集成多棵树，这就是GBDT。限制决策树复杂度的方法有很多，比如限制树的最大深度、叶子节点的最少样本数、向下分支时节点的最少样本数、使用Bagging的思想对训练样本进行自助法采样、采用随机森林的思想对特征采样、进行代价复杂性剪枝等。