【はじめに】

皆様こんにちは。本日も見てくれてありがとうございます。

そして、今回は数学理論がメインのお話ですので、数式が嫌いな人はそっと閉じてください（笑）。

背景としては、最近研究の都合でランダムフォレスト(LightGBM)の条件分岐過程を理解する必要があったため、自分で計算してアウトプットできるレベルまで知識を深めようという狙いで情報収集をしておりました。

そのなかでLightGBM公式論文と、GBDTの元祖の論文を見つけたのですが、この2つの論文で分岐の良し悪しを決める数式が違うことに気づき、機械学習では実際どれが使われているのか？何が違うのか？を整理するための備忘録として計算式をまとめました。

結果的にはGBDTの元祖の論文(XGBoost)が実装されているっぽいのですが、該当コード(Ｃ++)を探して読む気になれなかったので、主に学習時の数学理論とサンプルデータを使った検証を行っています。

【目的】

LightGBM公式論文にある分散gainとXGBoostのgainについて比較を行う

【定義について】

まずは公式論文のLightGBM(2017)^1.，セクション3.1から分散gainの式を(1)に示します。

これはGOSS用の近似評価、言わば仕様設計レベルの定義のようで、本来実装されているLightGBM のgain式とは別物のようです。

\[ V_{j|O(d)}=\frac{1}{n_O} \left( \frac{( \sum_{x_{i}\in O :x_{ij}\leq d } g_{i} )^2} {n_{l|O}^j(d)} + \frac{( \sum_{x_{i}\in O :x_{ij}\leq d } g_{i} )^2} {n_{r|O}^j(d)} \right) \tag{1} \]

このとき(1)の\(n_{l|O}^j(d)\),\(n_{r|O}^j(d)\)は左右のノード。\(O\)はデータ集合として扱われており、ある特徴\(x_{j}\)を閾値\(d\)で分割した時の勾配のばらつきを表す。

簡単に書き換えるとこういう事らしい。 \[V(d)=\frac{1}{n}\left( \frac{(\sum g_{iL})^2}{n_{L}} + \frac{(\sum g_{iR})^2}{n_{R}} \right) \tag{1'} \]

そして、2つ目にXGBoost(2016)^2.，セクション2.2の式から損失関数の係数を省いた(2)がLightGBMの実装(C++)で使われている式との事です。

※今回は計算を単純化するため、λ，γ＝0とします

\[ gain=\left(\frac{ \left( \sum_{i}g_{i} \right)^2 }{\sum_{i}h_{i}+\lambda}\right)_{L} + \left(\frac{ \left( \sum_{i}g_{i} \right)^2 }{\sum_{i}h_{i}+\lambda}\right)_{R} - \left(\frac{ \left( \sum_{i}g_{i} \right)^2 }{\sum_{i}h_{i}+\lambda}\right)_{R+L}-\gamma　\tag{2} \]このとき、 \[ Ls=\frac{1}{2}(y_{i}-y_{i}^{'})^{2} \quad, \quad g_{i}=\frac{\partial Ls}{\partial y_{i}^{'}}=y_{i}^{'}-y_{i} \quad, \quad h_{i}=\frac{\partial}{\partial y_{i}^{'}} \left( \frac{\partial Ls}{\partial y_{i}^{'}} \right)=1 \]

\(g_{i}\)は予測値\(y_{i}^{'}\)を正・負どちらに動かすかを決定する方向ベクトルで、各行(データ点)の勾配。

\(h_{i}\)は損失\(Ls\)が2乗誤差の場合常に1で、誤差の修正強度を示す。

【検証】

これらを踏まえて、表1からそれぞれの方法でgain(情報利得)を計算します。

回帰問題の場合、初期予測値(BaseScore)は実測値の平均となるので、今回y’は全て12とします。

予測値について少し補足しておくと、

分岐はサンプルデータの実測値と予測値を使って計算しますが、次の式のように木が増える毎に1つ前の木の予測値と現在の葉の値（leaf value）を使って随時予測値を更新していきます。

\(t\)：木、\(\eta\)：学習率のとき、サンプル\(x_{i}\)の予測値は次式(3)で表せる \[y_{i}^{'t}=y_{i}^{'(t-1)}+ \eta \cdot leaf\ value_{t}(x_{i})　\tag{3}\] また、更新は初期予測値から最終予測まで繰り返すことから、\(f_{0}\)：BaseScoreとすると、結果的に(4)の関係が成り立つ。 \[y_{i}^{'}=f{0}+\sum_{t=1}^{T} \eta \cdot leaf\ value_{t}(x_{i})\tag{4}\]

予測値については以上です。詳しい情報については出典の2.、3.に同様の記載があると思いますので、ご確認ください。

では実際の計算に移ります。

表1　サンプルデータ（x1，ｘ2からｙを予測する想定）

	ｘ1	ｘ2	y(実測値)	y’(予測値)	y’－ｙ(勾配)
1	20	5	10	12	2
2	21	6	11	12	1
3	19	10	13	12	-1
4	18	11	14	12	-2

例題）表1の特徴\(x2\)を7以上かそうではないかの条件で分割する。

この場合、勾配\(g_{i}\)とヘッセ行列\(h_{i}\)は

\[g_{1}=12-10=2 \quad, \quad h_{1}=1\] \[g_{2}=12-11=1 \quad, \quad h_{2}=1\] \[g_{3}=12-13=-1 \quad, \quad h_{3}=1\] \[g_{4}=12-14=-2 \quad, \quad h_{4}=1\]

左右と全体のノード、およびデータ数\(n\)は

\[ \begin{eqnarray} \sum g_{L}=2+1=3\\ \sum h_{L}=1+1=2\\ n_{L}=2\\[8pt] \sum g_{R}=-1+-2=-3\\ \sum h_{R}=1+1=2\\ n_{R}=2\\[8pt] \sum g_{L+R}=2+1+(-1)+(-2)=0\\ \sum h_{L+R}=1+1+1+1=4\\ n_{L+R}=4\\ \end{eqnarray} \]

式(1’)より分散gainは \[V(d)=\frac{1}{4} \left( \frac{3^2}{2}+ \frac{(-3)^2}{2} \right)= \frac{1}{4}\cdot 9=2.25\]

式(2)より本来のgainは \[gain=\frac{3^2}{2} + \frac{(-3)^2}{2} - \frac{0^2}{4} = 9\] となります。

【結果】

上記の答えが示すところは、

(1’)は平均的な誤差改善度（＝計算の高速化に加え、そこそこ良い分割を選ぶための評価）で、(2)は理論的にも正統な誤差減少量を示しており、

共に条件分岐の良し悪しを決定するという目的で利用され、大きければ大きいほど良い指標となっています。

つまり(2)の方が正確なgain式と誤差減少量ですが、その分計算コストが大きく、

扱うデータサンプルが多ければ(2)より(1’)の方が計算が少ない分、時短で処理ができるというメリットがあり、分岐点の探索に使えそうな理論だという事が分かりました。

また今回の検証から、ランダムフォレストはランダムではなく、完全にデータ駆動で条件分岐を行っており、学習の段階で分岐条件と、どの特徴が重要だったかを決定している事が明確になりました。

そして、この計算から寄与率の本質的な理解ができます。

というのも、もし\(x1\)が\((20,21,25,26)\)という並びだった場合、 \(x1\)を23で分けるのと、\(x2\)を7で分けるのとでは、同じ\(g_{i}\)と\(h_{i}\)を使って計算するため、求められるgainは同じになります。

つまり、データの大小関係が完全に一致している特徴が含まれている場合、どちらの特徴を使っても同じ分岐になるため、分岐が行われたときの重要度が分散するという現象が起きます。

重要度が分散すると、結果的にどの特徴が影響を与えていたのか判断しずらくなるため、モデルに入力する前段階から共線性を持っているか否かの調査を行う事が重要と言えます。

【おわりに】

今回は備忘録も兼ねて、かなり技術的なお話だったのですが、

冒頭の目的にもあるように、はじめは条件分岐の仕方について調べるつもりが、結果として”モデルの学習過程を辿りました”という内容になってしまいました(;^ω^)

それだけ実装にはいろいろな仕様上の工夫が必要だという事ですね

【出典】

1. Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu(2017):"LightGBM: A Highly Efficient Gradient Boosting Decision Tree",NIPS'17: Proceedings of the 31st International Conference on Neural Information Processing Systems
   Pages 3149 - 3157
2. Tianqi Chen, Carlos Guestrin(2016):”XGBoost: A Scalable Tree Boosting System”, arXiv:1603.02754 [cs.LG]
3. Jerome H. Friedman(2001):”Greedy function approximation: A gradient boosting machine.”,Ann. Statist. 29(5): 1189-1232