ブースティング

ブースティング#

ブースティング（boosting）はKearns (1988)の「（0.5よりわずかに正解率が高い程度の）弱い学習器を使って強い学習器を作ることはできるか？」という仮説（boosting hypothethis）から生まれた

Schapire (1990) The strength of weak learnability. の提案は

  1. 分類器\(h_1\)を\(N\)個のサンプルで訓練する

  2. \(h_1\)で分類に失敗したサンプルと正しく分類できたサンプルを半々にした\(N\)個のサンプルで\(h_2\)を訓練する

  3. \(h_1\)と\(h_2\)で分類結果が一致しない\(N\)個で\(h_3\)を訓練する

  4. ブーストされた分類器\(h_B\)は\(h_1, h_2, h_3\)の分類結果の多数決で分類を行う

AdaBoost#

誤差に適応的に重みをかけてブースティングする。

2000年代前半に大ヒットした

Friedman (2001)がAdaBoostを一般化して勾配ブースティングを提案。誤差関数を指数誤差としたときの勾配ブースティングと同値であることを示した。

勾配ブースティング#

Friedman, J. H. (2001). Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189-1232.

勾配が0なのが最適性の1次条件なので、勾配を説明して0に近づける

加法モデルの観点からの説明#

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

\[ \newcommand{\argmin}{\mathop{\rm arg~min}\limits} f(x; \boldsymbol{\theta}) = f_0(x; \theta_0) + \beta_1 f_1(x; \theta_1) + \cdots + \beta_M f_M(x; \theta_M) \]

の形で予測モデルを構築することを考える。ここで\(\boldsymbol{\theta} = (\theta_0, \dots, \theta_M)\)は関数を形づくるパラメータ（例えば線形回帰の重み）である。

このモデルは\(\boldsymbol{\beta}, \boldsymbol{\theta}\)の2つのパラメータベクトルを推定する必要がある。 すべてのパラメータを一度に学習するのではなく、\(\beta_m f_m(x; \theta_m)\)を一つずつ学習していく方法で考える。全体としては次のように行う

Note

Algorithm: Forward Stagewise Additive Modeling

  1. \(f_0(x) = 0\)で初期化

  2. \(m = 1\)から\(M\)までについて、

    1. パラメータを推定する：

      • \((\beta_m, \theta_m) = \argmin_{\beta, \theta} \sum^N_{i=1} L(y_i, f_{m-1}(x_i) + \beta f(x_i; \theta) )\)

    2. \(f_m(x) = f_{m-1}(x) + \beta_m f(x; \theta_m)\)

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

\[\begin{split} \begin{align} L(y_i, f_{m-1}(x_i) + \beta f(x_i; \theta)) &= (y_i - f_{m-1}(x_i) - \beta f(x_i; \theta))^2 \\ &= (\text{residual}_{im} - \beta f(x_i; \theta))^2 \end{align} \end{split}\]

となり、これは\(m-1\)回目のモデルの残差\(y_i - f_{m-1}(x_i)\)を近似するように\(m\)回目のモデルを学習させると捉えることができる

Friedman et al. (2000)はAdaboostが段階的加法モデルと等しいことを指摘した。

最急降下法からの説明#

最急降下法は最小化問題

\[ \newcommand{\b}[1]{\boldsymbol{#1}} \min_{\b{x}} f(\b{x}) \]

において、勾配

\[\begin{split} \nabla f(\b{x}) = \begin{pmatrix} \frac{\partial f(\b{x})}{ \partial x_1 }\\ \\ \vdots \\ \frac{\partial f(\b{x})}{ \partial x_n } \end{pmatrix} \end{split}\]

を用いて

\[ \b{x}_{t+1} = \b{x}_t - \alpha_t \nabla f(\b{x}_t) \]

のような更新を反復して最適な\(\b{x}\)を探索する方法である

書き方を変えると、\(t+1\)回目の入力\(\b{x}_t+1\)はそれまでの反復の和

\[ \b{x}_{t+1} = \b{x}_0 - \alpha_1 \nabla f(\b{x}_1) - \alpha_2 \nabla f(\b{x}_2) - \cdots - \alpha_t \nabla f(\b{x}_t) \]

であり、負の勾配\(-\nabla f(\b{x}_t)\)を\(\alpha_t\)で加重和していることがわかる。

この負の勾配を再現して加重和を行うのが段階的加法モデルでありブースティングであり、勾配ブースティングである

Contents