LightGBM: A Highly Efficient Gradient Boosting Decision Tree

[raxman0721]

論文

LightGBM: A Highly Efficient Gradient Boosting Decision Tree

著者/所属機関

Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang,Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu

1. どんなもの？

決定木のアンサンブル学習シリーズ。
GOSSとEFBという手法を使って、GBDT(Gradient Boosting Decision Tree)の約20倍のスピードアップを示せた。

2. 先行研究と比べてどこがすごい？

スピード。
精度をほぼ落とさず、スピードアップが出来た。

3. 技術や手法のキモはどこ？

GOSS(Gradient-based One-Side Sampling)

勾配が大きいサンプルに重心をおいてダウンサンプリングすることで、効率的に学習をすすめることが出来る。

1. 定数a,bを設定する。(それぞれ割合)
2. 弱学習器で予測して、loss(勾配)を出す。
3. 勾配の絶対値でソートする。
4. 上位a割をtopSetとして格納
5. 残ったデータのb割をrandSetとして格納
6. データの分布が変わらない様にrandSetに(1-a)/bだけ重み付けする。
7. 学習

上位からa割のサンプル(topSet)は全て学習に使うが、残りはb割(randSet)のみ使用。
randSetは最後に(1-a)/bをかけて重みを修正する。

EFB(Exclusive Feature Bundling)

スパースな特徴量同士をマージさせることで、特徴量の数を減らすことが出来る。
ワンホットエンコーディングしたものを元に戻すイメージ。

Algorithm 3でまとめる特徴量同士グループ分けする。 Algorithm 4では同じグループの特徴量を一つの特徴量にまとめる。

4. どうやって有効だと検証した？

複数の分類問題と、ランク付け問題のデータセットを使用。
それぞれスパースなデータとデンスなデータがあって、データ数もそれなりに多い。

• xgb_eta(XGBoost + Pre-ssorted algorithm)
• xgb_his(XGBoost + Histogram-based algorithm)
• lgb_baseline(LGBMのGOSSとEFBを使わなかったもの)
• lgb_baseline + EFB
• LightGBM (LGBMの全て使ったもの)

それぞれ上記5種類のモデルで比較。

学習時間の比較

学習時間はどのデータセットでも圧勝 またGOSSはデータセットが大きいデータの方が効果が大きい。 EFBはスパースなデータの場合は特に効果が大きい。

精度の比較

精度はほぼ変わらず。というか少し上がっている。

推移

5. 議論はある？

無い。

6. 次に読むべき論文は？

NIPS 2017