LightGBM: a highly efficient gradient boosting decision tree
- 1. LightGBM:A Highly Efficient Gradient Boosting Decision Tree(NIPS 2017) Paper Friday Yusuke Kaneko
- 2. About Paper ● Authors Guolin Ke, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu(Microsoft) Qi Meng(Peking University) ● NIPS(2017) ● links ○ https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.p df ○ http://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradi
- 3. About LightGBM(LGBM) ● Microsoft謹製Gradient Boosting Decision Tree(GBDT)アルゴリズム ● 2016年に登場し、Kaggleなどで猛威を振るう → 「速い, 精度良い , メモリ食わない」というメリット ● 現在はPython , Rのパッケージが存在
- 5. Abstract ● GBDTはXGBoostなどの効果的実装がある一方、ビッグデータの(つまり、特徴量の 数やインスタンスの数が大きい)場合にはefficiencyやスケーラビリティが十分でな いという問題がある ● これを解決するために、 1. Gradient-based One-Side Sampling(GOSS) 2. Exclusive Feature Bundling(EFB) の新手法を提案 ● GBDT + GOSS +EFB をLightGBM(LGBM)と呼ぶ ● 実験の結果、従来手法の20倍の速さで同等のaccuracyを獲得可能
- 7. Motivation ● GBDTの問題点：特徴量の次元が高かったりデータサイズが大きい場合には efficiencyやスケーラビリティが十分でない → 理由：各特徴に対し、全てのあり得る分岐点のinformation gainの推定のために 全データを参照しないといけないから(当然、時間もメモリも食う) ● 上記の問題を解決した、スケーラビリティなどが十分なGBDTの実装を提案したい
- 8. Two novel techniques in LGBM 1. Gradient-based One-Side Sampling(GOSS) Idea: Infromation gainの定義より、勾配の絶対値 が大きい*データインスタンスがより大きく information gainに貢献 → 勾配の大きなインスタン スを残し、勾配の小さなインスタンスをダウンサン プリングする 2. Exclusive Feature Bundling(EFB) Idea: 実データ解析において特徴量のサイズは大 きくなるが、殆どの特徴はスパースで排他的 (exclusive)、つまり同時に非ゼロの値を取ることは ほぼない(例: One-hot encodingして生成した特徴) → greedy algorithmによって、これらの排他的特徴 をまとめることで特徴量を削減 (*注 : 以下勾配の大小という表現は全て絶対値についての表現とする)
- 10. CART(Classification and Regression Trees) ● 右図のように特徴空間を分割していき、 最適な分割点と特徴量を選んで最も 当てはまりが良くなりようにする Hastie et al .ESL p.306
- 11. GBDT ● (ざっくりいえば)勾配を元に 擬似的な残差を求め、それを 元に誤差が最小化されるように 弱分類器(GBDTの場合は決定木) をフィッティングさせる Hastie et al .ESL p.361 負の勾配 Friedman(2001) Annals of Statistics 擬似的な残差
- 12. XGBoost ● LGBMが出る前の主要なGBDT実装(Kaggleでもまだ現役で使ってる人は多い) ● 損失関数から直接、木の分岐点を求めるというidea(LGBMでも同様の発想を使う) ● Histogram-based algorithmとPre-sorted algorithmの2つを導入
- 13. Pre-sorted algorithm VS Histogram-based algorithm ● GBDTの訓練において一番時間がかかるのは最適な分割点を探すパート．これを 探すアルゴリズムは主に2つ ● 1. Pre-sorted algorithm ...事前にソートした特徴量の値上の、全ての有り得る分割点を数え上げる → 最適分割点は求まるが時間効率が悪くメモリも食うので非効率 2. Histogram-based algorithm … 連続値特徴量を離散値を取るbinにまとめて、このbinを元にヒストグラムを構成 する → 精度は僅かに犠牲になるがメモリ効率も時間効率も良い
- 14. Histogram-based algorithm ● 右図がHistogram-based algorithmの概要 ● LGBMではHistogram-based Algorithmのみが 採用されている.(XGBではPre-sortedが デフォルト) ● Histogram-based Algorithmによって 計算コストは O(#data * #feature)から O(#bin * #feature)に削減可能
- 15. Histogram-based algorithm ● Histogram-based algorithmにおいて、カテゴリデータは以下のように扱っている． (https://github.com/Microsoft/LightGBM/issues/1279) “So when #category is smaller than max_bin, the #bin is smaller than max_bin. otherwise it use the most frequent categories and stop when use 99% data.”
- 16. 3. GOSS
- 17. Two novel techniques in LGBM(再掲) 1. Gradient-based One-Side Sampling(GOSS) Idea: Infromation gainの定義より、勾配の絶対値 が大きいデータインスタンスがより大きく information gainに貢献 → 勾配の大きなインスタンスを残し、勾配の小さな インスタンスをダウンサンプリングする 2. Exclusive Feature Bundling(EFB) Idea: 実データ解析において特徴量のサイズは大 きくなるが、殆どの特徴はスパースで排他的 (exclusive)、つまり同時に非ゼロの値を取ることは ほぼない(例: One-hot encodingして生成した特徴) → greedy algorithmによって、これらの排他的特徴 をまとめることで特徴量を削減
- 18. Algorithm Description ● 「勾配の小さなインスタンスをダウンサンプリングする」ことについて → 何も考えずにそのまま実行すると、データの分布が変わってしまうので精度悪化 を招く → この問題を回避するのがGOSS
- 19. Algorithm Description 1. 定数a, b を設定 2. データインスタンスの勾配の絶対値に 従いソートし、上位a * 100%のデータを 選択．残りのデータのうちb * 100%を ランダムサンプリング． 3. その後、information gainの計算時に、 (1-a)/bだけサンプルされたデータを 重み付けで増幅させる
- 20. Theoretical Analysis ● GBDTにおいて、特徴の分割によるinformation gainは分割後の分散によって計算 される．GOSSを用いた時には以下の式で近似する 固定された木の枝内の訓練データ数 分割の左側のデータ数 分割の右側のデータ数 損失関数の 負の勾配 勾配の大きいデータ 勾配の小さいデータ ウェイト
- 21. Theoretical Analysis ● GOSSの近似誤差については上の定理が成立 (結局何を言っているかというと)分割が過度にアンバランスではない限り( つまり か でない限り)、近似誤差は第２項が dominateする.これは のオーダーで (第２項) なので、サンプルサイズが大きければ近似はほぼ正確になる
- 22. 4 . EFB
- 23. Two novel techniques in LGBM(再掲) 1. Gradient-based One-Side Sampling(GOSS) Idea: Infromation gainの定義より、勾配の絶対値 が大きいデータインスタンスがより大きく information gainに貢献 → 勾配の大きなインスタンスを残し、勾配の小さな インスタンスをダウンサンプリングする 2. Exclusive Feature Bundling(EFB) Idea: 実データ解析において特徴量のサイズは大 きくなるが、殆どの特徴はスパースで排他的 (exclusive)、つまり同時に非ゼロの値を取ることは ほぼない(例: One-hot encodingして生成した特徴) → greedy algorithmによって、これらの排他的特徴 をまとめることで特徴量を削減
- 24. Algorithm Description ● 排他的特徴量をバンドルにまとめることによって、計算コストをO(#data * #feature) から O(#data * #bundle)に削減が可能 問題. A. どの特徴量をまとめるべきなのか？ B.バンドルをどのように構成すべきなのか？
- 25. Algorithm Description(A) ● 最適バンドルを見つけるのはグラフ彩色問題と同等と見做せるが、これはNP-困難 問題． → 最適バンドルを見つけるのではなく、各特徴を頂点とした時に排他的でない全て の2特徴量についてエッジを引くという問題に縮小する → 貪欲法で解くことが可能
- 26. Algorithm Description(A) ● 完全に排他的でない特徴量も多く存在する → わずかなコンフリクトを許容すれば、さらに計算効率性を上昇させることが可能 → 定数γを各バンドルの最大のコンフリクトの割合の閾値として設定する
- 27. Algorithm Description(A) 1. まず、特徴量の全コンフリクトに 対応したウェイトで重み付けた エッジでグラフを構成する 2. 特徴量をグラフの次数（頂点に接す るエッジの重みの総和）で降順に ソート 3. 順序づけられた特徴量をそれぞれ 確認し、既存のバンドルにアサイン するか新しいバンドルを構成する
- 28. Greedy Bundlingについて ● 訓練の前に回すだけでよく、計算コストはO(#feature^2). → 特徴量が数百万ほどになると探索コストはかかる ● 順序付けのアルゴリズムとして、グラフをバンドルするのでなく、単に非ゼロ要素で ソートすれば良いという、よりefficientなアルゴリズムを提案．
- 29. Algorithm Description(B) ● 特徴量を上手く同じバンドルにマージする方法が必要 → つまり、特徴量のバンドルから元の特徴量の値を識別できることを保証しないと いけない ● Histogram-based algorithmを採用しているので排他的特徴量を異なるビンに入れ ることでバンドルを構成可能． 例: feature.A [0 ,10) feature.B [0, 20) feature.A [0 ,10) feature.B [10, 30) Bundle(A +B) [0 ,30) Bに+10 まとめる
- 31. 5. Experiments
- 32. Experiments ● 5つのPublicに入手可能なデータセットについて手法を比較 ● データセットの詳細は下記. 上2つはOne-hot encodingをしたスパースな特徴量が 殆どなデータセットなのに対し、下２つはdenseな特徴量とsparseな特徴量が混 在．
- 33. Overall Comparison ● 使用手法は 1. xgb_eta (XGBoost + Pre-sorted algoritgm) 2. xgb_his (XGBoost + Histogram-based algorithm) 3. lgb_baseline (LGBMからGOSSとEFBを抜いたもの) 4. lgb_baseline + EFB 5. LightGBM
- 34. Overall Time Cost Comparison ● lgb_baselineとEFB_Onlyの比較を見ても、EFBはスパースデータには大きな効果 あり(LETORはdenseなのでさほど変わらず) ● KDDデータのような大規模データではGOSSが特に効果あり out of memory
- 35. Overall Accuracy Comparison ● xgbと比較してもそこまで精度は変わらず … EFBやGOSSが精度悪化に繋がることはほぼない
- 36. Analysis on GOSS ● サンプリング比率を変えた時のSGBとGOSSの比較. →SGBよりGOSSの方がいい(SGBはoverallサンプリングの比率の設定しかできなく てGOSSはa,bの値を調整できるので当たり前な気はするが...)
- 37. (论文外の内容)
- 39. LightGBMのパラメータ ● 葉のサイズを主に調整する(max_depthも設定可能) ● カテゴリ変数の名前を指定してあげることでOne-Hot Encodingなしで取り扱いが可 能(One-hot encodingすると1/10くらい遅くなるからやるなとどこかにあったはず)
- 41. Conclusion
- 42. conclusion ● GOSS + EFB + GBDT の新アルゴリズムの提案 ● メモリ消費と計算時間を劇的に抑えつつ、従来手法と同等の精度維持を sparse/dense データで確認 ● また、XGBoostではOOMになるようなサイズのデータでも計算可能
- 43. Reference 1. Ke, Guolin, et al. "Lightgbm: A highly efficient gradient boosting decision tree." Advances in Neural Information Processing Systems. 2017. 2. Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016. 3. Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. No. 10. New York, NY, USA:: Springer series in statistics, 2001. 4. Friedman, Jerome H. "Greedy function approximation: a gradient boosting machine." Annals of statistics (2001): 1189-1232.