　勾配ブースティングについて勉強している過程で、「統計的機械学習の基礎」の10.9節を読みました。本節は、数式も多く理解に時間がかかりました。再度本節を読んだときに、すっと頭に入ってくるように記事にまとめておきたいと思います。

本記事のサマリ

　本記事では、10.9節のサマリと（10.32）式の導出方法を記載します。また、補足的に決定木の場合、なぜ $R _ j$ が推定できるのかについても述べたいと思います。なお、本記事の数式中に現れる文字の説明はしません。適宜、原本をご覧ください。

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

Amazon

10.9節のサマリ

　私の理解が正しければ、10.9節は下記のようにまとめられると思います。

ブースティング木のモデルは、 $f_M(x) = \displaystyle{\sum} _ {m=1}^M T(x; \Theta _ m)$ で表現される。ただし、 $\Theta _ m = \{R _ {jm}, \gamma _ {jm}\}_{j=1, \cdots, J}$ である。 $\Theta _ m$ は推定対象のパラメータである。
$\Theta = \{\Theta _ m\}_{m=1, \cdots, M}$ は、損失関数 $L$ を用いて、 $\Theta = {\rm argmin}\displaystyle{\sum} _ {n=1}^N L(y _ i, f _ M(x))$ で推定できる。
の厳密な最小化は非常に困難なので、前向き段階的加法的モデリングによって近似的な最小化を行う。
- ただし、 $R _ {jm}$ が既知の場合には、 $\gamma _ {jm}$ は容易に推定できるが、 $R _ {jm}$ が未知の場合には、前向き段階的加法的モデリングを用いても、 $R _ {jm}, \gamma _ {jm}$ 共に推定が困難な場合が多い。

(10.32)式の導出

　損失関数が指数損失、 $R _ {jm}$ が既知の場合において、前向き段階的加法的モデリングによって得られる $\hat{\gamma} _ {jm}$ が、 $\hat{\gamma} _ {jm} = \dfrac{1}{2} {\rm log} \dfrac{\sum _ {x_i \in R _ {jm}} w _ {i}^{(m)} I(y _ i = 1)}{\sum_{x _ i \in R _ {jm}} w _ {i}^{(m)} I(y _ i = -1)}$ であることを証明します。
　まず最初に、 $\hat{\gamma} _ {jm}$ の定義を確認します。 $\hat{\gamma} _ {jm}$ の定義は、

$\begin{eqnarray} \hat{\gamma} _ {jm} &=& \underset{\gamma_{jm}}{{\rm argmin}} \displaystyle{\sum}_{x_i \in R_{jm}}L(y_i, f_{m-1}(x_i)+\gamma_{jm}) \\ &=& \underset{\gamma_{jm}}{{\rm argmin}} \displaystyle{\sum}_{x_i \in R_{jm}} {\rm exp}\left( -y_i(f_{m-1}(x_i)+\gamma_{jm})\right) \\ &=& \underset{\gamma_{jm}}{{\rm argmin}} \displaystyle{\sum}_{x_i \in R_{jm}} w_i^{(m)} {\rm exp}\left( -y_i\gamma_{jm}\right) \tag{1} \end{eqnarray}$

です。ここで、理解しやすいよう表1のような場合に、(1)式の和がどのように展開されるかを見てみます。

　表1の場合、最後の和は、

$\begin{eqnarray} & & w_1^{(m)}{\rm exp}(\gamma_{jm})+w_2^{(m)}{\rm exp}(\gamma_{jm})+w_3^{(m)}{\rm exp}(-\gamma_{jm})+w_4^{(m)}{\rm exp}(-\gamma_{jm}) +w_5^{(m)}{\rm exp}(-\gamma_{jm}) \\ &=& (w_1^{(m)}+w_2^{(m)}) {\rm exp}(\gamma_{jm}) + (w_3^{(m)}+w_4^{(m)}+w_5^{(m)}){\rm exp}(-\gamma_{jm}) \\ &=& \left\{w_1^{(m)}I(y_1=-1)+w_2^{(m)}I(y_2=-1)+w_3^{(m)}I(y_3=-1)+w_4^{(m)}I(y_4=-1)+w_5^{(m)}I(y_5=-1)\right\} {\rm exp}(\gamma_{jm}) + \left\{w_1^{(m)}I(y_1=1)+w_2^{(m)}I(y_2=1)+w_3^{(m)}I(y_3=1)+w_4^{(m)}I(y_4=1)+w_5^{(m)}I(y_5=1)\right\} {\rm exp}(-\gamma_{jm}) \\ &=& \left\{\displaystyle{\sum}_{x_i \in R_{jm}} w_i^{(m)}I(y_i=-1)\right\} {\rm exp}(\gamma_{jm}) + \left\{\displaystyle{\sum}_{x_i \in R_{jm}} w_i^{(m)}I(y_i=1)\right\} {\rm exp}(-\gamma_{jm}) \tag{2} \end{eqnarray}$

となります。(1)式は表1に限らず(2)式の形になるので、(2)式を $\gamma _ {jm}$ について最小化すれば良いことになります。なので、(2)式を微分して、 $=0$ となる式を解けば良いです。微分して $=0$ とした式は、

$\begin{eqnarray} \left\{\displaystyle{\sum}_{x_i \in R_{jm}} w_i^{(m)}I(y_i=-1)\right\} {\rm exp}(\gamma_{jm}) - \left\{\displaystyle{\sum}_{x_i \in R_{jm}} w_i^{(m)}I(y_i=1)\right\} {\rm exp}(-\gamma_{jm}) =0 \end{eqnarray}$

です。これを解くと、 $\hat{\gamma} _ {jm} = \dfrac{1}{2} {\rm log} \dfrac{\sum _ {x_i \in R _ {jm}} w _ {i}^{(m)} I(y _ i = 1)}{\sum_{x _ i \in R _ {jm}} w _ {i}^{(m)} I(y _ i = -1)}$ が得られます。　この結果を、前向き段階的加法的モデリングに書き下してみると、図1のようになります。

アルゴリズム中の2-aの箇所が一般的には計算が困難で、工夫が必要なところになります。

補足（決定木の $R_j$ の推定について）

　「10.9節のサマリ」のところで「 $R _ {jm}$ が既知の場合には、 $\gamma _ {jm}$ は容易に推定できるが、 $R _ {jm}$ が未知の場合には、前向き段階的加法的モデリングを用いても、 $R _ {jm}, \gamma _ {jm}$ 共に推定が困難な場合が多い」と記載しました。決定木を構築する際も同様の問題に直面しているのですが、決定木の場合は主に2つの制約を設けることで、 $R_j$ の推定を容易にしています。その制約とは、下記の2つです。

$J=2$ としている。つまり一回の分岐で分かれるのは、二個のノードにしか分割されない。
$R_1 = \{X | X_j>s\}, R_2 = \{X | X_j\leq s \}$ の制約をかけている。つまり、 $R_1 = \{X | ||X||>s\}$ とか、 $R_1 = \{X | X_j X_k>s\}$ など、 $R_1, R_2$ の分割の仕方が無限にある中で、簡単な分割に限定している。