介绍
在解析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实现比较