Gradient Tree Boosting
概要
問題設定
予測モデルの出力f(x)とその差分を計算するロス関数を定義する
$ l\left(y_{n}, f\left(x_{n}\right)\right)
これは複数の関数の和として表される、加法的モデルであるとする。(t回学習ステップがある)
$ f(x)=\sum_{i=1}^{t} f^{(i)}(x)
データ点に対する当てはまりだけだとオーバーフィットするので正則化項を加えた $ \mathrm{Obj}=\sum_{n=1}^{N} l\left(y_{n}, f\left(x_{n}\right)\right)+\Omega(f)
を最小化する問題を考える
各ステップでの学習
ある学習ステップtにおいて、それまでに決定した関数は全て固定する。
$ f^{(t)}のみについて学習し$ f^{(1)}~$ f^{(t-1)}は固定。
そのため、各学習ステップ時点での出力は下記のように変化する。
$ \begin{aligned} \tilde{y}^{(0)} &=0 \\ \tilde{y}^{(1)} &=\tilde{y}^{(0)}+f^{(1)}=f^{(0)}+f^{(1)} \\ \tilde{y}^{(2)} &=\tilde{y}^{(1)}+f^{(2)}=f^{(0)}+f^{(1)}+f^{(2)} \\ \vdots & \\ \tilde{y}^{(t)} &=\tilde{y}^{(t-1)}+f^{(t)}=\sum_{i=1}^{t-1} f^{(i)}+f^{(t)} \end{aligned}
つまり、ある時点での出力は、t-1時点での出力に、t時点の関数fの値を加えてもとめられる。
目的関数に代入すると
https://gyazo.com/89fb8c71ba27ecea62670b9a0b01f731
t-1時点までの正則化項はt時点で変化しないため定数とみなせる。
目的関数のロス関数の部分をテイラー展開して二次の項までの近似を行うと https://gyazo.com/ec2b0600927c88b770c4f7c21e587d82
これを目的関数に代入し、最適化の際に関係のない定数の部分を省くと、
https://gyazo.com/8344ee1dc5ab4b3c0b841dcb9ed1e113
ObjはN個のデータに対する予測の差分の合計を求めている
g_nは勾配、h_nはヘシアン
g_n, h_nを直前の予測値で評価したものからなる
g_n, h_n以外の部分は、各ステップで解かなければならない関数は同じ
目的関数は上記。
そしてこの目的関数を木構造の予測器で解いて行く。