简介
本文主要讲提升树的模型与算法，并会在最后对梯度提升树进行比较与描述。在看XGBoost原理与推导前，可先看本文，对提升树有一个基本了解。
提升树模型
我们先来看一下提升树的模型，提升方法实际采用的仍然是加法模型(即基函数的线性组合)和前向分步算法。当基函数是决策树的时候，这个提升方法就叫提升树。根据上述，我们可以把提升树的模型公式表示出来： \[f_M(x)=\sum_{m=1}^MT(x;\Theta_m) \tag{1}\] 其中，\(T(x;\Theta_m)\)就表示决策树。\(x\)为输入的样本。\(\Theta_m\)为第\(m\)棵树的参数，从回归树原理与推导中来看，类似其叶子节点权重。\(M\)为树的总棵树。
提升树算法
提升树算法也是用前向分步算法，我们设第\(m\)步的模型是 \[f_m(x)=f_{m-1}(x)+T(x;\Theta_m) \tag{2}\] 也就是说模型是在之前训练好的结果上加上当前的决策树的输出。
对于第\(m\)步的最优参数\(\hat{\Theta}_m\)，根据经验风险最小化的策略，有： \[\hat{\Theta}_m=\arg \min_{\Theta_m}\sum_{i=1}^N\mathcal{L}(y_i,f_m(x_i)) \tag{3}\] 我们假定采用平方误差损失，即有： \[\mathcal{L}(y,f_m(x))=(y-f_m(x))^2 \tag{4}\] 我们把(2)式代入(4)式，有： \[\mathcal{L}(y,f_{m-1}(x)+T(x;\Theta_m))=(y-f_{m-1}(x)-T(x;\Theta_m))^2 \tag{5}\] 我们令 \[r=y-f_{m-1}(x) \tag{6}\] 则(5)式可以写成： \[\mathcal{L}(y,f_{m-1}(x)+T(x;\Theta_m))=(r-T(x;\Theta_m))^2 \tag{7}\] 我们把\(r\)叫作当前模型拟合数据的残差(residual)，从(7)式可以看到，要使损失变小，即要让当前的树的输出拟合当前模型的残差。如何去拟合呢？可以参考回归树原理与推导。
梯度提升树
对于上述提升树，我们做了一个假设为损失为平方误差损失，如果推及一般损失函数，每一步的优化并不简单了。针对这个问题，Freidman提出了梯度提升的算法，即利用损失函数的负梯度在当前模型的值来近似(6)式中的残差(如果损失为平方误差损失，那么负梯度就是残差)。即 \[r_{mi}=-[\frac{\partial \mathcal{L(y_i,f(x_i))}}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} \tag{8}\] 其中\(i\)为样本数，\(m\)为提升迭代第\(m\)轮。与我们比较熟悉的梯度下降的算法思想类似。
参考文献
《统计学习方法》李航 8.4
