Xgboost, LightGBM, CatBoost

　決定木系の最後の記事では、Xgboost, LightGBM, CatBoostについて解説します。これらはDecisionTree系の実装としてはデファクトスタンダードとなっています。H2OやRanger、Yggdrasil（二つあるようです。Yggdrasil, Yggdrasil Decision Forests）などほかにも様々な実装は存在していますが、Kaggleなどではよく用いられているのはXgboostなどのようです（あまりSolutionをきちんと見ていないのでもしかしたらつかわれているのかもしれません）。

Xgboost

　LightGBM, CatBoostでも使われるアルゴリズムのもととなった実装です。eXtreme Gradient Boosting machineです。以前の記事で述べたようにSLIQ、SPRINTがもととなっていますが、決定的に異なる点があります。それは分割点の評価ための式です。ナイーブなGradientBoostingTreeでは、MSEを主に用いていました。

\text{MSE} = \frac{1}{N} \sum_{i=1}^N (y_i - \tilde{y}_i)^2 \\

（正確には親ノードのサンプル数を$N$、MSEを$\text{MSE}_p$、子ノードをサンプル数とMSEをそれぞれ$N_L, N_R, \text{MSE}_L, \text{MSE}_R$と置いたとき、

\text{MSE} - \frac{N_L}{N} \text{MSE}_L - \frac{N_L}{N} \text{MSE}_R

を評価します。）

ここで$p_i(\sum_{c=1}p_i=1)$は全部でC個のラベルの内のi番目のラベルの割合です。これはタスクが分類でも回帰でもベースとしてはRegressorとなっているためです。しかしここで疑問が浮かびます。分類の場合に例えばloglossを目的関数としたとします。しかし、分割の評価はMSEです。このように食い違うものを基準としてTreeを構築するより良いものがあるのではないでしょうか。

　そこでXgboostは目的関数の1階、2階微分を用いて分割の評価を行います。式変形はかなり複雑なので、解説してくださっている非常にわかりやすい記事を見てください。最終的に分割の評価は以下の式で決定されます。

\frac{G_L^2}{H_L} + \frac{G_R^2}{H_R} - \frac{G^2}{H^2}

ここで、Lは$x_i$に対応する$y_i$とモデルの予測を入力とする損失関数で、GとHはそれぞれGradientとHessianです(添え字のLとRは左と右の子ノードで、添え字ナシは親ノードを表しています。)。つまり、モデルの精度評価と分割の評価が全く同一の基準で行われます。Xgboostはそれを初めて提案しました（多分）。ナイーブなGradientBoostingTreeとくらべ追加でHの計算が必要になるので、若干処理が重くなると思います。

高速化

　Xgboostではいくつかの高速化の工夫が加えられています。以下はすべてFortLearnerでは未実装です。

Approximate Algorithm

　通常、分割点の評価はすべての可能な点（＝ソート済みの隣り合うデータの数値が異なる点）で行われます。すべての点で評価をすると当然時間がかかるので、評価点自体を削減することは意味があります。簡単にはパーセンタイルを求めその値の位置のみで分割点の評価を行います。FortLearnerではこちらは実装しておりません。特に速度面において特に優れているような記載が見当たらなかったためです。CART、SLIQ、CLOUDSのすべてにおいて最も時間のかかる点はデータをとってくる点でした。正直分割点の評価は実世界のデータにおいて、サンプル数にくらべデータのユニーク数が非常に少ない点を考えると実装する意味があるのかが疑問だったからです。一番の理由は実装がいまいち理解できていないためです。

Sparsity Aware Split Finding

　こちらはSparse、つまりデータがほぼ０やNullになっている場合です。これは主に右か左のどちらか一方にこのようなデータを押し付けることで得られます。Xgboostの論文では、昇順ソート済みデータの右側と左側のそれぞれから分割点を評価しています。こちらも実装していないのでアイデアのみですが、どちらかに押し付けるデータを事前に計算しておいて（これは片方にしかながれないのであれば根ノードで一度計算しておけばよい？）、各分割点で右左のどちらかのノードに押し付ける評価を行えばよいのではないかと思いました。そうすれば2度も配列全体をスキャンする必要もないですので速そうかなと思いました。FortranでNullが扱いにくすぎて現状あきらめています。

Cache Aware Imlementation

　上記二つはデータの特性に関するものでした。これはハードウェア的な実装の最適化です。GとHを評価しなければならないのですが、ポインタを経由して元のソートされていないデータにアクセスするため、キャッシュヒットミスが発生しやすくなります。そのためバッファを用意し（サイズ３２とか？）、そこにGとHを格納し、分割点の評価に利用するのような感じかと思っています。

LightGBM

　Microsoft作成のOSSです。Lightの名の通り、3つの内最もメモリ使用量が軽いはずです。

Binnig

　CLOUDSの解説をした記事で書くべきでしたが、Binningのアルゴリズムについて少し見てみます。簡単には以下の3つがあります。Scikit-learnにはKBinsDiscretizerとして実装されています。

uniform
1. equal width ともいいます。各特徴量の最大最小を等間隔に刻みます。ビンの内部にサンプルが存在しない場合もあります
quantile
1. equal frequency ともいいます。各特徴量を刻んだ時に各ビンに含まれるサンプル数が同じになるようにします
1-dim kmeans
1. 1次元のデータへKmeansを適用します。Fisher Groupingともいいます。Scikit-learnの実装は非常に遅いです。おそらく汎用的な実装（高次元にも適用できる実装）をそのまま1次元の場合にも用いていると思います。

1-dim kmeans

　少し話題がそれますが、1-dim kmeansについて書きたいと思います。Scikit-learnのKBinsDiscretizerをHiggsデータセット（サンプル数1000万）に対して適用すると一晩たっても終わっていませんでした。さすがにこれでは実用性が感じられないので、何とか高速化したいと思いました。スマートな方法としては1-dim kmeansを動的計画法を用いて行う、Fisher-Groupingを用いる方法です。
　いまいち動的計画法自体の概念が広すぎて、実問題への適用が理解できなかったのでもっと簡単な方法がないかと考えました。1-dim kmeansしか使い道はないが、とりあえずは速くなる方法です。そこで考えたのが、データのユニーク値とそのカウントを集計する方法です。何度も述べている通り、実世界のデータではサンプル数に比べ各特徴量のユニーク値は少ないことが多いです（いくつかの特徴量を組み合わせてユニークになる。例えば性年代、住所、職業、学歴を組み合わせて一人に特定できる）。この考えに基づいて専用の1-dim kmeansを実装してみると一晩かかっても終わらない計算が、1分もかからずに終えることができました。
　もともとはChoropleth Mapと呼ばれるものに用いられていた手法のようです。関連の文献を調べてみるといろいろな実装方法が存在していました。これを用いてLightGBMの性能変化を調べてみるのも面白いと思ったのですが、力尽きてしまいました。

Gradient-based One-Side Sampling: GOSS

　基本的な部分は説明済みのためスキップします。GOSSは利用するサンプルを少なくすることで高速化を図ります。

Adaboostでは直前までの学習結果からデータの重みが決定されますが、GOSSでは単純にGradientの絶対値の大きさがそれにあたります。絶対値が大きい＝まだ十分に学習ができていない、小さい＝十分に学習ができていると解釈することができます。Gradient絶対値上位a%と、残りから（＝上位a%のサンプル以外から）b%をそれぞれ取得し学習データとします。単純にサンプリングしてしまうと勾配の小さい側のサンプルが過少に評価されてしまうため、勾配の評価の際は小さい側のみ$(1-a)/b$で割り戻します。非常に単純なアルゴリズムですが、すべてのサンプルを使う場合の良い近似となっているようです。

Exclusive Feature Bundling

　GOSSはサンプル数を減らすことによる高速化でしたが、こちらは特徴量数を減らすことによる高速化です。ヒストグラム作成時に高次元データではSparseなデータであることが多く、二つに特徴量の０である部分が交互になっていれば一つにまとめることができます。簡単には特徴量のセットを作成する際に、すでに保持している特徴量セットと新たな特徴量がコンフリクト（０でない部分が重なる？）が規定回数以下であれば一つにまとめることができるセットであることがわかります。その後、実際にどのように一つにまとめるかですが、まとめる前の一つ目の特徴量の最大値が二つ目の特徴量の最小値よりちいさいように変換します。実際の分割はまとめた特徴量でなく元も特徴量ごとに行われるらしいので、この分割点の位置を保存しておけば、ヒストグラム上は一つの列内の収まっている状態でも元の状態を復元できます。

カテゴリ特徴量の扱い方

　大本のCARTでのカテゴリ特徴量の扱い方は、A、B、,,,, Zとカテゴリがあった場合、AorNot,、BorNotという風に分割が評価されます。Scikit-learnはOne-Hot Encodeしてから実施しましょう。このように一つを取って、それ以外と比べます。しかし、LightGBMは少し違います。各カテゴリの統計量を計算、それに従ってカテゴリをソートし、Fisher-Groupingで二つにグループに分割を行います。したがって、LightGBMでは、AandCandW or Othersという風に分割が実行されるということです。

CatBoost

　Categorical特徴量の扱いに関してさらに異なる手法をしめしました。Target Encodingの1種で、数値でないものを数値に変換します。カテゴリを数値に変換するという点ではLightGBMも同じですが、少し異なります。LightGBMは推論時にはカテゴリしか見ません。一方Target Encodingは推論時においてもカテゴリを数値に変換し、学習済みの分割条件の評価を行います。

Category Encoders

　Category Encodersというライブラリがあり、すべてそちらにまとまっているので、非常に基礎的なものを簡単に説明します。

Greedy Target Encoding

　各カテゴリを正解の統計量（2値分類であればラベル１の割合、回帰であれば予測したい値の平均など）を数値をして置き換えます。最も単純で分かりやすいのですが、学習データのみの傾向を保持しているので、検証時にはあまり良い性能を示してくれません。用いないほうが良いでしょう。

Leave One Out Encoding

　少しでもオーバーフィットを減少させるために、全訓練データではなく、対象のサンプル以外の正解から統計量を算出します。こちらもできれば用いないほうが良いでしょう。さらに削減するために、データセットを5つ程度のグループに分け、あるグループのカテゴリの変換のために、そのグループ以外の正解を用いて統計量を計算するものもあります。Hold-Out Encodingと呼ばれるものです。

Label Encoding, Count Encoding

　もっと単純にはラベルを特に何も考えず整数に置き換えるもの、出現カウントで置き換えるものなどがあります。

Ordered Target Statistics

　上記の大体のものがオーバーフィットが気になるものばかりでした。そこでCatBoostが考案したものは、

データをランダムな順序で並び替える
あるデータのカテゴリの数値への変換は、そのデータより前にあるデータのみを用いて統計量を計算する

です。ただ学習時にはどうするかというと、各カテゴリの正解の平均などの統計量を用います。分割決定時にはランダムに並び替えられたもので行われるので、推論時に単純な学習データの平均を用いてもオーバーフィットしづらいのかなと思います。

その他

　オーバーフィットやリークがしづらい作りになっているようです参考。ここで一つ思いついたものがあるのですが、そもそも直近でカテゴリ特徴量への対応をしようと思っていないので、今後時間があれば試してからまた記事を書いてみたいと思います。

以上

9. Xgboost, LightGBM, CatBoost