提升树是以分类树或者回归树为基本分类器的提升方法，提升树的效果在众多算法中，算是比较顶尖的。

提升树的思想很简单：

j

特征为$x$，输入空间为$\chi$。需要拟合的target(目标值)为$y$。

那么，可以将输入空间划分为$J$个互不相交的区域$R_1,R_2,....,R_J$，并且在每个空间加入常量$c_j$，那么树可以表示为：

$T(x)=\sum\limits_{j=1}^Jc_jI(x\in R_j)$

最开始，建立一个"空模型"，$f_0(x)=0​$。

第一轮，建立一个模型$T_1(x)$,来拟合$y-f_0(x)$ ，模型$f_1(x)=f_0(x)+T_1(x;\Theta_1)$

第二轮，建立一个模型$T_2(x;\Theta_2)$，来拟合$y-f_1(x)$，模型$f_2(x)=f_1(x)+T_1(x;\Theta_2)$

第三轮、第四轮……直到第M轮，建立$T_M(x;\Theta_M)​$来拟合$y-f_{M-1}​$，最终的模型为$f_M(x)=f_{M-1}(x)+T_M(x;\Theta_M)​$。

第$m​$轮预测的target是$y-f_{m-1}(x)​$，是当前模型与真实数据之间的差值，它被称为残差(residual)。回归问题的提升树只要让当前模型的残差最小化就OK了。

最终求的解为：

$$ \hat\Theta_m=\arg\min\limits_c\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)) $$

不难看出，最终的模型，其实是$\sum\limits_{m=1}^MT(x,\Theta_m)​$。而$T(x,\Theta_m)​$学习的是$f_{m-1}(x)​$对$y​$预测的残差。

算法(回归问题的提升树)

设第$m$轮的模型$f_{m}(x)$的损失函数为

$$ Loss=\sum\limits_{i=1}^NL(y_i,f_m(x_i)) $$

损失通常是均方差的形式$(y_i-f_m(x_i))^2​$。

输入：数据集$\{(x_1,y_1),(x_(x_1,y_1),y_2),...,(x_N,y_N)\}$。

输出：提升树$f_M(x)$

1. 初始化$f_0(x)=0​$
2. 对$m=1,2,...,M​$，

(a)计算残差$r_{mi}=y_i-f_{m-1}(x_i),\quad i=1,2,...,N​$

(b)拟合残差$r_{mi}$，让损失函数$Loss$的值最小，得到$T(x;\Theta_m)$

(c)更新$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)​$

1. 得到最终的回归提升树

$f_M(x)=\sum\limits_{m-1}^MT(x;\Theta_m)​$

梯度提升算法

提升树的拟合，可以用梯度提升算法(gradient boosting)来进行。

与最速下降思想类似，利用损失函数的负梯度在当前模型的值：

$$ -\left[ \frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right] $$

不过这次梯度不是修改$f_{m-1}(x_i)$的值，而是用来确定$T_m(x;\Theta)$要拟合的值(残差的近似值)。

算法(梯度提升算法)

输入：数据集$\{(x_1,y_1),(x_(x_1,y_1),y_2),...,(x_N,y_N)\}$。

输出：回归树$f_M(x)​$

1. 初始化$f_0(x)=\arg\min\limits_c\sum\limits_{i=1}^ML(y_i,c)​$,($c​$在之后的计算中是个常数，类似回归分析中的偏置(bias))
2. 对$m=1,2,...,M​$，

(a)计算残差

$$ r_{mi}=-\left[ \frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1}(x)} $$

(b)对$r_{mi}$拟合一个回归树，得到第$m$棵树。

(c)对$J=1,2,...,J​$，计算

$$ c_{mi}=\arg\min\limits_c\sum\limits_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c) $$

(d)更新$f_m(x)=f_{m-1}(x)+\sum\limits_{c_mj}I(x\in R_{mj})​$

1. 得到最终的回归提升树

$$ \hat f(x)=\sum\limits_{m=1}^M\sum\limits_{j=1}^J=c_{mj}I(x\in R_{mj}) $$

第1步初始化，得到一个最优的常数，2(a)步计算损失函数的负梯度在当前模型的值，对于平方损失函数，就是残差，对于一般损失函数，就是残差的近似值。2(b)进行拟合。2(c)则利用线性搜索估计叶节点区域的值，最小化损失函数。2(d)更新回归树。第3步得到最终的输出模型$\hat f(x)$。