サマリ

本記事は、分類問題を解くための機械学習手法の一つであるAdaBoostについて解説した記事です。AdaBoostとは、機械学習の手法の中でもブースティングに分類される手法です。
- ブースティングとは、次の2段階からなるアルゴリズムです。
  - 前に学習した分類器を基に、より良い分類器を作成し、多数の分類器を作成する。
  - 作成した多数の分類器の合議を取り、分類を行う。
AdaBoostは、「前向き段階的加法的モデリング」において指数損失を最小化する問題と同値的であることが、AdaBoostが提案された5年後に発見されました。

　本記事では、AdaBoostのアルゴリズムについて説明したいと思います。AdaBoostが「前向き段階的加法的モデリング」における指数損失を最小化する問題と同値的であることについては、次の記事のトピックにしようと思います。
　なお、本記事は下記の書籍とQiitaの記事を参考にしています。

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

Amazon

qiita.com

AdaBoostのアルゴリズム

　まず最初に、AdaBoostの目的について述べます。
　特徴量が $\boldsymbol{X} \in \mathbb{R}^J$ 、目的変数が $Y \in \{-1, 1\}$ であるデータに対して、誤分類率

$err = \dfrac{1}{N} \displaystyle{\sum_{i=1}^N}I(y_i \neq G(\boldsymbol{x}_i))$

を小さくする分類器 $G(\boldsymbol{x})$ を見つけることがAdaBoostの目的です。

　次にAdaBoostの考え方について述べます。
　まず最初に、ランダムな予測よりは少しマシな分類器を考えます。これを $G_1(\boldsymbol{x})$ とします。この分類器単体で予測しても、ランダムな予測より少しマシなだけなので、使い物にはなりません。そこで、 $G_1(\boldsymbol{x})$ よりさらにマシと思われる分類器 $G_2(\boldsymbol{x})$ を作成します。
　以上のように、少しマシな分類器を作成することを目指して、多数の分類器を作成していきます。そして作成した分類器の列 $G_m(\boldsymbol{x}) (m=1, \cdots, M)$ の合議をとって、最終的な予測を作ります。
　なお、最後に作成された分類器単体を使うのではなく、分類器の列全体を使って合議をとる理由としては、分類器を更新する際に必ずしもマシな分類器が作成されるとは限らないためです。マシな分類器を作成することを目指しますが、必ずしもマシになるとは限らないということで、分類器の列全体の合議をとるのです。

　次にAdaBoostのアルゴリズムを数式を用いて具体的に記述し、その数式の意味について記載します。ただし、アルゴリズム中のsignは、入力が正であれば1を、負であれば-1を返す関数です。

　アルゴリズム中に出てくる数式の意味をざっくり説明していきます。
　まず、 ${\rm err} _ m$ ですが、これは重みづけをした誤分類率を表します。重みが初期状態のとき、つまり $w_i = \dfrac{1}{N}$ のときは、一般的な誤分類率と同じ式になります。

　次に、 $\alpha_m$ ですが、少し式変形すると $\alpha_m = {\rm log}\left(\dfrac{1}{{\rm err_m}}-1\right)$ となります。このことから、 ${\rm err} _ m$ に対して、 $\alpha_m$ が単調減少になっていることがわかります。したがって、誤分類率が大きい分類器 $G_m(\boldsymbol{x})$ に対しては、 $\alpha_m$ が小さくなり、誤分類率が小さい分類器では、 $\alpha_m$ が大きくなります。これにより、3の合議において、正しく予測できている分類器 $G_m(\boldsymbol{x})$ の影響が大きくなり、誤って予測している分類器の影響が小さくなるようになっています。

　最後に、重み $w_i$ について説明します。重み $w_i$ は次のように変形することができます。

${\displaystyle w_i \leftarrow w_i {\rm exp}\left( {\rm log} \dfrac{1-{\rm err}_m}{{\rm err}_m} I(y_i \neq G_m(\boldsymbol{x}_i)) \right) = \begin{eqnarray} \left\{ \begin{array}{l} w_i (正しく分類されたとき)\\ w_i \left( \frac{1}{{\rm err}_m}-1 \right) (誤って分類されたとき) \end{array} \right. \end{eqnarray} }$

したがって、正しく予測された標本の重みは更新の際に値が変わることはありません。また、誤って予測された標本の重みについては、以下のように考えることができます。

　基本的には、ランダムな予測よりも良い分類器を作成する
→ ${\rm err} _ m>\dfrac{1}{2}$ となる
→ $\dfrac{1}{{\rm err} _ m}-1>1$ となる

　以上のことから、誤って分類された標本の重み $w_i \left( \frac{1}{{\rm err} _ m}-1 \right)$ は、大きくなります。決定境界近くの標本の解像度を高くするイメージです。
　以上で、AdaBoostのアルゴリズムに関するざっくりとした説明は終了です。次の記事では、AdaBoostは「前向き段階的加法的モデリング」において指数損失を最小化する問題と同値的であることをトピックにしようと思います。