Press "Enter" to skip to content

XGBoost原理解析

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

摘要:对xgboost论文中的细节进行记录。

 

算法原理

 

系统设计

 

基于column block的并行

 

 

树学习最耗时的部分通常是对数据进行排序,为了降低排序带来的计算负荷,xgb使用基于block的结构对数据进行存储。每个block中的数据以compressed format(CSC)格式存储,每列按照数值大小进行排序。这样的数据结构仅需要在训练前计算一次,在后续的迭代过程中,可以重复使用。

 

对于精确算法,将所有数据保存在一个block中。建树的过程可以实现特征级别的并行,即每个线程处理一个特征。在单个线程内部,对数据的单次扫描可计算所有叶子节点在该特征上的最优分裂点。

 

对于近似算法,可以将不同的数据(按行)分布在不同的block中,并可以将不同的block分布到不同的机器。使用排好序的数据,qutile finding算法只需要线性扫描数据即可完成。

 

利用这样的结构,在对单个特征寻找分裂点时,也可以实现并行化,这也是xgb能够进行分布式并行的关键。

 

缓存感知(cache aware access)

 

block结构降低了计算的复杂度,但也带来了另外一个问题,那就是对梯度信息的读取是不连续的,如果梯度信息不能全部装进cache,这会导致cpu缓存命中率降低,从而影响性能。

 

在精确算法中,xgb使用cache-aware prefetch算法缓解这个问题。也就是为每个线程分配一个buffer,将梯度信息读入buffer,并以mini-batch的方式进行梯度累加。

 

对于近似算法,解决缓存命中失效的方法是选择合适的block size。过小的block size导致单线程的计算负载过小,并行不充分,过大的block size又会导致cache miss,因此需要做一个平衡。论文建议使用的block size为2^16。

 

核外计算(out of core computation)

 

为进行核外计算,将数据划分为多个block。计算期间,使用独立线程将磁盘上的block结构数据读进内存,因此计算和IO可以同步进行。然而,这只能解决一部分问题,因为IO占用的时间要远多于计算。因此,xgb使用以下两种方式优化:

 

数据压缩(block compression):将block按列进行压缩,并使用独立线程解压缩。这样可以对IO和CPU的占用时间进行对冲。

 

数据分区(block sharding):将数据分散到多个磁盘,每个磁盘使用一个线程读取数据,以此提高磁盘吞吐量。

 

单机精确算法实现

 

在XGBoost的实现中,对算法进行了模块化的拆解,几个重要的部分分别是:

 

I. ObjFunction:对应于不同的Loss Function,可以完成一阶和二阶导数的计算。

 

II. GradientBooster:用于管理Boost方法生成的Model,注意,这里的Booster Model既可以对应于线性Booster Model,也可以对应于Tree Booster Model。

 

III. Updater:用于建树,根据具体的建树策略不同,也会有多种Updater。比如,在XGBoost里为了性能优化,既提供了单机多线程并行加速,也支持多机分布式加速。也就提供了若干种不同的并行建树的updater实现,按并行策略的不同,

 

I). inter-feature exact parallelism (特征级精确并行)

 

II). inter-feature approximate parallelism(特征级近似并行,基于特征分bin计算,减少了枚举所有特征分裂点的开销)

 

III). intra-feature parallelism (特征内并行)

 

IV). inter-node parallelism (多机并行)

 

此外,为了避免overfit,还提供了一个用于对树进行剪枝的updater(TreePruner),以及一个用于在分布式场景下完成结点模型参数信息通信的updater(TreeSyncher),这样设计,关于建树的主要操作都可以通过Updater链的方式串接起来,比较一致干净,算是Decorator设计模式的一种应用。

 

XGBoost的实现中,最重要的就是建树环节,而建树对应的代码中,最主要的也是Updater的实现。所以我们会以Updater的实现作为介绍的入手点。

 

updater_colmaker.cc:
ColMaker::Update()
     -> Builder builder;
     -> builder.Update()
          -> InitData()
          -> InitNewNode() // 为可用于split的树结点(即叶子结点,初始情况下只有一个
                           // 叶结点,也就是根结点) 计算统计量,包括gain/weight等
          ->  for (depth = 0; depth < 树的最大深度; ++depth)
               -> FindSplit()
                    -> for (each feature) // 通过OpenMP获取
                                          // inter-feature parallelism
                         -> UpdateSolution()      
                              -> EnumerateSplit()  // 每个执行线程处理一个特征,
                                                   // 选出每个特征的
                                                   // 最优split point
                              -> ParallelFindSplit()   
                                   // 多个执行线程同时处理一个特征,选出该特征
                                   //的最优split point; 
                                   // 在每个线程里汇总各个线程内分配到的数据样
                                   //本的统计量(grad/hess);
                                   // aggregate所有线程的样本统计(grad/hess),       
                                   //计算出每个线程分配到的样本集合的边界特征值作为
                                   //split point的最优分割点;
                                   // 在每个线程分配到的样本集合对应的特征值集合进
                                   //行枚举作为split point,选出最优分割点
                         -> SyncBestSolution()  
                               // 上面的UpdateSolution()/ParallelFindSplit()
                               //会为所有待扩展分割的叶结点找到特征维度的最优split 
                               //point,比如对于叶结点A,OpenMP线程1会找到特征F1 
                               //的最优split point,OpenMP线程2会找到特征F2的最
                               //优split point,所以需要进行全局sync,找到叶结点A
                               //的最优split point。
                         -> 为需要进行分割的叶结点创建孩子结点     
               -> ResetPosition() 
                      //根据上一步的分割动作,更新样本到树结点的映射关系
                      // Missing Value(i.e. default)和非Missing Value(i.e. 
                      //non-default)分别处理
               -> UpdateQueueExpand() 
                      // 将待扩展分割的叶子结点用于替换qexpand_,作为下一轮split的
                      //起始基础
               -> InitNewNode()  // 为可用于split的树结点计算统计量

 

 

ColMaker的整个建树操作中,最tricky的地方应该是用于支持intra-feature parallelism的ParallelFindSplit(),关于这个计算逻辑,上面有一些文字描述,辅助下图可能会更为直观:

XGB vs GBDT

传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。
传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。
xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。
Shrinkage(缩减),相当于学习速率(xgboost中的eta)。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把eta设置得小一点,然后迭代次数设置得大一点。(补充:传统GBDT的实现也有学习速率)
列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。
对缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。
xgboost工具支持并行。xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那幺各个特征的增益计算就可以开多线程进行。
可并行的近似直方图算法。树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点.

参考链接

 

https://arxiv.org/pdf/1603.02754.pdf

 

http://www.ra.ethz.ch/CDstore/www2011/proceedings/p387.pdf

 

https://www.zhihu.com/question/41354392

 

https://weibo.com/p/1001603801281637563132

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注