机器学习12 提升树模型与梯度提升

这一篇继续boosting，介绍一下提升树算法，提升树以决策树为基模型，依然是加法模型，优化算法是前向分步算法。

针对分类问题，决策树是二叉分类树，回归问题则是二叉回归树。

第m步之后的模型，是 $f_m(x) = f_{m-1}(x) +T(x;\Theta_m)$

$f_{m-1}(x)$ 是m步学习之前的模型，通过极小化损失函数，得到第m棵决策树的参数 $\Theta_m$

$\hat \Theta_m = \mathop{argmin}_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$

针对不同的问题，区别在于损失函数的不同，回归问题采用的是平方误差，分类问题是指数损失误差

当处理二分类问题的时候，提升树模型，等价于基模型为二叉决策树的AdaBoost算法。因此这边不再做详细的介绍

因此这一篇我们主要介绍一下回归问题中的提升树

$T(x;\Theta) = \sum_{j=1}^J c_j1(x\in R_j)$

参数 $\Theta = \{(R_1,c_1), (R_2，c_2),(R_3,c_3),...,(R_j,c_j)\}$ 表示树的区域划分和每个区域的输出值， J就是叶子结点的个数。

这个问题的前向分部算法可以表示为：

$f_0(x) = 0$

$f_m(x) = f_{m-1}(x) + T(x;\Theta_m), m = 1,2,...,M$

$f_M(x) = \sum_{m=1}^MT(x;\Theta_m)$

第m步时，只需要求解

$\hat \Theta_m = \mathop{argmin}_{\Theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$

采用平方误差， $L(y,f(x)) = (y - f(x))^2$

即 $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$

$r = y - f_{m-1}(x)$ , 即第m-1次学习后模型的拟合残差。所以对于第m次学习，只需要拟合当前模型的残差即可。

如果理解了前一篇，这一篇的提升树理解起来应该比较容易。

但是提升树也有局限性，当损失函数是平方损失或是指数损失的时候，前向分步算法去优化每一步是比较简单的（上一篇与这一篇分别解决了其中一类）。但是对于一般的损失函数，可能不容易优化，这就有了梯度提升算法。每一次学习，都是在拟合损失函数的负梯度，只要损失函数梯度存在，就可以优化了，因此更具有普适性。下一篇，我们将会仔细介绍梯度提升树算法GBDT，希望大家可以跟我一样，认识到模型是一步步演变进化的过程。