XGBoost在2015年到2017年间kaggle比赛中大放异彩。本文依据2016年论文《XGBoost: A Scalable Tree Boosting System》翻译总结。
处理的问题包括：库存销售预测、高能量物理事件分类、web text 分类、客户行为预测、运动检测、广告点击率预测、产品分类、风险预测等。
XGBoost成功的最主要因素是其可扩展性。比大部分算法快10倍，可以扩展支持几十亿的样本数据。
XGBoost支持hadoop、Flink、Spark。阿里天池云平台也集成了XGBoost。
本文的主要贡献是： 1）我们设计和建立了一个可扩展的端到端的树提升系统。 2）我们引入了一个新颖的稀疏感知算法，可以并行的树训练； 3）我们提出了一个理论上公平的权重分位数略图方法，方便近似学习。 4）对于硬盘上的大数据的树学习，我们提出了一个有效的缓存感知块结构，以及数据压缩、分片。
相关算法比较：
为了防止过拟合，目标函数增加了正则项。
数据D有n个样本，m个特征。
树集成模型有K个累加函数，如上图中小孩=2+0.9=2.9：
其中q表示每个树的结构。T表示每个树中叶子节点数。 故f_k对应于一个树结构q及其叶子的权重w。 不像决策树，每个回归树在每个叶子节点上有一个连续的分数，我们使用w_i表示第i个（i-th）叶子的分数。
最终目标函数如下：
上式的第2项时正则惩罚项，如果该项为0，那么目标函数就是普通的梯度树提升。
上面的目标函数可以写成下面形式：
将f 二阶泰勒展开：
去掉常数项，变成下面公式：
定义I_J={i|q(x_i )=j} 为第j个叶子上的样本（实例）集合。则上面公式可以写成如下形式：
然后可以得到下面公式：
上面的公式6可以作为一个积分函数，测量一个树结构q的质量。
下面是上面公式的图示：
实际中，不可能列举出所有可能的树结构。而采用一个贪婪算法，从一个单独的叶子节点开始，迭代的添加分支。所以实际中用如下公式：
除了上面2.1节提到的正则化防止过拟合，还有下面两个技术。
第一个技术是收缩。是在树提升的每一步后，添加一个权重因子η。类似梯度优化中的学习率，减少了每个个性的树和叶子空间对将来树的影响，来改善模型。
第二个技术是列（特征）下采样。这个技术通常在随机森林中使用，之前没有被使用到树提升模型。该技术也加速了并行算法的计算。
树学习的一个关键问题是找到上章公式7中的最佳分割点。
该算法是对连续特征的所有可能的分割进行迭代。为了有效的运行此算法，一般首先根据特征值对数据排序。然后按顺序计算梯度特征。算法如下：
Exact Greedy Algorithm会贪婪的迭代所有可能的分割点，不是非常有效率的，比如当数据不能全部加载到内存中时，以及分布式计算时。所有提出了近似算法。
近似算法首先根据特征分布的百分位选择候选分割点。然后根据这些候选的点，将连续特征匹配到桶（buckets） 分割，进行统计分析，找到最佳的解决方案。
这个算法有两个变体，分别是global和local的。Global变体是在树创建的开始阶段，就提出候选的分割，然后使用这些提出的建议分割在所有水平上进行分割查找；local 变体是在每次分割后重提出。
下图可以看出，local变体要求较少的候选者，而global变体如果给了足够多的候选者也可以达到local变体的准确率。
近似算法的一个重要步骤是产生候选分割点。通常一个特征的百分位用来制作候选的分布。
我们引入了一个新颖的分布式的权重百分位略图算法，处理权重数据。论文的创新点，算法较复杂。
在真实世界中，输入x经常是稀疏的（有很多零）。比如（1）数据集中数据的缺失；（2）统计上的0输入；（3）特征工程的人为加工导致的，比如one-hot 编码。
我们引入的稀疏感知算法可以处理各种形式的稀疏数据。
让算法知道数据中稀疏样式是非常重要的，为此，我们对于稀疏引入一个默认方向。如下图：
树学习中最消耗时间的是数据的排序，为了减少排序成本，我们将数据存储到内存中，这个内存存储单元叫做block。
每个block中的数据是采用压缩格式存储。每列是根据其相应的特征值排序。如下图：
在近似算法中，block结构也是有用的；列的block结构也支持列的下采样。
上面提到的block结构有助于优化分割查找的计算复杂度，但是要求间接的获取基于行的梯度统计信息，这些值是以特征值的顺序存取的。这涉及非连续的内存存取。所以引入了内存感知预读取算法，在每个线程中分配一个内部的buffer，获取梯度统计信息。
我们需要选择一个正确的block size。当block 太小，会导致每个线程拥有小的工作量、不是高效的并行运算；当block 太大，会导致缓存丢失，梯度统计信息不能适配CPU 缓存。好的block大小要权衡这两者，实验结果2的16次方效果较好，如下图：
在计算时，要使用一个独立的线程来预获取block到主内存buffer，所以计算与硬盘读取同时发生。我们需要减少硬盘 IO的开销、增加吞吐量。用两个技术，一个是block压缩，26%到29%的压缩率；另一个是block 分片技术，将数据分片存储到多个磁盘上，可以提高磁盘的吞吐量。
可以看到XGBoost运行速度快，准确率也较高。
可以看到XGBoost很快。
