提升树是以分类树或回归树为基础分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。当损失函数是平方损失和指数损失函数时是普通提升树，当利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树时称为梯度提升决策树(GBDT)。
提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
如果我们取一个基本分类器if (x > 30) 1 else 0，这可以看做是由一个根节点直接连接两个叶结点的简单决策树，即所谓的决策树桩(decision stump)。提升树模型可以表示为决策树的加法模型。
$$ f_M(x) = \sum_{m=0}^{M}{\alpha}_{m}G_{m}(x) $$
其中，$T(x;{\theta}_m)$表示决策树；${\theta}_m$为决策树的参数；M为树的个数。
提升树算法采用前向分布算法。首先确定初始提升树$f_0(x) = 0$，第m步的模型是
$$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $$
其中，f_{m-1}(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数 $ {\theta}_m$，
$$ {\theta}_m = argmin_{{\theta}_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i;{\theta}_m)) $
由于树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
当提升树使用平方误差损失函数时可解决回归问题，当使用指数损失函数时可解决分类问题。
输入：训练数据集$ T={(x_1, y_1), (x_2, y_2), ... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $
输出：提升树$ f_M(x) $
(1) 初始化 $ f_0(x) = 0$
(2) 对m=1,2,...,M
(a) 按式$r=y-f_{m-1}(x)$计算残差
$$ r_{mi} = y_i - f_{m-1}(x_i), i = 1,2,...,N $$
(b) 拟合残差$ r_{mi} $学习一个回归树，得到$T(x;{\theta}_m)$
(c) 更新$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $
(3) 得到回归问题提升树
$$ f_M(x) = \sum_{m=1}^{M}T(x;{\theta}_m) $$
已知如表8.2所示的训练数据，x的取值范围为区间[0.5, 10.5]，y的取值范围为区间[5.0, 10.0]，学习这个回归问题的提升树模型，考虑只用树桩作为基函数。
$$ 提升树实例，训练数据表 $$
| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y_i$ | 5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05 |
解 按照提升树算法，第1步求$f_i(x)$ 即回归树$T_i(x)$。
首先通过以下优化问题：
$$ min_s [min_{c_1}\sum_{x_i \in R_i } (y_i - c_i)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2] $$
求解训练数据的切分点s:
$$ R_1 = {x|x<= s}, R_2 = {x|x>s} $$
容易求得在$ R_1, R_2 $内部使平方损失误差达到最小值的$c_1,c_2$为
$$ c_1 = \frac{1}{N} \sum_{x_i \in R_i}y_i, c_2 = \frac{1}{N} \sum_{x_i \in R_2}y_i $$
这里$N_1, N_2$是$R_1, R_2$的样本点数。
求训练数据的切分点。根据所给数据，考虑如下切分点：
$$ 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5 $$
对各切分点，不难求出相应的$R_1, R_2, c_1, c_2$及
$$ m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 $$
例如，当s=1.5时，
$$R_1 = {1}, R_2 = {2, 3, ...10}, c_1 = 5.56, c_2 = 7.50$$
$$m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 = 0 + 15.72 = 15.72 $$
现将s及m(s)的计算结果列表如下：
$$提升树算法，计算数据表$$
| s | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 | 6.5 | 7.5 | 8.5 | 9.5 |
|---|---|---|---|---|---|---|---|---|---|
| $m(s)$ | 15.72 | 12.07 | 8.36 | 5.78 | 3.91 | 1.93 | 8.01 | 11.73 | 15.74 |
由上表可知，当s=6.5时m(s)达到最小值，此时$R_1={1,2,...,6}, R_2={7,8,9,10}, c_1=6.24, c_2 = 8.91,$所以回归树$T_1(x)$为：
$$T_1(x) = \begin{cases} 6.24& \text{x<6.5}\\ 8.91& \text{x >= 6.5} \end{cases}$$
$$f_i(x)=T_i(x)$$
用$f_i(x)$拟合训练数据的残差见下表，表中$r_2i=y_i - f_i(x_i), i=1,2,...,10.$
$$提升树算法，残差表$$
| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $r_{2i}$ | -0.68 | -0.54 | -0.33 | 0.16 | 0.56 | 0.81 | -0.01 | -0.21 | 0.09 | 0.14 |
用$f_1(x)$拟合训练数据的平方损失差：
$$L(y, f_i(x)) = \sum_{i=1}^{10}(y_i - f_1(x_i))^2 = 1.93 $$
第2步求$T_2(x)$。方法与求$T_1(x)$一样，只是拟合的数据是上表的残差。可以得到：
$$T_1(x) = \begin{cases} -0.52,& \text{x<3.5}\\ 0.22& \text{x <= 3.5} \end{cases}$$
$$f_2(x) = f_1(x) + T_2(x) = \begin{cases} 0.57,& \text{x<3.5}\\ 6.46,& \text{3.5 <= x <= 6.5}\\ 9.13,& \text{x >= 6.5} \end{cases}$$
用$f_2(x)$拟合训练数据的平方损失误差是：
$$L(y,f_2(x)) = \sum_{i=1}^{10}(y_i - f_2(x_i))^2 = 0.79$$
继续求得：
$$T_3(x) = \begin{cases} 0.15,& \text{x<6.5}\\ -0.22& \text{x >= 6.5} \end{cases} L(y,f_3(x))=0.47,$$
$$T_4(x) = \begin{cases} -0.16,& \text{x<4.5}\\ 0.11& \text{x >= 4.5} \end{cases} L(y,f_4(x))=0.30,$$
$$T_5(x) = \begin{cases} 0.07,& \text{x<6.5}\\ -0.11& \text{x >= 6.5} \end{cases} L(y,f_5(x))=0.23,$$
$$T_6(x) = \begin{cases} -0.15,& \text{x<2.5}\\ 0.04& \text{x >= 2.5} \end{cases} $$
$$f_6(x) = f_5(x) + T_6(x) = T_1(x) + ... + T_5(x) + T_6(x) \\ = \begin{cases} 5.63,& \text{x<2.5}\\ 5.82,& \text{2.5 >= x < 3.5} \\ 6.56,& \text{3.5 >= x < 4.5} \\ 6.83,& \text{4.5 >= x < 6.5} \\ 8.95,& \text{x >= 6.5} \end{cases} $$
用$f_6(x)$拟合训练数据的平方损失误差是：
$$L(y,f_6(x)) = \sum_{i=1}^{10}(y_i - f_6(x_i))^2=0.17$$
假设此时已满足误差要求，那么$f(x) = f_6(x)$即为所求提升树。
提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不是那么容易。针对这一问题，Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法，器其关键是利用损失函数的负梯度在当前模型的值：
$$ -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
梯度提升算法:
输入：训练数据集$ T={(x_1, y_1), (x_2, y_2),... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $ 损失函数L(y, f(x));
输出：回归树f(x).
(1) 初始化
$$ f_0(x) = argmin_c{\sum_{i=1}^NL(y_i, c)} $$
(2) 对m=1,2,...,M
(a) 对i=1,2,...,N,计算
$$ r_{mi} = -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$
(b) 对$ r_{mi} $拟合一个回归树，得到第m棵树的叶节点区域$R_{mj}, j=1,2,...,J$
(c) 对$ j=1,2,...J, $计算
$$ c_{mj} = argmin_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_{j=1}^{J}c_{mj}I(x \in $_{mj}) $
(3) 得到回归树
$$ \hat{f(x)} = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^Jc_{mj}I(x \in R_{mj}) $$
算法第1步初始化，估计使损失函数极小化的常数值，它只是一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2(b)步估计回归树叶结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数极小化。第2(d)步更新回归树。第2步得到输出的最终模型$ \hat{f(x)} $