大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

文章目录

• • @[toc]
• 1. 背景
• • 1.1 Gradient Boosting
  • 1.2 提升树-boosting tree
  • • 回归问题提升树算法
• 2 Gradient Boosting Decision Tree
• • 2.1 函数空间的数值优化
  • 2.2 算法
  • Shrinkage
• 总结
• 附录
• • 参考资料
  • 相似算法：

1. 背景

决策树是一种基本的分类与回归方法。决策树模型具有分类速度快，模型容易可视化的解释，但是同时是也有容易发生过拟合，虽然有剪枝，但也是差强人意。

提升方法（boosting）在分类问题中，它通过改变训练样本的权重（增加分错样本的权重，减小分队样本的的权重），学习多个分类器，并将这些分类器线性组合，提高分类器性能。boosting数学表示为：
$$f(x)=w_0+\sum _{m=1}^M{w}_m{\varphi }_m(x)$$

其中w是权重，$\varphi$是弱分类器的集合，可以看出最终就是基函数的线性组合。

于是决策树与boosting结合产生许多算法，主要有提升树、GBDT等。本文主要是GBDT学习笔记。

1.1 Gradient Boosting

Gradient Boosting是一种Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数是评价模型性能（一般为拟合程度+正则项），认为损失函数越小，性能越好。而让损失函数持续下降，就能使得模型不断改性提升性能，其最好的方法就是使损失函数沿着梯度方向下降（讲道理梯度方向上下降最快）。

Gradient Boost是一个框架，里面可以套入很多不同的算法。

1.2 提升树-boosting tree

以决策树为基函数的提升方法称为提升树，其决策树可以是分类树OR回归树。提升树模型可以表示为决策树的加法模型。
$$f_M(x)=\sum _{m=1}^{M}T(x;{\Theta }_m)$$
其中，$T(x;{\Theta }_m)表示决策树，$${\Theta }_m$表示树的参数，M为树的个数。

回归问题提升树算法

输入：训练数据集$T={(x_1,y_1),(x_2,y_2),···,(x_N,y_N)}, x_i \in \chi = R^n, y_i \in \gamma, \ i=1,2,···,N $；$\gamma$为输出空间。

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

1. 初始化$f_0(x)=0$

2. 对于$m=1,2,...M$:

   1. 计算残差（后一棵树拟合前一颗树残差）：

      $$r_{mi}=y_i-f_{m-1}(x_i)$$

   2. 拟合残差学习一个回归树，得到$T(x;{\Theta }_m)$

   3. 更新$f_m(x)=f_{m-1}(x)+T(x;{\Theta }_m)$

3. M次迭代之后得到提升树：

   $$f_M(x)=\sum _{m=1}^{M}T(x;{\Theta }_m)$$

   ​

2 Gradient Boosting Decision Tree

提升树的学习优化过程中，损失函数平方损失和指数损失时候，每一步优化相对简单，但对于一般损失函数优化的问题，Freidman提出了Gradient Boosting算法，其利用了损失函数的负梯度在当前模型的值
$$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}{]}_{f(x)=f_{m-1}(x)}$$
作为回归问题提升树算法的残差近似值，去拟合一个回归树。

2.1 函数空间的数值优化

优化目标是使得损失函数最小，(N是样本集合大小)：
$$F^{\ast }(x)=\underset{\rho }{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y_i,\rho )$$
GBDT是一个加法模型：$f_m(x)$是每一次迭代学习的到树模型。
$$\hat{F}(x)=F_M(x)=\sum _{m=1}^M{f}_m(x)$$
对于其每一步迭代：
$$f_m(x)=-{\rho }_m{g}_m(x)$$
其中
$$\begin{gathered} g_m(x)=[\frac{\partial \varphi (F(x))}{\partial F(x)}{]}_{F(x)=F_{m-1}(x)} \\ \varphi (F(x))=E_y[L(y,F(x))|x],F_{m-1}(x)=\sum _{i=0}^{m-1}{f}_i(x) \end{gathered}$$
其实$L(y,F(x))$就是损失函数，$\varphi (F(x))$是当前x下的损失期望，$g_m(x)$是当前x下的函数梯度。最终$f_m(x)$学习的是损失函数在函数空间上的负梯度。

对于权重${\rho }_m$通过线性搜索求解（这也是后面算法改进的点）：
$${\rho }_m=\arg \underset{\rho }{\min }{E}_{y,x}L(y,F_{m-1}(x)-\rho \ast g_m(x))$$
理解：每一次迭代可以看做是采用梯度下降法对最优分类器$F^{\ast }(x)$的逐渐比较，每一次学习的模型$f_m(x)$是梯度，进过M步迭代之后，最后加出来的模型就是最优分类器的一个逼近模型，所以$f_m(x_i)$使用单步修正方向$-g_m(x_i)$：
$$-g_m(x_i)=g_m(x)=[\frac{\partial L(F(x))}{\partial F(x)}{]}_{F(x)=F_{m-1}(x)}$$
这里的梯度变量是函数，是在函数空间上求解（这也是后面XGBoost改进的点），注意以往算法梯度下降是在N维的参数空间的负梯度方向，变量是参数。这里的变量是函数，更新函数通过当前函数的负梯度方向来修正模型，是它更优，最后累加的模型近似最优函数。

2.2 算法

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋅ ⋅ ⋅ , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),···,(x_N,y_N)\} T={
(x1​,y1​),(x2​,y2​),⋅⋅⋅,(xN​,yN​)},$ x_i \in \chi = R^n$，$ y_i \in \gamma={-1,+1}, \ i=1,2,···,N $；

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

1. 初始化

   $$f_0(x)=arg\underset{c}{\min }\sum _{i=1}^{N}L(y_i,c)$$

2. 对m=1,2,…M

   1. 对i=1,2,…,N，计算

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

   2. 对$r_{mi}$拟合一颗回归树，得到第m棵树的叶结点区域$R_{mj},j=1,2,...J$，即一棵由J个叶子节点组成的树。

   3. 对$j=1,2,...J$，计算

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

      2.2,2.3这一步相当于回归树递归在遍历所有切分变量j和切分点s找到最优j,s，然后在每个节点区域求最优的c。参考回归树生成算法

   4. 更新$f_m(x)=f_{m-1}(x)+\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$

3. 得到回归树

   $$\hat{f}(x)=f_M(x)=\sum _{m=1}^M{f}_m(x)=\sum _{m=1}^M\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$$

算法1步获得使得损失函数最小的常数估计值，是一个只有根节点的树。在2.1步计算损失函数的负梯度在当前模型的值，将它作为残差估计。在2.2步估计回归树的叶结点区域，来拟合残差的近似值。在2.3步利用线性搜索估计回归树叶结点区域的值，使损失函数最小化。2.4更新回归树。第3步获得输出的最终模型。

Shrinkage

Shrinkage的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。

数学方程对比：

• 之前：$f_m(x)=f_{m-1}(x)+\sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$
• Shrinkage：$f_m(x)=f_{m-1}(x)+step\ast \sum _{j=1}^J{c}_{mj}I(x\in R_{mj})$

Shrinkage仍然以残差作为学习目标，但对于残差学习的结果，只累加一小部分，step一般取值0.001-0.01(非gradient的step)，使得各个树的残差是渐变而不是陡变的，即将大步切成了小步。Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。

总结

原始的boosting算法开始时，为每一个样本赋上一个权重值。在每一步训练中得到的模型，会使得数据点的估计有对有错，在每一步结束后，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高的权重。然后等进行了N次迭代（由用户指定），将会得到N个简单的分类器（basic learner），然后我们将它们组合起来（比如说可以对它们进行加权、或者让它们进行投票等），得到一个最终的模型。

那么GBDT算法中并未有权重的改变，哪里有boosting思想 ？

Gradient Boosting与Boosting区别在于，每一计算的是为了减少上一次的残差，下一个模型主要在残差减少的梯度方上建立模型，使得残差往梯度方向上减少。

虽然不同，但是GBDT算法会更关注那些梯度比较大的样本，和Boosting思想类似。

附录

CSDN原文：http://blog.csdn.net/shine19930820/article/details/65633436
公众号：百川NLP

参考资料

• 《统计学习方法》
• 《The Elements of Statistical Learning 》
• 《Machine Learning A Probabilistic Perspective》
• http://www.lai18.com/content/1406280.html

相似算法：

• LightGBM原理: A Highly Efficient Gradient Boosting Decision Tree
• XGBoost原理- A Scalable Tree Boosting System
• 数据挖掘十大算法 』笔记二：SVM-支持向量机
• 《Top 10 algorithms in data mining》