共计 3606 个字符，预计需要花费 10 分钟才能阅读完成。
GBDT（Gradient Boosting Decision Tree）是被工业界宽泛应用的机器学习算法之一，它既能够解决回归问题，又能够利用在分类场景中，该算法由斯坦福统计学传授 Jerome H. Friedman 在 1999 年发表。本文中，咱们次要学习 GBDT 的回归局部。
在学习 GBDT 之前，你须要对 CART、AdaBoost 决策树有所理解，和 AdaBoost 相似，GBDT 也是一种 Boosting 类型的决策树，即在算法产生的泛滥树中，前一棵树的谬误决定了后一棵树的生成。
咱们先从最为简略的例子开始，一起来学习 GBDT 是如何结构的，而后联合理论知识，对算法的每个细节进行分析，力求由浅入深的把握该算法。
咱们的极简数据集由以下 3 条数据形成，应用它们来介绍 GBDT 的原理是再好不过了，假如咱们用这些数据来结构一个 GBDT 模型，该模型的性能是：通过身高、色彩爱好、性别这 3 个特色来预测体重，很显著这是一个回归问题。
身高（米）
色彩爱好
性别
体重（kg）
1.6
Blue
Male
88
1.6
Green
Female
76
1.5
Blue
Female
56
结构 GBDT 决策树
GBDT 的第一棵树只有 1 个叶子节点，该节点为所有样本的初始预测值，且该值到所有样本间的 MSE（Mean Squared Error）是最小的。实际上，初始值就是所有样本的平均值，即 (88+76+56)/3 = 73.3，起因咱们在下文会具体介绍。
接下来，依据预测值，咱们算出每个样本的残差（Residual），如第一个样本的残差为：88 – 73.3 = 14.7，所有样本的残差如下：
身高（米）
色彩爱好
性别
体重（kg）
残差
1.6
Blue
Male
88
14.7
1.6
Green
Female
76
2.7
1.5
Blue
Female
56
-17.3
接着，咱们以残差为目标值来构建一棵决策树，结构形式同 CART 决策树，这里你可能会问到为什么要预测残差？起因咱们马上就会晓得，产生的树如下：
因为咱们只有 3 个样本，且为了保留算法的细节，这里只用了 2 个叶子节点，但理论工作中，GBDT 的叶子节点通常在 8-32 个之间。
而后咱们要解决有多个预测值的叶子节点，取它们的平均值作为该节点的输入，如下：
下面这棵树便是第 2 棵树，聪慧的你肯定发现了，第 2 棵树实际上是第 1 棵树和样本之间的误差，咱们拿第 3 个样本作为例子，第一棵树对该样本的预测值为 73.3，此时它和目标值 56 之间的误差为 -17.3，把该样本输出到第 2 棵树，因为她的身高值为 1.5，小于 1.55，她将被预测为 -17.3。
既然后一棵树的输入是前一棵树的误差，那只有把所有的树都加起来，是不是就能够对后面树的谬误做出弥补，从而达到迫近实在值的目标呢。这就是咱们为什么以残差建树的起因。
当然树之间不会间接相加，而是在求和之前，乘上一个学习率，如 0.1，这样咱们 每次都能够在正确的方向上，把误差放大一点点。Jerome Friedman 也说过这么做有助于晋升模型的泛化能力（low variance）。
整个过程有点像梯度降落，这应该也是 GBDT 中 Gradient 的来历。GBDT 的预测过程如下图所示：
按此办法更新上述 3 个样本的预测值和残差，如下：
样本
目标值
预测值
残差
1
88
73.3 + 0.1 × 8.7 = 74.17
13.83
2
76
73.3 + 0.1 × 8.7 = 74.17
1.83
3
56
73.3 + 0.1 × (-17.3) = 71.57
-15.57
比拟这两棵树的残差：
样本
树 1 的残差
树 2 的残差
1
14.7
13.83
2
2.7
1.83
3
-17.3
-15.57
可见，通过 2 棵树预测的样本比只用 1 棵树更靠近目标值。接下来，咱们再应用第 2 棵树的残差来构建第 3 棵树，用第 3 棵树的残差来构建第 4 棵树，如此循环上来，直到树的棵数满足预设条件，或总残差小于肯定阈值为止。以上，就是 GBDT 回归树的原理。
深刻 GBDT 算法细节
GBDT 从名字上给人一种不明觉厉的印象，但从上文能够看出，它的思维还是十分直观的。对于只想理解其原理的同学，至此曾经足够了，想学习更多细节的同学，能够持续往下浏览。
初始化模型
该算法次要分为两个步骤，第一步为初始化模型：
F0(x)=argminγ∑i=1nL(yi,γ)
上式中，$F$ 示意模型，$F_0$ 即模型初始状态；L 为 Loss Function，n 为训练样本的个数，$y_i$ 为样本 i 的目标值，gamma 为初始化的预测值，意为找一个 gamma，能使所有样本的 Loss 最小。
前文提过，GBDT 回归算法应用 MSE 作为其 Loss，即：
L(yi,yi^)=12(yi−yi^)2
公式中 $hat{y_i}$ 示意第 i 个样本的预测值，咱们把例子中的 3 个样本带入 $F_0$ 中，得：
F0(x)=12(88−γ)2+12(76−γ)2+12(56−γ)2
要找到一个 gamma，使上式最小，因为上式是一个抛物线，那么 $d(F_0)/dgamma=0$ 时，上式有最小值，于是：
d(F0)dγ=(γ−88)+(γ−76)+(γ−56)=0
上式化简后，你一眼就能够看出 gamma = (88+76+56)/3 = 73.3，即 初始值就是所有样本的平均值，
模型迭代
算法的第二个步骤是一个循环，伪代码如下：
for m = 1 to M:
_(A)_
_(B)_
_(C)_
_(D)_其中，m 示意树的序号，M 为树的总个数（通常该值设为 100 或更多），(A) (B) (C) (D) 代表每次循环中的 4 个子步骤，咱们先来看 (A)
(A) 计算
rim=−[∂L(yi,F(xi))∂F(xi)]F(x)=Fm−1(x)
咱们把 $F(x_i)$ 换成 $hat{y_i}$，该式子其实是对 Loss 求 $hat{y_i}$ 的偏微分，该偏微分为：
∂L(yi,yi^)∂yi^=∂12(yi−yi^)2∂yi^=−(yi−yi^)
而 $F(x)=F_{m-1}(x)$ 意为应用上一个模型来计算 $hat{y_i}$，即用 m-1 棵已生成的树来预测每一个样本，那么 $r_{im} = y_i-hat{y_i}$ 就是下面说的计算残差这一步。
(B) 应用回归决策树来拟合残差 $r_{im}$，树的叶子节点标记为 $R_{jm}$，其中 j 示意第 j 个叶子节点，m 示意第 m 棵树。该步骤的细节如果不分明能够查看 CART 回归树一文。
(C) 对每个叶子节点，计算
γjm=argminγ∑xi∈RijL(yi,Fm−1(xi)+γ)
下面式子尽管较为简单，但它和初始化步骤中的式子的目标是一样的，即在每个叶子节点中，找到一个输入值 gamma，使得整个叶子节点的 Loss 最小。
$gamma_{jm}$ 为第 m 棵树中，第 j 个叶子节点的输入，$sum_{x_i in R_{ij}}L$ 示意在第 j 个叶子节点中所有样本的 Loss，如上面的树中，右边叶子节点上有 1 个样本，而左边叶子节点内有 2 个样本，咱们心愿依据这些样本来求得对应叶子的惟一输入，而 Loss 最小化就是解决之道。
在 Loss 函数中，第 2 个参数 $F_{m-1}(x_i) + gamma$ 是模型对样本 i 的预测，再加上 $gamma$，对于只有 1 个样本的叶子节点来说，$gamma$ 就是该样本残差，而对于有多个样本的节点来说，$gamma$ 为能使 Loss 最小的那个值，上面就这两种状况别离阐明：
以下面这棵树为例，右边叶子节点只有 1 个样本，即样本 3，将它带入到公式中：
γ11=argminγL(y3,F0(x3)+γ)=argminγ(12(56−(73.3+γ))2)=argminγ(12(−17.3−γ)2)
要求左边的式子最小，和下面一样，咱们令其导数为 0：
ddγ[12(−17.3−γ)2]=17.3+γ=0
算得 $gamma_{11} = -17.3$，所以当叶子中只有 1 个样本时，该叶子的输入就是其残差。
再来看下左边这个节点，其中蕴含 2 个样本，同样把样本 1 和样本 2 带入到公式中，得：
γ21=argminγ(L(y1,F0(x1)+γ)+L(y2,F0(x2)+γ))=argminγ(12(88−(73.3+γ))2+12(76−(73.3+γ))2)=argminγ(12(14.7−γ)2+12(2.7−γ)2)
对左边求导：
ddγ[12(14.7−γ)2+12(2.7−γ)2)]=γ−14.7+γ−2.7
上式为 0 时，Loss 最小，即
γ−14.7+γ−2.7=0
于是
γ=14.7+2.72=8.7
可见，当叶子中有多个样本时，该叶子的输入值就是所有样本残差的平均值。
(D) 更新模型，下次迭代中应用 m 棵树来做预测：
Fm(x)=Fm−1(x)+ν∑j=1Jmγjm
上式中，$nu$ 示意学习率。之后，训练将从新来到 (A) 步骤，进入下一棵树构建的循环中。
总结
本文咱们一起学习了 GBDT 的回归算法，一开始，通过一个简略的例子形容了 GBDT 的原理，之后，咱们对 GBDT 的每个步骤进行了逐个分析，心愿本文能给你带来播种。
原文链接
本文为阿里云原创内容，未经容许不得转载。
