【树模型与集成学习】(task6)梯度提升树GBDT+LR

学习总结

（1）不同问题的提升树学习算法，主要区别在于使用的损失函数不同，如用平方误差损失函数的回归问题、用指数损失函数的分类问题、用一般损失函数的一般决策问题等。

（2）不管是二分类问题的提升树，还是回归问题的提升树，这里的损失函数都很方便：前者是用指数损失函数，所以可以当做是Adaboost的个例，Aadaboost的流程；而后者是当使用平方误差损失时，可以直接拟合残差。

而使用不同的损失函数，对应的凸优化问题不同，现在我们希望找到一个通用的方式，求解一般性凸优化问题——GBDT就是用来解决该问题（大体过程如上图）。

由于GBDT是利用残差训练的（用负梯度去拟合残差），在预测的过程中，我们也需要把所有树的预测值加起来，得到最终的预测结果。

（3）我们把以决策树为基础的一系列模型统称为树模型，也是 AI 比赛中最常用的模型。

• 决策树经历了三次改进，ID3、C4.5、CART，主要区别在于一个根据信息增益划分特征、一个根据信息增益率、一个根据基尼指数。
• 随机森林=决策树+Bagging集成学习
• GBDT=决策树+AdaBoost集成学习
• XGB是陈天奇2014年提出，相当于GBDT的工程改进版，在实用性和准确度上有很大提升。比如：使用泰勒二阶展开近似损失函数，支持处理缺失值、在特性粒度上并行计算等等特性。

（4）Gradient Boosting是Boosting中的一大类算法，基本思想是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加 的形式结合到现有模型中。在每 一轮迭代中，首先计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重，最终实现对模型的更新。

文章目录

• ​​学习总结​​
• ​​一、GBDT+LR简介​​
• ​​二、逻辑回归模型​​
• ​​三、GBDT模型​​

• ​​3.1 初始化GBDT​​
• ​​3.2 循环生成决策树​​

• ​​1. 计算负梯度得到残差​​
• ​​2. 使用回归树来拟合​
• ​​3. 对于每个叶子节点, 计算最佳残差拟合值​​
• ​​4. 更新模型​

• ​​四、GBDT+LR模型​​

• ​​4.1 训练阶段​​
• ​​4.2 预测阶段​​
• ​​4.3 几个关键点​​

• ​​五、用于回归时的GBDT​​

• ​​5.1 函数空间的优化问题​​
• ​​5.2 调节学习率环节过拟合​​
• ​​5.3 另一角度：转换损失函数​​

• ​​六、用于分类时的GBDT​​

• ​​6.1 GBDT拟合的对象和流程​​

• ​​（1）将次拟合减少至次拟合​​
• ​​（2）求出负梯度​​
• ​​（3）初始化​

• ​​6.2 单调约束（Monotonic Constraints）​​

• ​​七、作业​​

• ​​7.1 GBDT和梯度下降的联系​​
• ​​7.2 GBDT用于分类问题的算法流程。​​
• ​​7.3 为什么使用集成的决策树？ 为什么使用GBDT构建决策树而不是随机森林？​​
• ​​7.4 面对高维稀疏类特征的时候(比如ID类特征)， 逻辑回归一般要比GBDT这种非线性模型好， 为什么​​
• ​​7.5 实现GBDT的分类树​​
• ​​7.6 实现GBDT的回归树​​
• ​​7.7 GBDT的优缺点​​

• ​​（1）优点​​
• ​​（2）缺点​​

• ​​7.8 GBDT多分类​​

• ​​Reference​​

一、GBDT+LR简介

协同过滤和矩阵分解存在的劣势就是仅利用了用户与物品相互行为信息进行推荐， 忽视了用户自身特征， 物品自身特征以及上下文信息等，导致生成的结果往往会比较片面。

2014年由Facebook提出的GBDT+LR模型， 该模型利用GBDT自动进行特征筛选和组合， 进而生成新的离散特征向量， 再把该特征向量当做LR模型的输入， 来产生最后的预测结果， 该模型能够综合利用用户、物品和上下文等多种不同的特征， 生成较为全面的推荐结果， 在CTR点击率预估场景下使用较为广泛。

二、逻辑回归模型

逻辑回归模型非常重要， 在推荐领域里面， 相比于传统的协同过滤， 逻辑回归模型能够综合利用用户、物品、上下文等多种不同的特征生成较为“全面”的推荐结果， 关于逻辑回归的更多细节， 可以参考下面给出的链接，这里只介绍比较重要的一些细节和在推荐中的应用。

逻辑回归是在线性回归的基础上加了一个 Sigmoid 函数（非线形）映射，使得逻辑回归成为了一个优秀的分类算法， 学习逻辑回归模型， 首先应该记住一句话：逻辑回归假设数据服从伯努利分布,通过极大化似然函数的方法，运用梯度下降来求解参数，来达到将数据二分类的目的。

相比于协同过滤和矩阵分解利用用户的物品“相似度”进行推荐， 逻辑回归模型将问题看成了一个分类问题， 通过预测正样本的概率对物品进行排序。这里的正样本可以是用户“点击”了某个商品或者“观看”了某个视频， 均是推荐系统希望用户产生的“正反馈”行为， 因此逻辑回归模型将推荐问题转化成了一个点击率预估问题。而点击率预测就是一个典型的二分类， 正好适合逻辑回归进行处理， 那么逻辑回归是如何做推荐的呢？ 过程如下：

1. 将用户年龄、性别、物品属性、物品描述、当前时间、当前地点等特征转成数值型向量
2. 确定逻辑回归的优化目标，比如把点击率预测转换成二分类问题， 这样就可以得到分类问题常用的损失作为目标， 训练模型
3. 在预测的时候， 将特征向量输入模型产生预测， 得到用户“点击”物品的概率
4. 利用点击概率对候选物品排序， 得到推荐列表

推断过程可以用下图来表示：

这里的关键就是每个特征的权重参数， 我们一般是使用梯度下降的方式， 首先会先随机初始化参数， 然后将特征向量（也就是我们上面数值化出来的特征）输入到模型， 就会通过计算得到模型的预测概率， 然后通过对目标函数求导得到每个的梯度， 然后进行更新

这里的目标函数长下面这样：

求导之后的方式长这样：

这样通过若干次迭代， 就可以得到最终的了， 关于这些公式的推导，可以参考下面给出的文章链接， 下面我们分析一下逻辑回归模型的优缺点。

优点：

1. LR模型形式简单，可解释性好，从特征的权重可以看到不同的特征对最后结果的影响。
2. 训练时便于并行化，在预测时只需要对特征进行线性加权，所以性能比较好，往往适合处理海量id类特征，用id类特征有一个很重要的好处，就是防止信息损失（相对于范化的 CTR 特征），对于头部资源会有更细致的描述
3. 资源占用小,尤其是内存。在实际的工程应用中只需要存储权重比较大的特征及特征对应的权重。
4. 方便输出结果调整。逻辑回归可以很方便的得到最后的分类结果，因为输出的是每个样本的概率分数，我们可以很容易的对这些概率分数进行cutoff，也就是划分阈值(大于某个阈值的是一类，小于某个阈值的是一类)

当然， 逻辑回归模型也有一定的局限性

1. 表达能力不强， 无法进行特征交叉， 特征筛选等一系列“高级“操作（这些工作都得人工来干， 这样就需要一定的经验， 否则会走一些弯路）， 因此可能造成信息的损失
2. 准确率并不是很高。因为这毕竟是一个线性模型加了个sigmoid， 形式非常的简单(非常类似线性模型)，很难去拟合数据的真实分布
3. 处理非线性数据较麻烦。逻辑回归在不引入其他方法的情况下，只能处理线性可分的数据， 如果想处理非线性， 首先对连续特征的处理需要先进行离散化（离散化的目的是为了引入非线性），如上文所说，人工分桶的方式会引入多种问题。
4. LR 需要进行人工特征组合，这就需要开发者有非常丰富的领域经验，才能不走弯路。这样的模型迁移起来比较困难，换一个领域又需要重新进行大量的特征工程。

所以如何自动发现有效的特征、特征组合，弥补人工经验不足，缩短LR特征实验周期，是亟需解决的问题， 而GBDT模型， 正好可以自动发现特征并进行有效组合

三、GBDT模型

GBDT全称梯度提升决策树，在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一，在前几年深度学习还没有大行其道之前，gbdt在各种竞赛是大放异彩。原因大概有几个，一是效果确实挺不错。二是即可以用于分类也可以用于回归。三是可以筛选特征， 所以这个模型依然是一个非常重要的模型。

GBDT是通过采用加法模型(即基函数的线性组合），以及不断减小训练过程产生的误差来达到将数据分类或者回归的算法， 其训练过程如下：

gbdt通过多轮迭代， 每轮迭代会产生一个弱分类器， 每个分类器在上一轮分类器的残差基础上进行训练。 gbdt对弱分类器的要求一般是足够简单， 并且低方差高偏差。 因为训练的过程是通过降低偏差来不断提高最终分类器的精度。 由于上述高偏差和简单的要求，每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的（也就是加法模型）。

GBDT的伪代码

关于GBDT的详细细节，依然是可以参考下面给出的链接。这里想分析一下GBDT如何来进行二分类的，因为注意gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的， 而这里的残差指的就是当前模型的负梯度值， 这个就要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的， 而gbdt 无论用于分类还是回归一直都是使用的CART 回归树， 那么既然是回归树， 是如何进行二分类问题的呢？

GBDT 来解决二分类问题和解决回归问题的本质是一样的，都是通过不断构建决策树的方式，使预测结果一步步的接近目标值， 但是二分类问题和回归问题的损失函数是不同的， 关于GBDT在回归问题上的树的生成过程， 损失函数和迭代原理可以参考给出的链接， 回归问题中一般使用的是平方损失， 而二分类问题中， GBDT和逻辑回归一样， 使用的下面这个：

其中， 是第个样本的观测值， 取值要么是0要么是1， 而是第个样本的预测值， 取值是0-1之间的概率，由于我们知道GBDT拟合的残差是当前模型的负梯度， 那么我们就需要求出这个模型的导数， 即， 对于某个特定的样本， 求导的话就可以只考虑它本身， 去掉加和号， 那么就变成了， 其中如下：

如果对逻辑回归非常熟悉的话， 一定不会陌生吧， 这就是对几率比取了个对数， 并且在逻辑回归里面这个式子会等于， 所以才推出了的那个形式。 这里令, 即, 则上面这个式子变成了：

这时候，我们对求导， 得

这样， 我们就得到了某个训练样本在当前模型的梯度值了， 那么残差就是。

GBDT二分类的这个思想，其实和逻辑回归的思想一样，逻辑回归是用一个线性模型去拟合这个事件的对数几率， GBDT二分类也是如此， 用一系列的梯度提升树去拟合这个对数几率， 其分类模型可以表达为：

下面我们具体来看GBDT的生成过程， 构建分类GBDT的步骤有两个：

3.1 初始化GBDT

和回归问题一样， 分类 GBDT 的初始状态也只有一个叶子节点，该节点为所有样本的初始预测值，如下：

上式里面， 代表GBDT模型， 是模型的初识状态， 该式子的意思是找到一个，使所有样本的 Loss 最小，在这里及下文中，都表示节点的输出，即叶子节点， 且它是一个 形式的值(回归值)，在初始状态，。

下面看例子(该例子来自下面的第二个链接)， 假设我们有下面3条样本：

我们希望构建 GBDT 分类树，它能通过「喜欢爆米花」、「年龄」和「颜色偏好」这 3 个特征来预测某一个样本是否喜欢看电影。 我们把数据代入上面的公式中求Loss:

为了令其最小， 我们求导， 且让导数为0， 则：

于是， 就得到了初始值, 模型的初识状态

3.2 循环生成决策树

回忆一下回归树的生成步骤， 其实有4小步， 第一就是计算负梯度值得到残差， 第二步是用回归树拟合残差， 第三步是计算叶子节点的输出值， 第四步是更新模型。 下面我们一一来看：

1. 计算负梯度得到残差

此处使用棵树的模型， 计算每个样本的残差, 就是上面的, 于是例子中， 每个样本的残差：

2. 使用回归树来拟合 r i m r_{im} rim​

这里的表示样本，回归树的建立过程可以参考下面的链接文章，简单的说就是遍历每个特征， 每个特征下遍历每个取值， 计算分裂后两组数据的平方损失， 找到最小的那个划分节点。 假如我们产生的第2棵决策树如下：

3. 对于每个叶子节点 j j j, 计算最佳残差拟合值

就是在刚构建的树中， 找到每个节点的输出, 能使得该节点的loss最小。 那么我们看一下这个的求解方式， 这里非常的巧妙。 首先， 我们把损失函数写出来， 对于左边的第一个样本， 有

这个式子就是上面推导的， 因为我们要用回归树做分类， 所以这里把分类的预测概率转换成了对数几率回归的形式， 即， 这个就是模型的回归输出值。而如果求这个损失的最小值， 我们要求导， 解出令损失最小的。 但是上面这个式子求导会很麻烦， 所以这里介绍了一个技巧就是使用二阶泰勒公式来近似表示该式， 再求导， 伟大的泰勒：

这里就相当于把当做常量， 作为变量， 将二阶展开：

这时候再求导就简单了

Loss最小的时候， 上面的式子等于0， 就可以得到:

因为分子就是残差(上述已经求到了)， 分母可以通过对残差求导，得到原损失函数的二阶导：

这时候， 就可以算出该节点的输出：

这里的下面表示第棵树的第个叶子节点。 接下来是右边节点的输出， 包含样本2和样本3， 同样使用二阶泰勒公式展开：

求导， 令其结果为0，就会得到， 第1棵树的第2个叶子节点的输出：

可以看出， 对于任意叶子节点， 我们可以直接计算其输出值：

4. 更新模型 F m ( x ) F_m(x) Fm​(x)

这样， 通过多次循环迭代， 就可以得到一个比较强的学习器

下面分析一下GBDT的优缺点：

我们可以把树的生成过程理解成自动进行多维度的特征组合的过程，从根结点到叶子节点上的整个路径(多个特征值判断)，才能最终决定一棵树的预测值， 另外，对于连续型特征的处理，GBDT 可以拆分出一个临界阈值，比如大于 0.027 走左子树，小于等于 0.027（或者 default 值）走右子树，这样很好的规避了人工离散化的问题。这样就非常轻松的解决了逻辑回归那里自动发现特征并进行有效组合的问题， 这也是GBDT的优势所在。

但是GBDT也会有一些局限性， 对于海量的 id 类特征，GBDT 由于树的深度和棵树限制（防止过拟合），不能有效的存储；另外海量特征在也会存在性能瓶颈，当 GBDT 的 one hot 特征大于 10 万维时，就必须做分布式的训练才能保证不爆内存。所以 GBDT 通常配合少量的反馈 CTR 特征来表达，这样虽然具有一定的范化能力，但是同时会有信息损失，对于头部资源不能有效的表达。

所以， 我们发现其实GBDT和LR的优缺点可以进行互补。

四、GBDT+LR模型

2014年， Facebook提出了一种利用GBDT自动进行特征筛选和组合， 进而生成新的离散特征向量， 再把该特征向量当做LR模型的输入， 来产生最后的预测结果， 这就是著名的GBDT+LR模型了。GBDT+LR 使用最广泛的场景是CTR点击率预估，即预测当给用户推送的广告会不会被用户点击（二分类问题）。

有了上面的铺垫， 这个模型解释起来就比较容易了， 模型的总体结构长下面这样：

4.1 训练阶段

训练时，GBDT 建树的过程相当于自动进行的特征组合和离散化，然后从根结点到叶子节点的这条路径就可以看成是不同特征进行的特征组合，用叶子节点可以唯一的表示这条路径，并作为一个离散特征传入 LR 进行二次训练。

比如上图中， 有两棵树，x为一条输入样本，遍历两棵树后，x样本分别落到两颗树的叶子节点上，每个叶子节点对应LR一维特征，那么通过遍历树，就得到了该样本对应的所有LR特征。构造的新特征向量是取值0/1的。 比如左树有三个叶子节点，右树有两个叶子节点，最终的特征即为五维的向量。对于输入x，假设他落在左树第二个节点，编码[0,1,0]，落在右树第二个节点则编码[0,1]，所以整体的编码为[0,1,0,0,1]，这类编码作为特征，输入到线性分类模型（LR or FM）中进行分类。

4.2 预测阶段

预测时，会先走 GBDT 的每棵树，得到某个叶子节点对应的一个离散特征(即一组特征组合)，然后把该特征以 one-hot 形式传入 LR 进行线性加权预测。

4.3 几个关键点

1. 通过GBDT进行特征组合之后得到的离散向量是和训练数据的原特征一块作为逻辑回归的输入， 而不仅仅全是这种离散特征
2. 建树的时候用ensemble建树的原因就是一棵树的表达能力很弱，不足以表达多个有区分性的特征组合，多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足，迭代多少次就会生成多少棵树。
3. RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因。
4. 在CRT预估中， GBDT一般会建立两类树(非ID特征建一类， ID类特征建一类)， AD，ID类特征在CTR预估中是非常重要的特征，直接将AD，ID作为feature进行建树不可行，故考虑为每个AD，ID建GBDT树。

1. 非ID类树：不以细粒度的ID建树，此类树作为base，即便曝光少的广告、广告主，仍可以通过此类树得到有区分性的特征、特征组合
2. ID类树：以细粒度 的ID建一类树，用于发现曝光充分的ID对应有区分性的特征、特征组合

五、用于回归时的GBDT

DT－Decision Tree决策树，GB是Gradient Boosting，是一种学习策略，GBDT的含义就是用Gradient Boosting的策略训练出来的DT模型。
模型的结果是一组回归分类树组合(CART Tree Ensemble)： T1,…, Tk 。其中 Tj 学习的是之前 （j - 1） 棵树预测结果的残差。

这种思想就像准备考试前的复习，先做一遍习题册，然后把做错的题目挑出来，在做一次，然后把做错的题目挑出来在做一次，经过反复多轮训练，取得最好的成绩。

5.1 函数空间的优化问题

数据集：设数据集为，模型的损失函数为、

目标：利用多棵回归决策树来进行模型集成：设第轮时，已知前轮中对第个样本的集成输出为，则本轮的集成输出为

其中，是使得当前轮损失达到最小的决策树模型。

【练习】对于均方损失函数和绝对值损失函数，请分别求出模型的初始预测。

特别地，当时，。

记第轮的损失函数为

令上述损失最小化不同于一般的参数优化问题，我们需要优化的并不是某一组参数，而是要在所有决策树模型组成的函数空间中，找到一个使得最小。因此我们不妨这样思考：学习一个决策树模型等价于对数据集进行拟合，设，，此时的损失函数可改记为

由于只要我们获得最优的，就能拟合出第轮相应的回归树，此时一个函数空间的优化问题已经被转换为了参数空间的优化问题，即对于样本而言，最优参数为

对于可微的损失函数，由于当时的损失就是第轮预测产生的损失。

因此我们只需要在处进行一步梯度下降（若能保证合适的学习率大小）就能够获得使损失更小的，而这个值正是我们决策树需要拟合的。
以损失函数为例，记残差为

则实际损失为

【练习】给定了上一轮的预测结果和样本标签，请计算使用平方损失时需要拟合的。
【答】现在用平方损失时，求需要拟合的。
损失函数为

记残差为
则损失为：
【练习】当样本计算得到的残差时，本例中的函数在处不可导，请问当前轮应当如何处理模型输出？
【答】不可做梯度下降，直接取。

根据在零点处的梯度下降可知：

5.2 调节学习率环节过拟合

为了缓解模型的过拟合现象，我们需要引入学习率参数来控制每轮的学习速度，即获得了由拟合的第m棵树后，当前轮的输出结果为

5.3 另一角度：转换损失函数

对于上述的梯度下降过程，还可以从另一个等价的角度来观察：若设当前轮模型预测的输出值为，求解的问题即为

由于当时，损失函数的值就是上一轮预测结果的损失值，因此只需将在在的位置进行梯度下降，此时当前轮的预测值应为

从而当前轮学习器需要拟合的目标值为

上述的结果与先前的梯度下降结果完全一致，事实上这两种观点在本质上没有任何区别，只是损失函数本身进行了平移，下图展示了它们之间的联系。

GBDT的特征重要性：
在sklearn实现的GBDT中，特征重要性的计算方式与随机森林相同，即利用相对信息增益来度量单棵树上的各特征特征重要性，再通过对所有树产出的重要性得分进行简单平均来作为最终的特征重要性。

【练习】除了梯度下降法之外，还可以使用​​牛顿法​​​来逼近最值点。请叙述基于牛顿法的GBDT回归算法。
【答】 牛顿法是求的0点，用牛顿迭代法：

六、用于分类时的GBDT

CART树能够同时处理分类问题和回归问题，但是对于多棵CART进行分类任务的集成时，我们并不能将树的预测结果直接进行类别加和。

在GBDT中，我们仍然使用回归树来处理分类问题。

6.1 GBDT拟合的对象和流程

对于分类问题，我们假设得到了个得分来代表样本属于对应类别的相对可能性，那么在进行Softmax归一化后，就能够得到该样本属于这些类别的概率大小。其中，属于类别k的概率即为。此时，我们就能够使用多分类的交叉熵函数来计算模型损失，设为第个样本的类别独热编码，记，则该样本的损失为

上述的个得分可以由棵回归树通过集成学习得到，树的生长目标正是使得上述的损失最小化。记第轮中棵树对第个样本输出的得分为
，则此时。与GBDT处理回归问题的思路同理，只需要令损失函数在处梯度下降即可：

我们需要计算第二项中每一个梯度元素，即

对于第个元素有

由于在上式的第二项里，个中只有一个为，且其余为，从而得到

此时，棵回归树的学习目标为：

同时，为了减缓模型的过拟合现象，模型在第轮实际的为

（1）将 K K K次拟合减少至 K − 1 K-1 K−1次拟合

由于每一轮都需要进行棵树的拟合，因此GBDT在处理多分类时的速度较慢。
事实上，我们可以利用概率和为的性质，将次拟合减少至次拟合，这在处理类别数较少的分类问题时，特别是在处理二分类问题时，是非常有用的。具体来说，此时我们需要个得分，记为，则样本相应属于个类别的概率值可表示为

当时，仍然使用独热编码来写出损失函数：

（2）求出负梯度

类似地记，我们可以求出负梯度：

当时，不妨规定，此时损失函数可简化为

负梯度为

（3）初始化 F ( 0 ) \textbf{F}^{(0)} F(0)

最后，我们可以使用各个类别在数据中的占比情况来初始化。
具体地说，设各类别比例为（），我们希望初始模型的参数满足

对二分类（0-1分类）而言，设正负样本占比分别为和，则初始模型参数应当满足

【练习】请验证多分类负梯度的结果。
【练习】请验证二分类负梯度的结果。
【练习】设二分类数据集中正样本比例为，请计算模型的初始参数。

6.2 单调约束（Monotonic Constraints）

有时我们会对某个特征或某些特征如何影响模型的输出有先验的知识，例如每天投入在学习的有效时间上越长就越有可能在考试中取得好的成绩，即有效学习时间长度和考试分数是一种单调增的约束关系。许多GBDT的实现（sklearn中的​​Histogram-Based GBDT​​​、​​XGBoost​​​和​​LightGBM​​​）都提供了单调约束的参数选项，有关其在内部的实现原理可以参考​​本文​​。

七、作业

7.1 GBDT和梯度下降的联系

GBDT使用梯度提升（Gradient Boosting）作为训练方法，而在逻辑回归或者 神经网络的训练过程中往往采用梯度下降（Gradient Descent）作为训练方法。

两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新：
（1）只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。
（2）在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。

梯度提升：

梯度下降：

7.2 GBDT用于分类问题的算法流程。

7.3 为什么使用集成的决策树？ 为什么使用GBDT构建决策树而不是随机森林？

GBDT是boosting的， 随机森林是Bagging的，回顾task3说的基分类器的错误 = 偏差 + 方差。
Boosting通过逐步聚集基分类器分错的样本，减少集成分类器的偏差；Bagging通过分而治之的策略，通过对训练样本多次采用，综合决策多个训练出来的模型，来减少集成分类器的方差。

7.4 面对高维稀疏类特征的时候(比如ID类特征)， 逻辑回归一般要比GBDT这种非线性模型好， 为什么

逻辑回归的优点：

1. LR模型形式简单，可解释性好，从特征的权重可以看到不同的特征对最后结果的影响。
2. 训练时便于并行化，在预测时只需要对特征进行线性加权，所以性能比较好，往往适合处理海量id类特征，用id类特征有一个很重要的好处，就是防止信息损失（相对于范化的 CTR 特征），对于头部资源会有更细致的描述
3. 资源占用小,尤其是内存。在实际的工程应用中只需要存储权重比较大的特征及特征对应的权重。
4. 方便输出结果调整。逻辑回归可以很方便的得到最后的分类结果，因为输出的是每个样本的概率分数，我们可以很容易的对这些概率分数进行cutoff，也就是划分阈值(大于某个阈值的是一类，小于某个阈值的是一类)

7.5 实现GBDT的分类树

from sklearn.tree import DecisionTreeRegressor as DT
from sklearn.datasets import make_classification
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split
import numpy as np

class GBDTClassifier:

    def __init__(self, max_depth=4, n_estimator=1000, lr=0.2):
        self.max_depth = max_depth
        self.n_estimator = n_estimator
        self.lr = lr
        self.booster = []

        self.best_round = None

    def record_score(self, y_train, y_val, train_predict, val_predict, i):
        train_predict = np.exp(train_predict) / (1 + np.exp(train_predict))
        val_predict = np.exp(val_predict) / (1 + np.exp(val_predict))
        auc_val = roc_auc_score(y_val, val_predict)
        if (i+1)%10==0:
            auc_train = roc_auc_score(y_train, train_predict)
            print("第%d轮\t训练集： %.4f\t"
                "验证集： %.4f"%(i+1, auc_train, auc_val))
        return auc_val

    def fit(self, X, y):
        X_train, X_val, y_train, y_val = train_test_split(
            X, y, test_size=0.25, random_state=0)
        train_predict, val_predict = 0, 0
        # 按照二分类比例的初始化公式计算
        fit_val = np.log(y_train.mean() / (1 - y_train.mean()))
        next_fit_val = np.full(X_train.shape[0], fit_val)
        last_val_score = - np.infty
        for i in range(self.n_estimator):
            cur_booster = DT(max_depth=self.max_depth)
            cur_booster.fit(X_train, next_fit_val)
            train_predict += cur_booster.predict(X_train) * self.lr
            val_predict += cur_booster.predict(X_val) * self.lr
            next_fit_val = y_train - np.exp(
                train_predict) / (1 + np.exp(train_predict))
            self.booster.append(cur_booster)
            cur_val_score = self.record_score(
                y_train, y_val, train_predict, val_predict, i)
            if cur_val_score < last_val_score:
                self.best_round = i
                print("\n训练结束！最佳轮数为%d"%(i+1))
                break
            last_val_score = cur_val_score

    def predict(self, X):
        cur_predict = 0
        for i in range(self.best_round):
            cur_predict += self.lr * self.booster[i].predict(X)
        return np.exp(cur_predict) / (1 + np.exp(cur_predict))

if __name__ == "__main__":

    X, y = make_classification(
        n_samples=10000, n_features=50, n_informative=20, random_state=1)
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.25, random_state=0)

    model = GBDTClassifier()
    model.fit(X_train, y_train)
    prediction = model.predict(X_test)
    auc = roc_auc_score(y_test, prediction)
    print("\n测试集的AUC为 %.4f"%(auc))

得到的结果为：

第10轮  训练集： 0.9269 验证集： 0.8911
第20轮  训练集： 0.9474 验证集： 0.9129
第30轮  训练集： 0.9578 验证集： 0.9238
第40轮  训练集： 0.9645 验证集： 0.9322
第50轮  训练集： 0.9699 验证集： 0.9383
第60轮  训练集： 0.9744 验证集： 0.9443
第70轮  训练集： 0.9776 验证集： 0.9480
第80轮  训练集： 0.9801 验证集： 0.9517
第90轮  训练集： 0.9820 验证集： 0.9539
第100轮 训练集： 0.9840 验证集： 0.9568
第110轮 训练集： 0.9854 验证集： 0.9584
第120轮 训练集： 0.9868 验证集： 0.9598

训练结束！最佳轮数为121

测试集的AUC为 0.9634

7.6 实现GBDT的回归树

from sklearn.tree import DecisionTreeRegressor as DT
from sklearn.datasets import make_regression
from sklearn.metrics import mean_absolute_error
from sklearn.model_selection import train_test_split
import numpy as np

class GBDTRegressor:

    def __init__(self, max_depth=4, n_estimator=1000, lr=0.2):
        self.max_depth = max_depth
        self.n_estimator = n_estimator
        self.lr = lr
        self.booster = []

        self.best_round = None

    def record_score(self, y_train, y_val, train_predict, val_predict, i):
        mse_val = mean_absolute_error(y_val, val_predict)
        if (i+1)%10==0:
            mse_train = mean_absolute_error(y_train, train_predict)
            print("第%d轮\t训练集： %.4f\t"
                "验证集： %.4f"%(i+1, mse_train, mse_val))
        return mse_val

    def fit(self, X, y):
        # 在数据集中划分训练集和验证集
        X_train, X_val, y_train, y_val = train_test_split(
            X, y, test_size=0.25, random_state=0)
        train_predict, val_predict = 0, 0
        next_fit_val = np.full(X_train.shape[0], np.median(y_train))
        # 为early_stop做记录准备
        last_val_score = np.infty
        for i in range(self.n_estimator):
            cur_booster = DT(max_depth=self.max_depth)
            cur_booster.fit(X_train, next_fit_val)
            train_predict += cur_booster.predict(X_train) * self.lr
            val_predict += cur_booster.predict(X_val) * self.lr
            # 平方损失为((y - (F_{m-1} + w)^2)/2，若记残差为r
            # 即为((r - w)^2)/2，此时关于w在0点处的负梯度求得恰好为r
            # 因此拟合的值就是y_train - train_predict
            next_fit_val = y_train - train_predict
            self.booster.append(cur_booster)
            cur_val_score = self.record_score(
                y_train, y_val, train_predict, val_predict, i)
            if cur_val_score > last_val_score:
                self.best_round = i
                print("\n训练结束！最佳轮数为%d"%(i+1))
                break
            last_val_score = cur_val_score

    def predict(self, X):
        cur_predict = 0
        # 在最佳验证集得分的轮数停止，防止过拟合
        for i in range(self.best_round):
            cur_predict += self.lr * self.booster[i].predict(X)
        return cur_predict

if __name__ == "__main__":

    X, y = make_regression(
        n_samples=10000, n_features=50, n_informative=20, random_state=1)
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.25, random_state=0)

    model = GBDTRegressor()
    model.fit(X_train, y_train)
    prediction = model.predict(X_test)
    mse = mean_absolute_error(y_test, prediction)
    print("\n测试集的MSE为 %.4f"%(mse))

得到的结果为：

第10轮  训练集： 125.5180 验证集： 134.8806
第20轮  训练集： 89.8797  验证集： 104.4727
第30轮  训练集： 68.7123  验证集： 87.0258
第40轮  训练集： 54.8424  验证集： 75.9678
第50轮  训练集： 45.2828  验证集： 68.2107
第60轮  训练集： 38.8341  验证集： 62.9527
第70轮  训练集： 34.1962  验证集： 58.9250
第80轮  训练集： 30.8356  验证集： 56.0184
第90轮  训练集： 28.4778  验证集： 54.0267
第100轮 训练集： 26.7017  验证集： 52.5821
第110轮 训练集： 25.0525  验证集： 51.2764
第120轮 训练集： 23.8643  验证集： 50.3764
第130轮 训练集： 22.9112  验证集： 49.5915
第140轮 训练集： 22.0003  验证集： 49.0042

训练结束！最佳轮数为144

测试集的MSE为 51.1359

7.7 GBDT的优缺点

（1）优点

（1）预测阶段的计算速度快，树与树之间可并行化计算。
（2）在分布稠密的数据集上，泛化能力和表达能力都很好。
（3）采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性， 能够自动发现特征间的高阶关系，并且也不需要对数据进行特殊的预处理如归一化等。

（2）缺点

（1）GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。
（2）GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理 数值特征时明显。
（3）训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提 高训练速度。

7.8 GBDT多分类

from sklearn.tree import DecisionTreeRegressor as DT
from sklearn.datasets import make_classification
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split
import numpy as np

def one_hot(y):
    res = np.zeros((y.size, y.max()+1))
    res[np.arange(y.size), y] = 1
    return res

class GBDTMultiClassifier:

    def __init__(self, max_depth=4, n_estimator=1000, lr=0.2):
        self.max_depth = max_depth
        self.n_estimator = n_estimator
        self.lr = lr
        self.booster = []

        self.n_classes = None
        self.best_round = None

    def get_init_val(self, y):
        init_val = []
        y = np.argmax(y, axis=1)
        for c in range(self.n_classes):
            init_val.append(np.log((y==c).mean()))
        return np.full((y.shape[0], self.n_classes), init_val)

    def record_score(self, y_train, y_val, train_predict, val_predict, i):
        train_predict = np.exp(train_predict) / np.exp(
            train_predict).sum(1).reshape(-1, 1)
        val_predict = np.exp(val_predict) / np.exp(
            val_predict).sum(1).reshape(-1, 1)
        auc_val = roc_auc_score(y_val, val_predict)
        if (i+1)%10==0:
            auc_train = roc_auc_score(y_train, train_predict)
            print("第%d轮\t训练集： %.4f\t"
                "验证集： %.4f"%(i+1, auc_train, auc_val))
        return auc_val

    def fit(self, X, y):
        X_train, X_val, y_train, y_val = train_test_split(
            X, y, test_size=0.25, random_state=0)
        self.n_classes = y.shape[1]
        train_predict = np.zeros((X_train.shape[0], self.n_classes))
        val_predict = np.zeros((X_val.shape[0], self.n_classes))
        next_fit_val = self.get_init_val(y_train)
        last_val_score = - np.infty
        for i in range(self.n_estimator):
            last_train = train_predict.copy()
            self.booster.append([])
            for m in range(self.n_classes):
                cur_booster = DT(max_depth=self.max_depth)
                cur_booster.fit(X_train, next_fit_val[:, m])
                train_predict[:, m] += cur_booster.predict(X_train) * self.lr
                val_predict[:, m] += cur_booster.predict(X_val) * self.lr
                next_fit_val[:, m] = y_train[:, m] - np.exp(
                    last_train[:, m]) / np.exp(last_train).sum(1)
                self.booster[-1].append(cur_booster)
            cur_val_score = self.record_score(
                y_train, y_val, train_predict, val_predict, i)
            if cur_val_score < last_val_score:
                self.best_round = i
                print("\n训练结束！最佳轮数为%d"%(i+1))
                break
            last_val_score = cur_val_score

    def predict(self, X):
        cur_predict = np.zeros((X.shape[0], self.n_classes))
        for i in range(self.best_round):
            for m in range(self.n_classes):
                cur_predict[:, m] += self.lr * self.booster[i][m].predict(X)
        return np.exp(cur_predict) / np.exp(cur_predict).sum(1).reshape(-1, 1)


if __name__ == "__main__":

    X, y = make_classification(
        n_samples=10000, n_features=50, n_informative=20,
        n_classes=3, random_state=1)
    y = one_hot(y)
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.25, random_state=0)

    model = GBDTMultiClassifier()
    model.fit(X_train, y_train)
    prediction = model.predict(X_test)
    auc = roc_auc_score(y_test, prediction)
    print("\n测试集的AUC为 %.4f"%(auc))

Reference

• ​​datawhale notebook​​
• 《百面机器学习》
• 《统计学习方法》李航
• ​​GBDT的原理和应用​​
• 王喆 - 《深度学习推荐系统》
• ​​决策树之 GBDT 算法 - 分类部分​​
• ​​深入理解GBDT二分类算法​​
• ​​逻辑回归、优化算法和正则化的幕后细节补充​​
• ​​梯度提升树GBDT的理论学习与细节补充​​
• ​​推荐系统遇上深度学习(十)–GBDT+LR融合方案实战​​
• ​​CTR预估中GBDT与LR融合方案​​
• ​​GBDT+LR算法解析及Python实现​​
• ​​常见计算广告点击率预估算法总结​​
• ​​GBDT–分类篇​​
• ​​GBDT的python源码实现​​
• ​​通俗讲解GBDT​​
• ​​老弓的学习笔记-GBDT-b站讲解​​
• ​​大T同学笔记​​

论文

• ​​http://quinonero.net/Publications/predicting-clicks-facebook.pdf 原论文​​
• ​​Predicting Clicks: Estimating the Click-Through Rate for New Ads​​\
• ​​Greedy Fun tion Approximation : A Gradient Boosting​​