GBDTのひとつ、Catboost

GBDTという手法がKaggleなどでもメジャーなものになってきました。
今回はそんなGBDTライブラリの一つで比較的新しいCatboostについて見ていきます。
Catboostは、ロシア最大手検索エンジンサイトであるYandex社から2017年にリリースされ、11月29日現在v0.20まで公開されています。その革新さをいくつかあげられていたのでそれらをこちらの論文に沿いながら確認していきます。

目次

カテゴリ変数の扱い

勾配バイアスの扱い

決定木選定アルゴリズム

実際に動かしてみた

カテゴリ変数の扱い

前処理

機械学習にあたってカテゴリ変数を扱うときにはそれらを学習させるためにデータの前処理が必要です。
しかし、Catboostではそれらを内部で吸収し、自分で処理してくれます。
たとえば、低カーディナリティ（性別などのように該当する項目が少ない）カテゴリ変数に対してはOne-hotエンコーディングがなされることが一般的です。これは前処理時か、学習を始める際に変換されるものですが、Catboostでは学習時に後述するカテゴリ変数のコンビネーションでも使いうるので前処理をせずにそのまま渡すのが望ましいとされています。
また、ユーザIDのようにカーディナリティの高い変数を扱う際にはそれらの統計量（Target Statistics）を使いますが、これは訓練データの中だけで完結したものであるため、ターゲットリーケージ(target leakage)という過学習の危険性が非常に高いものになります。
そこで、Catboostではランダムにデータを選び、その中から統計量を取るという作業を繰り返し代用値を計算するという手法で対処されています。 具体的に以下の式で代用値が算出されています。

ここで、データセット{\({X_i, Y_i}\)}とし, \(X_i\)は\((x_{i, 1},...x_{i, m}\))のm次元ベクトルで表され、σは順列（どのデータを取るかの集合）、Pを重要度、aをPの重みとして計算されています。
重要度を足すのは頻度の低いカテゴリから生じるノイズを減らすことを目的としていて、回帰問題ではデータセットのラベル値の平均、二値クラス分類問題では真の先験的遭遇確率（True a priori distribution）がよく用いられます。
ここでの統計量の算定の仕方にもランダム性を用いることは、過学習回避に有効です。

カテゴリ変数のコンビネーション

Catboostでは、統計量を使った過学習回避としてもう１つカテゴリ変数を組み合わせる、新奇な手法で対処しています。
たとえば、音楽のレコメンド機能で、ユーザIDと、そのユーザが好きなジャンルという２つのカテゴリ変数があるとします。あるユーザーがロックを好んでいるというデータがあるときに、この２つを上述の代用値に置き換えると、この新しい代用値群は、新たな変数として過学習を気にすることなく使うことができるようになります。
しかしこのカテゴリ変数の組み合わせは、カテゴリ変数が多ければ多いほど指数関数的にその数を増します。
全てを考慮することはまだできないため、新たな木構造を生成する際に最初の枝に対しては組み合わせを考えず、それ以降について組み合わせを適用することである程度貪欲にそして正確性を保った結果が保証されています。

勾配バイアスの扱い

GBDTライブラリでは、新しい木を生成する際に、現在の木から、そして同じデータセットから勾配近似値を求めるため、真の確率分布と予測勾配値の確率分布の差異でを生むPrediction shiftという危険性を抱えています。
もう少し詳しくこの木を作る過程を見ていきます。
まず、どんな構造の木を使うかを選定し、それが決まったら葉に値を入れていきます。どの構造を使うかは、アルゴリズムが様々な種類を列挙し、それらに点数付けをして最良のものを選びます。ここで葉の値は勾配の近似値あるいはニュートン法によって一般的に計算されています。
この木の構造選定に際して起こるprediction shiftに対処するためにCatboostではOrdered Boostingという手法を取っています。Ordered Boostingは前回のブースティング段階で毎回新たなデータセットを個別にサンプリングして木を作っていきます。
毎回新たなデータセットを使うというのは限られたデータの中では不可能に思われますが、上述のカテゴリ変数のコンビネーションによってその数を確保することに成功しています。

決定木の選定アルゴリズム

Catboostでは、予測をOblivious Decision Treesを用いて行われています。
ここでObliviousは、全ての木で同様の分岐基準を使われていることを示しています。この木構造は均衡が取れていて過学習をしづらく、また後述する性質上実行速度が高速という特徴を持っています。
Oblivious Treesではそれぞれの葉のインデックスは深さと一致する2値ベクトルで表されます。モデル予測の際には、様々な数値データをバイナリ特徴量に変換して計算をします。
全てのベクトル特徴量は連続ベクトルBに保管され、葉の値は大きさ\(2^d\)(dは葉の深さ)のベクトルで保管されます。

実際に動かしてみた

実際のデータを用いたベンチマークが、公式のGithubにあります。
実行時のスコアから見ていきます。

Score

	Default CatBoost	Tuned CatBoost	Default LightGBM	Tuned LightGBM	Default XGBoost	Tuned XGBoost	Default H2O	Tuned H2O
Adult	0.272978 (±0.0004) (+1.20%)	0.269741 (±0.0001)	0.287165 (±0.0000) (+6.46%)	0.276018 (±0.0003) (+2.33%)	0.280087 (±0.0000) (+3.84%)	0.275423 (±0.0002) (+2.11%)	0.276066 (±0.0000) (+2.35%)	0.275104 (±0.0003) (+1.99%)
Amazon	0.138114 (±0.0004) (+0.29%)	0.137720 (±0.0005)	0.167159 (±0.0000) (+21.38%)	0.163600 (±0.0002) (+18.79%)	0.165365 (±0.0000) (+20.07%)	0.163271 (±0.0001) (+18.55%)	0.169497 (±0.0000) (+23.07%)	0.162641 (±0.0001) (+18.09%)
Appet	0.071382 (±0.0002) (-0.18%)	0.071511 (±0.0001)	0.074823 (±0.0000) (+4.63%)	0.071795 (±0.0001) (+0.40%)	0.074659 (±0.0000) (+4.40%)	0.071760 (±0.0000) (+0.35%)	0.073554 (±0.0000) (+2.86%)	0.072457 (±0.0002) (+1.32%)
Click	0.391116 (±0.0001) (+0.05%)	0.390902 (±0.0001)	0.397491 (±0.0000) (+1.69%)	0.396328 (±0.0001) (+1.39%)	0.397638 (±0.0000) (+1.72%)	0.396242 (±0.0000) (+1.37%)	0.397853 (±0.0000) (+1.78%)	0.397595 (±0.0001) (+1.71%)
Internet	0.220206 (±0.0005) (+5.49%)	0.208748 (±0.0011)	0.236269 (±0.0000) (+13.18%)	0.223154 (±0.0005) (+6.90%)	0.234678 (±0.0000) (+12.42%)	0.225323 (±0.0002) (+7.94%)	0.240228 (±0.0000) (+15.08%)	0.222091 (±0.0005) (+6.39%)
Kdd98	0.194794 (±0.0001) (+0.06%)	0.194668 (±0.0001)	0.198369 (±0.0000) (+1.90%)	0.195759 (±0.0001) (+0.56%)	0.197949 (±0.0000) (+1.69%)	0.195677 (±0.0000) (+0.52%)	0.196075 (±0.0000) (+0.72%)	0.195395 (±0.0000) (+0.37%)
Kddchurn	0.231935 (±0.0004) (+0.28%)	0.231289 (±0.0002)	0.235649 (±0.0000) (+1.88%)	0.232049 (±0.0001) (+0.33%)	0.233693 (±0.0000) (+1.04%)	0.233123 (±0.0001) (+0.79%)	0.232874 (±0.0000) (+0.68%)	0.232752 (±0.0000) (+0.63%)
Kick	0.284912 (±0.0003) (+0.04%)	0.284793 (±0.0002)	0.298774 (±0.0000) (+4.91%)	0.295660 (±0.0000) (+3.82%)	0.298161 (±0.0000) (+4.69%)	0.294647 (±0.0000) (+3.46%)	0.296355 (±0.0000) (+4.06%)	0.294814 (±0.0003) (+3.52%)
Upsel	0.166742 (±0.0002) (+0.37%)	0.166128 (±0.0002)	0.171071 (±0.0000) (+2.98%)	0.166818 (±0.0000) (+0.42%)	0.168732 (±0.0000) (+1.57%)	0.166322 (±0.0001) (+0.12%)	0.169807 (±0.0000) (+2.21%)	0.168241 (±0.0001) (+1.27%)

全ての結果でcatboostが1番良いスコアをマークしています(Log lossのため低いほどよい)。
また、ほぼ全ての結果においてcatboostのデフォルト値を用いた結果が、チューニング後の他ライブラリより高い結果となっています。

モデル評価時間

ライブラリ	所要時間
XGBoost 32Thread	4.89 s ± 223 ms per loop (mean ± std. dev. of 5 runs, 1 loop each)
LightGBM 32Thread	11.1 s ± 402 ms per loop (mean ± std. dev. of 5 runs, 1 loop each)
Catboost 32Thread	184 ms ± 806 µs per loop (mean ± std. dev. of 5 runs, 1 loop each)

こちらも他を圧倒しています。

モデル作成時間

test size	catboost	lightgbm	xgboost
1000	0.069	0.002	0.011
5000	0.349	0.001	0.047
10000	0.770	0.001	0.089

初めてcatboostが遅れをとる結果になりました。 しかも相当のビハインドがあります。
これらのベンチマークは2年前のもので、Python2で書かれたものなので一概にこの結果が正しいと言えるかはわかりません。
そこでAmazonデータセットに対してデフォルト値で比較してみました。詳しいコードは以下を参照してください。

ライブラリ	モデル作成時間時間	スコア
XGBoost	1.805s	0.7452
LightGBM	0.6343s	0.8326
Catboost	149.301s	0.8845

Catboostが圧倒的に時間がかかっているのがわかります。

まとめ

特段のチューニングなしでもかなり良い結果を得られるライブラリでした。
しかし、Catboostを使う際には適切なパラメータチューニングの上で相応のマシンスペックと時間の確保が必要になりそうです。
12/8から行われるneurIPSにも論文が出されるそうなので、そこでの発表も楽しみです。

参考文献

CatBoost: unbiased boosting with categorical features

CatBoost: gradient boosting with categorical features support

Mastering The New Generation of Gradient Boosting

CatBoost Document

LightGBM Document

XGBoost Document

Catboost Benchmarks

Twitter・Facebookで定期的に情報発信しています！
Follow @acceluniverse