Kaggle Days TokyoでのGBDT実装の話

先日行われたKaggle Days Tokyoで発表した資料になります。

前半は主に外国の方向けのKaggle本の紹介、後半はGBDTをスクラッチ実装する話です。
拙い英語ですが、雰囲気で読んで下さい。ちょっと説明に優しさが足りない気もしますね。直前にKaggle Santaコンペをやっていたのが良くない。。

speakerdeck.com

コードはこちらです。Cython版でxgboostの1/4くらいの速度でまぁまぁな速さです。
sklearnやxgboostのコードを読むと、抽象化やいろいろなケースに対応するためのコードがあってアルゴリズムを理解するのに苦労するのですが、 シンプルにアルゴリズム部分が分かりやすいような書き方にしたつもりです。 www.kaggle.com www.kaggle.com

他にも、@nyker_gotoさんの実装を教えて頂いたのでご紹介します。

github.com

C++でも200～300行ほどでGBDT(XGBoost)実装できるけど、ライブラリの1/10ぐらいのスピードしか出ないんだよな…。多分、実装面で相当の工夫があるのだと思っている。 #kaggledaystokyo

— Jack (@sakata_ryuji) 2019年12月11日

帰りにJackさんと少し話したのですが、私が気づいたxgboostの工夫は以下です。

• ノードごとにデータを走査すると、計算量がO（ノード）になってしまう。
  深さごとにデータを走査し、データの属するノードに応じて処理を行うようにすると、計算量をO（深さ）にできる。
• SortedCSCPageという構造を使い、データを疎に保持するようにしている。
  欠損値が多い場合などはその分スキップできるので速くなる。