XGBoost的方法源自于Friedman的二阶方法，XGBoost在正则化目标函数上做了小改进。XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进。（XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致）

---

1.引言

• We design and build a highly scalable end-to-end tree boosting system.
• We propose a theoretically justified weighted quantile sketch for efficient proposal calculation.
• We introduce a novel sparsity-aware algorithm for par- allel tree learning.
• We propose an effective cache-aware block structure for out-of-core tree learning.
• 高度可扩展的端到端树提升系统
• 在树结构学习中有效处理权重的分布式加权直方图调整框架
• 介绍了一种新的稀疏感知并行树学习算法
• 介绍了一种用于核外树学习的缓存感知块结构

2. 树结构算法

2.1 正则化

  对于一个含n个训练样本，m个features的给定数据集D，所使用的树集成模型（见图“树集成模型”）使用K次求和函数（下图公式1）来预测输出（加法模型）。

原文
树集成模型
  q表示每棵树（回归树CART）的结构，它会将一个训练样本实例映射到相对应的叶子索引上；T是树中的叶子数；每个fk对应于一个独立的树结构q和叶子权重w。与决策树不同的是，每棵回归树包含了在每个叶子上的一个连续分值（梯度提升算法中的平均值c），我们使用wi 来表示第i个叶子上的分值。对于一个给定样本实例，我们会使用树上的决策规则(由q给定)来将它分类到叶子上，并通过将相应叶子上的分值(由w给定)做求和，计算最终的预测值。为了在该模型中学到这些函数集合，我们最小化下面的正则化目标函数
正则化目标函数
惩罚函数，参考CSDN-简之

2.2 Gradient Tree Boosting：又名 GBM、GBRT、 GBDT、 MART，是一类很常用的集成学习算法

  迭代决策树算法，由多棵决策树组成，并将所有树的输出结果累加起来。且每一棵树是从之前所有树的残差中来学习的。GBRT 几乎可用于所有的回归问题（线性/非线性）（相对LR仅能用于线性回归，GBRT的适用面非常广），也可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。

原文2.2

  在2.1中的目标函数公式（对应论文公式2）上中的树集成模型包含函数作为参数，传统的欧几里得空间优化方法无法对其进行优化。因此，模型是以相加的方式训练（前向分步算法）的。认为y ̂_i(t)是第i个实例在第t次迭代时的预测，加入一个新的ft来最小化以下目标。目标函数表达式为：

目标函数

  对于该函数的优化，在 XGBoost 中使用了泰勒展开式，与 GDBT 不同的是 XGBoost 使用了泰勒二次展开式。去掉常数项（如下图“常数项”），最终得到简化后的函数（损失函数），如下图“损失函数”。

常数项 损失函数

  Freidman提出了梯度提升树算法(GBT)。梯度提升树(GBT)的一个核心思想是利用损失函数的负梯度在当前模型的值作为残差的近似值，本质上是对损失函数进行一阶泰勒展开，从而拟合一个回归树。

原文2.2（2）

  定义q函数将输入x映射到某个叶节点上，则定义每个叶子节点j上的样本集合为

叶子结点上的样本集合
  将损失函数进行重写，并展开Ω 项（参考正则化项），得到图“原文2.2（2）”中的公式（4）。对于固定结构q(x)，可以通过图“原文2.2（2）”中的公式（5）计算出叶子j的最优权值ωj^*和最优值（ 图“原文2.2（2）”中的公式（6），可作为评分函数来评定树结构的质量）。

2.3 对应原文2.3

  除了正则化目标外，还使用了另外两种技术来进一步防止过拟合。

• 收缩技术（弗里德曼提出），收缩以一个因素η衡量新增的权重每一步后的树形提升。
• 列(特征)子抽样，源于随机森林，根据用户反馈，使用列子抽样比传统的行子抽样(也支持行子抽样)更能防止过拟合。列子样本的使用也加速了后面描述的并行算法的计算。

3.分裂查找算法

  构建树,寻找分裂点的时候需要关注两个问题：选用什么特征（维度）进行切割和在所选特征（维度）取什么样的阈值进行切割。

3.1 精确贪心算法：Basic Exact Greedy Algorithm

  在所有特征上，枚举所有可能的划分。精确贪心算法从树的根节点开始，对每个叶节点枚举所有的可用特征。文中指出：为了更高效，该算法必须首先根据特征值对数据进行排序，以有序的方式访问数据来枚举打分公式中的结构得分（structure score）的梯度统计(gradient statistics)。（就是写两层循环穷举这两个参数，逐个尝试后保留最优的切分方案。 ）
  该算法要求穷举所有数据，当数据不能完全装入内存时（特征量比较大，设备不支持），就不可能有效地这样做。

3.2 求近似值算法：Approximate Algorithm

  分桶操作，该算法首先会根据特征分布的百分位数，提出候选划分点。将连续型特征映射到由这些候选点划分的分桶(buckets)中，聚合统计信息，基于该聚合统计找到proposal中的最优解。（计算每个桶中的统计信息就可以求出最佳分裂点的最佳分裂收益值）

3.3 加权分位直方图：Weighted Quantile Sketch

  采用分位数的直方图近似计算分位点，以近似获取特定的查询。使用随机映射将数据流投射在一个小的存储空间内作为整个数据流的概要，这个小空间存储的概要数据（需要保留原序列中的最小值和最大值）称为Sketch，可用于近似回答特定的查询。

3.4 稀疏值处理：Sparsity-aware Split Finding

  在每个树节点中添加一个默认方向，对于缺失数据让模型自动学习默认的划分方向。采用的是在每次的切分中，让缺失值分别被切分到左节点以及右节点，通过计算得分值比较两种切分方法哪一个更优，则会对每个特征的缺失值都会学习到一个最优的默认切分方向。

4 总结

  XGBoost 在目标函数上加入了惩罚项，使模型的泛化能力大大增强，且对行列支持降采样，优化了计算速度。
  比较有意思的点在于稀疏值处理，让模型自动学习，默认划分节点，选择最优。