FastDBT和LightGBM在XGBoost之后提出，FastBDT针对多类别问题进行了优化，从实现层面获得了更快的训练速度，LightGBM则在树的生成进行了改进，文章按以下思路介绍

  1. FastDBT简介及代码走读，LightGBM简介
  2. 从算法层面讨论下三者的异同点

FastDBT篇

树模型从模型层面和实现层面两种可行的改进方式：1.模型层面的改进：如SGBDT采用的样本采样方式[1]，或者对弱作用特征的剪枝[2]。2.实现层面的改进，见引文[3].FastDBT延续自SGBDT，SGBDT在每层树的构建中并非所有样本都使用到，按参数$\alpha$对数据进行随机采样。
FastDBT有如下三个实现层面上的加速：

  1. 数据在内存的存储方式，分为两种a.结构体数据，b.数组结构体，如下图1。区别在于当对其中一维特征进行遍历的时候，按数组结构体的方式存储使得内存连续，提升内存访问速度。
  2. 将正例负例进行区分存储，减少一半左右的计算累计直方图(calculation of the cumulative probability histograms， CPH)缓存占用，同时节约了if判断条件跳转的浪费。
  3. 同层节点并行计算。由于每层的节点的数据来自于被父节点分割的子集，FastBDT在对不同的节点同时计算CPH（临时存储多个节点点的CPH），可以连续进行内存访问避免跳跃。
    图1：数据内存布局

下面进行FastDBT建树部分代码走读：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
main()
  ->train()
    ->data=readDataFile() //data结构为：vector<vector<float>>
    //上一步数据作为2D向量读入
    //FastDBT需要分桶后的数据,使用FeatureBinning对每个特征进行数据分桶。
    //先初始化FeatureBinning，对于每个特征，遍历所有样本对应的特征值，进行分桶边界的初始化
	for(unsigned int iFeature = 0; iFeature < numberOfFeatures; ++iFeature)
	    //枚举特征，得到每个特征特征值列表
        std::vector<double> feature;
        feature.reserve(numberOfEvents);
        for(auto &event : data) 
          feature.push_back( event[iFeature] )
        //根据特征值进行对应桶的设定，
        featureBinnings.push_back(FastBDT::FeatureBinning<double>(nCuts, feature)); 
        nBinningLevels.push_back(nCuts)
 
   //eventSample存储完成特征值->分桶index的数据
   //将数据分为signal和background两个部分（1为signal，0为background），提供更快地访问速度
   for(auto &event : data)
     for(unsigned int iFeature = 0; iFeature < numberOfFeatures; ++iFeature)
	   //找到当前样本特征值对应特征所属的桶
       bins[iFeature] = featureBinnings[iFeature].ValueToBin( event[iFeature])
       // bins存有该样本的，权重为1
	   //signal取决于数据的_class标签是否为1;1则是正例，否则为负例。
        eventSample.AddEvent(bins, 1.0, _class == 1)
        
    //ForestBuilder类负责树模型的训练
    //输入为数据eventSample，树的个数nTrees
	//树的正则化因子Shrinkage，采样率randRatio,层数nLevels
    FastBDT::ForestBui1lder dt(eventSample, nTrees, shrinkage, randRatio, nLevels)
    //将生成的树组合为forest
    FastBDT::Forest<double> forest( dt.GetShrinkage(), dt.GetF0(), true)
    for( auto t : dt.GetForest() )
    //将树的节点由index转为特征值
      auto tmp=removeFeatureBinningTransformationFromTree(t,            
               featureBinnings)
      forest.AddTree(tmp)

有几个实现细节比较trick需要提一下

  1. FeatureBinning的内部实现采用了二分查找树（调了几个小时代码没弄明白，幸亏Thomas解答并帮忙增加了注释）
    特征值分桶核心代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //枚举每一层树
    for(uint64_t iLevel = 0; iLevel < nLevels; ++iLevel):
      //桶的数目double
      const uint64_t nBins = (1 << iLevel)
      //枚举每个桶
      for(uint64_t iBin = 0; iBin < nBins; ++iBin) {
      //记特征值下标为 size/2^(iLevel+1)+iBin*size/2^iLevel
      //第bin_index指向的有序特征的对应二分查找位置
      binning[++bin_index] = \
        first[(size >> (iLevel+1)) + ((iBin*size) >> iLevel)]

  2. ForestBuilder类的初始化时完成SGBDT每一棵树的级联
    boosting过程的核心代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //生成nTrees棵树
    for(unsigned int iTree = 0; iTree < nTrees; ++iTree):   
    // Update the event weights according to their F value
    // 使用对应的F值进行更新每个样本的权重，F值为pseudo_response
    updateEventWeights(sample)
    // Prepare the flags of the events
    // 根据randRatio进行采样，eventsamples内有flag可以标记样本是否可用
    prepareEventSample(sample, randRatio, sPlot ) 
    // TreeBuilder类进行单棵树的生成, nLayersPerTree为树的层
    TreeBuilder builder(nLayersPerTree, sample)
    //将生成的树加入到森林中
    forest.push_back( Tree<unsigned int>( builder.GetCuts(), \
          builder.GetNEntries(), builder.GetPurities(), \
          builder.GetBoostWeights() ) )

  3. TreeBuilder类完成单棵树的生成
    TreeBuilder核心代码走读：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //生成每一棵树需要探索的节点，存在nodes列表
    for(unsigned int iLayer = 0; iLayer <= nLayers; ++iLayer) 
      for(unsigned int iNode = 0; iNode < (1<<iLayer); ++iNode)
            nodes.push_back( Node(iLayer, iNode) );
    // 每棵树的节点是从顶向下，从左到右生成，
    // 树是贪心法生成，我们迭代计算每一层的节点
    // 对于不同的分裂节点和特征，生成正负例的累计直方图
    for(unsigned int iLayer = 0; iLayer < nLayers; ++iLayer) 
      //计算累计直方图，signal,background分别计算
      //由于signal,background在存储上物理分离，可以进行连续访问
      CumulativeDistributions CDFs(iLayer, sample) 
      //选择合适的特征和值，更新到当前节点
      UpdateCuts(CDFs, iLayer) 
      //采样数据，SGBDT特有操作
      UpdateFlags(sample) 
      //根据分裂节点划分样本
      UpdateEvents(sample, iLayer)

  4. 计算累计直方图，得到正例和负例的累计直方图

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //对于所有在这一层的节点，每一个特征，填充累计直方图bins
    //将每个特征的bins进行填充
    for(int iEvent = firstEvent; iEvent < lastEvent; ++iEvent)
      for(int iFeature = 0; iFeature < nFeatures; ++iFeature )
        int subindex = nBinSums[iFeature] + values.Get(iEvent,iFeature);
        bins[index+subindex] += weights.Get(iEvent);
        //在前一步得到的bins中，顺序累计所有的桶内的值，得到累计直方图
      for(int iNode = 0; iNode < nNodes; ++iNode) {
        for(int iFeature = 0; iFeature < nFeatures; ++iFeature)
        // 从位置2起始是因为0位置放置非自然数
        for(int iBin = 2; iBin < nBins[iFeature]; ++iBin)
          unsigned int index = iNode*nBinSums.back() \
                               + nBinSums[iFeature] + iBin;
          bins[index] += bins[index-1];

  5. 根据正负例的累计直方图，查找最优分裂点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    Weight currentLoss = LossFunction(signal, bckgrd);
    //遍历每一个特征的每一个桶
    for(int iFeature = 0; iFeature < nFeatures; ++iFeature)
      // 从位置2起始是因为0位置放置非自然数
      for(unsigned int iCut = 2; iCut < nBins[iFeature]; ++iCut) {
        Weight s = CDFs.GetSignal(iNode, iFeature, iCut-1);
        Weight b = CDFs.GetBckgrd(iNode, iFeature, iCut-1);
        //计算基尼系数，从函数看这里应该是简化的基尼系数
        Weight currentGain = currentLoss - \
                LossFunction( signal-s, bckgrd-b ) - LossFunction( s, b );
    	if( cut.gain <= currentGain ) 
            cut.gain = currentGain;
            cut.feature = iFeature;
            cut.index = iCut;
            cut.valid = true;

到这里为止，我们已经看完几个重要的模块，关于FastBDT的介绍告一段落，有需要的同学可以继续在github上阅读更详细的代码，附上代码仓库地址。

LightGBM篇

LightGBM主要思路还在GBDT框架内，重复部分不再赘述，这篇我打算偷个懒，把LightGBM的新特性细数一遍，当然附上详细的算法文档，里面介绍很到位：《LightGBM中的GBDT实现》@chenghuige 网盘地址，代码仓库地址。

  1. 单机采用Histogram算法，这点同FastBDT一样，而XGboost单机是Greedy进行的。
  2. 大多数GBDT工具(FastDBT/XGboost)按逐层(level wise)的方式进行生长，而LightGBM从当前节点出发找到一个分类增益最大的叶子，然后继续分裂(leaf wise)，如此循环。优点是在分类次数相同的前提下，可以得到更好的精度。缺点可能会导致树的深度过大，解决方式是增加最大深度限制。
  3. 计算直方图时的优化：避免重复计算直方图，构造一个叶子的直方图后，可以用求差的方式得到它兄弟叶子的直方图。
    图1 优化点

XGboost/FastGBM/LightGBM，三者的异同点

三者都是GBDT很好的实现，枚举几点异同：

  1. FastBDT在单机分类问题进行了极致的优化和探索，当然也限制了其在回归问题的应用。而XGboost和LightGBM可以用于分类和回归，并很好支持了并行化。
  2. XGboost单机版本Greedy进行，并对每个特征有进行pre-sort操作，带了额外的开销。这点在FastBDT和LightGBM中进行了规避。
  3. FastBDT中可以看到受SGBDT影响较大，XGboost也支持对样本的采样，LightGBM未做考核，暂无结论。
  4. LightGBM选择生长树的方式选择分类增益最大叶子进行生长，而XGboost和FastBDT是逐层进行。

此外，XGboost在业界运用较多，对各大平台很友好，目前仍有活跃着很多贡献者，最新进展为《Support Dropout on XGBoost》

引文：
[0]Keck T. FastBDT: A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate classification[J]. 2016.
[1]Tong Zhang Rie Johnson. Learning nonlinear functions using regularized greedy forest.IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(5):942–954, May 2014. doi: 10.1109/TPAMI.2013.159. PDF
[2]Ron Appel, Thomas Fuchs, Piotr Dollar, and Pietro Perona. Quickly boosting decision trees – pruning underachieving features early. In Sanjoy Dasgupta and David Mcallester, editors, Proceedings of the 30th International Conference on Machine Learning (ICML-13), volume 28, pages 594–602. JMLR Workshop and Conference Proceedings, May 2013. PDF .
Tong Zhang Rie Johnson. Learning nonlinear functions using regularized greedy forest. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(5):942–954, May 2014. doi: 10.1109/TPAMI.2013.159. PDF.
[4]如何看待微软新开源的LightGBM?, lightGBM作者@guolinke

PS. 家里有事，穿插了一次部门bui，没时间码字，sorry，接下来探索一下embeding方面的文章。
ShawnXiao@baidu