本記事のサマリ

　本記事では、勾配ブースティング木の考え方について説明します。まず、最初に前向き段階的加法的モデリングと呼ばれるアルゴリズムを紹介します。次に、最急降下法と勾配ブースティング木の漸化式の関係性について説明します。最後に、これらをまとめた勾配ブースティング木のアルゴリズムを示します。なお、本記事に記載の数式や文字は全て「統計的機械学習の基礎」にならっており、本記事では定義しません。

統計的学習の基礎 ―データマイニング・推論・予測―

Amazon

前向き段階的加法的モデリング

　前向き段階的加法的モデリングとは、目的関数 $\sum _ {i=1}^N L(y _ i, f(x _ i))$ を $\boldsymbol{f} = (f(x_1), \cdots, f(x_N))$ について近似的に最小化する手法の一つです。アルゴリズムを図１に示します。

　勾配ブースティング木を一言で表すと、前向き段階的加法的モデリングにおいて予測関数を、

$f_M(x) = \displaystyle{\sum_{i=1}^M} T(x;\Theta_m) \tag{1}$

に制約して解くアルゴリズムです。
　（１）式に現れる $\Theta_m$ について、もう少し詳細に説明します。図１の２－１と（１）式をあわせると、

$\Theta_m = \underset{\Theta}{\rm argmin} \displaystyle{\sum_{i=1}^N}L(y_i, f_{m-1}(x_i)+T(x;\Theta))　\tag{2}$

となります。 $\Theta_m$ は、終端領域 $\{R _ {jm}\} _ {j=1, \cdots, J}$ とその領域のパラメータ $\{\gamma _ {jm}\} _ {j=1, \cdots, J}$ です。多くの損失関数において、 $\{R _ {jm}\} _ {j=1, \cdots, J}$ が決まれば、 $\{\gamma _ {jm}\} _ {j=1, \cdots, J}$ は容易に求まるという関係が知られています。なので、図１の２－１を $\{R _ {jm}\} _ {j=1, \cdots, J}$ を求めるステップと、 $\{\gamma _ {jm}\} _ {j=1, \cdots, J}$ を求めるステップに分けて計算を行います。

最急降下法（ $\{R _ {jm}\} _ {j=1, \cdots, J}$ の推定方法）

　勾配ブースティング木では、 $\{R _ {jm}\} _ {j=1, \cdots, J}$ を求めるステップにおいて、最急降下法の考え方を用います。まずは、（３）式と（４）式をご覧ください。（３）式は最急降下法の漸化式、（４）式は（１）式から導出される漸化式です。

$\begin{eqnarray} f_{m}(x) &=& f_{m-1}(x) -\rho_m g_m(x) \tag{3} \\ f_{m}(x) &=& f_{m-1}(x) +T(x;\Theta_m) \tag{4} \end{eqnarray}$

　二つの漸化式を比較すると、最後の $-\rho _ m g _ m(x)$ と $T(x; \Theta_m)$ だけが異なることがわかります。そこで、特徴量を $x$ 、目的変数を $g _ m(x)$ とした回帰木をあてはめます。具体的には、

$\displaystyle{\sum_{i=1}^N}\left( -g_m(x_i)-T(x_i;\Theta_m)\right)^2$

の最小化を行います。なお、ステップ幅 $\rho _ m$ は重要ではないので1としています。図２にイメージ図を載せておきます。

$\{\gamma _ {jm}\} _ {j=1, \cdots, J}$ の推定方法

　 $\{R _ {jm}\} _ {j=1, \cdots, J}$ が推定できたら、 $\{\gamma _ {jm}\} _ {j=1, \cdots, J}$ を推定します。（２）式を変形すると、

$\gamma_{jm} = \underset{\gamma}{\rm argmin} \displaystyle{\sum_{x_i \in R_{jm}}}L(y_i, f_{m-1}(x_i)+\gamma)$

となります。これについては、

$T(x; \Theta_m) = \displaystyle{\sum_{j=1}^J}\gamma_{jm} I(x_i \in R_{jm})$

を使うと、比較的簡単に導出できます。

勾配ブースティング木のアルゴリズム

　以上をまとめると、勾配ブースティング木のアルゴリズムは図３のようになります。

　なお、初期化の仕方については「統計的機械学習の基礎」に説明がありませんでした。しかし、目的関数が $\sum _ {i=1}^N L(y _ i, f(x _ i))$ であることを踏まえると、自然な初期化だと思います。

まとめ

　今回は勾配ブースティング木のアルゴリズムの考え方について記事を書きました。正直、勾配ブースティング木を正しく理解することは難しく、今でも完全に理解したわけではありません。
　ただ、完璧に理解したわけではないものの、勾配ブースティング木を理解するポイントは、データに回帰木をあてはめるのではなく、勾配に回帰木をあてはめることだということはなんとか理解できました。最初にこの考え方に触れたときは、自分の中にない考え方だったので、非常に驚きました。
　次回の記事では、損失関数が最小二乗誤差のときの勾配ブースティング木を、Pythonでスクラッチ実装した結果について書こうと思います。