xgboostでどのような処理が行われているのかを、メモの意味でまとめてみました。 たぶん続きます。なお、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。 ソースコードは以下を参照しています。 https://github.com/dmlc/xgboost (release_0.90を参照) 前提 以下の前提とする: ブースター(booster)はgbtree 決定木のアルゴリズム（tree_method）はexact カスタム目的関数を使わない GPUの使用、マシン並列を行わない xgboostでは、tree_methodオプションで決定木を作成するアルゴリズムを選択できる。 デフォルトではデータ数が一定未満の場合にはexact、それ以上であればapproxが適用される。 (4UL << 20UL = 4194304件が境目、GBTree::PerformTreeMethod

前回（xgboostのコードリーディング - threecourse’s blog）の続きです。 前回同様、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。 pre-sortedアルゴリズムとhistogram-basedアルゴリズム 決定木を作成するアルゴリズムとして、pre-sortedとhistogram-basedというアルゴリズムがある。 （参考） NIPS2017読み会 LightGBM: A Highly Efficient Gradient Boosting Decision T… xgboostでは、 tree_method=exactでは、pre-sortedアルゴリズムが利用される。 tree_method=histやLightGBMでは、histogram-basedアルゴリズムが利用される。 pre-sortedでは、以下のような計算の流れとなる。 予