xgboostでどのような処理が行われているのかを、メモの意味でまとめてみました。
たぶん続きます。なお、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。

ソースコードは以下を参照しています。
https://github.com/dmlc/xgboost (release_0.90を参照)

前提

以下の前提とする:

ブースター(booster)はgbtree
決定木のアルゴリズム（tree_method）はexact
カスタム目的関数を使わない
GPUの使用、マシン並列を行わない

xgboostでは、tree_methodオプションで決定木を作成するアルゴリズムを選択できる。
デフォルトではデータ数が一定未満の場合にはexact、それ以上であればapproxが適用される。
(4UL << 20UL = 4194304件が境目、GBTree::PerformTreeMethodHeuristicメソッド参照）また、histを設定することで、lightgbmのようなヒストグラムを用いた手法を利用できる。

学習の流れ

以下のようなPythonコードを呼び出すとする。

import xgboost as xgb
# param, dtrain, num_roundには適当な値が入っているとする
bst = xgb.train(param, dtrain, num_round)

このとき、xgb.trainでは、以下のように学習が実行される。

1. python-package/xgboost/training.pyのtrainメソッド

そこから_train_internalメソッドを呼びだして学習を行う。
学習において、決定木の作成ごとに、BoosterクラスのUpdateメソッドを通して、c++のメソッド_LIB.XGBoosterUpdateOneIterを呼び出す

2. src/c_api/c_api.ccのXGBoosterUpdateOneIterメソッド

LearnerImplクラスのUpdateOneIterを呼び出す。

3. src/learner.ccのLearnerImplクラスのUpdateOneIterメソッド

ObjFunctionクラスのGetGradientメソッドを呼び出し、各データの勾配を求める（この部分の説明は省略）
GBTreeクラスのDoBoostメソッドを呼び出し、決定木を作成する

4. src/gbm/gbtree.ccのGBTreeクラスのDoBoostメソッド

BoostNewTreesメソッドを呼び出す。
BoostNewTreesメソッドの中で、各updaterについてUpdateを行う。
今回の設定では、updaterはColMakerとTreePrunerの2つであり、ColMakerクラスのUpdateメソッドが木を作成する部分の本体と言える。（TreePrunerの説明は省略）なお、tree_methodによりupdaterが変わり、アルゴリズムの変更が反映される。今回はexactなのでColMakerが使われるがapproxであればHistMaker、histであればQuantileHistMakerが使われる。

5. src/tree/updater_colmaker.ccのColMakerクラスのUpdateメソッド

ColMaker::BuilderクラスのUpdateメソッドを呼び出す。

6. src/tree/updater_colmaker.ccのColMaker::BuilderクラスのUpdateメソッド

木の深さごとに以下を行う：

FindSplitメソッドを呼び出す。
- FindSplitメソッドでは、UpdateSolutionメソッドを呼び出す。
- UpdateSolutionメソッドでは、特徴量ごとにEnumerateSplitメソッドを呼び出す。
- EnumerateSplitメソッドは、ある特徴量で最適な分割点とロスを求めるメソッドである。
  特徴量の値でソート済のレコードのインデックスのリストがあるので、順次勾配の値を累積することで、分割後のロスが最も小さくなる特徴量の値を求めることができる。
ResetPositionメソッドなどを呼び出し、データが属する葉を更新するなどの、葉を分岐させる処理を行う。

計算量

ソースコードを調べた発端はここの話で、計算量について正しく理解したかったため。

xgboostのexact(pre-sorted)アルゴリズム

xgboostのexactオプションでの計算量は以下のとおり（と思われる・・）：

木の作成前に、特徴量ごとに特徴量の値でソートしたデータへの参照を作成しておく。これは一度だけO(データ数 x log(データ数）x 特徴量の数）が必要。
木を作成するごとに、各データの勾配/ヘシアンを求める必要があるが、これは最初にO(データ数)で計算できる。
各深さごとに、各特徴量ごとに、最適な分割をデータを走査して求める。特徴量の値でソート済のデータへの参照があれば、密なデータの場合にはO(データ数)で計算できる。
ここで、深さごとに計算しているのが一つのポイントで、同じ深さの各葉ごとに属するデータが排他なので、1度の走査で各葉に対して計算できる。もし葉ごとに全てのデータを走査すると無駄な走査が発生し、深さごとにO（データ数 x 葉の数）の計算が必要となってしまう。
結局、支配的な部分は特徴量の走査の部分となり、計算量は、O(決定木の数 x データ数 x 特徴量の数 x 深さ)になる。

メモ

コードの理解に役立つクラスの説明：

HostDeviceVectorクラスは、GPUへの対応が考慮されているvectorクラスであり、コードの理解上はただのリストと考えておけば良い。
Entry構造体は、indexとvalueの2つの値を保持する。indexは使われ方によってデータの行のindexになることも、特徴量（列）のindexになることもある。
SparsePageクラスは、行列データを保持するクラス。行または列を参照するためのoffsetを表すvectorと、列または行を参照するindexと保持している値を表すvectorを持つことで、疎なデータを効率的に保持できる。
SortedCSCPageクラスは、SparsePageクラスの派生クラスで、列ごとに分割しやすい形式で疎なデータを保持することができる。ColMakerなどでの計算でこのクラスが使われている。

threecourse’s blog

xgboostのコードリーディング

前提