LightGBM: A Highly Efficient Gradient Boosting Decision Tree

April 16, 2022

LightGBMは、GBDTを高速化したアルゴリズムであり、実験ではXGBoostよりも計算時間と消費メモリが少ない。 GBDTは決定木の分岐を決めるのに最も時間がかかる。 その前処理で特徴の値をソートする場合は、ソートがボトルネックになる。 勾配の小さいサンプルを除外することでデータを減らし、また、同時に0でない値にならない排他的な特徴をマージすることで特徴の種類を減らし、ソートを高速化した。

勾配の小さいサンプルは決定木が十分に学習しているとみなし、学習対象から除外する。 ただし、サンプルを除外するとデータの分布が変わるため、でランダムに勾配の小さいサンプルを選び、重みを与えたうえで学習対象にふくめる。 以下が具体的なアルゴリズムである。 goss

次元の多いデータがスパースな傾向にあることを利用し、同時に非0にならない特徴同士をまとめて次元数を減らす。 ただし、排他的なまとまりを見つける問題はNP困難なので、貪欲法で近似解をもとめる。 貪欲法は、問題を、特徴を点、排他的でない特徴間を辺にしたグラフの彩色問題におきかえる。 辺は共起する回数を重みにもつ。 点を次数の降順に並べ、順に、矛盾の少ない既存のまとまりに追加するか、新たなまとまりを生成することを繰り返す。 以下が具体的なアルゴリズムである。 bundle

論文をこちらからダウンロードできます。