読者です 読者をやめる 読者になる 読者になる

XGBoostにDart boosterを追加しました

はじめに

XGBoostにBoosterを追加しました。 以下のようなIssueを見つけ、興味があったので実装してみたものです。 github.com

今のところ、Dart boosterの仕様について私以外の誰も把握していないはずなので、皆さんに使って頂きたく解説記事を書きます。*1

モチベーション

論文の

Boosted Treesでは誤差を潰すために回帰木を大量に作ります。

木の数が多くなったときに残っている誤差は小さいですが、以降に構築される回帰木はその些末な誤差にフィッティングされることになります。

これは効率悪いように思われ、イテレーションの終盤においても一定の影響力を持った回帰木を作りたいということで、NN系でよく用いられる(ものとは趣きが異なるように私には思える)DropoutをBoosted Treesに転用しています。

自分の

  • XGBoostにはいつもお世話になっているのでcall-for-contributionに反応したかった
  • ライブラリ使ってるだけでしょ、という煽りが癪
  • Gitできないので5日でクビになってしまう
  • XGBoostエバンジェリストとしてSIerさんに拾ってもらいたい

実装について

DARTにおける回帰木の作り方は通常と同じです。 構築した回帰木に対するDropoutやスケーリングの処理を追加すれば良いので、回帰木をコントロールしているGradientBooster(今回は特にGBTree)を拡張するのみです。

ドロップ

Dart::PredictDropTreesをコールしています。 ここでntree_limitに0がセットされていると、既に構築した回帰木の幾つかをドロップしたleaf scoreを計算します。

したがって、学習結果を用いて予測値を得る場合にはntree_limitに正の値(num_roundと同じ数)を設定する必要があります。 ここはAPIを弄りたくなかったので複雑な仕様になっています。

スケーリング

ドロップしたleaf scoreに対して通常と同じように回帰木を構築します。

ドロップした回帰木と追加の回帰木で平均を取るためにDart::CommitModel内でNormalizeTreesをコールしています。

パラメータ

booster

dartを指定します。 内部的にはGBTreeを継承していますので、パラメータもgbtreeと同じものが設定できます。 Predメソッドでのバッファを無効化しているので、gbtreeと比べて学習が遅くなっています。

Dart boosterに固有のパラメータを以下で解説します。

sample_type

ドロップする回帰木のサンプリング方法を指定するオプションです。 デフォルトはuniformで、このとき一様にドロップする回帰木が選ばれます。 weightedに指定すると、影響力の大きな回帰木が選ばれやすくなります。

normalize_type

DARTではドロップする回帰木と新たに学習した回帰木の平均を取ります。 このときの平均の取り方を指定します。 デフォルトはtreeで、ドロップした回帰木のそれぞれ1本が新たに学習した回帰木と同じ重みを持つとして計算します。

 {\displaystyle
D = \sum_{i=1}^k F_i \sim \tilde{F}
}

 {\displaystyle
\alpha \left( \sum_{i=1}^k F_i + \frac{\lambda}{k} \tilde{F} \right)
\sim \alpha \left( 1 + \frac{\lambda}{k} \right) D = D, \quad
\alpha = \frac{k}{k + \lambda}
}

learning_rateを小さく、num_roundを大きくした場合に影響力が小さくなりすぎるので、forestというオプションを用意しています。 ドロップした回帰木の合計と新たに学習した回帰木が同じ重みを持つとして計算します。

 {\displaystyle
\alpha \left( \sum_{i=1}^k F_i + \lambda \tilde{F} \right) \sim \alpha \left( 1 +\lambda \right) D = D, \quad
\alpha = \frac{1}{1 + \lambda}
}

rate_drop

既存の回帰木がドロップされる確率を設定します。

skip_drop

論文ではlearning_rateが1で固定されているので問題となりませんが、learning_rateを小さな値に設定した場合には足踏みを繰り返して学習が進みません。 あるイテレーションではドロップせずに、通常のGBTreeのようにboostingできるような仕様にしています。 イテレーション毎にドロップをしない確率をskip_dropで設定します。

数値実験

こちら

パラメータによってはgbtreeより良い精度を出せているようです。

今後について

Boosted Treesでは通常learning_rateを小さく設定しているため、既にbaggingが効いてしまっています。 論文のアルゴリズムのように、ドロップした回帰木と同じような値を新たな回帰木に学習させて、それらの平均を取っているだけでは劇的な性能改善は望めないでしょう。

過学習は怖いですが、バリデーションのスコアを参照してセレクションを効かせるような仕組みに発展させたいです。*2

その他

  • NormalizeTreesの計算が間違っていたらご指摘ください*3
  • Boosted Trees周辺で数学的に難しくない論文があれば教えて下さい、XGBoostベースで組んでみます

*1:私の英語力の問題で、日本語記事が世界最速です。DARTでライバルに差をつけるなら今ですよ。

*2:卒業論文くらいにはちょうど良いテーマだと思いますが大学生の皆さん如何でしょう?

*3:既に、Pull requestが通ってから1日で修正をしてしまっている…