LightGBMの勉強をした。
特徴
LighGBM では通常のGBDTに対してGradient-based One-Side Sampling (GOSS)とExclusive Feature Bundling (EFB) という2つの改善を行うことで精度を保ちつつ計算量を削減しています。
GOSSについて
決定木を最適化するときにどこのしきい値で区切るのかを探索するパートが最も計算量がかかります。 これを計算するには本来はある閾値 $d$ で分割したときの分散 $V_{j}(d)$ を計算する必要があります。 この計算をするには全データを見る必要があるので計算量が大変大きいです。 LightGBMでは $V_{j}(d)$ の代わりに勾配の大きなところと勾配の小さなところからサンプリングして計算した分散 $\tilde{V}_{j}(d)$ を計算することにより、計算量を抑えています。
\[V_{j|O}(d)=\frac{1}{n_ { O } } \left( \frac { \left( \sum _ { \left\{ x _ { i } \in O : x _ { i j } \leq d \right\} } g _ { i } \right) ^ { 2 } } { n _ { l | O } ^ { j } ( d ) } + \frac { \left( \sum _ { \left\{ x _ { i } \in O : x _ { i j } > d \right\} } g _ { i } \right) ^ { 2 } } { n _ { r | O } ^ { j } ( d ) } \right)\] \[\tilde { V } _ { j } ( d ) = \frac { 1 } { n } \left( \frac { \left( \sum _ { x _ { i } \in A _ { l } } g _ { i } + \frac { 1 - a } { b } \sum _ { x _ { i } \in B _ { l } } g _ { i } \right) ^ { 2 } } { n _ { l } ^ { j } ( d ) } + \frac { \left( \sum _ { x _ { i } \in A _ { r } } g _ { i } + \frac { 1 - a } { b } \sum _ { x _ { i } \in B _ { r } } g _ { i } \right) ^ { 2 } } { n _ { r } ^ { j } ( d ) } \right)\]本来の分散との誤差も $\mathcal { O } \left( \frac { 1 } { n _ { l } ^ { j } ( d ) } + \frac { 1 } { n _ { r } ^ { j } ( d ) } + \frac { 1 } { \sqrt { n } } \right)$ なのでサンプルサイズ $n$ が大きければとても良い感じになる。
GOSSのアルゴリズム(原論文[1]より引用)
EFBについて
特徴量が高次元のとき、多くの場合ではそれはスパース性を持っています。つまり殆どの特徴量成分はゼロと考えることができます。よって、特徴量それぞれの成分の多くは互いに排他的、つまり、同時に非ゼロの値を取らないという性質が期待できそうです。
同時に非ゼロにならないという性質を持っている特徴量成分たちを Bundle としてまとめてあげることで、特徴量の次元削減をするというのがEFBの主要なアイデアです。
実際には成分同士が完全に排他的であることはないので、$K$ 回までは同時に非ゼロになることを許すという感じで適当な閾値をつくって Bundleを作っていきます。これをやっているのが、原論文 [1] のAlgorithm 3です。ただ Algorithm 3通りにやると計算量が $O(\text{特徴量数}^2)$ となってしまうので、Bundleを作るのではなく、非ゼロ成分の数でソートするみたいです。非ゼロ成分の個数が大きくなるほど、同時に非ゼロを取る確率もあがるからというイメージですね。
Greedy Bundlingのアルゴリズム(原論文[1]より引用)
そうやって作った Bundleを使って、特徴量を次元削減します。あるBundleを1次元のの特徴量にまとめるときに重要な条件は、まとめた特徴量から元の特徴量が復元できるというものです。例えば特徴量$A$ は $[0,10)$ をとり、特徴量 $B$ は$[0,20)$ を取るとします。 $A$ と $B$ をまとめるときに次のような操作をします。 まず、$B$ に 10 だけ足して (offset と原論文では呼んでいます)、範囲を $[10,30)$ にしてから、$[0, 30]$ の範囲で $A$ と $B$ をマージするという方法です。これを具体的に行っているのが Algorithm 4です。
Merge Exclusive Features(原論文[1]より引用)