この記事の読者

機械学習・マシンラーニングの手法の１つである「アダブースト / Ada Boost」について知りたい.

Index

Index
アダブースト / Ada Boost (Adaptive Boosting)
アルゴリズム
- 諸定義
- Ada Boosting M1 のアルゴリズム
アルゴリズムの導出
参考
- 書籍
- Web サイト

アダブースト / Ada Boost (Adaptive Boosting)

代表的なブースティングアルゴリズムに、アダブースト / Ada Boost (Adaptive Boosting)がある.

ブースティング / Boosting
- yhayato1320.hatenablog.com

アダブーストでは、弱識別器の学習結果に従って学習データに重みが付与される.

誤った学習データに対する重みを大きくし、 正しく識別された学習データに対する重みを小さくすることで、後で学習する識別器ほど、誤りの多い学習データに集中して学習するようにする.

アダブースは、2 クラス問題の識別器であり、多クラス問題に対応するためには、 $K-1$ 個の一対他の識別器を構成する必要がある.

アルゴリズム

諸定義

定義 / データセットのインデックス

学習データ : $x_i \in R^{d}\ (i=1,\ \cdots,\ N)$

$d$ は入力データの次元数
$N$ はデータ数

教師データ : $t_i\ =\ \{ -1, +1 \}\ (i=1,\ \cdots,\ N)$

学習データの重み : $w_{i}^{m} \in R\ (i=1,\ \cdots,\ N,\ m=1,\ \cdots,\ M)$

$M$ は識別器の数

定義 / 弱識別器のインデックス

弱識別器 : $y_m (x)\ =\ \{ -1, +1 \}\ (m=1,\ \cdots,\ M)$
各弱識別器の重み : $\alpha_m\ (m=1,\ \cdots,\ M)$

Ada Boosting M1 のアルゴリズム

データの重みを $w_{i}^{1}\ =\ \displaystyle \frac{1}{N}\ (i\ =\ 1,\ \cdots,\ N)$ に初期化する.

各識別器について以下を繰り返す.
1. 識別器 $y_m (x)$ を重み付き誤差関数
  
  $E_{m}\ =\ \displaystyle \frac {\displaystyle \sum_{i=1}^{N} w_{i}^{m} I(y_{m} (x_{i}) \neq t_{i})} {\displaystyle \sum_{i=1}^{N} w_{i}^{m}} \tag{1.1}$
  
  が最小になるように学習する.
  
  $I(y_{m} (x_{i}) \neq t_{i})$ は、識別関数の出力が教師データと一致したとき $0$ 、一致しなかったとき $1$ となる指示関数である.
2. 識別器 $y_{m} (x)$ に対する重み $\alpha_{m}$ を計算する.
  
  $\alpha_{m}\ =\ \log \left( \displaystyle \frac{1 - E_{m}}{E_{m}} \right) \tag{1.2}$
3. データの重み $w_{i}^{m+1}$ を次のように更新する.
  
  $w_{i}^{m+1}\ =\ w_{i}^{m} \exp \{ \alpha_{m} I(y_{m} (x_{i}) \neq t_{i}) \} \tag{1.3}$

入力 $x$ に対する認識結果を

$Y_{M} (x)\ =\ sign \left( \displaystyle \sum_{m=1}^{M} \alpha_{m} y_{m} (x) \right) \tag{1.4}$

に従って出力する.

$sign (\alpha)$ は符号関数であり、 $\alpha > 0$ で $+1$ 、 $\alpha = 0$ で $0$ 、 $\alpha < 0$ で $-1$ を出力する.

式 (1.1) に示したように、 $E_{m}$ は、ある識別器誤った学習データの正規化された重みの和になる.

式 (1.1) について後ほど後述

(各弱識別器の誤り率は $E_{m} \lt \displaystyle \frac{1}{2}$ となるように期待されて作られるので、 $\alpha_{m} \lt 0$ となる.)

それゆえ、式 (1.2) の各識別器の重み $\alpha_{m}$ は、誤差が小さいほどに大きくな値をとる.

式 (1.2) について後ほど後述

したがって、式 (1.4) の識別結果 $Y_{M} (x)$ の計算では、誤りの小さな $y_{m} (x)$ に大きな重みを与えることになる.

また、式 (1.3) の学習データの重み $w_{i}^{m}$ の更新では、誤った学習データの重みが $\exp \alpha_{m} (> 1)$ 倍される.

正しく識別された学習データの重みは変更されないが、式 (1.1) による $E_{m+1}$ の計算で正則化されるので相対的に小さくなる.

弱識別器の数 $M$ は、あまり大きいと過学習が生じ、汎化誤差が大きくなるので、交差検証法などで選ぶ必要がある.

アルゴリズムの導出

誤差関数の導入

アダブースト学習アルゴリズムは、指数誤差関数

$E\ =\ \displaystyle \sum_{i=1}^{N} \exp (-t_{i} f_{m} (x_i))$

を $m=1$ から $M$ まで逐次最小することにより導出することができる.

アダブースト全体の最適化(or 損失)関数. これを最小化することが目的.

ここで、 $f_m (x)$ は、

$f_{m} (x)\ =\ \displaystyle \frac{1}{2} \displaystyle \sum_{j=1}^{m} \alpha_{j} y_{j} (x)$

で定義された、弱識別器 $y_j (x)$ の $j=1$ から $m$ までの線形結合である.

$f_m (x)$ は各弱識別器の結果を合わせたもので、識別器全体としての結果を出力する一歩前の段階のものである.

$f_{m} (x)\ =\ f_{m-1} (x)\ -\ \displaystyle \frac{1}{2} \alpha_{m} y_{m} \tag{2.1}$

と、かけることに注意.

目的は、 $E$ を最小にする線形結合係数 $\alpha_j$ と弱識別器 $y_j (x)$ のパラメータを求めることにある.

最適化

逐次的な $E$ の最小化を考えるので、 $y_1 (x),\ \cdots,\ y_{m-1} (x)$ とそれらの係数 $\alpha_1\ \cdots,\ \alpha_{m-1}$ はすでに決まっているものとし、 $y_m (x)$ と $\alpha_m$ に関する最適化のみを考えることにする.

各弱識別器 $M=1$ から順々に、逐次的に、パラメータを決定していくので、ある弱識別器 $m$ での場合を考えばよい.

誤差関数 $E$ は、

$\begin{align} E&\ =\ \displaystyle \sum_{i=1}^{N} \exp (-t_{i} f_{m} (x_i)) \\ 式 (2.1) より\\ &\ =\ \displaystyle \sum_{i=1}^{N} \exp \left( -t_{i} f_{m-1} (x_i) - \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right) \\ &\ =\ \displaystyle \sum_{i=1}^{N} \exp \left( -t_{i} f_{m-1} (x_i) \right) \exp \left( - \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right) \\ 式 (2.2) より\\ &\ =\ \displaystyle \sum_{i=1}^{N} w_{i}^{m} \exp \left( - \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right) \end{align}$

と分解できる.

$w_{i}^{m}\ =\ exp ( -t_{i} f_{m-1} (x_{i}) ) \tag{2.2}$ を利用.

ある弱識別器 $m$ へのある入力データ $x_i$ の重み $w_i^m$ はその前の $1$ から $m-1$ までの識別器の統合された結果にラベル値をかけ合わせた、いわゆる誤差に依存するということか？

式(2.2) は逐次最適化の枠組みを中では定数とみなることができる.

$y_m (x)$ によって正しく認識された学習データの週報を $T_c$ で、誤って識別された集合を $T_e$ で表せば、 $t_i$ と $y_m (x_i)$ は $+1$ か $-1$ のどちらかしかとらないので、誤差関数 $E$ は

$\begin{align} E\ &=\ \displaystyle \sum_{i=1}^{N} w_{i}^{m} \exp \left(- \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right) \\ 式 (3.1) より& \\ &=\ \displaystyle \sum_{i \in T_{c}} w_{i}^{m} \exp \left(- \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right)\ +\ \displaystyle \sum_{i \in T_{e}} w_{i}^{m} \exp \left(- \displaystyle \frac{1}{2} t_{i} \alpha_{m} y_{m} (x_{i}) \right) \\ 式 (3.2) (3.3) より& \\ &=\ \displaystyle \sum_{i \in T_{c}} w_{i}^{m} \exp \left(- \displaystyle \frac{1}{2} \alpha_{m} \right) \ +\ \displaystyle \sum_{i \in T_{e}} w_{i}^{m} \exp \left(+ \displaystyle \frac{1}{2} \alpha_{m} \right) \\ \exp を外に出す& \\ &=\ \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_c} w_{i}^{m} + \exp \left( \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} \\ 式 (3.4) より& \\ &=\ \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_c} w_{i}^{m} + \exp \left( \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} \\ &+\ \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} - \exp \left( - \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} \\ 式 (3.5) (3.6) より& \\ &=\ \exp(- \displaystyle \frac{a_m}{2}) \displaystyle \sum_{i = 1}^{N} w_{i}^{m} \\ &+\ \left( \exp \left( \displaystyle \frac{a_m}{2} \right) - \exp \left( \displaystyle - \frac{a_m}{2} \right) \right) \displaystyle \sum_{i = 1}^{N} w_{i}^{m} I(y_{m}(x_{i}) \neq t_{i}) \\ 式 (3.7) (3.8) より& \\ &=\ \exp(- \displaystyle \frac{a_m}{2}) B\ +\ \left( \exp \left( \displaystyle \frac{a_m}{2} \right) - \exp \left( \displaystyle - \frac{a_m}{2} \right) \right) A \\ \end{align}$

と書くことができる.

総和の分解

$\displaystyle \sum_{i=1}^{N} を \displaystyle \sum_{i \in T_{c}} と \displaystyle \sum_{i \in T_{e}} に分割 \tag{3.1}$

$i \in T_c$ のとき: $t_i \times y_m (x_i)$ は $(1 \times 1)$ or $(-1 \times -1)$ より $t_i \times y_m (x_i)\ =\ 1 \tag{3.2}$
$i \in T_e$ のとき: $t_i \times y_m (x_i)$ は $(-1 \times 1)$ or $(1 \times -1)$ より $t_i \times y_m (x_i)\ =\ -1 \tag{3.3}$

式の調整のため、

$\exp \left( - \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} - \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m}\ =\ 0 \tag{3.4}$

を追加.

$\exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_c} w_{i}^{m}\ +\ \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m} \ =\ \exp \left(- \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i = 1}^{N} w_{i}^{m} \tag{3.5}$
$\exp \left(\displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m}\ -\ \exp \left( - \displaystyle \frac{a_m}{2} \right) \displaystyle \sum_{i \in T_e} w_{i}^{m}\ =\ \notag \\ \left( \exp \left( \displaystyle \frac{a_m}{2} \right) - \exp \left( \displaystyle - \frac{a_m}{2} \right) \right) \displaystyle \sum_{i = 1}^{N} w_{i}^{m} I(y_{m}(x_{i}) \neq t_{i}) \tag{3.6}$

$\displaystyle \sum_{i = 1}^{N} w_{i}^{m} I(y_{m}(x_{i}) \neq t_{i})\ =\ A \tag{3.7}$ $\displaystyle \sum_{i \in T_e} w_{i}^{m}\ =\ B \tag{3.8}$

最小値の極値を計算

$y_m (x)$ に関する $E$ の最小化は、 $B$ の項が定数なので、 $A$ の最小化となる.

$A = \displaystyle \sum_{i = 1}^{N} w_{i}^{m} I(y_{m}(x_{i}) \neq t_{i})$ を最小する.

また、 $\alpha_{m}$ に関する最小化は、誤差関数 $E$ を微分し、

$\displaystyle \frac{\partial E}{\partial \alpha_m}\ =\ \left( \displaystyle \frac{1}{2} \exp \left( \displaystyle \frac{\alpha_m}{2} \right)\ +\ \displaystyle \frac{1}{2} \exp \left( - \displaystyle \frac{\alpha_m}{2} \right) \right)A - \displaystyle \frac{1}{2} \exp \left( - \displaystyle \frac{\alpha_m}{2} \right) B\ =\ 0$

を解けば、誤差関数の最小時の $\alpha_m$ がわかる.

$\exp \alpha_m\ =\ \displaystyle \frac{B}{A} -1$ より
$\alpha_m\ =\ \log \left( \displaystyle \frac{B}{A} - 1 \right)\ =\ \log \displaystyle \frac{1 - \frac{A}{B}}{\frac{A}{B}}$