グラディエントブースティングとは何ですか？
定義
勾配ブースティングgradient boostingとは、決定木にブースティングを適用して性能を向上させる機械学習手法を指す。決定木の予測によって生じた残差を新たな従属変数として別の決定木を学習させ、これを繰り返して各ステージの残差に対応する最終モデルを決定する。
説明
勾配ブースティングは主に回帰問題で多用される古典的な機械学習手法であり、解釈可能性interpretabilityよりも予測性能自体が重視される状況で威力を発揮する。個人的には古典的手段の中では最もディープラーニングの精神に近い手法だと考えている。求める関数の近似のためにとにかく非線形活性化関数を乱暴に突っ込むように、具体的な形状は問わず決定木の組合せで問題解決を試みる点が似ている。実際にコンペティションなどで高い成績を残しており、優れた汎用性を幾度も証明してきた。
人気が高い点は別の利点にもつながる。原始的な形の勾配ブースティングを発展させ、手軽に使えるようにした XGBoost、LightGBM、CatBoost などのライブラリやアルゴリズムが公開されており、アクセスしやすい。アクセスしやすいのでより多く使われ、より多く使われることで良い成績を頻繁に残すという好循環が生まれた。
なぜ勾配か
残差を従属変数に置くという点は、一見すると偏微分で勾配を求めその方向へ値を移すという勾配降下法とは無関係に思えるが、形式的にどのように類似するかを見ていく。与えられたデータセット $\left\{ \left( x _{k} , y_{k} \right) \right\}_{k=1}^{n}$ に対して $t$ 段階モデル $f_{t}$ の $k$ 番目の残差 $r_{t} \left( x_{k} \right)$ は次のようになる。 $$ r_{t} \left( x_{k} \right) = y_{k} - f_{t} \left( x_{k} \right) $$ ここで $t$ 段階の $r_{t}$ を目標として新たに学習される決定木 $h_{t}$ は、ノードの分岐に応じて分かれる $i$ 番目領域 $R_{i}$ に属するデータセットの残差の平均 $\bar{r}_{i}$ を予測する、指示関数の線形結合と見なせる。 $$ h_{t} (x) = \sum_{i} \bar{r}_{i} \mathbf{1}_{R_{i}} (x) $$ この表記によれば $f_{t}$ は次のように決定木の和である。 $$ f_{t} (x) = h_{1} (x) + h_{2} (x) + \cdots + h_{t} (x) $$ ここでもし $h_{t}$ が $r_{t}$ を完全に予測できるなら、言い換えれば我々の目的通り $f_{t+1} \left( x_{k} \right) = y_{k}$ を満たせるなら $f_{t+1}$ は次を満たす。 $$ f_{t+1} \left( x_{k} \right) = f_{t} \left( x_{k} \right) + h_{t} \left( x_{k} \right) = y_{k} $$
通常回帰問題であれば損失関数 $L$ は MSE としてよく、これは残差二乗の平均である。 $$ L = {\frac{ 1 }{ n }} \sum_{k=1}^{n} \left( y_{k} - f_{t} \left( x_{k} \right) \right)^2 $$ $f_{t} (x)$ における $L$ のグラディエントは次のようになる。 $$ \begin{align*} & n \nabla L \\ =& {\frac{ \partial L }{ \partial f_{t} \left( x_{1} \right) }} + \cdots + {\frac{ \partial L }{ \partial f_{t} \left( x_{n} \right) }} \\ =& \sum_{k=1}^{n} -2 \left( y_{k} - f_{t} \left( x_{k} \right) \right) \\ =& -2 \sum_{k=1}^{n} h_{t} \left( x_{k} \right) \end{align*} $$ ここで注意すべき点は、通常の勾配降下法のように $x$ で微分するのではなく、$f_{t} (x)$ で微分していることだ。これは現在の設定がパラメータ空間で一点を探すのではなく、すべてのデータポイントに対する最適化を求めているため当然のことで、多くの文献が式としては記載しているが具体的説明を省略しているため理解が進まないことがある。結局全データセットで見れば次のような形をとる。 $$ \begin{align*} & \sum_{k} f_{t+1} \left( x_{k} \right) = \sum_{k} f_{t} \left( x_{k} \right) + \sum_{k} h_{t} \left( x_{k} \right) \\ \implies & \sum_{k} f_{t+1} \left( x_{k} \right) = \sum_{k} f_{t} \left( x_{k} \right) - {\frac{ n }{ 2 }} \nabla L \\ \implies & f_{t+1} (x) \approx f_{t} (x) - {\frac{ 1 }{ 2 }} \nabla L \end{align*} $$ ここで $\nabla L$ が $0$ に近いほど $f_{t+1} \approx f_{t}$ であり、我々が求めていた近似になる。
勾配降下法: 損失関数 $L$ の極小値を求めるために次のような更新規則を勾配降下法という。 $$\mathbf{w}_{t+1} \gets \mathbf{w}_{t} - \alpha \nabla L$$
最後に $\mathbf{w}_{t} = f_{t} (x)$ と置けば勾配ブースティングの本質が勾配降下法と同じであることが分かる。ここで学習率 $\alpha$ は $f_{t+1} (x) = f_{t} (x) + \alpha h_{t} (x)$ のように決定木の重みに対応させればよい。
なぜブースティングか
勾配ブースティングは文字通り逐次的に残差を従属変数とする点で、既存モデルが捉えられなかった弱点を補完するものと見なせる。これは別途重みを求めるようなプロセスがなくとも、十分にブースティングと呼べる。