介绍
在解析XGBoost的源码之前，我们先理解下陈天奇在paper《XGBoost: A Scalable Tree Boosting System》一文中提到的一些概念。
XGBoost的可扩展性(scalability)归因于一些重要的系统优化和算法优化。这些优化包括：
- 一种新的tree-learning算法(a novel tree learning algorithm)：用于处理稀疏数据(sparse data)
- 一种理论正确的加权分位数略图过程（a theoretically justified weighted quantile sketch procedure）：用于处理在近似的tree-learning中实例权重
由于XGBoost的并行化和分布式计算，使得learning过程比其它模型实现要快。更重要地，XGBoost实现了核外计算(out-of-core computation: 基于外存)，使得数据科学家们可以在pc机上处理上亿的训练实例。最终，会把这些技术结合起来实现一个end-to-end的系统，可以扩展到集群上。
主要内容：
- 1.设计和建立了一个高度可扩展的end-to-end tree boosting系统
- 2.提出了一种理论正确的加权分位数略图过程(theoretically justified weighted quantile sketch procedure)，用于高效地进行预计算
- 3.介绍了一种新的稀疏感知算法（sparsity-aware algorithm），用于并行化tree learning
- 4.提出了一种高效的内存感知块结构（cache-aware block structure），用于核外（out-of-core）tree learning
2.tree-boosting回顾
XGBoost的方法源自于Friedman的二阶方法。XGBoost在正则化目标函数上做了最小的改进。
2.1 正则化目标函数
对于一个含n个训练样本，m个features的结定数据集：$ D = {(x_i,y_i)} (|D|=n, x_i \in R^m, y_i \in R) $，所使用的tree ensemble model使用K次求和函数来预测输出：
\[\hat{y_{i}} = \phi(x_i) = \sum_{k=1}^{K} f_k(x_i), f_k \in F\]…… (1)
其中，$ F = {f(x)=w_{q(x)}}，满足(q: R^m \rightarrow T, w \in R^T) $，是回归树(CART)的空间。q表示每棵树的结构，它会将一个训练样本实例映射到相对应的叶子索引上。T是树中的叶子数。每个$ f_k $对应于一个独立的树结构q和叶子权重w。与决策树不同的是，每棵回归树包含了在每个叶子上的一个连续分值，我们使用$ w_i $来表示第i个叶子上的分值。对于一个给定样本实例，我们会使用树上的决策规则(由q给定)来将它分类到叶子上，并通过将相应叶子上的分值(由w给定)做求和，计算最终的预测值。为了在该模型中学到这些函数集合，我们会对下面的正则化目标函数做最小化：
\[L(\phi) = \sum_{i}l(\hat{y_i}, y_i) + \sum_{i}\Omega(f_k)\]……(2)
其中：$ \Omega(f) = \gamma T + \frac{1}{2}\lambda||\omega||^2 $
其中，$l$是一个可微凸loss函数（differentiable convex loss function），可以计算预测值$\hat{y_i}$与目标值$y_i$间的微分。第二项$ \Omega $会惩罚模型的复杂度。正则项可以对最终学到的权重进行平滑，避免overfitting。相类似的正则化技术也用在RGF模型(正则贪婪树)上。XGBoost的目标函数与相应的学习算法比RGF简单，更容易并行化。当正则参数设置为0时，目标函数就相当于传统的gradient tree boosting方法。
2.2 Gradient Tree Boosting
等式（2）中的tree ensemble模型将函数作为参数，不能使用在欧拉空间中的传统优化方法进行优化。模型以一种叠加的方式进行训练。正式地，$ \hat{y_i}^{(t)} $为第i个实例在第t次迭代时的预测，我们需要添加$ f_t $，然后最小化下面的目标函数：
\[L^{(t)}=\sum_{i=1}^{n}l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i)) + \Omega(f_t)\]这意味着，我们贪婪地添加$ f_t $，根据等式(2)尽可能地提升模型。使用二阶近似可以快速优化目标函数。
\[L^{(t)} \backsimeq \sum_{i=1}^{n}[l(y_i,\hat{y}^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \Omega(f_t)\]其中，$ g_i = \partial_{\hat{y}^{(t-1)}} l(y_i,\hat{y}^{(t-1)}) $ ，$ h_i = {\partial}_{\hat{y}^{(t-1)}}^{2} l(y_i, \hat{y}^{(t-1)}) $分别是loss function上的一阶梯度和二阶梯度。我们可以移除常数项，从而获得如下所示的在t次迭代时的简化版目标函数：
\[L^{(t)} = \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \Omega(f_t)\]……(3)
我们定义$ I_j= \{ i | q(x_i)=j \} $是叶子j的实例集合。将(3)式进行重写，并展开$ \Omega $项：
\[L^{(t)} = \sum_{i=1}^{n} [g_i f_t(x_i) + \frac{1}{2} h_i f_t^{2}(x_i)] + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2} \\ = \sum_{j=1}^{T}[(\sum_{i \in I_j} g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_{j}^{2}]+\gamma T\]……(4)
对于一个确定的结构q(x)，我们可以计算最优的权重 $ w_j^{\ast} $:
\[w_j^{\ast}=-\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i+\lambda}\]……(5)
代入(5)计算得到对应的loss最优解为：
\[L^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i+\lambda} + \gamma T\]……(6)
等式(6)可以作为一个得分函数（scoring function）来衡量一棵树结构q的质量（quality）。该分值类似于决策树里的不纯度(impurity score)，只不过它从一个更宽范围的目标函数求导得到。图2展示了该分值是如何被计算的。
图2:结构得分(structure score)计算。我们只需要在每个叶子上对梯度和二阶梯度统计求和，然后应用得分公式（scoring formula）来获得质量分（quality score）。
通常，不可能枚举所有可能的树结构q。而贪婪算法会从单个叶子出发，迭代添加分枝到树中。假设$ I_L $和$ I_R $是一次划分(split)后的左节点和右节点所对应的实例集合。$ I=I_L \bigcup I_R $，接着，在split之后的loss reduction为：
\[L_{split}=\frac{1}{2}[ \frac{(\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L}h_i+\lambda} + \frac{(\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R}h_i+\lambda} - \frac{(\sum_{i \in I}g_i)^2}{\sum_{i \in I}h_i+\lambda}] - \gamma\]……(7)
该式通常在实际中用于评估split的候选（split candidates）。
2.3 Shrinkage和列子抽样(column subsampling)
除了2.1节所提到的正则化目标函数外，还会使用两种额外的技术来进一步阻止overfitting。第一种技术是Friedman介绍的Shrinkage。Shrinkage会在每一步tree boosting时，会将新加入的weights通过一个因子$ \eta $进行缩放。与随机优化中的learning rate相类似，对于用于提升模型的新增树(future trees)，shrinkage可以减少每棵单独的树、以及叶子空间（leaves space）的影响。第二个技术是列特征子抽样(column feature subsampling)。该技术也会在RandomForest中使用，在商业软件TreeNet中的gradient boosting也有实现，但开源包中没实现。根据用户的反馈，比起传统的行子抽样（row sub-sampling：同样也支持），使用列子抽样可以阻止overfitting。列子抽样的使用可以加速并行算法的计算(后面会描述)。
3.Split Finding算法
3.1 Basic Exact Greedy Algorithm
tree learning的其中一个关键问题是，找到等式(7)的最好划分(best split)。为了达到这个目标，split finding算法会在所有特征（features）上，枚举所有可能的划分（splits）。我们称它为“完全贪婪算法(exact greedy algorithm)”。许多单机版tree-boosting实现中，包括scikit-learn，R’s gbm以及单机版的XGBoost，都支持完全贪婪算法(exact greedy algorithm)。该算法如算法1所示。它会对连续型特征（continuous features）枚举所有可能的split。为了更高效，该算法必须首先根据特征值对数据进行排序，以有序的方式访问数据来枚举等式(7)中的结构得分（structure score）的梯度统计(gradient statistics)。
[算法1]
3.2 近似算法
完全贪婪算法(exact greedy algorithm)很强大，因为它会贪婪地枚举所有可能的划分点。然而，当数据不能整个装载到内存中时，它就变得低效。在分布式设置中也存在相同的问题。为了在两种设置中支持高效地gradient tree boosting计算，需要一种近似算法。
我们总结了一个近似框架（approximate framework），重组了在文献[17,2,22]中提出的思想，如算法2所示。为了进行总结(summarize)，该算法会首先根据特征分布的百分位数(percentiles of feature distribution)，提出候选划分点(candidate splitting points)。接着，该算法将连续型特征映射到由这些候选点划分的分桶(buckets)中，聚合统计信息，基于该聚合统计找到在建议（proposal）间的最优解。
[算法2]
该算法有两个变种，取决于给定的建议（proposal）。全局变种（global variant）会在树构建的初始阶段，建议所有的候选划分，并在所有的层级（level）上使用相同的建议。局部变种（local variant）则在每次划分后重新建议（re-proposes）。比起局部法，全局法需要更少的建议步骤。然而，对于全局建议，通常需要更多的候选点，因为在每次划分之后，不需要重新定义候选。局部建议会在每次划分后重新定义候选，对于更深的树更合适。图3展示了在Higgs boson数据集上不同算法的比较。我们发现，局部建议确实需要更少的候选。如果两者的候选一样多，全局建议比局部建议会更精确。
图3: 在Higgs 10M数据集上的Test AUC收敛比较. eps参数对应于在近似略图（approximate sketch）上的accuracy。这大约可以在proposal中转换成1/eps buckets。我们发现local proposals需要更少的buckets，因为它会重新定义划分候选（split candidates）
大多数分布式tree learning近似算法都遵循该框架。显著的，也可以直接构建近似的梯度统计直方图（approximate histograms of gradient statistics）。也可以使用二分策略（binning strategies）来替代分位数（quantile）。分位数策略(quantile strategy)可以从分布式（distributable）和重计算（recomputable）中受益，详见下一节。从图3中可知，我们发现：给定合理的近似级别（approximation level），分位数策略(quantile strategy)可以获得与exact greedy算法相同的准确率。
对于单机设置，我们的系统高效地支持exact greedy；对于单机和分布式设置，也同时支持带local和global proposal方法的近似算法。用户可以根据需要自由选择。
3.3 加权分位数略图(Weighted Quantile Sketch)
在近似算法中很重要的一步是，提出候选划分点。通常，一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: $ D_k={(x_{1k}, h_1),(x_{2k},h_2),…(x_{nk},h_n)} $，来表示每个训练实例的第k个特征值以及它的二阶梯度统计。我们可以定义一个排序函数（rank functions）：$ r_k=R \rightarrow [0,+\infty) $：
\[r_{k}(z)=\frac{1}{\sum_{(x,h) \in D_k} h} \sum_{(x,k) \in D_k,x<z}^{} h\]……(8)
它表示相应第k个特征上的输入值小于z的实例的占比。它的目标是，找好候选划分点 $ {s_{k1}, s_{k2}, …, s_{kl}} $，例如：
\[\|r_k(s_{k,j}) - r_k(s_{k,j+1})\| < \epsilon, s_{k1}=min_{i}^{} x_{ik}, s_{kl}=max_{i}^{} x_{ik}\]……(9)
其中$ \epsilon $是近似因子（approximation factor）。直觉上，这意味着大约是 $ \frac{1}{\epsilon} $个候选点。这里，每个数据点通过$h_i$加权。为什么$h_i$可以表示权重呢？我们可以重写(3)式：
\[\sum_{i=1}^{n}\frac{1}{2}h_i(f_t(x_i)-g_i/h_i)^2 + \Omega(f_t) + constant\]它就是真正的加权squared loss，labels为$g_i/h_i $，权重为$h_i$。对于大数据集来说，要找到满足该原则（criteria）的候选集是不容易的。当每个样本实例都具有相同的权重时，有一种已经存在的算法可以解决该问题：分位数略图（quantile sketch）。因而，大多数已存在的近似算法，或者会重新排序来对数据的一个随机子集进行排序（有一定的失败率），或者是启发式的（heuristics），没有理论保障。
为了解决该问题，XGBoost引入了一种新的分布式加权分位数略图算法（distributed weighted quantile sketch algorithm），使用一种可推导证明的有理论保证的方式，来处理加权数据。总的思想是，提出了一个数据结构，它支持merge和prune操作，每个操作证明是可维持在一个固定的准确度级别。算法的详细描述在这里。
3.4 稀疏感知的划分查找（sparsity-aware Split Finding）
在许多现实问题中，输入x是稀疏的。有多种可能的情况造成稀疏：
- 1)数据中的missing values
- 2)统计中常见的零条目
- 3)特征工程：比如one-hot encoding
图4: 带缺省方向的树结构。当在split时相应的feature缺失时，一个样本可以被归类到缺省方向上
让算法意识到数据中的稀疏模式很重要。为了这么做，我们提出了在每个树节点上增加一个缺省的方向（default direction），如图4所示。当稀疏矩阵x中的值缺失时，样本实例被归类到缺省方向上。在每个分枝上，缺省方向有两种选择。最优的缺省方向可以从数据中学到。如算法3所示。关键的改进点是：只访问非缺失的条目$I_k$。上述算法会将未出现值（non-presence）当成是一个missing value，学到最好的方向来处理missing values。当未出现值对应于一个用户指定值时，应用相同的算法，可以通过将枚举(enumeration)限定到一致的解上。
[算法3]
据我们所知，大多数已存在的tree learning算法，或者只对dense data进行优化，或者需要指定函数来处理受限的情况：比如对类别编码（categorical encoding）。XGBoost以统一的方式处理稀疏模式。更重要的是，我们的方法充分使用稀疏性，它的计算复杂度与在输入中的未缺失条目(non-missing entries)的数目成线性关系。图5展示了在Allstate-10K数据集上稀疏感知和naive实现间的比较。我们发现，稀疏感知算法比naive版本要快50倍。这证实了稀疏感知算法的重要性。
图5: 稀疏感知算法（sparsity aware algorithm）在Allstate-10K上的影响。数据集很稀疏，主要因为one-hot编码。稀疏感知算法比naive版本（不会考虑稀疏性）要快50倍。
4.系统设计
4.1 用于并行学习的Column Block
tree learning最耗时的部分，是以有序方式获得数据。为了减少排序的开销，我们提出了将数据存储到内存单元（in-memory units）中，它们被称为“块（block）”。每个块中的数据，以压缩列（CSC）格式存储。每列由相应的特征值进行排序。输入数据的布局，在训练前只需要计算一次，在后续迭代中可复用。
在exact greedy algorithm中，我们将整个数据集存储到单个块中，通过对预排序的条目进行线性扫描的方式，来运行split search算法。我们会对所有叶子共同进行split finding算法，因而，在块上的一次扫描，将收集到在所有叶分枝上的划分候选的统计信息。图6展示了，我们如何将一个数据集转成该格式，并找到使用该块结构的最优划分（optimal split）。
图6: 用于并行学习的块结构。块中的每个列通过相应的特征值(feature value)进行排序。在块中的某列上进行一次线性扫描，足够枚举所有的划分点
当使用近似算法时，块结构也有用。这种情况下，可以使用多个块，每个块对应于数据集中行的子集。不同的块可以跨机器分布，或者以out-of-core设置的方式存储在磁盘中。使用排序过的结构，quantile finding步骤会在排好序的列上进行一次线性扫描（linear scan）。这对于局部建议算法（local proposal algorithms）特别有用，局部法的候选集通常在每次划分时生成。在直方图聚合(histogram aggregation)上进行二分查找，也变为一个线性时间的merge style算法。
为每列收集统计信息可以并行化，给定一个并行化算法来处理split finding。更重要的是，列块（column block）结构也支持列子抽样（column subsampling），它可以很容易地在一个块中选择列的一个子集。
时间复杂度分析
d为树的最大深度，K为树的总树目。对于exact greedy algorithm，原始的稀疏感知算法的时间复杂度：
\[O(K d |x|_{0}logn)\]这里，我们使用 \(|x|_{0}\) 来表示在训练数据中未缺失条目（non-missing entries）的数目。另一方面，块结构上的tree boosting的开销为：
\[O(Kd {|x|} _0 + {|x|}_{0}logn)\]这里， \(O( {\|x\|}_{0}log n)\) 是一次预处理开销(one time preprocessing cost)，可以分期(be amortized)。该分析展示了块结构可以帮助节省一个额外的$ log n $因子，其中当n非常大时就很大。对于近似算法，使用二分查找的原始算法时间复杂度为：
\[O(K d {|x|}_{0} log q)\]这里的q是在数据集中建议候选的数目。其中，q通常为32~100之间，log因子仍会引入间接开销。使用块结构，我们可以将时间减小到：
\[O(K d{|x|}_{0} + {|x|}_{0} logB)\]其中B是在每个块中的行的最大数。同样的，我们可以在计算中节约额外的log q因子。
4.2 内存感知访问（Cache-aware Access）
建议的块结构（the proposed block structure）可以帮助优化split finding的计算复杂度，新算法需要通过行索引（row index）间接取得梯度统计(gradient statistics)，因为这些值是以特征的顺序被访问的。这是非连续内存访问（non-continuous memory）操作。枚举划分（split enumeration）的naive实现，在累加(accumulation)与非连续内存读取操作(non-continuous memory fetch）间（详见图8），引入了立即读写依存（immediate read/write dependency）。当梯度统计（gradient statistics）不能装载进CPU cache里，或者cache miss发生时，会减慢split finding。
图8: 短范围内的数据依赖模式，由于cache miss，可引起停转（stall）
对于exact greedy algorithm，我们通过内存感知预取（cache-aware prefetching）算法来减缓该问题。特别的，我们在每个thread上分配一个internal buffer，获取gradient statistics存到该buffer中，接着以一种mini-batch的方式来执行累计（accumulation）。这种预取法将直接读/写依存，改变成一种更长的依存，当行的数目很大时可以帮助减少运行时开销。图7给出了在Higgs数据集和Allstate数据集上cache-aware vs. no cache-aware 的比较。当数据集很大时，我们发现exact greedy algorithm的cache-aware实现比naive版本的实现要快两倍。
图7: 在exact greedy algorithm中，cache-aware prefetching的影响。我们发现，cache-miss会在大数据集（1000w实例）上影响性能。使用cache-aware prefetching，可以提升数据集很大时的性能。
对于近似算法，我们通过选择一个合适的块大小（correct block size）来解决该问题。我们将块大小（block size）定义为在一个块中包含样本的最大数目，它会影响梯度统计的cache存储开销（cache storage cost）。选择一个过小的block size会导致每个thread会小负载（small workload）运行，并引起低效的并行化(inefficient parallelization)。在另一方面，过大的block size会导致cache miss，梯度统计将不能装载到CPU cache中。block size的好的选择会平衡两者。我们比较了在两个数据集上的block size的选择。结果如图9所示。结果展示选择在每个块上有$ 2^{16} $个样本时，会对cache property和parallelization做很好的平衡。
图9: 在近似算法中，block size的影响。我们发现，过小的块会引起并行化很低效，过大的块由于cache miss会让训练慢下来
4.3 Out-of-core计算
XGBoost的其中一个目标是，充分利用机器资源来达到可扩展的learning（scalable learning）。除了处理器和内存外，很重要的一点是，使用磁盘空间来处理不能完全装载进主存的数据。为了达到out-of-core计算，我们将数据划分成多个块，将每个块存到磁盘上。然而，这不能整体解决该问题，因为磁盘读（disk reading）会花费大多计算时间。减小开销和增加磁盘IO吞吐量很重要。我们主要使用两种技术来提升out-of-core计算。
块压缩（Block Compression） 块通过列(column)进行压缩，当加载进主存时可以由一个独立的线程即时解压(decompressed on the fly)。它会使用磁盘读开销来获得一些解压时的计算。我们使用一个通用目的的压缩算法来计算特征值。对于行索引（row index），我们从块的起始索引处开始抽取行索引，使用一个16bit的整数来存储每个偏移(offset)。这需要每个块有$ 2^{16} $个训练样本，这证明是一个好的设置。在我们测试的大多数数据集中，我们达到大约26% ~ 29%的压缩率。
块分片（Block Sharding） 第二个技术是，在多个磁盘上以一种可选的方式共享数据。一个pre-fetcher thread被分配到每个磁盘上，取到数据，并装载进一个in-memory buffer中。训练线程（training thread）接着从每个bufer中选择性读取数据。当提供多个磁盘时，这可以帮助增加磁盘读(disk reading)的吞吐量。
表1: 主要的tree boosting实现比较