XGBoost

XGBoost 是机器学习比赛中的大杀器，我之前也了解过许多，于无意中看到一篇关于其总结的文章，想到应该总结一下。本文结合参考文献和一些个人整理的资料，对 XGBoost 相关知识进行总结，力求通俗易懂。

XGBoost 最早是 DMLC 的一个开源项目，提供了一个梯度提高框架，它的目的在于提供一个“可扩展的、便携式和可分布的梯度提高（GBM，GBRT，GBDT）库”。近几年，由于受到在许多机器学习竞赛中获奖团队的青睐，XGBoost 逐渐成为机器学习领域具有较强实用性的算法工具选择之一。

基础知识

决策树是机器学习领域一种重要的算法，由于其简单，容易理解，拟合效果和，在很多问题特别是在工业领域，得到了非常广泛的应用。

决策树

举个例子，集训营某一期有100多名学员，假定给你一个任务，要你统计男生女生各多少人，当一个一个学员依次上台站到你面前时，你会怎么区分谁是男谁是女呢？很快，你考虑到男生的头发一般很短，女生的头发一般比较长，所以你通过头发的长短将这个班的所有学员分为两拨，长发的为“女”，短发为“男”。相当于你依靠一个指标“头发长短”将整个班的人进行了划分，于是形成了一个简单的决策树，而划分的依据是头发长短。这时，有的人可能有不同意见了：为什么要用“头发长短”划分呀，我可不可以用“穿的鞋子是否是高跟鞋”，“有没有喉结”等等这些来划分呢，答案当然是可以的。但究竟根据哪个指标划分更好呢？很直接的判断是哪个分类效果更好则优先用哪个。所以，这时就需要一个评价标准来量化分类效果了。

怎么判断“头发长短”或者“是否有喉结”是最好的划分方式，效果怎么量化呢？直观上来说，如果根据某个标准分类人群后，纯度越高效果越好，比如说你分为两群，“女”那一群都是女的，“男”那一群全是男的，那这个效果是最好的。但有时实际的分类情况不是那么理想，所以只能说越接近这种情况，我们则认为效果越好。

量化分类效果的方式有很多，比如信息增益（ID3）、信息增益率（C4.5）、基尼系数（CART）等等。具体可以参考我的博文：机器学习之决策树小结。

回归树与集成学习

回归树

事实上，分类与回归是两个很接近的问题，分类的目标是根据已知样本的某些特征，判断一个新的样本属于哪种已知的样本类，它的结果是离散值。而回归的结果是连续的值。当然，本质是一样的，都是特征（feature）到结果/标签（label）之间的映射。理清了什么是分类和回归之后，理解分类树和回归树就不难了。分类树的样本输出（即响应值）是类的形式，比如判断这个救命药是真的还是假的，周末去看电影还是不去。而回归树的样本输出是数值的形式，比如给某人发放房屋贷款的数额就是具体的数值，可以是 0 到 300 万元之间的任意值。所以，对于回归树，你没法再用分类树那套信息增益、信息增益率、基尼系数来判定树的节点分裂了，你需要采取新的方式评估效果，包括预测误差（常用的有均方误差、对数误差等）。而且节点不再是类别，是数值（预测值），那么怎么确定呢？有的是节点内样本均值，有的是最优化算出来的比如 XGBoost。

其中，用于回归任务的是 CART 算法，可以参考我的博文：机器学习之分类与回归树(CART)。

集成学习

集成学习也是机器学习中一种重要的方法，所谓集成学习，是指构建多个分类器（弱分类器）对数据集进行预测，然后用某种策略将多个分类器预测的结果集成起来，作为最终预测结果。通俗比喻就是“三个臭皮匠赛过诸葛亮”，或一个公司董事会上的各董事投票决策，它要求每个弱分类器具备一定的“准确性”，分类器之间具备“差异性”。集成学习根据各个弱分类器之间有无依赖关系，分为 Boosting 和 Bagging 两大流派：

• Boosting 流派，各分类器之间有依赖关系，必须串行，比如 AdaBoost、GBDT(Gradient Boosting Decision Tree)、XGBoost
• Bagging 流派，各分类器之间没有依赖关系，可各自并行，比如随机森林（Random Forest）

本文将要介绍的 XGBoost 属于 Boosting 方法，至于另一类集成学习方法，比如 Random Forest（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥关系。关于 Boosting、Bagging 和 AdaBoost，可以参考我的博文：机器学习之 Bootstrap、Bagging、Boosting 介绍。

Boosting 由多个相关联的决策树联合决策，什么叫相关联？举个例子：

• 有一个样本[数据->标签]是：[(2，4，5)-> 4]
• 第一棵决策树用这个样本训练的预测为3.3
• 那么第二棵决策树训练时的输入，这个样本就变成了：[(2，4，5)-> 0.7]
• 也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关

一个回归树形成的关键点在于：

• 分裂点依据什么来划分（如前面说的均方误差最小，loss）
• 分类后的节点预测值是多少（如前面说，有一种是将叶子节点下各样本实际值得均值作为叶子节点预测误差，或者计算所得）

从上面的两条定义可以看出，GBDT 和 XGBoost帮助我们规划了如何形成相关联的决策树，因此 GBDT 和 XGBoost 都属于 Boosting 学习方法的一种。

GBDT

GBDT 与 AdaBoost 不同，GBDT 每一次的计算是都为了减少上一次的残差，进而在残差减少（负梯度）的方向上建立一个新的模型。关于 GBDT，可以参考我的博文：机器学习之梯度提升决策树(GBDT)。

XGBoost 介绍

其实 XGBoost 和 GBDT 差别说大很大，说小很小。大体现在各种工程优化上面，因为 XGBoost 最开始就是一个算法库，提供了各种工程优化方法，而 GBDT 只是一种理论指导。小则体现在核心理论思想和算法原理并没有太大的区别。简单的讲，传统的 GBDT 使用了目标函数的一阶泰勒展开进行优化，而 XGBoost 扩展到二阶泰勒展开进行优化。

由于我上一篇博文中介绍 GBDT 的时候已经介绍了二阶展开，这地方就不贴推导公式了，直接先来看 XGBoost 的在损失函数为平方损失（square loss）的情况下的目标函数：

$$\begin{split} Obj^{(t)} &= \sum_{i=1}^n \left(y_i - (\hat{y}_i^{t-1} + f_t(x_i)) \right)^2 + \Omega(f_t) + constant \\ &= \sum_{i=1}^n \left[2(\hat{y}_i^{t-1} - y_i)f_t(x_i) + f_t(x_i)^2 \right] + \Omega(f_t) + constant \end{split}$$

其中，$(\hat{y}_i^{t-1} - y_i)$ 称之为残差（residual）。 XGBoost 和 GBDT 每一步在生成决策树时只需要拟合前面的模型的残差。

然后对目标函数进行泰勒展开，这一步我的上篇博文已经推导了，这里着重补充泰勒展开中的各项对应关系。

泰勒公式：

$$f(x+\Delta x) \approx f(x) + f'(x)\Delta x + \frac12 f''(x)\Delta x^2$$

其中 $f$ 对应目标函数中的 $\hat{y}_i^{t-1}$，$f$ 中的 $\Delta x$ 对应目标函数中的 $f_t(x_i)$，从而有 $f$ 对 $x$ 求导数就对应为目标函数对 $\hat{y}_i^{t-1}$ 求偏导。得到展开后的目标函数：

$$Obj^{(t)} \approx \sum_{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) + constant$$

其中，$gi$ 定义为 损失函数 $l(x)$ 的一阶导数：$g_i=\partial{\hat{y}^{t-1}}l(yi,\hat{y}^{t-1})$。$h_i$ 定义为损失函数的二阶导数：$h_i=\partial{\hat{y}^{t-1}}^2l(y_i,\hat{y}^{t-1})$。（其实这一步上一篇博文也讲到了）

接下来，考虑到第 $t$ 颗回归树是根据前面的 $t-1$ 颗回归树的残差得来的，相当于第 $t-1$ 颗回归树的值 $\hat{y}_i^{t-1}$ 已知，因此中括号内的第一项 $l(y_i, \hat{y}_i^{t-1})$ 对目标函数优化不影响（ $y_i$ 是第 $i$ 个样本的标签值，$l$ 是固定的损失函数，比如 L2 Loss）。从而得到了一个移除常数项的目标函数：

$$Obj^{(t)} \approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t)$$

可以看到，目标函数只依赖于每个样本在误差函数上的一阶导数 $g_i$ 和 二阶导数 $h_i$（相信你已经看出 XGBoost 和 GBDT 的不同了，目标函数保留了泰勒展开的二次项）。

正则项

我在 GBDT 中已经介绍了关于正则项的计算，也就是利用决策树的复杂度作为正则项，但是只介绍如何计算，下面根据一个实例（来自陈天奇的PPT）详细介绍一下。

假设我们要预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏，以及男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，逐一给各人在电子游戏喜好程度上打分，如下图所示。

在这个决策树中，我们使用了两个节点来区分不同的样本，总共得到三个叶节点，每个叶节点的得分分别是：+2，+0.1，-1。这些信息已经能够包含计算一颗决策树复杂度的所有条件。首先梳理计算决策树复杂度的几个规则：

• 用叶子节点集合以及叶子节点的得分来表示复杂度
• 每个样本都落在一个叶子节点上
• $q(x)$ 表示样本 $x$ 落在某个节点上（的映射函数），$w_q(x)$ 表示该节点的打分，也就是模型输出的预测值。

所以一颗决策树可以用结构函数 $q(x)$ 和叶子权重分布 $w_q(x)$ 表示，其中结构函数把输入映射到叶子的索引号上面去，而权重分布函数则给定了每个索引号对应的预测值。因此，上述决策树的映射关系可以表示为下图：

前面说了，用叶子节点集合以及叶子节点的得分来表示复杂度，具体的， XGBoost 中树的复杂度包含了两部分：

• 树里面叶子节点的个数 $T$
• 树上叶子节点的得分的 L2 （模平方）正则项

因此 XGBoost 的正则项表示为：

$$\Omega (f) = \gamma T + \frac{1}{2}\lambda ||w||^2$$

具体的，对于上面的决策树，其正则项计算如下图所示：

将正则项带入目标函数中（这一部分在 GBDT 中已经推导过了），可以得到：

$$\begin{split} Obj^{(t)} &\approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \\ &= \sum_{i=1}^n \left[ g_iw_{q(x_i)} + \frac12h_iw_{q(x_i)}^2 \right] + \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T \left[(\sum_{i \in I_j}g_i)w_j + \frac12(\sum_{i \in I_j}h_i + \lambda)w_j^2 \right] + \gamma T \end{split}\tag 6$$

其中，$I_j={ i \vert q(x_i)=j }$ 表示所有被划分到叶子节点 $j$ 的训练样本的集合，$g$ 是一阶导数，$h$ 是二阶导数。可以看到，目标函数中存在两种累加：

• $\sum_{i=1}^n$ 表示样本数
• $\sum_{j=1}^T$ 表示叶子节点数

这个推导的第二行到第三行中有一个关键的地方在于：$I_j$ 被定义为每个叶子节点 $j$ 上面样本下标的集合，也就是 $I_j={ i \vert q(x_i)=j }$ ，这里 $q(x_i)$ 表示：每个样本值 $x_i$ 都能通过函数 $q()$ 映射到树的某个叶子节点上。而当 $x_i$ 映射到集合$I$ 之后，$w_q(x_i)$ 就表示为 $w_j$ 因此，可以通过这个定义把两种累加统一到一起。

接着，定义 $Gj=\sum{i \in Ij}g_i$，$H_j=\sum{i \in I_j}h_i$，则目标函数可写为：

$$Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j + \frac12(H_i + \lambda)w_j^2 \right] + \gamma T$$

其中，$w_j$ 表示叶子节点的预测值，也就是我们要学习的东西。假设树的结构是固定的，即函数 $q(x)$ 确定，为了求得目标函数的极小值，令函数的 $Obj^{(t)}$ 一阶导数等于0，即可求得叶子节点 $j$ 对应的值为：

$$w_j^*=-\frac{G_j}{H_j+\lambda}$$

然后把 $w_j$ 最优解带入得到：

$$Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T$$

打分函数计算

推导了这么多，目标函数本质是度量决策树预测值与实际值的（带正则项的）误差，当我们指定了或者说构造了一个树之后，目标函数 $Obj$ 表示这棵树与实际值的误差。对于多个连续关联阶段的弱学习器，因为每个阶段学习的如何缩小上一阶段输出与实际值的差距，也就是学习的是残差，因此这一阶段的目标函数也表示截止到目前，我们在目标上面最多减少多少，也就是剩余多少残差还需要学习，因此这个值越小越好**（如果不理解这句话，需要反复看几遍，或者记住目标函数的本质意义）。

很有意思的一个事是，我们从头到尾了解了 XGBoost 如何优化、如何计算，但树到底长啥样，我们却一直没看到。很显然，一棵树的生成是由一个节点一分为二，然后不断分裂最终形成为整棵树。对于一棵树，其目标函数的极值我们也能够计算了，那么树怎么分裂的，或者说如何构造一棵树就成为了接下来我们要探讨的关键。

对于一个叶子节点如何进行分裂，xgboost作者在其原始论文中给出了两种分裂节点的方法

枚举法（贪心法）

现在的情况是只要知道树的结构，就能得到一个该结构下的最好分数，那如何确定树的结构呢？一个想当然的方法是：不断地枚举不同树的结构，然后利用打分函数来寻找出一个最优结构的树，接着加入到模型中，不断重复这样的操作。而再一想，你会意识到要枚举的状态太多了，基本属于无穷种，那咋办呢？我们试下贪心法，从树深度 0 开始，每一节点都遍历所有的特征，比如年龄、性别等等，对于某个特征，先按照该特征里的值进行排序，然后线性扫描该特征进而确定最好的分割点，最后对所有特征进行分割后，我们选择所谓的增益 Gain 最高的那个特征。

我们推导出来的目标函数的最优解是：

$$Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T$$

目标函数中的 $\frac{G^2}{H+\lambda}$ 部分表示每一个叶子节点对当前模型损失的贡献度，Gain 的计算之前介绍过，将这部分带入，得到 Gain 的计算公式：

回到树的构造上面，假设从 0 开始构造，我们就有一堆特征，现在我们遍历特征（不需要排序），对于要遍历的每个特征，应该先按照该特征的所有值进行排序，比如上述的游戏爱好程度的例子，我们选择年龄这个特征，则应该将 5 个人的年龄从小到大进行排序，然后分别选择 4 个分割点：

1. 把第一个人和后面四个人划分开
2. 把前两个人和后面三个人划分开
3. 把前三个人和后面两个人划分开
4. 把前面四个人和后面一个人划分开

接下来，把上面 4 种划分方法全都各自计算一下 Gain，看哪种划分方法得到的 Gain 值最大则选取哪种划分方法，经过计算，发现把第 2 种划分方法“前面两个人和后面三个人划分开”得到的 Gain 值最大，意味着在一分为二这个第一层层面上这种划分方法是最合适的。其实这一步骤我在决策树那篇博文中已经介绍过了，因此这里就不列举具体计算了。

这是对于某个特征，我们在每层都遍历所有未使用的特征，找到能够得到最大 Gain 的特征及其分割点进行树的分裂和构造。这里还有一个需要注意的问题，就是我们引入了正则项，对引入一个新的分裂进行了惩罚，因此引入分割不一定会使得情况变好，这也是我们引入新叶子的惩罚项的意义。优化这个目标对应了树的剪枝， 当引入的分割带来的增益小于一个阀值 $\gamma$ 的时候，则忽略这个分割。还有一种避免过拟合的方法是设置树的最大深度，即当树生长到最大深度则停止分裂。

上述的算法可以表示为：

近似算法

一般情况下，我们都是用贪心算法进行枚举构造，但是如果数据太大，不能直接进行计算，就需要使用近似算法。其算法步骤为：

具体的可以查阅相关资料，这里就不介绍了。

总结

从决策树到 CART 树，然后是 GBDT ，再到本篇的 XGBoost ，结合 Boosting ，我将机器学习中决策树相关领域涉及的知识做了简易的介绍。当然，还有很多知识没有来得及细细展开，如果感兴趣，可以在有需求的情况下，针对特定情况，再做更加深入的了解。

也希望自己后续能够继续坚持对这些机器学习理论的记录总结和探索，查漏补缺，与君共勉。

参考资料

• https://blog.csdn.net/v_july_v/article/details/81410574
• 陈天奇 PPT
• XGBoost 论文