SLIQ, CLOUDS, Oblivious Treeの解説

　今回は現在のGradient Boosting Decision Tree系統のデファクトスタンダードである、Xgboost、LightGBM、CatBoostでベースとして用いられているSLIQ, CLOUDS, Oblivious Treeについて解説します。

SLIQについて

　SLIQはXgboostのベースとなったアルゴリズムです。Pre-Sortアルゴリズムとも呼ばれます。CARTの紹介記事でも触れましたが、CARTはその処理時間のほとんどがソートに費やされます。SLIQはPre-Sortの名前の通り、ソート処理を事前に済ませておくことで速度向上を図るアルゴリズムです。単純にPre-Sortアルゴリズムを導入すると、同じハイパーパラメータであればCARTと同じ訓練結果しか出力することはできません。

SLIQのデータの持ち方について

　では、もう少しアルゴリズムの詳細にはいります。まずデータをどのように持つべきでしょうか。元論文では以下のように記載しています。
左端の表がもともとのデータです。AgeとSalaryからClassを予測する問題を考えています。Pre-Sortでは矢印の右側のようにデータを変換します。各特徴量ごとに昇順ソートを行い、その横に元のデータでの行番号を付与します。これらとは別にClass列はそのまま保持しておきます。
各特徴量に付与されている行番号を経由することで、正しいClassにたどり着くことができます。各列に追加データを付与するため、元のデータを保持したままでは約3倍のメモリを消費することになってしまいます。

各ノードでのSplitの選択方法

　次に各ノードでのSplitの選択方法を解説します。またまたCARTの紹介記事でも触れましたが、SLIQは実際にはノードごとの処理を行いません。同じ深さのノードすべてを一斉にSplit選択を行います。ただ、なぜそうしなければならないかを詳細に述べたいので、いったんノードごとでの選択方法から解説します。

　CARTと同じく各ノードではそのノードに含まれるサンプルのインデックスの配列を持っていること想定しています。しかし、CARTと異なりそのままでは非常に困ったことになります。CARTではインデックスに従いもともとのデータの配列にアクセスをすれば、簡単にデータを抽出できます。一方SLIQでは、各特徴量ごとにソートされてしまい、ノードが持っているデータがそのソートされたデータ中のどこに散らばっているかを知るすべがありません。上記の文献からの図では例えば、３と５のサンプルをノードが持つとして各特徴量ごとに位置が異なることがわかると思います。私が過去に実装した際は３つ実装を試しました。

（全サンプル数がN、現在のノードが持つサンプルの数をMとします。）

　一つ目は各特徴量のIndex部分を「頭からすべてひとつづつ」とり、現在のノードが持っているサンプルインデックスの配列に入っているかどうかを確認し、入っていれば現在のノードが持っているデータのため保持します。ただこれでは、配列すべてにアクセスするため、NxM回の処理が必要となります。二つ目はサンプルインデックスへの確認に、BinarySearchを用いました。これによりNxlog(M)回の処理に低減されます。しかし、それぞれ欠点があります。一つ目はMとNが同じ程度（Rootに近い側）で遅く、二つ目は逆にMがNに比べ非常に小さい場合に遅くなってしまうという欠点があります（ハイブリッドは試せていません）。また、実際にあまり早くなく意味がなさそうでした。

　三つ目に考えたのが、N個の要素をもつBooleanの配列を用意し、すべてFalseで初期化します。現在のノードが持つサンプルのインデックスの位置のみTrueに変更します。これにより、あるインデックスがそのノードに含まれるかどうかはBooleanの配列の該当のインデックスにアクセスするだけで判定することができます。つまり各特徴量ごとにM回の処理のみで済みます。一つ目と二つ目に比べると大幅に高速化されたと記憶しています。

　しかしながら上述の通り、これではXgboostなどには遠く及ばないほど低速になり、MaxDepthが8など深くなってしまうとScikit-LearnのDecisionTreeよりも低速になってしまいます。なぜでしょう？まず考えられる点は、Boolean配列へのアクセスがランダムアクセスであることです。しかしこれだけではありません。一番の問題は、各ノードに含まれていないサンプルに対しても含まれていないかどうかの判定を行う点です。全サンプルが１００万個、現ノードには２個しかサンプルが含まれていない場合でも、１００万回の判定処理が必要になります。深ければ深いほどこのようなノードが増えることで処理時間が増加していってしまいます。

　これを解決する方法が以前紹介させていただいたこちらの記事で紹介されています。CARTでは、同じ深さの異なるノードごとにサンプルの重複はありません。そのため、同じ深さのある一つのノードに含まれることが分かったサンプルは、ほかのノードではスキャンの対象とする必要がなくまります。N個の要素を持つ配列を作成しますが、今度はBoolean配列でなく、各サンプルが属するノード番号を持たせるようにします。この並びはもともとの入力データの並びです。こうすることで、全データのスキャンを大幅に抑えることができます。（配列へのランダムアクセスであることは抑えられないかと思います）

問題となるのはSplitの方法のみのため、SLIQについての紹介は以上です。

CLOUDS

　CLOUDSは、LightGBMのベースとなっているアルゴリズムです。Histogramベースアルゴリズムとも呼ばれます。

CLOUDSのデータの持ち方について

　まずCLOUDSの最大の特徴であるデータの持ち方について説明します。

　CARTやSLIQはデータを入力されたもののまま保持していますが、CLOUDSは異なり、Binningしたデータを保持します。0～N-1までの値を持つ整数へ変換することで、高速化が実現されます。LightGBMのデフォルトでは、0-255の8bitに収まる範囲で量子化を実施します。不思議なことに数百万サンプル（大体のデータでは普通各特徴量の数値のユニーク数は数万程度）の各特徴量をこの範囲に変換を実施しても特に精度の低下などはあまり見たことがありません。

　さらに、もう一つ重要なことがあります。Row Majorにデータを保持することです。詳細は後ほど解説します。Column Majorな言語の場合は転置したデータを保持します。

各ノードでのSplitの選択方法

　CLOUDSは高速ですが、適切に最適化をしてやらないとそこまで速度の恩恵を受けることができないかと思います。ここでは大雑把に3つ高速化のための処理を見ていきます。

1. Histogramの作成

　CARTでは各ノードでソートを行う必要がありました。一方CLOUDSではソート処理は必要なくなります。なぜならもともとの範囲が不明だったデータを固定された範囲に強制的に変更することで、データを並び替えることが不要になるからです（Binningの処理自体にはソートが必要になると思います）。0-255の範囲にデータがBinningされていれば、10の下には0-9のデータ以外がないことがなんの処理をしなくともわかっているからです。

　そのためCLOUDSでは、

0~N-1の大きさを持つ配列を作成
データをスキャンしながら配列に適宜クラスごとのカウント数などをインクリメンタルにカウントし、Histogram作成
作成したHistogramから最も良い特徴量と閾値を決定する

だけです。最も重いのは2番目のHistogramの作成です。

2. Row Majorな配置

　CARTでもSLIQでも基本的には特徴量分のループを回していました。しかし、CLOUDSは少し違います。まずなぜRowMajorなメモリ配置が必要かについて説明します。CARTもSLIQも（CLOUDS以外すべて？）RowMajorでもColumn Majorでもどちらでもあまり速度に影響はないと思います。

（データへのアクセスは、データのポインタ（N行D列）と現在のノードの持つサンプルのインデックス（M個の要素）をもって行います。M<=Nです）

なぜなら特徴量ごとにアクセスを行おうとすると、Column Majorの場合でも根ノードから少し深くなった段階で、メモリへの連続アクセスを行うことはできなくなるはずです。
CLOUDSでは特徴量ごとにHistogramの作成を行うのではなく、まずすべての特徴量についてのヒストグラムを作成し、その後最も良い分割点をスキャンします。
この全特徴量についてのヒストグラム作成の際に、CARTでは各特徴量ごとに一つ一つサンプルにアクセスしていましたが、
CLOUDSではあるサンプルにアクセスしそのBinnningされた全特徴量についてHistogramへの加算を行います。こうすることでメモリへの連続アクセスが可能となり、
かなりの高速化が実現できます。具体的には覚えていませんが、処理時間が数分の１になったと記憶しています。

3. Histogram作成回数の削減

　そのまま実装してしまうと、各ノードで毎回ヒストグラムを作成してしまうでしょう。しかしSLIQの部分でも説明したように、あるノードに含まれるサンプルはほかのノードには決して含まれません。これを考えると、

現在のノード($L$とする)のヒストグラム $H_L$ を計算すると、その兄弟ノード($R$)のヒストグラム $H_R$ は親ノードのヒストグラム $H$ との差分で計算することができる。つまり、$H_R = H - H_L$となる

このようにすることで大雑把には計算時間をさらに半分に削減することができます。また細かい点では、サンプル数の少ない側のヒストグラムを作成、もう片方は親ノードとの差分で計算するようにすればさらに速くなると思います。

　簡単に実装できる高速化の方法は以上です。全く手を付けられていませんが、ベクトル化、Cache-Aware Implementationなどもあるかと思います。ご存じの方がいらっしゃったらご教授いただけると非常にありがたいです。

Oblibious Tree

　Oblibious TreeはCatBoostのベースとなっているアルゴリズムです。大体の決定木系のアルゴリズムでは、各ノードで同じ分割条件が選ばれることはほぼないと思います。しかしこのアルゴリズムでは、同じ深さのノードではすべての分割条件が必ず同一になります。CPUでは学習速度の点ではあまり優れてはいませんが、推論速度という観点では非常に優れています。また、分割条件にあまり多様ではないため、汎化性能もBest-Fristと比較するとある程度良いと思います。

Oblibious Tree のデータの持ち方

　調べてもすぐに具体的な方法が出ていなかったため、どのような持ち方をしているのかがわかりませんでした。そのため、こうかな、と思う方法で実装してしまいました。データの持ち方に関してはSLIQと同じです。詳細は後述しますが、CARTのように単純にソートするのではなく、各ノードごとにサンプルをソートする、つまりソートキーが二つになるため、CARTと同じデータの持ち方では少し実装が面倒と思ったためです。

各ノードでのSplitの選択方法

　こちらもほぼSLIQと同じ方法で実装しました。少し異なる点として、SLIQが各ノードを独立して評価していたのに対して、こちらのアルゴリズムでは、それができない点です。少しづつ分割条件をずらしていくわけですが、同じ深さのノードのある一つのノードだけでそのノードの下に作成されるノードのサンプル数に変化が見られた時でも、その深さの全ノードの情報を集約して分割条件の評価を行わなければならなくなります。これは深くなればなるほど顕著になり、この点がSLIQよりも低速になってしまう原因かと思います。

推論の速度について

　上述の通り学習の速度ではあまり優れていませんが、同じ深さのノード間で同じ分割条件を共有しているとこが推論という点では、非常に高速化に寄与します。最終的にどの葉ノードに落ちるかわからないのはどのアルゴリズムでも変わらないのは当然ですが、例えばCARTではどの分割条件を適用すればよいかも根ノードから順に適用しなければわかりません。一方、Oblibious Treeは同じ深さではすべて同じ分割条件のため、完全に独立して条件を確認すればよいだけになります。各サンプルに対して32bit整数を付与し０に初期化して、0bit目を根ノードの分割条件、1bit目を深さ１のノードの分割条件という風にしてやれば、すべての条件を判定し終わった際にその整数自体がそのサンプルの属するノードの番号になるわけです（max_depthが32や64などという設定をすることは現実的にない（せいぜい8）と思うので、8bitや16bit程度でやった方が良いと思います）。

おわり

　Boosting Treeで主に使われているアルゴリズムについて簡単に説明しました。正直決定木を最初に実装した時のほうが時間がかかり、頭がこんがらかったかなと思います。もちろん、これらのベンチマーク的なライブラリがあったからこそ、高速化の余地があると思えた点はかなり大きいです。

以上