なぜCatboostの推論は速いの？
前回の記事｢AutoML v.s. Catboost｣に出てくるCatboostは、XGBoostやLightGBMと比べて30-60倍も推論が速いという特徴があります。
推論時間は、kaggleなどのコンペでは推論に時間をかけられるのであまり気にしませんが、実サービスとなると重要ですよね。
推論時間の比較
以下のグラフは、3大GBDTライブラリでの推論時間比較です。Catboostがずば抜けて速いことがやかります。 そして学習時間の速さに定評があるLightGBMは、なんと最遅です。
この推論時間の速さは、CatboostがGBDTのベースとなる決定木に symmetric tree と呼ばれる、特殊な形の木を使っているからです。
ここで、symmetric treeとは以下の図の右側のような木です。左側は普通の決定木です。
なぜsymmetric treeは速いか
｢同一の深さではすべての分岐条件が同じ｣ということが推論の並列化を可能としていて、これが推論時間の短縮を実現しています。
ちなみに、この木の構造が気持ち悪いという人はgrow_policyというパラメータを変えることで、変更できます（公式ドキュメントに詳細あり）。
おまけ：学習時間とGPU
CatboostはXGBoostと変わらない速度だからLightGBM使っとけ的な意見をよく耳にします。しかしそれは、CPUを用いた場合の話で、GPUを用いた場合は、学習時間でもCatboostが最速です。以下のグラフは、GPUでの学習時間を表しています。
並列化に向いたsymmetric treeと並列計算が得意なGPUの相性は抜群ということです。
皆さんも是非一度、deep learning以外でcolabのGPUを使い倒してみては如何でしょうか。
追記：GPU学習時間の検証
実際にcolabで、GPUを用いてLightGBMとCatboostの学習時間を計測しました。条件等は、下記のbinningの追記と同様です
公式の主張ほど学習時間の差はありませんが、それでもGPUがあればLightGBMより速いと言えそうです。
ただ、公式的にはデータセットがもっと大きいときに分散学習できるのが強みだと言っているので、そのような条件ではもっと差がつくのかもしれません。
レファレンス
図やグラフは、すべて以下の動画からの引用です。
CatBoost - the new generation of gradient boosting - Anna Veronika Dorogush - YouTube
この動画では、Yandexの開発者が直々にCatboostを初心者向けに解説してますので、このブログよりはるかに分かりやすいと思います。是非ご覧ください（ただし英語）。
また、各種時間の計測にかかる実験の条件等も説明されていますので、そちらに興味がある方もご覧ください。
追記：binningの時間も求めつつ実際に実験
一瞬だけbinningにかかる時間を考慮して実験してみてというツイートを観測したので，やってみた結果を書きます。
条件
- colabのGPUを使用
- sklearnの
make_classificationで特徴量次元128の二値分類データセット作成 - binningにかかる時間は，
max_depth=1, n_rounds=1としたときの推論時間として近似的に求める*1 - 推論時間は，
max_depth=6, n_rounds=1として学習させたモデルの推論時間。binningにかかる時間も含まれる
結果
- binningのみはLightGBMの方がCatboostよりも速い
- でも，推論全体にかかる時間はCatboostの方がLightGBMよりも速い
- ただし，symmetric treeがよく効くようにある程度max_depthが深くないとLightGBMが勝つ
- Catboostが主張してるほど推論は速くない（もっと適切な条件があるのかもしれないが）がLightGBMよりは速い
追追記：binning時間を近似なしで求める
ちゃんとLightGBMのDatasetをconstructしてbinningだけの時間を求めてみました（Catboostは遅延評価ではないっぽい）。すると，binningだけでもCatboostの方が速いという結果となりました。
以下，考察です（コードを読んでないので間違ってるかもしれません）。
- Catboostは，推論時にもbinningを完全におこなう
- 一方LightGBMは，推論時には分岐条件に含まれるものだけbinningする等して効率化している
max_depth=1, n_rounds=1のときの推論時間（=binningの近似時間）の異様な速さに説明が付く
アプデ
本記事を受けて、中の人がコメントしてくれています。
We have fast inference because we are using special tree shape - oblivious trees, they have the same condition on one level, so it could be done with SIMD instructions. We are now making GPU model inference backend, wich is even faster on large models. Stay tuned!
— Stas Kirillov (@kizillof) 2019年6月5日
*1:正しい近似なのか自信ないので、おかしかったら突っ込んで下さい
