LightGBMの論文を読んだ記録

はじめに

LightGBM:A Highly Efficient Gradient Boosting Decision Tree
を読んだので記録しておきます。機械学習はど素人なので間違いや見当違いな点がありましたらぜひご指摘いただきたいです。

LightGBMとは

GBDT(Gradient Boosting Decision Tree,勾配ブースティング決定木)のなかで最近人気のアルゴリズムおよびフレームワークのことです。マイクロソフトの方々が開発されています。

LightGBMには新しい点が2つあります。1つ目はGOSS(Gradient-based One-Side Sampling)、2つ目はEFB(Exclusive Feature Bunding)です。
LightGBMは名前にlightとついている通り、軽い(計算が早く、メモリ消費が少ない)ことが売りのアルゴリズムです。GOSSはデータを減らす工夫、EFBは特徴量を減らす工夫となっています。

この論文は
1. Introduction
2. Preliminaries(準備)
3. GOSS
4. EFB
5. Experiments
6. Conclusion
という構成になっています。この投稿では理論部分である2〜4を扱います。

準備：なぜGOSSやEFBが必要なのか

決定木のアルゴリズムで一番時間がかかるのは木の構造を決める(つまりどこで分割するかを決める)部分だそうです。これを短縮することで効率的に学習が行えます。

そのためにXGBoostというアルゴリズムでは特徴量をヒストグラムを使って離散的なグループに分け、グループの境界だけで分割を試すという工夫がなされました。これによりあらゆる点で分割を試すsklearnやRのgbmパッケージよりXGBoostは効率的に学習が行えました。
(以前投稿したXGBoostの記事も参考にしてみてください XGBoostの論文を読んだ記録)

LightGBMではこのヒストグラムによるアプローチを取り入れた上で、さらに
1. GOSSを使ってデータを減らす
2. EFBを使って特徴量を減らす
ことに成功しています。

データを減らしたり、特徴量を減らしたりする手法は他にもありますが、
- SGD以外の手法はAdaBoostをベースにしているのでGBDTにはそのまま使えない
- SGDを使うと正確性が損なわれる
という理由であまり望ましくないようです。(この理由は私にはよく分かりませんでした)

GOSS

一般に決定木のアルゴリズムが分割する場所を探す際には勾配が計算されます。
そしてGBDTでは勾配が小さいデータは誤差が少ないことと同義です。もしそうした既によく訓練されているデータを省ければ訓練の効率を上昇させることができます。

ですが単純に勾配が小さいデータを消すとデータの分布が変わってしまい、正確さが損なわれます。
そこでGOSSでは以下の方法でデータを減らしています。
1. 勾配が大きいものは全て残す (例として上位60%を残すとします)
2. 勾配が小さいものに対してはランダムサンプリングを行う (例として全体の10%分を残し、残り30%は消すとします)
3. ランダムサンプリングしたものはデータ数がもとに戻るように定数倍する (この例では10%分のデータを4倍すればデータ分布は崩れません)
これがLigthGBMの行う工夫の1つ目、GOSSです。

EFB

特徴量がたくさんあるデータでは、スパース(ほとんどの値が0)になることがしばしばあります。
ほとんど0の特徴量同士を結合させ、特徴量の数を減らすことができれば、より効率的に学習が行えます。
これがEFBの基本となる考え方です。

そのためには
1. どうやって結合させる特徴量を選ぶか
2. どうやって結合させるか
の2つが問題となります。

(1)特徴量の選び方

もし2つの特徴量が同時に0以外の数をとる、ということが起きないならその2つの特徴量は結合できます。すごく簡単な例だと、男かどうかという特徴量と女かどうかという特徴量は同時に0以外の数を取らないため、1つにまとめられます。
また多少は衝突(同じインスタンスに対してどちらも0以外の値をとる)してしまっても、衝突率が小さければあまり情報を失わずにまとめることができます。

こうした衝突率の小さい特徴量の選び方の問題はNP-hard(最適解を多項式時間で見つけることは困難)だそうです。なので近似解を見つけるためにグラフの色分け問題に帰着させ、探索します。各特徴量を頂点として幾何的に考えるようですが、詳細は分かりませんでした。

(2)特徴量の結合の仕方

例えばA特徴量が0〜10、B特徴量が0〜20の値をとるとします。
この時Bの全ての値に+10してBの範囲を10〜30に変えてあげれば、AとBの情報をきれいに分けることができます。なお論文ではずらす項はoffsetと呼んでいました。

まとめ

これまで見てきたように、LightGBMではGOSSとEFBという2つの方法により効率的に訓練を行うことができます。論文ではXGBoostを比較しても有意に良い結果が出ていました。