勾配ブースティング決定木

勾配ブースティング決定木#

Gradient Boosting Machine#

複数の関数に重みをかけて足し合わせた関数

f (x) = f_{0} (x; θ_{0}) + β_{1} f_{1} (x; θ_{1}) + \dots + β_{M} f_{M} (x; θ_{M})

の形で予測モデルを構築することを考える。ここで $θ_{0}, \dots, θ_{M}$ は関数を形づくるパラメータ（例えば線形回帰の重みや決定木の分岐の閾値）である。

このモデルは $β_{1}, β_{2}, \dots, β_{M}$ と $θ_{0}, θ_{1}, \dots, θ_{M}$ のパラメータを推定する必要がある。今回はすべてのパラメータを一度に学習するのではなく、 $β_{m} f_{m} (x; θ_{m})$ を一つずつ学習していく方法を考える。具体的には次のように行う。

前向き段階的加法モデリング（forward stagewise additive modeling）

$f_{0} (x) = 0$ で初期化
$m = 1$ から $M$ までについて、
1. パラメータを推定する： $(β_{m}, θ_{m}) = \underset{β, θ}{a r g m i n} \sum_{i = 1}^{N} L (y_{i}, f_{m - 1} (x_{i}) + β f (x_{i}; θ))$
2. 新たなモデルを足す： $f_{m} (x) = f_{m - 1} (x) + β_{m} f (x; θ_{m})$

これを前向き段階的加法モデリング（forward stagewise additive modeling）という。ブースティングはこの方法でアンサンブル学習を行う。

誤差関数が二乗誤差 $L (y, f (x)) = (y - f (x))^{2}$ の場合、

\begin{array}{r} \begin{aligned} L (y_{i}, f_{m - 1} (x_{i}) + β f (x_{i}; θ)) & = (y_{i} - f_{m - 1} (x_{i}) - β f (x_{i}; θ))^{2} \\ = ({residual}_{i, m - 1} - β f (x_{i}; θ))^{2} \end{aligned} \end{array}

となり、 $m - 1$ 回目のモデルの残差 ${residual}_{i, m - 1} = y_{i} - f_{m - 1} (x_{i})$ を近似するように $m$ 回目のモデル $β f (x_{i}; θ)$ を学習させていると捉えることができる。残差が大きければそれだけ訓練中に重視されるため「間違えた箇所を重点的に学習する手法」とも捉えることができる。

最適化の観点からの説明#

勾配降下法#

数理最適化において関数の最小化問題

min_{x} f (x)

を解く方法のひとつに勾配降下法（gradient descent method）あるいは最急降下法（steepest descent method）と呼ばれるものがある。これは目的関数の微分のベクトルである勾配

\begin{array}{r} \nabla f (x) = [\begin{array}{c} \frac{\partial f (x_{1})}{\partial x_{1}} \\ ⋮ \\ \frac{\partial f (x_{m})}{\partial x_{m}} \end{array}] \end{array}

を用いて

x_{m} = x_{m - 1} - α_{m - 1} \nabla f (x_{m - 1})

という値の更新を何度も繰り返して最適化を行っていく。ここで $α$ は学習率と呼ばれるパラメータで、値の更新量が多すぎると最適解を通り過ぎてしまうことがあるので小さめの値を乗じて更新幅を抑えるために用いられる。

最終的に $M$ 回反復して得た最適解 $x^{*}$ は

x^{*} = x_{0} - α_{1} \frac{\partial f (x_{1})}{\partial x_{1}} - α_{2} \frac{\partial f (x_{2})}{\partial x_{2}} - \dots - α_{M} \frac{\partial f (x_{M})}{\partial x_{M}}

となり、ブースティングにより得られる予測モデル

f (x) = f_{0} (x; θ_{0}) + β_{1} f_{1} (x; θ_{1}) + \dots + β_{M} f_{M} (x; θ_{M})

と同様に重み付き和の形になる。

ブースティング#

ブースティングは勾配降下法を機械学習で行っていると捉えることができる。

機械学習においては予測値 $f (x)$ と実測値 $y$ の誤差の最小化問題

min_{f (x)} L (y, f (x))

を解きたいため、勾配は誤差関数の予測モデルによる微分 $\frac{\partial L (y, f (x))}{\partial f (x)}$ によって得られる。

二乗誤差 $L (y, f (x)) = \frac{1}{2} (y - f (x))^{2}$ の場合、負の勾配は残差である

- \frac{\partial L (y, f (x))}{\partial f (x)} = y - f (x) = residual

前向き段階的加法モデルの節で「二乗誤差の場合は残差を近似するように学習している」と述べた。

L (y_{i}, f_{m - 1} (x_{i}) + β f (x_{i}; θ)) = ({residual}_{i, m - 1} - β f (x_{i}; θ))^{2}

これにより、学習されるモデル $β f (x; θ)$ は負の勾配を学習するようになり、最終的にそれらの和となるモデルは勾配降下法を解いた状態を近似することになる。

正則化つきGBDT#

$n$ 個の観測データがあり、 $m$ 次元の特徴量があるとする。

D = {(x_{i}, y_{i})}, | D | = n, x_{i} \in R^{m}, y \in R

勾配ブースティング決定木のモデルは次のように表される

{\hat{y}}_{i} = ϕ (x_{i}) = \sum_{k = 1}^{K} f_{k} (x_{i})

ここで

$f_{k} \in F$ は予測器
$F = {f (x) = w_{q (x)}}$ は回帰木の空間
- $q : R^{m} \to T$ は入力データ $x$ を木の各葉のインデックスに割り振る写像。 $T$ は各木の葉の数
- $w \in R^{T}$ は葉の重み（weights）と呼ばれ、予測に使われた葉の出力値。予測値は $w_{q (x)}$ の和となるので予測値のベースでもある

学習の際は正則化付き誤差関数

L (ϕ) = \sum_{i = 1}^{n} l (\hat{y}, y_{i}) + \sum_{k} Ω (f_{k})

を最小化する。ここで $l$ は微分可能な凸関数である誤差関数で、 $Ω$ は正則化項

Ω (f) = γ T + \frac{1}{2} λ | | w | |^{2}

学習は加法的に行うため $t$ 番目の誤差は次のようになる。

L^{(t)} (ϕ) = \sum_{i = 1}^{n} l (y_{i}, {\hat{y}}^{(t - 1)} + f_{t} (x_{i})) + Ω (f_{t})

テイラー展開による近似#

この誤差を二次近似したものを使うことで計算量を削減することもできることが知られている（Friedman et al., 2000）

L^{(t)} \approx \sum_{i = 1}^{n} [l (y_{i}, {\hat{y}}^{(t - 1)}) + g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t})

ここで

\begin{array}{r} g_{i} = \frac{\partial l (y_{i}, {\hat{y}}^{(t - 1)})}{\partial {\hat{y}}^{(t - 1)}} \\ h_{i} = \frac{\partial^{2} l (y_{i}, {\hat{y}}^{(t - 1)})}{\partial ({\hat{y}}^{(t - 1)})^{2}} \end{array}

定数項を省略すると

{\tilde{L}}^{(t)} = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + Ω (f_{t})

葉 $j$ におけるインスタンス（サンプル）の集合を $I_{j} = {i | q (x_{i}) = j}$ と表記すると、次のように書き換えることができる

\begin{array}{r} \begin{aligned} {\tilde{L}}^{(t)} & = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} \\ = \sum_{j = 1}^{T} [(\sum_{i \in I_{j}} g_{i}) w_{j} + \frac{1}{2} (\sum_{i \in I_{j}} h_{i} + λ) w_{j}^{2}] + γ T \end{aligned} \end{array}

固定した木の構造 $q (x)$ について、葉 $j$ の最適な重みは

w_{j}^{*} = - \frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i} + λ}

となる。

L1の場合

\begin{array}{r} \begin{aligned} {\tilde{L}}^{(t)} & = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} + α \sum_{j = 1}^{T} | w_{j} | \\ = \sum_{j = 1}^{T} [(\sum_{i \in I_{j}} g_{i}) w_{j} + \frac{1}{2} (\sum_{i \in I_{j}} h_{i} + λ) w_{j}^{2}] + γ T \end{aligned} \end{array}

L1の場合

\begin{array}{r} \begin{aligned} {\tilde{L}}^{(t)} & = \sum_{i = 1}^{n} [g_{i} f_{t} (x_{i}) + \frac{1}{2} h_{i} f_{t}^{2} (x_{i})] + γ T + \frac{1}{2} λ \sum_{j = 1}^{T} w_{j}^{2} + α \sum_{j = 1}^{T} | w_{j} | \\ = \sum_{j = 1}^{T} [(\sum_{i \in I_{j}} g_{i}) w_{j} + α | w_{j} | + \frac{1}{2} (\sum_{i \in I_{j}} h_{i} + λ) w_{j}^{2}] + γ T \end{aligned} \end{array}

$\sum_{j = 1}^{T} [\cdot]$ の内側を整理すると

w_{j}^{*} = - \frac{\sum_{i \in I_{j}} g_{i} \pm α}{\sum_{i \in I_{j}} h_{i} + λ}

最適な重み $w_{j}^{*}$ を誤差関数に戻すと

{\tilde{L}}^{(t)} (q) = - \frac{1}{2} \sum_{j = 1}^{T} \frac{(\sum_{i \in I_{j}} g_{i})^{2}}{\sum_{i \in I_{j}} h_{i} + λ} + γ T

となり、これ木の構造 $q$ の品質をスコアリングする関数として使うことができる。