引言

\quad \quad 在集成学习原理一文中，简单的介绍了根据个体学习器学习方式不同划分的两大类集成学习方法；在Boosting方法中介绍了其核心思想；在Adaboost算法一文中,介绍了Boosting家族的一个重要算法Adaboost，在BDT算法一文中,介绍了Boosting家族的一个重要算法提升树回顾一下

集成方法： 集成算法，是一种提高弱分类算法准确度的方法，将多个弱分类算法(也叫做基学习器)以一定的集成方式集合在一起，然后再将弱分类器的结果以一定的融合策略融合成一个结果，作为最终的结果输出。

boosting算法： 是集成学习算法的一种，核心思想是：
1）基学习器之间存在强依赖关系，每一个基分类器是在前一个基分类器的基础之上生成。具体实现方法跟基学习器有关；
2）将所有基学习器结果进行线性加权求和，作为最终结果输出；
3）是一个加法模型，故优化方法采用前向分步算法。

Adaboost算法：是Boosting家族的一个算法，核心思想：
1）基学习器采用单层决策树；
2）基学习器之间存在强依赖关系，每一个基学习器是在前一个基学习器的基础之上生成，具体实现方式是：提高被弱分类器错分样本的权值，降低正分样本的权值，作为下一轮基本分类器的训练样本。
3）将所有基学习器结果进行线性加权求和，作为最终结果输出；
4）是一个加法模型，故优化方法采用前向分步算法。

提升树算法： boosting+决策树，核心思想是：

1）基学习器采用决策树；
2）基学习器之间存在强依赖关系，每一个基学习器是在前一个基学习器的基础之上生成，具体实现方式是：每一棵树拟合的是样本在前一棵树的残差（损失函数是均方误差损失函数）；
3）将所有基学习器结果进行线性加权求和，作为最终结果输出；
4）是一个加法模型，故优化方法采用前向分步算法。

接下来，看一看Boosting家族中另一个更加常用的的算法GBDT。

1、概述

\quad \quad GBDT(Gradient Boosting Decision Tree)即梯度提升树，属于Boosting算法，它是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。GBDT算法无论处理回归问题还是分类问题使用的决策树都是CART回归树，原因是GBDT每次迭代要拟合的是梯度值，是一个连续值，所以要用回归树。

与Adboost的区别

\quad \quad 它和Adaboost有很大的不同。Adaboost 是利用前一轮弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去，简单的说是Boosting框架+任意基学习器算法+指数损失函数。GBDT也是迭代，也使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同，简单的说梯度提升树+CART回归树模型+任意损失函数。

2、CART回归树

\quad \quad 假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y n ) } D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\} D={ (x1​,y1​),(x2​,y2​),...,(xN​,yn​)}
假定已将输入空间划分为M个单元$R_1,R_2,...,R_M$，并且在每个单元$R_M$上有一个固定的输出值$c_m$,则

回归模型：
$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$
预测误差：平方误差
$$\sum _{x_i\in R_m}(y_i-f(x_i){)}^2$$

如何选择每一个单元上的最优输出值$c_m$？

\quad \quad 用平方误差最小的准则求解每个单元上的最优输出值得单元$R_M$上的$c_m$的最优值$\widehat{c_m}$是$R_M$上的所有输入实例$x_i$对应的输出$y_i$的均值，即
$$\widehat{c_m}=ave(y_i|x_i\in R_m)$$

如何对输入空间进行划分？

\quad \quad 采用启发式即二元切分的方法，假设选择第j个变量$x^{(j)}$和它的取值s，作为切分变量和切分点，那么就会得到两个区域：
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s }   和   R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}\leq s\} \ 和\ R_2(j,s)=\{x|x^{(j)}> s\} R1​(j,s)={ x∣x(j)≤s} 和 R2​(j,s)={ x∣x(j)>s}
当j和s固定时，我们要找到两个区域的代表值c1，c2使各自区间上的平方差最小：
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$
前面已经知道c1，c2为区间上的平均：
$$\widehat{c_1}=ave(y_i|x_i\in R_1(j,s))和\widehat{c_2}=ave(y_i|x_i\in R_2(j,s))$$

那么对固定的 j 只需要找到最优的s，然后通过遍历所有的变量，我们可以找到最优的j，这样我们就可以得到最优对（j，s），并得到两个区域。对每个区域重复上述过程，直到满足条件为止。
\quad \quad 这样的回归树通常称为最小二乘回归树。算法具体流程如下：

算法5.5 （最小二乘回归树生成算法）
输入：训练数据集D
输出：回归树$f(x)$
\quad \quad 在训练数据集所在的输入空间中，递归地将每一个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
（1）选择最优切分变量 j 和切分点 s，求解
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$
遍历变量j，对固定的切分变量j扫描切分点s,选择使上式达到最小值的对(j,s)
（2）用选定的对 (j,s) 划分区域，并决定相应的输出值 c：
R 1 ( j , s ) = { x ∣ x ( j ) ≤ s }   ，   R 2 ( j , s ) = { x ∣ x ( j ) > s } c m ^ = 1 N m ∑ x i ∈ R m ( j , s ) y i   x ∈ R m , m = 1 , 2 R_1(j,s)=\{x|x^{(j)}\leq s\} \ ，\ R_2(j,s)=\{x|x^{(j)}> s\}\\ \hat{c_m}=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i\,x\in R_m,m=1,2 R1​(j,s)={ x∣x(j)≤s} ， R2​(j,s)={ x∣x(j)>s}cm​^​=Nm​1​xi​∈Rm​(j,s)∑​yi​x∈Rm​,m=1,2
（3）继续对两个子区域调用步骤（1）（2），直至满足停止条件。
（4）将输入空间划分为M个区域$R_1,R_2,...,R_M$,生成决策树：
$$f(x)=\sum _{m=1}^M\widehat{c_m}I(x\in R_m)$$

CART算法详情

3、GBDT算法思想:负梯度拟合

\quad \quad 在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是$f_{t-1}(x)$, 损失函数是$L(y,f_{t-1}(x))$ , 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器$h_t(x)$ ，让本轮的损失 $$L(y_t,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$$ 达到最小。也就是说，本轮迭代需找到一个CART回归树，使本轮损失变得更小。由于GBDT选择了平方损失，则损失函数可化简为:
$$L(y,f_{t-1}(x)+h_t(x))=(y-f_{t-1}(x)-h_t(x){)}^2=(r-h_t(x){)}^2$$
其中$$r=y-f_{t-1}(x)$$是当前模型拟合数据的残差。而GBDT算法每轮迭代生成的CART回归树就是要拟合这个残差（这样才能前后抵消，使得损失函数达到最小）。

\quad \quad 上面就是GBDT的基本思路，但是没有解决损失函数拟合方法的问题。当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。

\quad \quad 第 t 轮的第 i 个样本的损失函数的负梯度表示为

$$r_{ti}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}{]}_{f(x)=f_{t-1}(x)}$$

【此时不同的损失函数将会得到不同的负梯度，如果选择平方损失，则
对于一般损失函数（梯度下降），拟合的就是残差的近似值。】
　　利用$(x_i,r_{ti}),i=1,2,\cdots ,m$ ,我们可以拟合一棵CART回归树，得到了第 t 棵回归树，其对应的叶结点区域 $R_{tj},j=1,2,\cdots ,J$。其中 J 为叶子结点的个数。

针对每一个叶子结点里的样本，我们求出使损失函数最小，也就是拟合叶子结点最好的输出值 $c_{tj}$
\mathop{ }\limits_{ }^{ } ​
$$c_{tj}=\underset{c}{\mathrm{argmin}}\sum _{x_i\in R_{tj}}L(y_i,f_{t-1}(x_i)+c)$$
这样我们就得到了本轮的决策树拟合函数如下：

$$h_t(x)=\sum _{j=1}^J{c}_{tj}I(x\in R_{tj})$$
从而本轮最终得到的强学习器的表达式如下：

$$f_t(x)=f_{t-1}(x)+\sum _{j=1}^J{c}_{tj}I(x\in R_{tj})$$
　　通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

4、GBDT 算法

• 回归问题

1. 用回归树去拟合残差，其实就是用回归树去拟合目标方程关于$f(x)$的梯度。
2. 回归的目标函数并不一定会用square loss。square loss的优点是便于理解和实现，缺点在于对于异常值它的鲁棒性较差，一个异常值造成的损失由于二次幂而被过分放大，会影响到最后得到模型在测试集上的表现。可以算则Absolute loss或者Huber loss代替。

• 分类问题

1. 此时的目标函数常用log loss，如KL-散度或者交叉熵。
2. 除了损失函数的区别外，分类问题和回归问题的区别还在于当多分类问题时，每轮可能会训练多个分类器。
   由于决策树是非线性的，并且随着深度的加深，非线性越来越强，所以基于决策树的GBDT也是非线性的。

\quad \quad GBDT的核心思想：利用损失函数的负梯度在当前回归树的值作为回归问题提升树算法中的残差的近似值去拟合下一个回归树。GBDT 每轮迭代的时候，都去拟合损失函数在当前模型下的负梯度。

\quad \quad 也就是说GBDT（梯度提升决策树 ）： 梯度 + 提升树。

1）基学习器采用回归树（就算解决的是分类任务，也是使用回归树，不是分类树）；
2）基学习器之间存在强依赖关系，每一个基学习器是在前一个基学习器的基础之上生成，具体实现方式是：每一棵树拟合的是损失函数在前一棵树上的负梯度（损失函数是一般损失函数）；
3）将所有基学习器结果进行线性加权求和，作为最终结果输出；
4）是一个加法模型，故优化方法采用前向分步算法。

4.1 GBDT回归算法

算法3.1 梯度提升算法
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\} T={ (x1​,y1​),(x2​,y2​),…,(xN​,yN​)}； 损失函数$L\left(y,f\left(x\right)\right)$ ，最大迭代次数即基回归树的总个数。
输出：强学习器$f(x)$
（1）初始化弱学习器：
$$f_0\left(x\right)=\underset{c}{\mathrm{argmin}}\sum _{i=1}^{N}L\left(y_i,c\right)$$
（2）对$m=1,2,\dots ,M$，其中$M$ 为基回归树的总个数。
（a）对样本$i=1,2,\dots ,N$，计算负梯度即残差
$$r_{mi}=-{\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]}_{f\left(x\right)=f_{m-1}\left(x\right)}$$
（b)利用$(x_i,r_{mi}),i=1,2,\cdots ,m$ ，拟合一棵CART回归树，得到第m棵回归树，其对应的叶结点区域 $R_{mj},j=1,2,\cdots ,J$。其中 J 为叶子结点的个数。
（c）对叶子区域$j=1,2,\dots ,J$，计算最佳拟合值
$$c_{mj}=\underset{c}{\mathrm{argmin}}\sum _{x_i\in R_{mj}}L\left(y_i,f_{m-1}\left(x_i\right)+c\right)$$
（d）更新强学习器$$f_m\left(x\right)=f_{m-1}\left(x\right)+\sum _{j=1}^J{c}_{mj}I\left(x\in R_{mj}\right)$$
（3）得到回归梯度提升决策树即强学习器
$$\hat{f}\left(x\right)=f_M\left(x\right)=\sum _{m=1}^M\sum _{j=1}^J{c}_{mj}I\left(x\in R_{mj}\right)$$

\quad \quad 回归树的分裂结点对于平方损失函数，拟合的就是残差；对于一般损失函数（梯度下降），拟合的就是残差的近似值，分裂结点划分时枚举所有特征的值，选取划分点。

4.2 GBDT分类算法

\quad \quad GBDT的分类算法从思想上和GBDT的回归算法没有本质区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。
　　为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

4.2.1 二元GBDT分类算法

\quad \quad 对于二元GBDT，如果用类似于对数似然函数作为损失函数，则损失函数为：
$$L(y,f(x))=log(1+exp(-yf(x)))$$
其中 y ∈ { − 1 , + 1 } y∈\{−1,+1\} y∈{ −1,+1}此时的负梯度误差为
$$r_{ti}=-[\frac{\partial L(y,f(xi)))}{\partial f(xi)}{]}_{f(x)=f_{t-1}(x)}=\frac{y_i}{1+exp(y_{i}f(x_i))}$$
\quad \quad 对于每轮生成的决策树，各个叶子节点的最佳负梯度拟合值为
$$c_{tj}=\underset{c}{\mathrm{argmin}}\sum _{x_i\in R_{tj}}log(1+exp(-y_i(f_{t-1}(x_i)+c)))$$
\quad \quad 由于上式比较难优化，我们一般使用近似值代替
$$c_{tj}=\frac{{\sum }_{x_i\in R_{tj}}{r}_{ti}}{{\sum }_{x_i\in R_{tj}}|r_{ti}|(1-|r_{ti}|)}$$
\quad \quad 除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。

4.2.2 多元GBDT分类算法

\quad \quad 假设类别数为K，则对数似然损失函数为：
$$L(y,f(x))=-\sum _{k=1}^K{y}_{k}log{p}_k(x)$$
其中如果样本输出类别为k，则$y_k=1$。第k类的概率$p_k(x)$的表达式为softmax函数：
$$p_k(x)=\frac{exp(f_k(x))}{{\sum }_{l=1}^{K}exp(f_l(x))}$$
\quad \quad 第t轮的第i个样本对应类别l的负梯度误差为
$$r_{til}=-[\frac{\partial L(y_i,f(x_i)))}{\partial f(x_i)}{]}_{f_k(x)=f_{l,t-1(x)}}=y_{il}-p_{l,t-1}(x_i)$$
\quad \quad 观察上式可以看出，其实这里的负梯度误差就是样本i对应类别l的真实概率和t−1轮预测概率的差值。

\quad \quad 对于生成的决策树，各个叶子节点的最佳负梯度拟合值为
$$c_{tjl}=\underset{c}{\mathrm{argmin}}\sum _{i=0}^m\sum _{k=1}^{K}L(y_k,f_{t-1,l}(x)+\sum _{j=0}^J{c}_{jl}I(x_i\in R_{tjl})$$
\quad \quad 由于上式比较难优化，我们一般使用近似值代替
$$c_{tjl}=\frac{K-1}{K}\frac{{\sum }_{x_i\in R_{tjl}}{r}_{til}}{{\sum }_{x_i\in R_{tjl}}|r_{til}|(1-|r_{til}|)}$$
\quad \quad 除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。

5、 GBDT的正则化

\quad \quad 和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式:

• 第一种是增加学习率即步长(learning rate)：
  $$f_k(x)=f_{k-1}(x)+\alpha h_k(x)$$
  $\alpha$的取值范围为$0<\alpha \le 1$。对于同样的训练集学习效果，较小的$\alpha$意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
• 第二种是通过子采样比例（subsample），取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
• 第三种是对于弱学习器即CART回归树进行正则化剪枝。

6、小结

GBDT主要的优点有：

1. 可以灵活处理各种类型的数据，包括连续值和离散值。

2. 可以做回归，也可以做分类。

3. 相对SVM来说，在相对少的调参时间情况下，预测的准确率也可以比较高。

4. 使用一些健壮的损失函数，对异常值的鲁棒性非常强。 比如 Huber损失函数和Quantile损失函数。

GBDT的主要缺点有：

由于弱学习器之间存在依赖关系，难以并行训练数据。

参考资料：
1、https://www.cnblogs.com/pinard/p/6140514.html
2、https://blog.csdn.net/zgcr654321/article/details/88414369
3、https://www.cnblogs.com/pinard/p/6143927.html