1 论文简介
XGBoost的作者是曾在华盛顿大学研究机器学习的大牛陈天齐，XGBoost全称是eXtreme Gradient Boosting，从名称看XGBoost仍然是GBDT，在GBDT基础上优化和增强。XGBoost以出众的效率和较高的预测准确率在各大算法比赛中被广泛使用。这篇文章介绍了XGBoost这种可扩展、端到端的Boosting Tree的新算法。
文章先介绍了Boosting Tree在现在机器学习领域中非常出彩，而XGBoost作为一种先进的Boosting Tree，被各大比赛的选手们广泛使用。2015年的Kaggle和KDDCup中，所有top排名的队伍都使用XGBoost。
XGBoost成功背后的最重要因素是在所有情况下的可扩展性。XGBoost在单台机器上的运行速度比现有流行解决方案快十倍以上，可在分布式或内存有限的环境中扩展到数十亿个实例。XGBoost的可扩展性是由于几个重要的系统和算法优化。文章介绍了这些创新：一种新颖的
稀疏数据感知算法，用于处理稀疏数据；一种
合理的加权分位数略图(weighted quantile sketch)能够在近似学习中处理有权重特征的数据。论文还提出了
缓存访问模式，
数据压缩和分片的方法。通过结合这些方法，XGBoost可扩展、并行和分布式处理使学习速度更快，用比现有系统少得多的资源来处理数十亿规模的数据。
2 Boosting Tree简介
2.1 Boosting Tree正则化项优化
文章先简单介绍了Gradient Boosting Tree。使用k棵独立的回归树（CART）使用Boosting集成预测，F包含所有k棵树。
这里，q是映射到树叶子节点索引的函数，T是叶子节点数，w是叶子权重，连续值，也叫score，是映射到该节点的预测值。
下图是Boosting Tree集成学习的示例。tree1中，+2是预测男孩对游戏感兴趣的权重w1，tree2中，+0.9是对男孩的权重w2。最终预测结果是两棵树的score简单加和。
下图是Boosting Tree的目标函数，前一项l是损失项，描述模型拟合训练数据的优劣，从训练数据预测有多好。后一项Ω是正则化项，Ω作为惩罚项减少模型复杂度，能平滑权重系数防止过拟合。这里
是叶子数，w是叶子权重，分别是L1和L2的正则化项。
下图是Boosting tree目标函数的另一种写法。根据加法模型，
第t棵树是在第t-1棵树的基础上学习优化而来，根据t-1棵树的预测值，计算残差，再拟合第t棵残差树。
注意：这里
残差，是下一轮要预测的目标值。
是泰勒公式里的
。
这里用到了高数知识泰勒展开公式。
根据泰勒二阶展开，g和h是损失函数的一阶和二阶导数。
对上式去掉常数项，这里t-1棵树的loss已经计算出来，可以作为常数项去除。（待进一步明确）
使用公式（2）替换公式（3）中的惩罚项。
目标函数现在是w的函数。对w求导求极值，令求导结果等于0。
可得到目标函数的最优值。w越小，树的结构就越好，预测的越好。
把公式（5）带回到公式（4），计算平方后合并同类项，
目标函数（6）是score函数，可用来衡量树结构质量的优劣和预测的好坏。
可以穷举所有的树结构q，利用公式（6）计算每棵树score，利用公式（5）优化叶节点权重，求最小化权重w。但树是无限多的，不可能穷举。实际中使用贪心算法，从一个节点出发，分割后形成一棵树。分割点的选择使用下图公式Gain的计算来选择。
HL左子树分数，HR右子树分数，第三项是不分割可以得到的分数。减第三项表示分割后比分割前变化量，
最后一项
是加入新叶子节点引入的复杂度代价
公式（7）同上，是Gain的另一种写法。
2.2 Shrinkage和subsampling防止过拟合
除了正则化项，Boosting Tree还加入了两项技术防止过拟合。第一项Shrinkage类似于随机梯度下降的步长（学习率），shrinkage是每次tree boosting后增加的学习率权重，能减少个体的影响，为后续的tree boosting留下更多空间，防止在构建某棵树时过拟合。第二项subsampling类似于RF里的列抽样，除了防止过拟合，subsampling还能在后续章节提到的并行计算加速计算。
3 如何寻找分割点的算法
3.1 传统贪心算法（Basic Exact Greedy Algorithm）
传统贪心算法，遍历所有分割点，选择最优分割点。如果有2个特征组合，一共有4对取值，穷举后要计算4次才能选择最优分割点。
传统算法必须先对特征值排序，然后遍历数据计算梯度值。缺点就是效率差，数据可能都不能全放进内存。
3.2 近似算法（Approximate Algorithm）
近似算法和传统贪心算法遍历所有分割点的做法不同，根据特征分位数的分布情况，给出备选特征分割点的建议（proposal）。
近似算法建议有两种方法，
Global方法在建树前对所有候选特征做分割选择，给出建议。并且在下层子树构建时都用建树时同样的选择。Global全局考虑，所以需要更多的候选特征。
Local方法在每次分割后re-propose，是对global分割后的优化，local方法提出的重新优化分割更精确，在更深的子树上分割更精确。但Local需要的候选特征更少。
现有的近似算法中，可以直接使用梯度分位数统计信息，也可以使用其他如二分策略（binning strategy）。梯度分位数统计在后续章节的分布式计算表现出色，甚至可接近传统贪心算法的准确度。
3.3 加权分位数略图 （weighted quantile sketch）
近似算法很重要的一步就是找到备选分割点。通常情况会均匀挑选一个特征的分位数作为候选。集合
表示样本第k个特征的特征值，h表示第n个样本损失函数的二阶梯度。据此定义一个排序函数：
（式8）
对于每个分割点，其函数值
表示用此分位点下包含的二阶导之和的比例
函数目标是找到一组候选的分割点
满足条件（式9）。即相邻的两个分割点之间的间隔小于给定的ε。这里的ε是一个近似系数。
直观上看，这大致表示总共选出1/ε个候选点。这里每一个点都按照其二阶导h进行加权。为了说明为何可以使用二阶导h作为权重，可以把等式3改写成如下形式。
即gi/hi做label时的L2损失平方乘以hi作为权重。
对于大规模数据集来说，很重要的是寻找符合条件的候选分割点。已有的分位数略图算法可以解决当样本权重相同时的问题。然而，还没有哪个现成的分位数略图算法可以解决权重不同的样本数据。因此，大多数近似算法使用随机抽样或启发式的方法，这些方法要不是有失败的可能，要不就是没有理论支撑。
为了解决这个问题，论文引入了一个新颖的，有理论支撑的分布式加权分位数略图算法，其大意是提出一个可以支持融合与剪枝操作的数据结构。而每一个合并与剪枝操作又能保证一定量级上的准确度。细节算法和证明见原论文中的链接。（待进一步阅读）
3.4 稀疏数据感知分割算法（Sparsity-aware Split Finding）
现实数据出现稀疏矩阵（Sparsity）非常普遍，比如存在缺失值，大量的0值，特征工程使用one hot encoding独热编码。因此，在每个树节点增加缺省方向，让算法知道当数据出现稀疏的情况，仍能快速准确分割。
如下图所示，红色是树节点的缺省方向，样本X2中性别是缺失值，根据缺省方向仍然可以被分割。
确定缺省方向有两种方法，最优方法也是default使用的是，只收集非缺失值，从非缺失值数据的统计信息学习到最好的缺省方向。
和其他算法相比，XGBoost能很好处理稀疏数据，随着数据量复杂度线性增长。使用稀疏矩阵感知算法的XGBoost，在实验中比其他算法快50倍，
4 系统实现
4.1 块存储
数据按列排序后在内存中以块（block）存储
排序很费时间，因此数据按列排序后在内存中以块存储，块中数据按列排序后以列压缩（CSC）方式存储。所有样本数据在计算前只需做一次排序，后续迭代多次使用排序结果。
传统贪心算法里，把所有数据集存储在一个block里，分割时可对预先排序的数据线性查找。因此一次扫描获得的数据统计信息，可以在后续各级分支计算上多次使用。
下图描述了这个过程。
在近似算法中，块结构也非常有用。整个数据使用多个块，每个块是整个数据集的子集。多个块可以分布在多台机器上，也可以从内存放在磁盘上。块中预排序的数据，分位数的计算分割也可以线性扫描。Local propose可以很方便在一个分支上频繁的做优化建议，二分搜索（binary search）也可在合并算法上线性计算。
在并行分割搜索时，可并行为每列数据收集统计信息，更有效率。块结构也能在列抽样（subsampling）操作时很方便选取列数据。
传统贪心算法的复杂度是
，d是树的最大深度，K棵树，
是数据中非缺失的样本数。如果使用块结构，Tree Boosting的复杂度是
，这里
是一次预处理排序，因此块结构节省了logn系数的开销。
近似算法中，二分查找算法的复杂度是
，这里q是特征数，通常特征数量是32到100，logq还是有一定开销。如果使用块结构，复杂度是
，B是块中能包含的最大行数。块结构也节省了logq系数的开销。
4.2 缓存访问机制
块结构方法简化了节点分割计算时的复杂度，但会频繁读取不连续内存里的行数据，内存不连续降低了节点分割计算的速度。
缓存访问机制能解决传统贪心算法里访问不连续内存数据的问题。先把梯度统计信息数据放在每个线程的缓存里，能直接在内存中读写，减少运行开销。
下图显示了在大数据量比较（10M）中，缓存访问机制比无缓存快2倍速度。值得注意的数据量1M时，缓存访问机制没有明显的速度提升。
近似算法里，调整合适的块结构大小能减少运行开销。如果选择太小的块结构不能充分发挥并行特性，太大的块结构可能使梯度统计信息不能装入cache，缓存无法命中。考虑这两种情况要选择合适的块大小。从下图两个数据集给出的实验结果，选择每个块中包括
样本的块大小效果最好，同时平衡了缓存命中和并行。
4.3 磁盘数据的块压缩和数据分片技术
当数据不能全部装入内存，数据以块存储在磁盘上。除了CPU和内存，也充分对磁盘读取进行优化。
主要有2个技术，块压缩技术对磁盘上的block按列做压缩。
数据分片技术，把数据分片到多个磁盘上，每个磁盘分别存储数据并读取到内存中。这两个技术都增加了磁盘吞吐量。
5 总结
论文读毕，深感作者考虑全面。
论文介绍XGBoost在目标函数设计上增加了L1和L2正则项，限制叶子节点数目，降低叶子权重。同时Shrinkage能降低步长，消除个别树过拟合，为后续树提升留出更多空间。
在算法设计上，论文提出近似算法，global全局考虑分割点，local细节优化global后的分割结果。加权分位数从分位数统计信息提升近似算法性能。缺省方向在实战中为稀疏数据树的分割提供帮助。
在系统实现上，XGBoost 提出了块结构，Cache存取，磁盘数据的压缩和分片技术。
综合看，XGBoost从CPU（算法设计），MEM（Cache），Disk（压缩和分片）各方面考虑，极尽优化之能。XGBoost既快又准，横扫各大比赛成为大杀器令人称道。
相关文献：
《
XGBoost: A Scalable Tree Boosting System》 : Tianqi Chen, Carlos Guestrin
XGBoost Documentation