xgboost原理

#!/usr/bin/python
import numpy as np
import xgboost as xgb
###
# advanced: customized loss function
#
print ('start running example to used customized objective function')

dtrain = xgb.DMatrix('../data/agaricus.txt.train')
dtest = xgb.DMatrix('../data/agaricus.txt.test')

# note: for customized objective function, we leave objective as default
# note: what we are getting is margin value in prediction
# you must know what you are doing
param = {'max_depth': 2, 'eta': 1, 'silent': 1}
watchlist = [(dtest, 'eval'), (dtrain, 'train')]
num_round = 2

# user define objective function, given prediction, return gradient and second order gradient
# this is log likelihood loss
def logregobj(preds, dtrain):
    labels = dtrain.get_label()
    preds = 1.0 / (1.0 + np.exp(-preds))
    grad = preds - labels
    hess = preds * (1.0-preds)
    return grad, hess

# user defined evaluation function, return a pair metric_name, result
# NOTE: when you do customized loss function, the default prediction value is margin
# this may make builtin evaluation metric not function properly
# for example, we are doing logistic loss, the prediction is score before logistic transformation
# the builtin evaluation error assumes input is after logistic transformation
# Take this in mind when you use the customization, and maybe you need write customized evaluation function
def evalerror(preds, dtrain):
    labels = dtrain.get_label()
    # return a pair metric_name, result
    # since preds are margin(before logistic transformation, cutoff at 0)
    return 'error', float(sum(labels != (preds > 0.0))) / len(labels)

# training with customized objective, we can also do step by step training
# simply look at xgboost.py's implementation of train
bst = xgb.train(param, dtrain, num_round, watchlist, logregobj, evalerror)

find ./ -name "*.cc" | awk -F "." '{print $2}' | xargs -i -t mv ./{}.cc  ./{}.cpp

cli_main.cc:
main()
     -> CLIRunTask()
          -> CLITrain()
               -> DMatrix::Load()
               -> learner = Learner::Create()
               -> learner->Configure()
               -> learner->InitModel()
               -> for (i = 0; i < param.num_round; ++i)
                    -> learner->UpdateOneIter()
                    -> learner->Save()    
learner.cc:
Create()
      -> new LearnerImpl()
Configure()
InitModel()
     -> LazyInitModel()
          -> obj_ = ObjFunction::Create()
               -> objective.cc
                    Create()
                         -> SoftmaxMultiClassObj(multiclass_obj.cc)/
                              LambdaRankObj(rank_obj.cc)/
                              RegLossObj(regression_obj.cc)/
                              PoissonRegression(regression_obj.cc)
          -> gbm_ = GradientBooster::Create()
               -> gbm.cc
                    Create()
                         -> GBTree(gbtree.cc)/
                              GBLinear(gblinear.cc)
          -> obj_->Configure()
          -> gbm_->Configure()
UpdateOneIter()
      -> PredictRaw()
      -> obj_->GetGradient()
      -> gbm_->DoBoost()         

gbtree.cc:
Configure()
      -> for (up in updaters)
           -> up->Init()
DoBoost()
      -> BoostNewTrees()
           -> new_tree = new RegTree()
           -> for (up in updaters)
                -> up->Update(new_tree)    

tree_updater.cc:
Create()
     -> ColMaker/DistColMaker(updater_colmaker.cc)/
        SketchMaker(updater_skmaker.cc)/
        TreeRefresher(updater_refresh.cc)/
        TreePruner(updater_prune.cc)/
        HistMaker/CQHistMaker/
                  GlobalProposalHistMaker/
                  QuantileHistMaker(updater_histmaker.cc)/
        TreeSyncher(updater_sync.cc)

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的树结点计算统计量