【論文紹介】LightGBM: A Highly Efficient Gradient Boosting Decision Tree
ちゃんと論文読んでなかったので、、、
課題
GBDTにおいて、最も計算コストのかかるのが決定木の学習、その中でも分岐の決定。
従来のGBDTにおいては、全てのあり得る分岐点を考慮するため、全てのレコードを元に学習を行うため、以下の二つが増えるごとに、計算コストも上がる。
- レコード数
- 特徴量数
モデルで扱うレコード数と特徴量数を共に減らせれば、計算効率がよくなって、データ数多くてもfeature数多くてもGBDTが実用的な学習速度で使用できるようになるっていう内容
提案手法概要
Gradient-based One-Side Sampling (GOSS)
- レコード数を減らすアルゴリズム
- lossの減少への貢献が大きいレコードと、小さいレコードという二つの集合に分けて、小さいレコードに対してランダムサンプリングすることでレコード数を減らす
- 単純にレコード数減らすと分布が変わってしまうので、それを考慮している
Exclusive Feature Bundling (EFB)
- 特徴量数を減らすアルゴリズム
- 同じレコードにおいて同時にnon zeroにならない（もしくはなるが許容量である）特徴量をカテゴリー値に変換し、さらに一つの特徴量としてまとめることで減らす
※ 同じレコードにおいて同時にnon zeroにならない特徴量＝one-hotだったり許容量であるという意味だとbag of wordsなど
GBDTにおけるsplitアルゴリズム
分岐点を探索するアルゴリズムは2種類
pre-sorted
- 特徴量の値をソートして、全ての分岐点を探索する
- 最適な分岐点が見つかるが、効率が悪い
histogram-based
- 値をbinで区切り、そのヒストグラムを使用する
- 効率が良い
論文における問題意識
ここで、より効率が良い、つまり実用的であるhistogram-basedを使用したいが、pre-sortedはsparseな特徴量において本来無視すべき0の値を無視できる一方、histogram-basedだとそれができない。0を0という値として扱ってしまうため、sparseな特徴量に対して学習効率が悪くなってしまう。
そのため、histogram-basedでsparseな特徴量における0を無視できるようにする必要がある。
※ XGBoostではpre-sorted, histogram-based共にサポートしている
提案手法詳細
各提案手法の詳細
Gradient-based One-Side Sampling (GOSS)
概要
- lossの減少への貢献が大きいレコードと、小さいレコードという二つの集合に分けて、小さいレコードに対してランダムサンプリングすることでレコード数を減らす
- 単純にレコード数減らすと分布が変わってしまうので、それを考慮している
手順
- レコードを勾配の絶対値で降順に並び替える
- 上位a件を部分集合Aとして取得
- 残りの(1-a)件からb件を部分集合Bとしてランダムサンプリング
- AとBの和集合を元に以下の式でIGの推定値を計算（Bのレコードに対しては定数(1-a)/bで重みづけされている）
※ 本来のIG
Exclusive Feature Bundling (EFB)
概要
同じレコード内で同時にnon zeroとならない特徴量（one-hotなど）同士を、一つの特徴量（bundle）としてまとめることで、特徴量数を減らす。 その際に、基本的には削減前と全く同じfeature histogramとなるようにする。つまり、元の特徴量を100%保持する。
以下の二つの手順で構成される
- マージする特徴量の組み合わせ探索
- マージの実行
重複の許容量
nonzeroの値が重複することはあるが、基本的にほとんど重複しない特徴量同士（bag of wordsなど）もまとめたい そのため、conflict（＝重複度合い）の許容量を決めて、最適な特徴量同士でまとめるようにする
- γ＝許容できるmaxのconflict rate
- (1-γ)nがconflictのないレコード数の最小値となる
マージする特徴量の組み合わせ探索
- グラフを用いた方法
- 用いない方法
の二つがある。後者は前者が計算コスト的にきつい時のための代替案
手順（グラフを用いた方法）
※ K=γn（conflict rate*レコード数）
- 各特徴量をノード、conflictの度合いを重みつきエッジとしたグラフを構築
- 重複度合いの大きさの総和で降順にソート
- 大きいものから、γを元に既存のbundleに入れるか、新しいbundleを作成して入れるかを決定する
手順（グラフを用いない方法）
上記手順だと、feature多すぎると計算コスト高くなるので、featureが数百万ある場合はこちらの方法を使う
- non zeroの値が多い＝conflictしやすいとみなせるため、上記1.2.においてグラフを作成せず、特徴量ごとのnon zeroの値の総和でソートする。
- 3.は共通（と書いてあるがconflict countどう求めるかは不明）
特徴量のマージ
histogram-basedアルゴリズムにおいて、binの作成時に、bundle内のfeatureのvalue同士が被らないようにoffsetを追加することによりマージする
例えば、
- [0, 10)の値をとるfeatureA
- [0, 20)の値をとるfeatureB
の二つで構成されるbundleの場合、Bにoffset=10を追加し、Bを[10, 30)に変換する。
それにより、[0, 30)の値をとる一つのfeatureとして使用可能になる
まとめ
- one-hotやbag of wordsみたいなスパースな特徴量を、カテゴリー値に変換することでdenseにする
- その上で、重複がない（もしくは許容できる）特徴量同士をマージする
この二つの処理を通して、特徴量を削減している。
思ったこと
学習時における計算効率を上げるために本来必要なかった処理を挟むという内容で推論速度への改善はないので、学習速度上がる代わりに追加した処理分推論速度は遅くなるのではないかと思った
一方で、EFBがあるからこそカテゴリー値やnull値をそのまま入力として許容してくれるというLightGBMの便利さが実現できているように思った（今後調べる必要）
実際推論速度に関してはXGBoost, CatBoostに比べて最遅らしい
