勾配ブースティング

残差に木を当てはめて少しずつ足していく

勾配ブースティングは、決定木をたくさん組み合わせて1つの予測モデルを作るアンサンブル学習の手法の1つです。中心にあるのは、「今のモデルがまだ当てられていない部分」に次の木を当てはめ、その木を少しだけモデルに足す、という操作の繰り返しです。

この仕組みは、ギャレス・ジェームズ(Gareth James)、ダニエラ・ウィッテン(Daniela Witten)、トレバー・ハスティー(Trevor Hastie)、ロバート・ティブシラニ(Robert Tibshirani)による教科書『An Introduction to Statistical Learning』(2013年)の第8章で、回帰木のブースティングのアルゴリズムとして手順の形で示されています。この教科書は同じ箇所で「勾配ブースティング」という語そのものは使っていません。ただ、そこで説明されている「残差に木を逐次的に当てはめ、縮小して加えていく」という構造は、G検定で勾配ブースティングと呼ばれる手法の中核と同じ形をしています。この解説は、その教科書の手順を手がかりにして仕組みを説明します。

アルゴリズムの手順

回帰の問題を例にとると、手順は次のようになります。訓練データを (x_i, y_i) とし、i はデータの番号です。

1. 最初のモデルを f(x) = 0 とします。何も予測しないモデルなので、すべての訓練データについて残差 r_i は正解そのもの、つまり r_i = y_i です。
2. b = 1, 2, ..., B の順に、次の3つを繰り返します。
(a) 今の残差 r を目標値として、分割の回数が d 回(終端ノードが d+1 個)の小さな決定木 f_b を当てはめます。
(b) その木に小さな係数 λ を掛けてからモデルに足します。式で書くと f(x) を f(x) + λ × f_b(x) に置き換えます。
(c) 足した分だけ残差を減らします。式で書くと r_i を r_i - λ × f_b(x_i) に置き換えます。
3. 最後に出来上がるモデルは、B 本の木をすべて足し合わせた f(x) = λ × f_1(x) + λ × f_2(x) + ... + λ × f_B(x) です。

ポイントは、2本目以降の木が元の正解 y を直接学ぶのではなく、それまでの木が説明しきれなかった残差を学ぶことです。木を1本足すたびに残差が少しずつ削られ、モデルは前の段階の弱点を補う方向へ段階的に改善されていきます。

小さく縮めて足す理由

手順の (b) で木をそのまま足さずに λ を掛けているのが、この手法の大事な特徴です。λ は縮小パラメータと呼ばれる小さな正の数で、典型的には 0.01 や 0.001 が使われます。1本の木が残差をいっぺんに消してしまわないように、1回の更新で進む量をわざと小さくしているわけです。

その代わりに、λ が小さいほど同じだけ残差を減らすのに多くの木が必要になります。つまり λ は学習の速度を決める値であり、木の本数 B とは片方を小さくすればもう片方を大きくする必要がある関係にあります。

木の大きさを決める分割数 d

もう1つの調整点が、各木の分割の回数 d です。d は1本1本の木がどれだけ複雑な形を表せるかを決めます。d = 1 のとき、各木は1回だけ分割する切り株のような木になり、スタンプと呼ばれます。スタンプは1つの変数しか使わないので、スタンプを足し合わせたモデルは、変数ごとの効果を足し合わせた加法モデルを当てはめることに相当します。d を大きくすると、木が複数の変数の組み合わせを表せるようになります。

まとめると、この手法の振る舞いは主に3つの値、木の本数 B、縮小パラメータ λ、分割数 d で調整されます。

「勾配」という名前について

参考にした教科書には、この手法がなぜ「勾配」と呼ばれるのかの説明はありません。ここで確かに言えるのは、残差を目標にして木を当てはめ、少しずつモデルを更新するという手順までです。名前の由来については、残差を少しずつ減らす方向にモデルを動かしていく更新の仕方が、損失を小さくする方向へ少しずつ進む考え方と関係していると考えられますが、この解説では根拠となる資料で確かめられていません。