xgboostのコードリーディング(その2)

前回(xgboostのコードリーディング - threecourse’s blog)の続きです。
前回同様、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。

pre-sortedアルゴリズムとhistogram-basedアルゴリズム

決定木を作成するアルゴリズムとして、pre-sortedとhistogram-basedというアルゴリズムがある。
(参考) NIPS2017読み会 LightGBM: A Highly Efficient Gradient Boosting Decision T…

xgboostでは、

pre-sortedでは、以下のような計算の流れとなる。

  1. 予め、特徴量ごとに、特徴量の値でソートしたデータへの参照を作成しておく
  2. 深さごとに、特徴量ごとに、ソートされたデータを走査してそれぞれの葉の分割点を決める

(参考)XGBoost: A Scalable Tree Boosting System のAlgorithm 1: Exact Greedy Algorithm for Split Finding

histogram-basedでは、以下のような計算の流れとなる。

  1. 予め、特徴量ごとにヒストグラムを作り、各データがどのbinに属するかを求めておく。
  2. 深さごとに、

(参考) LightGBM: A Highly Efficient Gradient Boosting Decision Tree のAlgorithm 1: Histogram-based Algorithm

計算量を考えたときに、histogram-basedでは、以下のようなメリットがある。

  • 深さごとに、
    • ヒストグラム作成部分の計算量はO(特徴量 x データ数)
    • 分割点の計算部分の計算量はO(特徴量 x ビンの数)

    となり、ヒストグラム作成部分が支配的となり、O(特徴量 x データ数)となることに変わりはない。
    ただし、ヒストグラム作成の処理の方が分割点の計算の処理より軽いために速くなる。

  • 分岐を行い、左の葉のヒストグラムを求めたとする。すると、右の葉のヒストグラムは親から左の葉のヒストグラムを引き算して計算することができ、O(特徴量 x データ数)でなく、O(特徴量 x ビンの数)で計算できるため、その部分の計算量が無視できる。(データ数の方がビンの数より十分に多い前提で考えている)
  • 葉ごとにその葉に属するデータ(のインデックス)のリストを持たせることができるため、深さ単位でなく葉単位での木の成長が行えるようになる。pre-sortedでは、特徴量の値ごとにソートされている必要があるため、このように葉ごとにリストを持たせることは行いにくい。histogram-basedでは、属するビンが分かればソートされている必要はない。

結局、1本の決定木を作る計算量のオーダーは、O(データ数 x 特徴量の数 x 深さ)で変わらないものの、定数倍が効いてhistogram-basedの方が速くなる、と理解している。

xgboostのapproxとhistの違い

xgboostのtree_methodには、exactの他にapproxhistのオプションがある。
approxhistの違いについては、以下で説明されている。
[New Feature] Fast Histogram Optimized Grower, 8x to 10x Speedup · Issue #1950 · dmlc/xgboost · GitHub

このIssueによると、ヒストグラムを作る点は同じであるが、イテレーションごとにヒストグラムを作り直すapproxと、使いまわすhistの違いがあり、histの場合だと以下のような高速化が可能になるとのこと。

  • Cache of the bins: 連続変数をbinのインデックスとし、データの構造をキャッシュする
  • Histogram subtraction trick: ヒストグラムを作成するときに、親と兄弟のヒストグラムの差をとる

Histogram subtraction trickは理解できたが、Cache of the binsはどう利用されているのか良くわからなかった。また、イテレーションごとにヒストグラムを作り直す`approx'でも、Histogram subtraction trickは実行できる気がする。

tree_method=approxでの学習の流れ(メモ)

tree_method=approxでは、決定木ごとに同じヒストグラムを使用する"global"と分岐ごとにヒストグラムを作成し直す"local"の2つの手法があるが、デフォルトでは"global"となり、UpdaterとしてColMakerの代わりにGlobalProposalHistMakerが利用される。
(なおGlobalProposalHistMakerは、HistMakerの派生クラスのCQHistMakerの派生クラス)

学習の流れは以下のようになる:

  1. HistMakerのUpdateメソッド

    • HistMakerのUpdateメソッド(オーバーライドされたprivateの方) を呼び出す。
    • HistMakerのprivateのUpdateメソッドでは、
      各深さごとに、CreateHistメソッド、FindSplitメソッドを呼び出す。
      (初期化処理やその他のメソッドは省略)
  2. GlobalProposalHistMakerのCreateHistメソッド
    特徴量ごとに、CQHistMakerのUpdateHistColメソッドを呼び出す。
    UpdateHistColメソッドでは、各データについて、対応するビンの値をアップデートする。

  3. HistMakerのFindSplitメソッド
    特徴量ごとに、HistMakerのEnumerateSplitメソッドを呼び出す。
    EnumerateSplitメソッドでは、ヒストグラムの走査を行う。

tree_method=histでの学習の流れ(メモ)

tree_method=histの場合、QuantileHistMakerが利用される。深さ単位で成長するdepthwiseか葉ごとに成長するlossguideが選べるが、以下はデフォルトのdepthwiseの学習の流れとなる。

  1. QuantileHistMakerのUpdateメソッド
    GHistIndexMatrixのInitメソッドで前処理を行ったあと、QuantileHistMaker::BuilderのUpdateメソッドが呼び出される
  2. QuantileHistMaker::BuilderのUpdateメソッド
    depthwiseの場合は、ExpandWithDepthWiseメソッドが呼び出される

  3. QuantileHistMaker::BuilderのExpandWithDepthWiseメソッド

    深さごとに、以下のメソッドが順に呼び出される

    1. BuildHistsBatch
    2. BuildNodeStatBatch
    3. EvaluateSplitsBatch
    4. CreateNewNodesBatch
  4. QuantileHistMaker::BuilderのBuildHistsBatchメソッド
    ヒストグラムを作成する
    一定のデータ数ごとにtaskに分けて分散処理できるようにしている様子

  5. QuantileHistMaker::BuilderのBuildNodeStatBatchメソッド
    葉の情報を更新する
  6. QuantileHistMaker::BuilderのEvaluateSplitsBatchメソッド
    ヒストグラムから分割点を求める
  7. QuantileHistMaker::BuilderのCreateNewNodesBatchメソッド
    新しい葉を作成する
    一見複雑なことをやっているように見えるが、単に分岐に基づいてデータを葉に振り分けているだけのように思える