黑客怎么攻击网站,优秀的个人网站,海口建站软件,VPS wordpress 教程GBDT#xff08;Gradient Boosting Decision Tree#xff09;是被工业界广泛使用的机器学习算法之一#xff0c;它既可以解决回归问题#xff0c;又可以应用在分类场景中#xff0c;该算法由斯坦福统计学教授 Jerome H. Friedman 在 1999 年发表。本文中#xff0c;我们主…GBDTGradient 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 个叶子节点该节点为所有样本的初始预测值且该值到所有样本间的 MSEMean Squared Error是最小的。实际上初始值就是所有样本的平均值即 (887656)/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γ∑i1nL(yi,γ)
上式中FFF 表示模型F0F_0F0 即模型初始状态L 为 Loss Functionn 为训练样本的个数yiy_iyi 为样本 i 的目标值gamma 为初始化的预测值意为找一个 gamma能使所有样本的 Loss 最小。
前文提过GBDT 回归算法使用 MSE 作为其 Loss即
L(yi,yi)12(yi−yi)2
公式中 yi^\hat{y_i}yi^ 表示第 i 个样本的预测值我们把例子中的 3 个样本带入 F0F_0F0 中得
F0(x)12(88−γ)212(76−γ)212(56−γ)2
要找到一个 gamma使上式最小因为上式是一个抛物线那么 d(F0)/dγ0d(F_0)/d\gamma0d(F0)/dγ0 时上式有最小值于是
d(F0)dγ(γ−88)(γ−76)(γ−56)0
上式化简后你一眼就可以看出 gamma (887656)/3 73.3即初始值就是所有样本的平均值
模型迭代 算法的第二个步骤是一个循环伪代码如下
for m 1 to M: (A) (B) © (D) 其中m 表示树的序号M 为树的总个数通常该值设为 100 或更多(A) (B) © (D) 代表每次循环中的 4 个子步骤我们先来看 (A)
(A) 计算
rim−[∂L(yi,F(xi))∂F(xi)]F(x)Fm−1(x)
我们把 F(xi)F(x_i)F(xi) 换成 yi^\hat{y_i}yi^该式子其实是对 Loss 求 yi^\hat{y_i}yi^ 的偏微分该偏微分为
∂L(yi,yi)∂yi∂12(yi−yi)2∂yi−(yi−yi^)
而 F(x)Fm−1(x)F(x)F_{m-1}(x)F(x)Fm−1(x) 意为使用上一个模型来计算 yi^\hat{y_i}yi^即用 m-1 棵已生成的树来预测每一个样本那么 rimyi−yi^r_{im} y_i-\hat{y_i}rimyi−yi^ 就是上面说的计算残差这一步。
(B) 使用回归决策树来拟合残差 rimr_{im}rim树的叶子节点标记为 RjmR_{jm}Rjm其中 j 表示第 j 个叶子节点m 表示第 m 棵树。该步骤的细节如果不清楚可以查看 CART 回归树一文。
© 对每个叶子节点计算
γjmargminγ∑xi∈RijL(yi,Fm−1(xi)γ)
上面式子虽然较为复杂但它和初始化步骤中的式子的目的是一样的即在每个叶子节点中找到一个输出值 gamma使得整个叶子节点的 Loss 最小。
γjm\gamma_{jm}γjm 为第 m 棵树中第 j 个叶子节点的输出∑xi∈RijL\sum_{x_i \in R_{ij}}L∑xi∈RijL 表示在第 j 个叶子节点中所有样本的 Loss如下面的树中左边叶子节点上有 1 个样本而右边叶子节点内有 2 个样本我们希望根据这些样本来求得对应叶子的唯一输出而 Loss 最小化就是解决之道。
在 Loss 函数中第 2 个参数 Fm−1(xi)γF_{m-1}(x_i) \gammaFm−1(xi)γ 是模型对样本 i 的预测再加上 γ\gammaγ对于只有 1 个样本的叶子节点来说γ\gammaγ 就是该样本残差而对于有多个样本的节点来说γ\gammaγ 为能使 Loss 最小的那个值下面就这两种情况分别说明
以上面这棵树为例左边叶子节点只有 1 个样本即样本 3将它带入到公式中
γ11argminγL(y3,F0(x3)γ)argminγ(12(56−(73.3γ))2)argminγ(12(−17.3−γ)2)
要求右边的式子最小和上面一样我们令其导数为 0
ddγ[12(−17.3−γ)2]17.3γ0
算得 γ11−17.3\gamma_{11} -17.3γ11−17.3所以当叶子中只有 1 个样本时该叶子的输出就是其残差。
再来看下右边这个节点其中包含 2 个样本同样把样本 1 和样本 2 带入到公式中得
γ21argminγ(L(y1,F0(x1)γ)L(y2,F0(x2)γ))argminγ(12(88−(73.3γ))212(76−(73.3γ))2)argminγ(12(14.7−γ)212(2.7−γ)2)
对右边求导
ddγ[12(14.7−γ)212(2.7−γ)2)]γ−14.7γ−2.7
上式为 0 时Loss 最小即
γ−14.7γ−2.70
于是
γ14.72.728.7
可见当叶子中有多个样本时该叶子的输出值就是所有样本残差的平均值。
(D) 更新模型下次迭代中使用 m 棵树来做预测
Fm(x)Fm−1(x)ν∑j1Jmγjm
上式中ν\nuν 表示学习率。之后训练将重新来到 (A) 步骤进入下一棵树构建的循环中。
总结 本文我们一起学习了 GBDT 的回归算法一开始通过一个简单的例子描述了 GBDT 的原理之后我们对 GBDT 的每个步骤进行了逐一剖析希望本文能给你带来收获。
原文链接 本文为阿里云原创内容未经允许不得转载。
