从零解读Xgboost(原理+代码)

会员服务 ·

从零解读Xgboost(原理+代码)

2020 年 11 月 13 日 AINLP

公式手敲的非常辛苦！！求三连！！

大家星标一下公众号哈，方便接受推送。最近改了一下排版，我要变成正规军了！

文中涉及到的公式和注解都可以左右滑动查看全部，涉及到的代码去这里下载：

https://github.com/DA-southampton/NLP_ability

全文目录如下：

0.提升树
1. xgboost原理解读

1.0 学习路径：
1.1 目标函数
1.2 泰勒公式对目标函数近似展开
1.3 树的参数化
1.4寻找树的形状-特征分裂

2.工程实现细节

2.0 特征分裂并行寻找
2.1 缓存访问
2.2 xgboost特征的重要性是如何评估的

3. 代码汇总

3.0 xgboost 如何筛选特征重要程度
3.1 xgboost完整训练代码

xgboost 代码调参
xgboost常规面试题
参考链接

0.提升树

首先要明确一点，xgboost 是基于提升树的。

什么是提升树，简单说，就是一个模型表现不好，我继续按照原来模型表现不好的那部分训练第二个模型，依次类推。

来几个形象的比喻就是：

做题的时候，第一个人做一遍得到一个分数，第二个人去做第一个人做错的题目，第三个人去做第二个人做错的题目，以此类推，不停的去拟合从而可以使整张试卷分数可以得到100分（极端情况）。

把这个比喻替换到模型来说，就是真实值为100，第一个模型预测为90，差10分，第二个模型以10为目标值去训练并预测，预测值为7，差三分，第三个模型以3为目标值去训练并预测，以此类推。

1. xgboost原理解读

1.0 学习路径：

我们xgboost的学习路径可以按照下面四个步骤来：

构造原始目标函数问题：

xgboost目标函数包含损失函数和基于树的复杂度的正则项；

泰勒展开问题：

原始目标函数直接优化比较难，如何使用泰勒二阶展开进行近似；

树参数化问题：

假设弱学习器为树模型，如何将树参数化，并入到目标函数中；这一步的核心就是要明白我们模型优化的核心就是优化参数，没有参数怎么训练样本，怎么对新样本进行预测呢？

如何优化化简之后的目标函数问题，优化泰勒展开并模型参数化之后的的目标函数，主要包含两个部分：

如何求得叶子节点权重
如何进行树模型特征分割

1.1 目标函数

1.1.0 原始目标函数

目标函数，可以分为两个部分，一部分是损失函数，一部分是正则（用于控制模型的复杂度）。

xgboost属于一种前向迭代的模型，会训练多棵树。

对于第t颗树，第i个样本的，模型的预测值是这样的：

进一步，我们可以得到我们的原始目标函数，如下：

从这个目标函数我们需要掌握的细节是，前后部分是两个维度的问题

两个累加的变量是不同的:

一个是i，i这边代表的是样本数量，也就是对每个样本我们都会做一个损失的计算，这个损失是第t个树的预测值和真实值之间的差值计算（具体如何度量损失视情况而定）。
另一个是累加变量是j，代表的是树的数量，也就是我们每个树的复杂度进行累加。

需要注意的是我们这里具体的损失函数是没有给出定义的，所以它可以是树模型，也可以是线性模型。

1.1.1 简单化简损失函数

正如上面所说，Xgboost是前向迭代，我们的重点在于第t个树，所以涉及到前t-1个树变量或者说参数我们是可以看做常数的。

所以我们的损失函数进一步可以化为如下，其中一个变化是我们对正则项进行了拆分，变成可前t-1项，和第t项：

基于此，在不改变目标函数精读的情况下，我们已经做了最大的简化，最核心的点就是我们认为前t-1个树已经训练好了，所以涉及到的参数和变量我们当成了常数。

接下来，我们使用泰勒级数，对目标函数近似展开.

1.2 泰勒公式对目标函数近似展开

使用泰勒公式进行近似展开的核心目标是就是对目标函数进行化简，将常数项抽离出来。

基本泰勒公式展开如下：

损失函数展开公式细节推导如下：

所以原有公式进行泰勒公式二阶展开，结果为:

进而我们可以得到目标函数展开公式为如下：

还是那句话，我们可以使用任意一个损失函数，这里没有定式。

上述中树的表达我们都是使用函数f(x)来表示，本质上模型的优化求解是在求参数，所以我们需要对树模型参数化才可以进行进一步的优化

1.3 树的参数化

树的参数化有两个，一个是对树模型参数化，一个是对树的复杂度参数化。

1.3.0 树模型参数化-如何定义一个树

主要是定义两个部分：

每棵树每个叶子节点的值(或者说每个叶子节点的权重) w：这是一个向量，因为每个树有很多叶子节点
样本到叶子节节点的映射关系 q：(大白话就是告诉每个样本落在当前这个树的哪一个叶子节点上)
叶子节点样本归属集合 I：就是告诉每个叶子节点包含哪些样本

1.3.1 树复杂度的参数化-如何定义树的复杂度

定义树的复杂度主要是从两个部分出发：

每个树的叶子节点的个数（叶子节点个数越少模型越简单）
叶子节点的权重值 w（值越小模型越简单）

对于第二点，我们可以想一下L正则不就是想稀疏化权重，从而使模型变得简单吗，其实本质是一样的。

我们树的复杂度如下：

范数

进而我们可以对树进行了参数化，带入到目标函数我们可以得到如下：

随后我们做如下定义：

叶子节点 j 所包含的样本的一阶导数累加之和为：

叶子节点 j 所包含的样本的二阶导数累加之和为：

进而我们可以进一步化简为：

针对这个目标函数，我们对Xgboost优有面临两个问题：

第一就是如何求得：这一步其实很简单，直接使用目标函数对求导就可以。

还有一个就是如何做到特征的分裂，接下来我们详细聊一下如何去做

1.4寻找树的形状-特征分裂

首先明确一点，我们增益使用的是基于当前特征分裂点前后，目标函数的差值。

我们当然是希望，使用这个分裂点，目标函数降低的越多越好。

1.4.0 贪心算法

本质上是做两次循环，第一个是是针对每个特征的每个分割点做一次循环，计算收益，从而选择此特征的最佳分割点。分裂收益使用的是分裂之后的目标函数的变化差值。

第二个循环是对样本所有特征的循环，从中挑选出收益最大的特征。

简单说就是首先找到基于每个特征找到收益最大的分割点，然后基于所有特征找到收益最大的特征。

然后在这所有的循环中，挑出增益最大的那个分割点

1.4.1 近似算法-分位数候选点

对于每个特征，不去暴力搜索每个值，而是使用分位点

根据样本数量选择三分位点或者四分位点等等；
或者根据二阶导数（也就是梯度）作为权重进行划分

也就是说原来是某个特征的所有取值是候选点，现在是某个特征的分位点作为候选点。

2.工程实现细节

2.0 特征分裂并行寻找

寻找特征分隔点需要对特征值进行排序，这个很耗时间。我们可以在训练之前先按照特征对样本数据进行排序，并分别保存在不同的块结构中。每个块都有一个按照某个特征排好序的特征加对应的一阶二阶导数。

对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益

2.1 缓存访问

特征是排好序，但是通过索引获取一阶二阶导数值是不连续的，造成cpu缓存命中率低；xgboost解决办法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就连续了；

同时通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。

2.2 xgboost特征的重要性是如何评估的

weight ：该特征在所有树中被用作分割样本的特征的总次数。
gain ：该特征在其出现过的所有树中产生的平均增益（我自己的理解就是目标函数减少值总和的平均值，这里也可以使用增益之和）。
cover ：该特征在其出现过的所有树中的平均覆盖范围。

这里有一个细节需要注意，就是节点分割的时候，之前用过的特征在当前节点也是可以使用的，所以weight才是有意义的。

3. 代码汇总

3.0 xgboost 如何筛选特征重要程度

xgboost 模型训练完毕之后，可以查一下每个特征在模型中的重要程度;

进一步的，我们可以暴力搜索一下，通过这个相关性筛选一下模型，看能不能在特征数量减少的情况下，模型表现能力不变甚至提升或者有我们可以接受的降低幅度。

核心代码如下(完整运行去github吧)

## 如何获取特征重要程度
print(model.feature_importances_)
plot_importance(model)
pyplot.show()

## 如何筛选特征
selection = SelectFromModel(model, threshold=thresh, prefit=True)

完整代篇幅太大，不展示在这里，直接去github：

3.1 xgboost完整训练代码

完整代篇幅太大，不展示在这里，直接去github：

xgboost 代码调参

框架参数：

booster：弱学习器类型
objective：分类还是回归问题以及对应的损失函数
n_estimators：弱学习器的个数

弱学习器参数：

max_depth：树的深度
min_child_weight：最小节点的权重阈值，小于这个值，节点不会再分裂；
gamma：节点分裂带来损失最小阈值，我们使用目标函数之差计算增益，小于这个阈值的时候，不再分裂
learning_rate:控制每个弱学习器的权重缩减系；这个系数会乘以叶子节点的权重值，它的作用在于削弱每个树的影响力，如果学习率小，对应的弱学习器的个数就应该增加。

xgboost常规面试题

与GBDT相比，Xgboost的优化点：

算法本身的优化：首先GBDT只支持决策树，Xgboost除了支持决策树，可以支持多种弱学习器，可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART；其次GBDT损失函数化简的时候进行的是一阶泰勒公式的展开，而Xgboost使用的是二阶泰勒公式的展示。还有一点是Xgboost的目标函数加上了正则项，这个正则项是对树复杂度的控制，防止过拟合。
可以处理缺失值。尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向
运行效率：并行化，单个弱学习器最耗时的就是决策树的分裂过程，对于不同特征的特征分裂点，可以使用多线程并行选择。这里想提一下，我自己理解，这里应该针对的是每个节点，而不是每个弱学习器。这里其实我当时深究了一下，有点混乱。为什么是针对每个节点呢？因为我每个节点也有很多特征，所以在每个节点上，我并行（多线程）除了多个特征，每个线程都在做寻找增益最大的分割点。还有需要注意的一点是Xgboost在并行处理之前，会提前把样本按照特征大小排好序，默认都放在右子树，然后递归的从小到大拿出一个个的样本放到左子树，然后计算对基于此时的分割点的增益的大小，然后记录并更新最大的增益分割点。

参考链接

刘建平：https://www.cnblogs.com/pinard/p/11114748.html

B站视频：https://www.bilibili.com/video/BV1mZ4y1j7UJ?from=search&seid=4849972439430408952

知乎：Microstrong：https://zhuanlan.zhihu.com/p/83901304

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入AINLP技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注NLP技术交流

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。