LightGBM: A Highly Efficient Gradient Boosting Decision Tree

論文を自分なりにまとめる。（未完、ほぼ日本語訳かも）

papers.nips.cc

　Abstruct

Gradient Boosting Decision Tree(GBDT)は機械学習で人気のアルゴリズムであり、 XGBoost, pGBRTなどの実装があるが、まだまだ演算効率やスケーラビリティは良くない。分岐ポイントになる可能性がある箇所で特徴量ごとにすべてのデータをスキャンする必要があり、その処理に時間がかかってしまうことが原因としてあげられる。そこでこの問題に取り組むために、 Gradient-based One-Side Sampling（GOSS）、Exclusive Feature Bundling(EFB)という２つの方法を提案する。 GOSSは小さいGradientsになるデータインスタンスを取り除いて、残りをInformation gainに利用する。 EFBは互いに独立している特徴を削減するアイディア。特徴を互いに独立していると証明するのはNP困難だが、貪欲アルゴリズムを利用すると非常に良い予測結果となった。たくさんの公開されているデータで実験したところ、精度を保ったまま従来のGBDTより２０倍も高速となることがわかった。

1. Introduction

機械学習のアルゴリズムとして広くGBDTは使われているが、大きなデータを扱うときの実行時間が非常に長いという問題がある。データのInstanceを減らすと良いが、その方法は自明ではない。データのインスタンスとは特徴量を列としたときの行にあたる。扱うデータ種のようなものと自分は認識している。データをサンプリングする方法として、Weightsに従ってサンプリングする方法があるが、Weightsがわからないと適用できないため、シンプルにGBDTに適用することはできない。そこで２つの方法を提案する。

Gradient-based One-Side Sampling(GOSS)

GBDTの厳密なWeightはわからないが、Gradientsが違うとInformation gainの計算過程が違うことに気づいた。特に、大きなGradientsはよりInformation gainに対する寄与が大きい。なのでダウンサンプリングするときにInformation gainの精度を保つために大きなGradientsをもつデータInstanceを残すようにすればよく、小さいGradientsの中からランダムに削除するようにする。このようにすることでランダムにサンプリングするより、Information gainの精度を保つことに成功した。