『XGBoost模型』详解 | 300张图详解机器学习算法(10)
是 的缩写称呼，它是一个非常强大的 算法工具包，优秀的性能（效果与速度）让其在很长一段时间内霸屏数据科学比赛解决方案榜首，现在很多大厂的机器学习方案依旧会首选这个模型。
在并行计算效率、缺失值处理、控制过拟合、预测泛化能力上都变现非常优秀。本文我们给大家详细展开介绍 ，包含『算法原理』和『工程实现』两个方面。
关于 的工程应用实践，欢迎大家参考的另外一篇实战文章 工具库建模应用详解 .tech/-/194
本篇部分内容涉及到机器学习基础知识、决策树/回归树/GBDT算法，没有先序知识储备的宝宝可以查看的文章 、 、 及
1.算法原理可视化解读
关于的原理，其作者陈天奇本人有一个非常详尽的 做了系统性的介绍，我们在这里借助于这个资料给大家做展开讲解。(链接见文末)
1）监督学习中的一些重要概念
在开始介绍 Tree之前，我们先来回顾一下机器学习中的一些重要的概念。
（1）监督学习核心要素
符号（）： 表示训练集中的第 个样本。
模型（Model）：对于已知的 如何预测 ？
线性模型（ Model） （包括线性回归和逻辑回归），预测值 根据不同的任务有不同的解释：
参数（）：需要从数据中学习的东西。
目标函数（ ）
训练数据损失函数（ Loss）
正则化项（）：描述了模型的复杂程度。
（2）监督学习进阶知识
Ridge回归：
Lasso：
逻辑回归（ ）：
（3）目标函数及偏差方差权衡
回顾一下目标函数 ，为什么目标函数需要两部分组成呢？
2）回归树（ Tree）和集成（）（1）回归树（ Tree）
回归树，也就是分类回归树（ and Tree）（详情请查看文章回归树模型详解）
（2）回归树集成（ Tree ）
从上图的左图可以看出，共有 个训练样本。
从上图的中图可以看出，每个叶子节点都有预测值：第一个叶子结点的预测值是 ，第二个叶子结点的预测值是 ，第三个叶子结点的预测值是 。
最终的预测值就是样本在每颗树中所在的叶子结点的预测值的和。
（3）树集成方法
树集成的方法使用非常广泛，像GBM、随机森林等（详见文章 图解机器学习 | GBDT模型详解 和 图解机器学习 | 随机森林分类模型详解）。多达半数的数据挖掘竞赛通过使用各种各样的树集成方法而获胜。
（4） Tree的模型和参数
模型：假设我们有K棵树： 。其中，F为包含所有回归树的函数空间。
参数：包括每棵树的结构和叶子结点中的分数。或者使用函数当作参数： 。
（5）在单变量上学习 Tree
单变量也就是单个特征，通过了解如何在单变量上学习 Tree，我们可以对 Tree的学习模式有个简单的概念。
举例：假设回归树只有一个输入变量t（时间），希望预测小哥在t时刻有多喜欢浪漫音乐。
从上左图可以看到，这位小哥在单身的时候，对浪漫音乐的喜欢程度很低；但是当他遇到了女朋友，随着体内荷尔蒙的分布增加，他对浪漫音乐的喜欢程度增加了；但是有一天分手了，他对浪漫音乐的喜欢程度又变低了。当然，我们也可以发现，上右图的回归树很容易能表达上左图。
为了构建上右图的树，我们需要学习两个东西：
单变量回归树的目标（阶跃函数）
（6）一般情形的 Tree
首先回顾上面我们对 Tree的定义：
模型：假设我们有K棵树：
目标函数：
当我们讨论树的时候，通常是启发式的：
大多数启发式算法都能很好地映射到目标函数，采用形式（目标）视图让我们知道我们正在学习什么：
回归树集成定义了如何得到预测值，它不仅仅可以做回归，同样还可以做分类和排序。具体做什么任务依赖于『目标函数』的定义：
3） （如何学习）
在这一节中我们将正式学习 。这里，的处理大家可以对比GBDT模型（可参考文章 图解机器学习 | GBDT模型详解）来理解核心差异。
（1）解决方案
目标函数：
在做GBDT的时候，我们没有办法使用SGD，因为它们是树，而非数值向量——也就是说从原来我们熟悉的参数空间变成了函数空间。
解决方案：初始化一个预测值，每次迭代添加一个新函数（ ）：
（2）目标函数变换
第一步：根据上面的公式，目标函数可以做如下变形
这里我们考虑平方损失，此时目标函数又可以变形为：
第二步：所以我们的目的就是找到 使得目标函数最低。然而，经过上面初次变形的目标函数仍然很复杂，目标函数会产生二次项。
在这里我们引入泰勒展开公式：
目标函数利用泰勒展开式就可以变成：
第三部：把常数项提出来，目标函数可以简化为
思考：为什么要做这么多变化而不直接生成树？
（3）重新定义树
在前面，我们使用 代表一颗树，在本小节，我们重新定义一下树：我们通过叶子结点中的分数向量和将实例映射到叶子结点的索引映射函数来定义树：（有点儿抽象，具体请看下图）
从上图可以看出，共有3个叶子结点，第一个叶子结点的权重为+1，第二个叶子结点的权重为0.1，第三个叶子结点的权重为-1；其中，小男孩属于第1个叶子结点，老奶奶属于第3个叶子结点。
（4）定义树的复杂程度
通过下面的式子定义树的复杂程度（定义并不是唯一的）
（5）重新审视目标函数
定义在叶子结点 中的实例的集合为：
根据每棵叶子重新定义目标函数：
（6）计算叶子结点的值
一些知识需要先了解。对于一元二次函数： ，我们很容易得到这个函数的最小值和最小值对应的 。
也就是：
0 \\min_x Gx+\frac{1}{2}Hx^2 & =-\frac{1}{2}\frac{G^2}{H}\end{}" data--type="block-" style=" : block; text-align: ; : auto; : block; ---: touch; ">
如何求叶子结点最优的值？接着继续变化目标函数：
假设树的结构 是固定的，那么每一个叶子结点的权重的最优值为
目标函数的最优值为
下图是前面公式讲解对应的一个实际例子。
这里再次总结一下，我们已经把目标函数变成了仅与 这五项已知参数有关的函数，把之前的变量 消灭掉了，也就不需要对每一个叶子进行打分了！那么现在问题来，刚才我们提到，以上这些是假设树结构确定的情况下得到的结果。但是树的结构有好多种，我们应该如何确定呢？
（7）贪婪算法生成树
上一部分中我们假定树的结构是固定的。但是，树的结构其实是有无限种可能的，本小节我们使用贪婪算法生成树：
接下来要考虑的是如何寻找最佳分裂点。
例如，如果 是年龄，当分裂点是 的时候的增益 是多少？
我们需要做的仅仅只是计算每一边的 和 ，然后计算
对排序后的实例进行从左到右的线性扫描就足以决定特征的最佳分裂点。
所以，分裂一个结点的方法是：
时间复杂度：
（8）如何处理分类型变量
一些树学习算法分别处理分类变量和连续变量，我们可以很容易地使用我们推导出的基于分类变量的评分公式。但事实上，我们没有必要单独处理分类变量：
我们可以使用 one-hot 方式处理分类变量：
如果有太多的分类的话，矩阵会非常稀疏，算法会优先处理稀疏数据。
（9）修剪和正则化
回顾之前的增益，当训练损失减少的值小于正则化带来的复杂度时，增益有可能会是负数：
此时就是模型的简单性和可预测性之间的权衡。
2.核心原理归纳解析1）目标函数与泰勒展开
也是一个加法模型，每一步迭代只优化当前步中的子模型。第 步我们有：
目标函数设计为『经验风险』+『结构风险』（正则项）：
在数学中，我们可以用泰勒公式近似 ，具体如下式。对损失函数运用二阶展开来近似。
更多数学知识推荐阅读的AI数学基础系列教程 图解AI数学基础：从入门到精通系列教程（链接见文末）
对应 的损失函数，我们在上式里将 视作 ， 视作 ， 视作关于 的函数，得到：
又因前 个子模型已经确定了，故上式中除了关于 的部分都是常数，不影响对 的优化求解。目标函数可转化为：
2）的正则化
实际上，的基分类器对决策树和线性模型都支持，这里我们只讨论更常见的『基于树』的情况。为防止过拟合，设置了基于树的复杂度作为正则项：
作为回归树，叶子节点越多、输出的回归值越大，树的复杂度越高。
最终目标函数如下：
下面是一个数学转换处理，为了使正则项和经验风险项合并到一起。我们把在样本层面上求和的经验风险项，转换为叶节点层面上的求和。
定义节点 上的样本集为 ，其中 为将样本映射到叶节点上的索引函数，叶节点 上的回归值为 。
进一步简化表达，令 ， 注意这里 和 都是关于 的函数：
转化到这个形式后，我们可以看出，若一棵树的结构已经确定，则各个节点内的样本 也是确定的，即 ， 、 被确定，每个叶节点输出的回归值应该使得上式最小，由二次函数极值点：
按此规则输出回归值后，目标函数值也就是树的评分如下公式，其值越小代表树的结构越好。观察下式，树的评分也可以理解成所有叶节点的评分之和：
3）节点分裂准则
我们之前文章决策树模型详解里给大家讲到了决策树模型是递归生长形成的，而的子模型树也一样，需要要依赖节点递归分裂的贪心准则来实现树的生成。
（1）贪心准则
子树的基本处理思路和CART一样，会对特征值排序后遍历划分点，将其中最优的分裂收益作为该特征的分裂收益，选取具有最优分裂收益的特征作为当前节点的划分特征，按其最优划分点进行二叉划分，得到左右子树。
上图是一次节点分裂过程，很自然地，分裂收益是树 A 的评分减去树B的评分。虚线框外的叶节点，即非分裂节点的评分均被抵消，只留下分裂后的 LR 节点和分裂前的 S 节点进行比较，因此分裂收益的表达式为：
（2）近似算法
基于性能的考量，还对贪心准则做了一个近似版本，简单说，处理方式是『将特征分位数作为划分候选点』。这样将划分候选点集合由全样本间的遍历缩减到了几个分位数之间的遍历。
展开来看，特征分位数的选取还有和local两种可选策略：
这两种情况里，由于 只能划分一次，其划分粒度需要更细。
XGB 原始 paper 中对 Higgs Boson 数据集进行了实验，比较了精确贪心准则、 近似和 local 近似三类配置的测试集 AUC，用 eps 代表取分位点的粒度，如 代表将数据集划分为 个 ，发现 （）和 local（）均能达到和精确贪心准则几乎相同的性能。
工具包支持上述提到的3类配置。
（3）加权分位数
查看目标函数 ，令偏导为易得 ，此目标函数可理解为以 为权重， 为标签的二次损失函数：
在近似算法取分位数时，实际上会取以二阶导 为权重的分位数（ ），如下图表示的三分位。
4）列采样与学习率
为了进一步优化效果，在以下2个方面进行了进一步设计：
列采样
学习率
5）特征缺失与稀疏性
也能对缺失值处理，也对特征稀疏问题（特征中出现大量的0或one-hot 结果）做了一些优化。用『稀疏感知』策略来同时处理这两个问题：
依然通过遍历得到分裂节点，NA的方向有两种情况，在此基础上对非缺失值进行切分遍历。
如上图所示，若某个特征值取值为1，2，5和大量的NA，会遍历以上6种情况（3个非缺失值的切分点×缺失值的两个方向），最大的分裂收益就是本特征上的分裂收益，同时，NA将被分到右节点。
3.工程优化1）并行列块设计
将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。
2）缓存访问优化
特征值排序后通过索引来取梯度 会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，为每个线程分配一个单独的连续缓存区，用来存放梯度信息。
3）核外块计算
数据量非常大的情形下，无法同时全部载入内存。将数据分为多个储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。为了进一步提高磁盘读取数据性能，还使用了两种方法：
4. vs GBDT
我们对之前讲解过的GBDT（参考文章 ）和这里的做一个对比总结：
链接整理
斯坦福CS229课程视频 | 机器学习-吴恩达主讲(2018·完整版)
陈天奇 ~usman///.pdf
图解机器学习算法(1) | 机器学习基础知识
图解机器学习算法(2) | 模型评估方法与准则
图解机器学习算法(3) | KNN算法及其应用
图解机器学习算法(4) | 逻辑回归算法详解
图解机器学习算法(5) | 朴素贝叶斯算法详解
图解机器学习算法(6) | 决策树模型详解
图解机器学习算法(7) | 随机森林分类模型详解
图解机器学习算法(8) | 回归树模型详解
图解机器学习算法(9) | GBDT模型详解
图解机器学习算法(10) | 模型最全解析
图解机器学习算法(11) | 模型详解
图解机器学习算法(12) | 支持向量机模型详解
图解机器学习算法(13) | 聚类算法详解
图解机器学习算法(14) | PCA降维算法详解
推荐教程
THE END
转载请联系本公众号(-Hub)获得授权