学生の時に統計的学習の基礎（Hastie,Tibshirani,Friedman 2009）を使って機械学習を学んでいたのですが、PRMLと違って勉強会の資料や勉強ブログなどの解説記事が少なく相応に苦労したのをふと思い出しました。
前半はともかく、後半に進むにつれて絶滅は進行していくので、ここでは後半の一部を書こうかなと。（前半の章は私が書くよりも優れた解説がたくさんありますし。）
とういうことで、今回は10章のブースティングです。基本的に行間を埋めるような形で書いていきます。統計的学習の基礎で苦労している人の助けになれば幸いです。
１．ブースティングとは
そもそものブースティングの発想は、大量の弱分類器の出力を組み合わせて、強力な合議を形成するというものです。弱分類器というのは、ランダムに予測した場合よりも、若干良い誤分類率を持つ分類器のことです。
なんとなくバギングやランダムフォレストに似ていますが、ブースティングの特徴は、逐次的に分類器を作っていくことにあります。
２．AdaBoost のイメージ
この本の中では、最も一般的なブースティング手法として、AdaBoostが紹介されています。（adaptive boosting：適応的ブースティングの略）
AdaBoostのイメージは、次のようなものです。
まず、1つ目の弱分類器として、ランダムに予測するよりも若干性能の良いものを考えます。これを $G_1$ とします。次に $G_1$ で誤分類したデータ点の重要度が高くなるようにデータを重み付けします。そして、この重み付けデータを用いて、分類器 $G_2$ を生成します。同じように誤分類したデータ点の重みが大きくなるようにデータの重要度を更新していき、分類器を繰り返し生成します。このようにして $G_M$ まで生成し、最終的な予測を $G_1$ ～ $G_M$ の多数決により出力します。
図で書くとこんな感じですかね。
３．AdaBoost を数式で
イメージはなんとなく掴めたと思うので、数式を使って表現していきます。
今回は2値分類問題について考えます。つまり、
説明変数が、
X = (X_1,X_2,...,X_d) = \left(
\begin{array}{ccc}
x_{11} & \cdots & x_{1d}\\\
\vdots & \ddots & \vdots \\\
x_{n1} & \cdots & x_{Nd}
\end{array}
\right)
（また、$i = 1,...,N$ に対して、$ x_i = (x_{i1},...,x_{id})^T$（つまり $x_i$ は $X$ の行成分を転置したもの）としておきます。）
目的変数が、
Y = \left(
\begin{array}{c}
y_1\\
\vdots\\
y_N
\end{array}
\right),\quad y_i \in \{ -1,1 \},\,(\,i=1,...,N\,)
の $2$ クラス分類問題です。
任意の説明変数 $x_i$ に対して、$G(x) $ を $\{-1\,,1\}$ のうち、どちらかの予測結果を出力する分類器とします。
AdaBoostは次のように計算していきます。
| アルゴリズム：AdaBoost |
|---|
１． データの重み $\omega_i$ を初期化する。普通、最初は全て同じ重みにするので、
\omega_i^{(1)}=\frac{1}{N} \tag{3.1}
のように設定する。
２． $m=1$ ～ $M$ に対して以下を行う。
2-1. 重み $\omega_i^{(m)}$ を用いて、分類器 $G_m(X\,)$ を学習データに当てはめる。
2-2. 重み付き誤分類率を計算する。
err_m=\frac{\sum_{i=1}^N \omega_i^{(m)} \, I\{y_i \neq G_m(x_i)\}}{\sum_{i=1}^{N} \omega_i^{(m)}} \tag{3.2}
2-3. 分類器の重み $\alpha_m$ を計算する。
\alpha_m = \log \frac{1-err_m}{err_m} \tag{3.3}
2-4. 重みを更新する。
\omega_i^{(m+1)} = \omega_i^{(m)}×e^{\alpha_m I\{y_i \neq G_m(x_i)\}} \tag{3.4}
３． 重み付き多数決により、最終的な予測値を出力する。
G(X)= \mbox{sign} \left(\sum_{m=1}^M \alpha_m G_m (X\,) \right) \tag{3.5}
2-4 における重みの更新（式（3.4））
\omega_i^{(m+1)} = \omega_i^{(m)}×e^{\alpha_m I\\{y_i \neq G_m(x_i)\\}}\tag{3.4}
について、はてなが頭に浮かぶ人がいるかもしれませんが、これは次のような更新を1つの式で表しているものです。
① $y_i$ が $G_m(x_i)$ によって正しく分類された場合
$y_i$ が $G_m(x_i)$ によって正しく分類された時は、
\begin{eqnarray}
\omega_i^{(m+1)}&=&\omega_i^{(m)}×e^{\alpha_m ×\,0} \tag{3.5}\\
\\
&=&\omega_i^{(m)} \tag{3.6}
\end{eqnarray}
となり、重みはそのまま。
② $y_i$ が $G_m(x_i)$ によって誤分類された場合
$y_i$ が $G_m(x_i)$ によって誤分類された時は、
\begin{eqnarray}
\omega_i^{(m+1)}&=&\omega_i^{(m)}×e^{\alpha_m ×\,1} \tag{3.7}\\
\\
&=&\omega_i^{(m)}×e^{\log \frac{1-err_m}{err_m}} \tag{3.8}\\
\\
&=&\omega_i^{(m)}×\frac{1-err_m}{err_m} \tag{3.9}\\
\end{eqnarray}
に更新される。
特に誤分類され続けたデータ点の重みは、繰り返される度にどんどん大きくなります。つまり、AdaBoostは、前のステップで正しく分類できなかったものに重点を置いて学習するということが分かります。
-----備考-----
確認するまでもないと思いますが、本当に誤分類されたものの重みは増大しているの？と聞かれたことがあったので…
誤分類率は、
err_m=\frac{\sum_{i=1}^N \omega_i^{(m)} \, I\{y_i \neq G_m(x_i)\}}{\sum_{i=1}^{N} \omega_i^{(m)}} \tag{3.2}
なので、 $0≤err_m≤1$ となります（どう見ても分母より分子の方が個数が多いですね）。誤分類した時の重みの増加具合は $\frac{1-err_m}{err_m}=\frac{1}{err_m}-1$ となり、$1$ 以上になります。$1$ 以上の掛け算を繰り返しているので、ちゃんと増大してくれていることが分かります。こういう確認も大切だよね。
ついでですが、最後の多数決
G(X)= \mbox{sign} \left(\sum_{m=1}^M \alpha_m G_m (X\,) \right) \tag{3.5}
についても、分類器の重みは $\alpha_m=\frac{1-err_m}{err_m}$ なので、より正確に分類できた分類器にはより大きな影響力があるということも分かりますね。
----------
４．基底関数を用いた、加法的展開当てはめ
なぜブースティングがうまくいったのかということが10.2節に書いてあります。曰く、ブースティングの成功は不思議な話ではないそうです。
秘密は、最後の多数決の部分にあります。
G(X)= \mbox{sign} \left(\sum_{m=1}^M \alpha_m G_m (X\,) \right) \tag{3.5}
この表現は、一連の初等的な基底関数 $G_m(X\,)$ を用いた加法的展開を当てはめる方法と見ることができます。基底関数展開の特徴は、柔軟なモデリングが可能になることで、これが強さの秘密らしいです。（基底展開自体の話は5章に書いてあります。）
より一般的には、基底関数展開を次のような形で表現します。
f(X) = \sum_{m=1}^{M} \beta_m b(X\,|\,\gamma_m) \tag{4.1}
ここで、$\beta_m\,(m=1,...,M)$ は展開係数、$b(X\,|\,\gamma_m)$ は、パラメータ集合 $\gamma$ で決定される基底関数。
一般的に基底関数の加法的モデルは、
\min_{\{\beta_m,\gamma_m\}_{m=1}^{M}} \sum_{i=1}^{N}L \left(y_i, \sum_{m=1}^{M} \beta_m b(x_i \,|\, \gamma_m) \right) \tag{4.2}
によって行われるのですが、これを実行するには、ほとんどの場合で計算量の大きい数値最適化手法が必要になってしまいます。
５．前向き段階的加法的モデリング
一般的な基底関数の加法的モデル当てはめは、計算量の大きい数値最適化が必要ということでしたが、これを近似的に解く方法があります。そのひとつが前向き段階的加法的モデリングです。
前向き段階的加法的モデリングは、すでに追加された展開係数や基底関数のパラメータを調整することなく、新たな基底関数を順次追加することで、近似的に解く方法です。
計算は次のようになります。
| アルゴリズム：前向き段階的加法的モデリング |
|---|
１．$f_0(x)=0$ として初期化する。
２．$m=1$～$M$ に対して以下を行う。
2-1. 展開係数 $\beta_m$ と基底関数のパラメータ $\gamma_m$ を計算する。
\left(\beta_m \,,\, \gamma_m \right)= \mathop{\rm argmin}\limits_{\beta \,,\, \gamma} \sum_{i=1}^{N}L \Bigl(y_i \,,\, f_{m-1}(x_i)+\beta b(x_i \,|\, \gamma) \Bigl) \tag{5.1}
2-2. 現在の展開に追加する。
f_m(x) = f_{m-1}(x)+ \beta_m b(x \,|\, \gamma_m) \tag{5.2}
アルゴリズムを見てわかるかもしれませんが、ざっくり言うと、最適化を$M$ 段階に分けて、各段階で最適な基底関数を加えていくよ。すでに加えられている基底関数は、途中で都合が悪くなってしまっても修正はしないよ。というものです。名前のまんまですね。
６．前向き段階的加法的モデリングで指数損失を用いる
先の前向き段階的加法的モデリングにおいて、損失関数 $L$ が指数損失の場合を考えます。すなわち、
L(y,f(X))=e^{-yf(X)} \tag{6.1}
の場合です。また、基底関数はAdaboostで用いた分類器 $G_m(X) \in \{-1,1\}$ とします。
この時、各ステップにおいて追加される展開係数 $\beta_m$ と基底関数 $G_m(X)$ を求めるのに
(\beta_m \,,\, G_m)=\mathop{\rm argmin}\limits_{\beta \,,\, G} \sum_{i=1}^N e^{-y_i \{f_{m-1}(x_i) + \beta G(x_i) \}} \tag{6.2}
を解く必要があります。
$ e^{-y_i f_{m-1}(x_i)} $ は $\beta$ にも $G$ にも依存しないので、各観測値に対する重みとみなすことができます。これを $\omega_{i}^{(m)}$ とおくと、先ほどの最適化問題（6.2）は、次のように書くことができます。
(\beta_m \,,\, G_m)=\mathop{\rm argmin}\limits_{\beta \,,\, G} \sum_{i=1}^N \omega_{i}^{(m)}e^{-\beta y_i G(x_i)} \tag{6.3}
これに対する解は $2$ ステップで求めることができ、まず、任意の $\beta > 0$ に対して、$G_m(X)$ に対する解について考えます。$y_i \in \{-1,1\}\,\,,\,\,G_m \in \{-1,1\}$ より、
y_iG_m(x_i)=
\begin{cases}
1 \,\,\,\,\,\,\,,\,\,\, y_i=G_m(x_i)\\
\\ \tag{6.4}
-1 \,\,\,,\,\,\,y_i \neq G_m(x_i) \\
\end{cases}
なので、式 $(6.3)$ における規準 $\sum_{i=1}^{N} \omega_{i}^{(m)} e^{- \beta y_i G(x_i)}$ は、
\begin{eqnarray}
\sum_{i=1}^{N}e^{- \beta y_i G(x_i)} &=& \sum_{y_i=G(x_i)} \omega_{i}^{(m)} e^{- \beta} + \sum_{y_i \neq G(x_i)} \omega_{i}^{(m)} e^{\beta} \tag{6.5}\\
\\
&=& \sum_{i=1}^{N} \biggl(\omega_{i}^{(m)} e^{\beta} I\{y_i = G(x_i)\} + \omega_{i}^{(m)} e^{\beta} I\{y_i \neq G(x_i)\}\biggl) \tag{6.6}\\
\\
&=& \sum_{i=1}^{N} \biggl(\omega_{i}^{(m)} e^{\beta} I\{y_i = G(x_i)\} + \omega_{i}^{(m)} e^{\beta} I\{y_i \neq G(x_i)\\
\\
&+&\omega_{i}^{(m)} e^{- \beta} I\{y_i \neq G(x_i)\}-\omega_{i}^{(m)} e^{- \beta} I\{y_i \neq G(x_i)\} \biggl) \tag{6.7}\\
\\
&=&(e^{\beta}-e^{- \beta})\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G(x_i)\} + e^{-\beta}\sum_{i=1}^{N}\omega_{i}^{(m)} \tag{6.8}
\end{eqnarray}
と変形することができます。式（6.6）から式（6.7）は $\omega_{i}^{(m)} e^{- \beta} I{y_i \neq G(x_i)}$ を足して引いているだけです。結局、式（6.3）の解は、
G_m = \mathop{\rm argmin}\limits_{G} \sum_{i=1}^N \omega_{i}^{(m)} I\{y_i \neq G(x_i)\} \tag{6.9}
となります。次に $\beta$ を求めます。 $G_m$ を式（6.3）に代入し、式（6.8）と同じように変形すると、
\begin{eqnarray}
\beta_m &=& \mathop{\rm argmin}\limits_{\beta} \sum_{i=1}^N \omega_{i}^{(m)}e^{-\beta y_i G_m(x_i)} \tag{6.10} \\
\\
&=& \mathop{\rm argmin}\limits_{\beta} \left \{ (e^{\beta}-e^{- \beta})\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\} + e^{-\beta}\sum_{i=1}^{N}\omega_{i}^{(m)} \right \} \tag{6.11}
\end{eqnarray}
微分して $0$ とおくと、
\begin{align}
& (e^{\beta}+e^{-\beta})\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\} - e^{-\beta}\sum_{i=1}^{N}\omega_{i}^{(m)} = 0 \tag{6.12}\\
\\\\
& (e^{\beta}+e^{-\beta})\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\} = e^{-\beta}\sum_{i=1}^{N}\omega_{i}^{(m)} \tag{6.13}\\
\\\\
& (e^{2\beta}+1) = \frac{\sum_{i=1}^{N}\omega_{i}^{(m)}}{\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\}} \tag{6.14}\\
\\\\
& e^{2\beta} = \frac{\sum_{i=1}^{N}\omega_{i}^{(m)}}{\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\}} - 1 \tag{6.15}\\
\\\\
& e^{2\beta} = \frac{\sum_{i=1}^{N}\omega_{i}^{(m)} - \sum_{i=1}^{N}\omega_{i}^{(m)}I\{y_i \neq G_m(x_i)\}}{\sum_{i=1}^{N} \omega_{i}^{(m)} I\{y_i \neq G_m(x_i)\}} \tag{6.16}\\
\\
& e^{2\beta} = \frac{1 - \frac{\sum_{i=1}^{N}\omega_{i}^{(m)}I\{y_i \neq G_m(x_i)\}}
{\sum_{i=1}^{N}\omega_{i}^{(m)}}
}{\frac{\sum_{i=1}^{N} \omega_{i}^{(m)}I\{y_i \neq G_m(x_i)\}}
{\sum_{i=1}^{N}\omega_{i}^{(m)}}} \tag{6.17}\\
\\
& e^{2\beta} = \frac{1 - err_m}{err_m} \tag{6.18}\\
\\
& \beta = \frac{1}{2} \log{\frac{1 - err_m}{err_m}} \tag{6.19}
\end{align}
が得られます。この時の近似は、
f_m(x) = f_{m-1} + \beta_m G_m(x) \tag{6.20}
で与えられ、重みの更新は、
\omega_i^{(m+1)} = \omega_i^{(m)} × e^{-\beta_m y_i G_m(x_i)} \tag{6.21}
となります。
ここで、$-y_iG_m(x_i)=2I\{y_i \neq G_m(x_i)\}-1$ という事実（突然出てきましたが、$y_i \neq G_m(x_i)$ と $y_i = G_m(x_i)$ で実際に確認してみれば確かに事実だということはすぐに分かると思います。）を用い、$2\beta_m=\alpha_m$ とおくと、重みの更新式（6.21）は、
\begin{eqnarray}
\omega_i^{(m+1)} &=& \omega_i^{(m)} × e^{\beta_m (2I\{y_i \neq G_m(x_i)\}-1)} \tag{6.22}\\
\\
&=& \omega_i^{(m)} × e^{2 \beta_m I\{y_i \neq G_m(x_i)\}}×e^{-\beta_m}\tag{6.23}\\
\\
&=& \omega_i^{(m)} × e^{\alpha_m I\{y_i \neq G_m(x_i)\}}×e^{-\beta_m}\tag{6.24}\\
\end{eqnarray}
となり、$e^{-\beta_m}$ は全ての重みに同じ数を掛けているので特に効果はなく、結局、これはAdaBoostの2-4（式（3.4））と等価になります。
つまりAdaBoostは、前向き段階的加法的モデリングによって、指数損失規準を最小化していることになります。
なんでこんなことがひらめくんですかね。Friedmanマジで天才。
-----備考-----
AdaBoostは初め、PAC学習の枠組みで構築されたそうです。それがFriedman(2000)によって、そもそもAdaBoostって損失関数最小化の枠組みで議論できちゃうんだよ。つまり、統計的推測の枠組みで議論できてしまうんだよねってことが示されました。統計的な枠組みで議論できるようになったことにより、何を推定しているのか、どの程度上手く推定することができるのか、その推定量がどんな性質を持っているのか、などが議論できるようになりました。これらを基にすることで、更なる改善の道が拓かれたというわけです。そういえば、AdaBoostのアルゴリズムでは、そもそも損失関数という話は出てきていませんでしたね。何を食べて育ったら、こういう思考にたどり着くんでしょうね。
---------------
７． AdaBoostは何を推定しているのか
AdaBoostと指数損失規準を用いた前向き段階的加法的モデリングの等価性が示されたことで、指数損失規準の性質を調べることにより、AdaBoostに対する理解を進めることができるようになりました。
母集団での最小化を考えると（危険関数の最小化を考えると）、
\begin{eqnarray}
f^{*}(x) &=& \mathop{\rm argmin}\limits_{f(x)} E_{Y|x} \left \lbrack \, e^{-Yf(x)} \, \right \rbrack \tag{7.1}\\
\\
&=& \mathop{\rm argmin}\limits_{f(x)} \int \sum_{y} e^{-yf(x)}Pr(Y=y \,|\, x)p(x)dx \tag{7.2}
\end{eqnarray}
各 $x$ で $\sum_{y} e^{-yf(x)}Pr(Y=y \,|\, x)$ を最小にする $f(x)$ を考えればいいので、これを微分して $0$ でおきます。
\begin{align}
& \frac{\partial}{\partial f(x)} \sum_{y} e^{-yf(x)}P(Y=y \,|\, x)=0 \tag{7.3}\\
\\
& - \sum_{y} e^{-yf(x)} P(Y=y \,|\, x)=0 \tag{7.4} \\
\\
& - e^{-f(x)}P(Y=1 \,|\, x) + e^{f(x)}P(Y=-1 \,|\, x)=0 \tag{7.5} \\
\\
& e^{2f(x)} = \frac{P(Y=1 \,|\, x)}{P(Y=-1 \,|\, x)} \tag{7.6} \\
\\
& f^{*}(x) = \frac{1}{2} \log \frac{P(Y=1 \,|\, x)}{P(Y=-1 \,|\, x)} \tag{7.7}
\end{align}
となります。つまり、AdaBoostによる加法的展開は、$P(Y=1 \,|\, x)$ の対数オッズの $\frac{1}{2}$ を推定していることが分かります。なるほどね。
８．ブースティング木
ブースティング木は、早い話が木の和
f_M = \sum_{m=1}^{M} T(x \, | \, R_{jm} \,,\, \gamma_{jm}) \,\,,\,\,(j=1,2,...,J_m)\tag{8.1}
を考えようというものです。ここで、$R_{jm}$ は木の終端頂点で表現される領域、$\gamma_{jm}$ はそれぞれの領域に割り当てられる定数です。$m$ 番目の木に対する $R_{jm}$ と $\gamma_{jm}$ のイメージはこんな感じ。
木の和は、前向き段階的加法的モデリングで導出することができます。
前向き段階的加法的モデリングで導出する場合には、アルゴリズムの2-1において現在のモデル $f_{m-1}(x)$ を用い、パラメータ $R_{jm} \,,\, \gamma_{jm}$ について、
\{R_{jm} \,,\, \gamma_{jm}\} = \mathop{\rm argmin}\limits_{R_{jm} \,,\, \gamma_{jm}} \sum_{N}^{i=1} L \biggl(y_i \,,\, f_{m-1}(x_i) + T(x_i \, | \, R_{jm} \,,\, \gamma_{jm} ) \biggr) \tag{8.2}
を解く必要があります。各ステップにおいて加わる木は、式（8.2）を最大限減少される木なので、負の勾配要素
-\left \lbrack \frac{\partial L(y_i , f(x_i))}{\partial f(x_i)} \right \rbrack_{f(x_i)=f_{m-1}(x_i)}
と同じようなものだと考えることができます。そこで、前向き段階的加法的モデリングにおける、学習器$T_m$を追加するところで、学習器を追加する前のモデルで負の勾配を計算し、この負の勾配に適合するように木を構築します。（木を追加することによる効果が、損失を最も下げるというものになって欲しいためです。）
-----備考-----
本には、「寄る究極の目的は未知のデータに汎化させることであるが、残念なことに勾配は訓練データ点でしか定義されない」というようなことが書いてあり、「このジレンマに対する対処策として、勾配に近付くような木を導き出す（つまり、木を負の勾配に当てはめる）」ということが書いてあります。
なんかよくわかんないですけど、この前の章に損失関数のロバスト性がどうのこうのという話があるので、外れ値を想定しての話なんですかね。たしかに外れ値が入っていると、そのデータ点は各ステップで間違い続けられて、最終的な重みは大きくなってしまいそうだというのは、なんとなく分かります。Tukey's biweightとか微分可能な損失関数を使えば、勾配情報だけを使ってもジレンマというものに直面しなくて済むのかなぁとか思いましたが、実際それでうまくいくのかはよく分かりません。
余談なのですが、卒業研究でロバストなブースティングを研究しようと思っていた時に、外れ値を混ぜた数値実験したのですが、思ったほど悪くならなかった記憶があるんですよね。まぁ数値実験の設定などに依るでしょうし、そもそもその数値実験の設定を忘れてしまったので何とも言えないのですが、、、
--------------
さて、ここまでの話をアルゴリズムにまとめると以下のようになります。
| アルゴリズム：勾配ブースティング木 |
|---|
１． $f_0$ を初期化する。例えば次のようにする。
f_0(x) = \mathop{\rm argmin}\limits_{\gamma} \sum_{i=1}^{N} L(y_i \,,\, \gamma) \tag{8.3}
２． $m=1$ ～ $M$ に対して、以下を行う。
2-1. $i=1,2,...,N$ に対して、負の勾配 $r_{im}$ を計算する。
r_{im}=-\left \lbrack \frac{\partial L(y_i , f(x_i))}{\partial f(x_i)} \right \rbrack_{f=f_{m-1}} \tag{8.4}
2-2. 終端領域 $R_{jm}\,\,(j=1,2,...,J_{m})$ を与える回帰木を $r_{jm}$ に適合させる。
例えば、$2$乗誤差を用いると、
\{R_{jm} \,,\, \gamma_{jm}\} = \mathop{\rm argmin}\limits_{R_{jm} \,,\, \gamma_{jm}} \sum_{N}^{i=1} \biggl \{r_{im}-T(x_i \,|\, R_{jm} \,,\, \gamma_{jm})\biggr \}^2
2-3. $j=1,2,...,J_{m}$ に対して、それぞれの領域に割り当てられる定数 $\gamma_{jm}$ を計算する。
\gamma_{jm} = \mathop{\rm argmin}\limits_{\gamma} \sum_{x_i \in R_{jm}} L \biggl( y_i \,,\,\
f_{m-1}(x_i)+\gamma \biggr) \tag{8.5}
※2-3で例のように2乗誤差を使っている場合は、既に $\gamma_{jm}$ を求めているので、ここは不要。
2-4. モデルを更新する。
f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J_m}\gamma_{jm}I(x \in R_{jm}) \tag{8.6}
３． $\hat{f}(x)=f_M(x)$ を出力する。
勾配ブースティングにおける調整パラメータは、繰り返し回数 $M$ と、各ステップ $m$ における木の大きさ $J_m\,\,,\,\,(m=1,2,...,M)$ のふたつです。これら調整パラメータの決め方についても本に書いてありますが、そんなに難しい話でもなく、読めば分かると思うので割愛します。結論だけ書くと（ちょっと疲れてきた。）
◆繰り返し回数 $M$ について：
確認用標本に対する予測リスクを最小にするようなものを選ぶ。ちなみにKaggleで勝つデータ分析の技術（門脇,阪田,保坂,平松 2019）には、アーリーストッピングがいいんじゃないというようなことが書いてありました。
◆各木の大き $J_m$ について：
全ての木の大きさを $J$ に揃える。$J$ は経験的に $4≤J≤8$ にするとうまくいく。
というような感じです。
９．まとめ
・ブースティングは、たくさんの弱学習器を逐次的に学習していき、それらに多数決を取らせることによって強学習器を構築する方法。
・Friedmanによって、前向き段階的加法的モデリングにおいて損失関数に指数損失を用いることと、AdaBoostが等価であることが示された。
・AdaBoostが指数損失を最適化しているということが分かったので、これによりAdaBoostの統計的性質が調べられるようになった。例えば、AdaBoostにより得られる加法的展開は、クラス帰属確率の対数オッズの $\frac{1}{2}$ を推定している。
・木の和を導出するのに、前向き段階的加法的モデリングを用いることができるが、これを解くための高速近似アルゴリズムとして、勾配ブースティングの枠組みが構築される。
・損失関数を最小化する際に、損失関数をテイラー展開しで2次の項まで近似し、これを最小化しようというのがXGBoostです。これについてもおまけとして書こうかなと思っていたのですが、私が書くよりも遥かに優れた記事があったので、こちらを参照ください。
▶XGBoost論文を丁寧に解説する(1)
※コメント部分も非常に参考になります。
▶XGBoost論文を丁寧に解説する(2): ShrinkageとSubsampling
（記事一覧を見たら強化学習シリーズもあったので、後でじっくり読んでいきたいと思います。神of神。ありがたやぁ。）
★参考文献★
【1】Hasitie,Tibshirani,Friedman：統計的学習の基礎 (2009)
【2】Friedman：AdaBoost(2000)
【3】Freund,Schapire：A Tutorial on Boosting(1996)
【4】Chen：Introduction to Boosted Trees(2014)