# GBDT 提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型： $$f\_m(x)=\sum\limits\_{m=1}^MT(x;\Theta\_m)$$ 其中， $$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$$ ， $$\hat{\Theta}*m=\arg\min\limits*{\Theta\_m}\sum\limits\_{i=1}^NL(y\_i,f\_{m-1}(x\_i)+T(x\_i;\Theta\_m))$$ 下面讨论针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括平方误差损失函数的回归问题，用指数函数的分类问题，以及用一般损失函数的一般决策问题。 ## 分类问题 将GBDT应用于回归问题，相对来说比较容易理解。因为回归问题的损失函数一般为平方差损失函数，这时的残差，恰好等于预测值与实际值之间的差值。每次拿一棵决策树去拟合这个差值，使得残差越来越小，这个过程还是比较intuitive的。而将GBDT用于分类问题，则显得不那么显而易见。 在说明分类之前，我们先介绍一种损失函数。与常见的直接求预测与真实值的偏差不同，这种损失函数的目的是最大化预测值为真实值的概率。这种损失函数叫做对数损失函数（Log-Likehood Loss），定义如下 $$L(Y,P(Y|X))=-\log P(Y|X)$$ 对于二项分布， $$y^*\in{0,1}$$ ，我们定义预测概率为 $$p(x)=P(y^*=1)$$ ，即二项分布的概率，可得 $$L(y^*,p(x))=\begin{cases} -\log(p(x)),\ \ \text{if}\ y^*=1\ -\log(1-p(x)),\ \ \text{if}\ y^\*=0 \end{cases}$$ 即，可以合并写成 $$L(y^\*,p(x))=-y\_i\log(p(x))-(1-y\_i)\log(1-p(x))$$ 即 $$L(y^\*,p(x))=-y\_i\log\hat{y\_i}-(1-y\_i)\log(1-\hat{y\_i})$$ 对于 $$p(x)$$ 与 $$F(x)$$ 的关系，我们定义为 $$p(x)=\frac{e^{F(x)}}{e^{F(x)}+e^{-F(x)}}$$ ### 二分类 类似于逻辑回归、FM模型用于分类问题，其实是在用一个线性模型或者包含交叉项的非线性模型，去拟合所谓的对数几率 $$\ln \frac{p}{1-p}$$ 。而GBDT也是一样，只是用一系列的梯度提升树去拟合这个对数几率，实际上最终得到的是一系列CART回归树。其分类模型可以表达为： $$P(y=1|x)=\frac{1}{1+e^{-\sum^M\_{m=0}h\_m(x)}}$$ 其中， $$h\_m(x)$$ 就是学习到的决策树。 清楚了这一点之后，我们便可以参考逻辑回归，单样本 $$(x\_i,y\_i)$$ 的损失函数可以表达为交叉熵： $$loss(x\_i,y\_i)=-y\_i\log\hat{y\_i}-(1-y\_i)\log(1-\hat{y\_i})$$ 假设第 $$k$$ 步迭代之后当前学习器为 $$F(x)=\sum\limits\_{m=0}^kh\_m(x)$$ ，将 $$\hat{y\_i}$$ 的表达式带入之后， 损失函数写为： $$loss(x\_i,y\_i|F(x))=y\_i\log(1+e^{-F(x\_i)})+(1-y\_i)\[F(x\_i)+\log(1+e^{-F(x\_i)})]$$ 可以求得损失函数相对于当前学习器的负梯度为： $$-\frac{\partial loss}{\partial F(x)}|\_{x\_i,y\_i}=y\_i-\frac{1}{1+e^{-F(x\_i)}}=y\_i-\hat{y\_i}$$ 可以看到，同回归问题很类似，下一棵决策树的训练样本为： $${x\_i,y\_i-\hat{y\_i}}\_{i=1}^n$$ ，其所需要拟合的残差为真实标签与预测概率之差。于是便有下面GBDT应用于二分类的算法： * $$F\_0(x)=h\_0(x)=\log\frac{p\_1}{1-p\_1}$$ ，其中 ![p\_1](https://www.zhihu.com/equation?tex=p_1) 是训练样本中y=1的比例，利用先验信息来初始化学习器 * $$\text{For}\ m=1,2\dots,M$$ ： * 计算 $$g\_i=\hat{y\_i}-y\_i$$ ，并使用训练集 $${(x\_i,-g\_i)}^n\_{i=1}$$ 训练一棵回归树 $$t\_m(x)$$，其中 $$\hat{y\_i}=\frac{1}{1+e^{-F\_{m-1}(x)}}$$ * 通过最小化损失函数找树的最优权重： $$\rho\_m=\mathop{\arg\min}\limits\_p\sum\limits\_iloss(x\_i,y\_i|F\_{m-1}(x)+\rho t\_m(x))$$ * 考虑shrinkage，可得这一轮迭代之后的学习器 $$F\_m(x)=F\_{m-1}(x)+\alpha\rho\_m t\_m(x)$$ , $$\alpha$$ 为学习率 * 得到最终学习器： $$F\_m(x)$$ ### 多分类 模仿上面两类分类的损失函数，我们能够将 $$K$$ 类分类的损失函数定义为 $$-\sum\limits\_{k=1}^Ky\_k\log p\_k(x)$$ 其中， $$p\_k(x)=P(y\_k=1|x\_k)$$ ，且将 $$p\_k(x)$$ 与 $$F\_k(x)$$ 关系定义为 $$F\_k(x)=\log p\_k(x)-\frac{1}{K}\sum\limits\_{l=1}^K\log p\_l(x)$$ 或者，换一种表达方式 $$p\_k(x)=\frac{e^{F\_k(x)}}{\sum\_{i=1}^Ke^{F\_i(x)}}$$ 即，对于多分类问题，则需要考虑以下softmax模型： $$P(y=1|x)=\frac{e^{F\_1(x)}}{\sum\_{i=1}^ke^{F\_i(x)}}$$ $$P(y=2|x)=\frac{e^{F\_1(x)}}{\sum\_{i=2}^ke^{F\_i(x)}}$$ ... ... 其中 $$F\_1\dots F\_k$$ 是 $$k$$ 个不同的tree ensemble。每一轮的训练实际上是训练了 $$k$$ 棵树去拟合softmax的每一个分支模型的负梯度。可见，这k棵树同样是拟合了样本的真实标签与预测概率之差，与二分类的过程非常类似。 ## 回归问题 已知一个训练数据集 $$T = {(x\_1,y\_1),(x\_2,y\_2),\dots,(x\_N,y\_N)},\ x\_i\in \mathcal{X}\subseteq R^n$$ ， $$\mathcal{X}$$ 为输入空间， $$y\_i\in\mathcal{Y}\subseteq R$$ ， $$\mathcal{Y}$$ 为输出空间。如果将输入空间 $$\mathcal{X}$$ 划分为 $$J$$ 个互不相交的区域 $$R\_1,R\_2,\dots,R\_J$$ ，并且在每个区域上确定输出的常量 $$c\_j$$ ，那么树可表示为 $$T(x;\Theta)=\sum\limits\_{j=1}^Jc\_jI(x\in R\_j)$$ 其中，参数 $$\Theta={(R\_1,c\_1),(R\_2,c\_2),\dots,(R\_J,c\_J)}$$ 表示树的区域划分和各区域上的常数。 $$J$$ 是回归树的复杂度即叶结点个数。 回归问题提升树使用以下前向分布算法： * $$f\_0(x)=0$$ * $$f\_m(x)=f\_{m-1}(x)+T(x;\Theta\_m),\ \ m=1,2,\dots,M$$ * $$f\_M(x)=\sum\limits\_{m=1}^MT(x;\Theta\_m)$$ 在前向分步算法的第 $$m$$ 步，给定当前模型 $$f\_{m-1}(x)$$ ，需求解 $$\hat{\Theta}*m=\arg\min\limits*{\Theta\_m}\sum\limits\_{i=1}^NL(y\_i,f\_{m-1}(x\_i)+T(x\_i;\Theta\_m))$$ 得到 $$\hat{\Theta}\_m$$ ，即第 $$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)]$$ 这里， $$r=y-f\_{m-1}(x)$$ 即当前模型拟合数据的残差。所以，对回归问题的提升树算法来说，只需简单地拟合当前模型的残差。 #### 回归问题的提升树算法 输入：训练数据集 $$T = {(x\_1,y\_1),(x\_2,y\_2),\dots,(x\_N,y\_N)},x\_i\in\mathcal{X}\subseteq R^n,y\_i\in\mathcal{Y}\subseteq R$$ 输出：提升树 $$f\_M(x)$$ （1）初始化 $$f\_0(x)=0$$ （2）对 $$m = 1,2,\dots,M$$ * （a）按 $$r\_{mi}=y\_i-f\_{m-1}(x\_i)$$计算残差 * （b）拟合残差 $$r\_{mi}$$ 学习一个回归树，得到 $$T(x;\Theta\_m)$$ * （c）更新 $$f\_m(x)=f\_{m-1}(x)+T(x;\Theta\_m)$$ （3）得到回归提升树： $$f\_M(x)=\sum\limits\_{m=1}^MT(x;\Theta\_m)$$ #### 举例如下 | $$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 | 对于 $$m = 1$$ ： 求 $$f\_1(x)$$ 即回归树 $$T\_1(x)$$ ，首先通过以下优化问题： $$\min\limits\_s\[\min\limits\_{c\_1}\sum\limits\_{x\_i\in R\_1}(y\_i-c\_1)^2+\min\limits\_{c\_2}\sum\limits\_{x\_i\in R\_2}(y\_i-c\_2)^2]$$ 求解训练数据的切分点 $$s$$ ： $$R\_1={x|x\leq s}$$ $$R\_2={x|x> s}$$ 容易求得在 $$R\_1,R\_2$$ 内部使平方损失误差达到最小值的 $$c\_1,c\_2$$ 为 $$c\_1=\frac{1}{N\_1}\sum\limits\_{x\_i\in R\_1}y\_i$$ $$c\_2 = \frac{1}{N\_2}\sum\limits\_{x\_i\in R\_2}y\_i$$ 这里 $$N\_1,N\_2$$ 是 $$R\_1,R\_2$$ 的样本点数 求训练数据的切分点。根据所给数据，考虑如下切分点：1.5, 2.5, 3.5, 4.5, 6.5, 7.5, 8.5, 9.5 对各切分点，求出相应的 $$R\_1,R\_2,c\_1,c\_2$$ 及 $$m(s)=\min\limits\_{c\_1}\sum\limits\_{x\_i\in R\_1}(y\_i-c\_1)^2+\min\limits\_{c\_2}\sum\limits\_{x\_i\in R\_2}(y\_i-c\_2)^2$$ 例如，当 $$s= 1.5$$ 时， $$R\_1={1}$$ ， $$R\_2={2,3,\dots,10}$$ ， $$c\_1=5.56$$ ， $$c\_2=7.50$$ ， $$m(s)=\min\limits\_{c\_1}\sum\limits\_{x\_i\in R\_1}(y\_i-c\_1)^2+\min\limits\_{c\_2}\sum\limits\_{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,\dots,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,\ \ x<6.5\ 8.91,\ \ x\geq6.5\end{cases}$$ $$f\_1(x) = T\_1(x)$$ 用 $$f\_1(x)$$ 拟合训练数据的残差 $$r\_{2i}=y\_i-f\_1(x),\ \ i=1,2,\dots,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\_1(x))=\sum\limits\_{i=1}^{10}(y\_i-f\_1(x\_i))^2=1.93$$ 对于 $$m = 2$$ ： 求 $$T\_2(x)$$ ，方法与求 $$T\_1(x)$$ 一样，只是拟合的数据为上一步的残差。可以得到 $$T\_1(x)=\begin{cases}-0.52,\ \ x<3.5\ 0.22,\ \ \ \ \ x\geq3.5\end{cases}$$ $$f\_2(x) = f\_1(x)+T\_2(x)=\begin{cases}-0.52+6.24=5.72,\ \ x<3.5\ 6.24+0.22=6.46,\ \ \ \ \ 3.5\leq x<6.5\ 8.91+0.22=9.13,\ \ \ \ \ \ x\geq6.5\end{cases}$$ 用 $$f\_2(x)$$ 拟合训练数据的平方损失误差是： $$L(y,f\_2(x))=\sum\limits\_{i=1}^{10}(y\_i-f\_2(x\_i))^2=0.79$$ 对于 $$m = 3,4,\dots,M$$： 继续按上述方法计算，直至求得拟合训练数据的平方误差到可接受范围。 ## 梯度提升 提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，梯度提升算法利用最速下降法的近似方法，其核心是利用损失函数的[负梯度](https://zhuanlan.zhihu.com/p/33260455)在当前模型的值 $$-\[\frac{\partial L(y,f(x\_i))}{\partial f(x\_i)}]*{f(x)=f*{m-1}(x)}$$ 作为回归问题提升树算法中的残差的近似值，拟合一个回归树。 #### 梯度提升算法 输入：训练数据集 $$T = {(x\_1,y\_1),(x\_2,y\_2),\dots,(x\_N,y\_N)},x\_i\in \mathcal{X}\subseteq R^n,y\_i\in \mathcal{Y}\subseteq R$$ 损失函数 $$L(y,f(x))$$ 输出：回归树 $$\hat{f}(x)$$ （1）初始化： $$f\_0(x)=\arg\min\limits\_c\sum\limits\_{i=1}^NL(y\_i,c)$$ （2）对 $$m = 1,2,\dots,M$$ * （a）对 $$i=1,2,\dots,N$$ ，计算 * $$r\_{mi} = -\[\frac{\partial L(y\_i,f(x\_i))}{\partial f(x\_i)}]*{f(x)=f*{m-1(x)}}$$ * （b）对 $$r\_{mi}$$ 拟合一个回归树，得到第 $$m$$ 棵树的叶结点区域 $$R\_{mj},j=1,2,\dots,J$$ * （c）对 $$j = 1,2,\dots,J$$ ，计算 * $$c\_{mj}=\arg\min\limits\_c\sum\limits\_{x\_i\in R\_{mi}}L(y\_i,f\_{m-1}(x\_i)+c)$$ * （d）更新 $$f\_m(x)=f\_{m-1}(x)+\sum\limits\_{j=1}^Jc\_{mi}I(x\in R\_{mi})$$ （3）得到回归树： $$\hat{f}(x)=f\_M(x)=\sum\limits\_{m=1}^M\sum\limits\_{j=1}^Jc\_{mi}I(x\in R\_{mi})$$ 算法第（1）步初始化，估计使损失函数极小化的常数值，它是只有一个根节点的数。 第（2a）步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。 第（2b）步估计回归树叶结点区域，以拟合残差的近似值。 第（2c）步利用线性搜索估计叶结点区域的值，是损失函数极小化。 第（2d）步更新回归树 第（3）步得到输出的最终模型。 ## Source {% embed url="" %} {% embed url="" %}