サマリ

過去の記事で、AdaBoostのアルゴリズムをざっくり説明しました。

aisinkakura-datascientist.hatenablog.com

本記事は、下記のトピックについて書いていこうと思います。

AdaBoostは前向き段階的加法的モデリングを用いて、指数損失の最小化問題を解くことと同値的である。
- 前向き段階的加法的モデリングとは、基底関数展開に対する損失関数を近似的に最小化するアルゴリズムである。
  - 基底関数展開とは、 $f(\boldsymbol{x}) = \displaystyle{\sum_{m=1}^M \beta_m b(\boldsymbol{x}; \boldsymbol{\gamma} _ m)}$ で表現される関数のことである。
指数損失とは、 $L(y, f(\boldsymbol{x})) = {\rm exp}(-yf(\boldsymbol{x}))$ で表現される損失関数のことである。

なお、本記事では、上記サマリの細かい箇所から説明していこうと思います。つまり、「基底関数展開→前向き段階的加法的モデリング→指数損失→AdaBoostが前向き段階的加法的モデリングを用いて指数損失を最小化する問題と同値的である」という順番で説明していきます。

基底関数展開

　基底関数展開とは、ある関数 $f$ を複数の基底関数で展開することを表します。数式で書くと以下のようになります。

$f(\boldsymbol{x}) = \displaystyle{\sum_{m=1}^M \beta_m b(\boldsymbol{x}; \boldsymbol{\gamma} _ m)} \tag{1}$

ここで、 $b$ は基底関数と呼ばれる関数、 $\gamma_m$ は $b$ を決定するパラメータ、 $\beta_m$ は展開係数と呼ばれるパラメータです。
　基底関数展開の具体的な数式に、区分多項式があります。区分多項式の例としては、下記のようなものがあります。曲線等を描く関数 $f(x)$ に対して、

$\begin{align} b_1(x) &= 1 \\ b_2(x) &= x \\ b_3(x) &= (x-\xi_1)_+ \\ b_4(x) &= (x-\xi_2)_+ \\ \end{align}$

を用いて、

$f(x) = \beta_1 b_1(x) + \beta_2 b_2(x) + \beta_3 b_3(x) + \beta_4 b_4(x)$

と展開する手法が基底関数展開です。ここでは、 $\boldsymbol{\gamma} = (\xi_1, \xi_2)$ となっています。

　区分多項式については、以前まとめたことがあるのでご興味あれば見て頂けると幸いです。 aisinkakura-datascientist.hatenablog.com

前向き段階的加法的モデリング

　前向き段階的加法的モデリングとは、 $\{\beta _ m, \gamma _ m\}_{m=1, \cdots, M}$ に対して、 $\displaystyle{\sum _ {i=1}^N}L \left(y _ i, \sum _ {m=1}^M \beta _ m b(\boldsymbol{x} _ i; \gamma _ m)\right)$ を近似的に最小化するアルゴリズム *1の一つです。
　前向き段階的加法的モデリングのアルゴリズムは非常にシンプルです。過去に得られた基底関数を基に、その段階で最も損失関数を小さくするような次の基底関数を逐次的に見つけていくというアルゴリズムになっています。具体的には、図1に記載します。

指数損失関数

　指数損失関数とは、下記のような式で表現される損失関数です。　ただし、今回は二値分類問題を解くことを前提とし、 $y, f(\boldsymbol{x}) \in \{-1, 1\}$ とします。

$L(y, f(\boldsymbol{x})) = {\rm exp}(-yf(\boldsymbol{x})) = \left\{ \begin{array}{l} \dfrac{1}{e}\ (y=f(\boldsymbol{x})の場合) \\ e \ (y\neq f(\boldsymbol{x})の場合) \\ \end{array} \right.$

AdaBoostが前向き段階的加法的モデリングを用いて、指数損失を最小化する問題と同値的であることの証明

　証明の前に、証明の前提と目的を整理しておきます。

前提
- 二値分類を考える。したがって、 $y, f(\boldsymbol{x}) \in \{-1, 1\}$ とする。
- $b=G$ は二値分類の弱分類器とする。
- 損失関数は指数損失 $L(y, f(\boldsymbol{x})) = {\rm exp}(-yf(\boldsymbol{x}))$ とする。
- $\beta>0$ とする。
目的
- 前向き段階的加法的モデリングの更新式がAdaBoostの更新式と一致すること。

　まず最初に、前向き段階的加法的モデリングの更新式（2-1）を指数損失を用いて陽に書くと、

$\begin{eqnarray} (\beta_m, G_m) &=& \underset{\beta, G}{{\rm argmin}} \displaystyle{\sum_{i=1}^N} L(y_i, f_{m-1}(\boldsymbol{x}_i)+\beta G(\boldsymbol{x}_i))) \\ &=& \underset{\beta, G}{{\rm argmin}} \displaystyle{\sum_{i=1}^N} {\rm exp}(-y_i (f_{m-1}(\boldsymbol{x}_i)+\beta G(\boldsymbol{x}_i)) \\ &=& \underset{\beta, G}{{\rm argmin}} \displaystyle{\sum_{i=1}^N} {\rm exp} (-y_i f_{m-1}(\boldsymbol{x}_i)) {\rm exp}(-\beta y_i G(\boldsymbol{x}_i)) \tag{2} \end{eqnarray}$

となります。ここで、 $w_i^{(m)} = {\rm exp} (-y _ i f _ {m-1}(\boldsymbol{x} _ i))$ とすると、(2)式は、

$\underset{\beta, G}{{\rm argmin}} \displaystyle{\sum_{i=1}^N} w_i^{(m)}{\rm exp}(-\beta y_i G(\boldsymbol{x}_i)) \tag{3}$

となります。ここで、 $y_i, G(\boldsymbol{x} _ i) \in \{-1, 1\}$ を用いると、 $y_i = G(\boldsymbol{x} _ i)$ のとき、 $-y_i G(\boldsymbol{x} _ i)=1$ 、 $y_i \neq G(\boldsymbol{x} _ i)$ のとき、 $-y_i G(\boldsymbol{x} _ i)=1$ となります。これを用いると、(3)式は、

$\underset{\beta, G}{{\rm argmin}} \left\{ e^{-\beta} \displaystyle{\sum_{y_i= G(\boldsymbol{x}_i)}}w_i^{(m)} + e^{\beta} \displaystyle{\sum_{y_i \neq G(\boldsymbol{x}_i)}}w_i^{(m)} \right \} \tag{4}$

となります。ここで、

$\displaystyle{\sum_{y_i= G(\boldsymbol{x}_i)}}w_i^{(m)} = \displaystyle{\sum_{i=1}^N} w_i^{(m)} - \displaystyle{\sum_{y_i \neq G(\boldsymbol{x}_i)}}w_i^{(m)}$

を(4)式に代入し、整理すると

$\underset{\beta, G}{{\rm argmin}} \left\{ e^{-\beta} \displaystyle{\sum_{i=1}^N} w_i^{(m)} + (e^{\beta}-e^{-\beta}) \displaystyle{\sum_{y_i \neq G(\boldsymbol{x}_i)}}w_i^{(m)} \right\} \tag{5}$

となります。

$G$ についての最小化

　ここからは、先に(5)式を $G$ について最小化し、その後 $\beta$ について最小化することを考えます。
　(5)式の第一項は、 $G$ とは無関係です。したがって、 $G$ について最小化する際には、第二項のみを検討します。第二項について、任意の $\beta>0$ に対して、 $e^{\beta}-e^{-\beta}>0$ となります。したがって、

$\begin{eqnarray} G_m &=& \underset{G}{{\rm argmin}} \displaystyle{\sum_{y_i \neq G(\boldsymbol{x}_i)}}w_i^{(m)} \\ &=& \underset{G}{{\rm argmin}} \displaystyle{\sum_{i=1}^N} w_i^{(m)} I(y_i \neq G(\boldsymbol{x}_i)) \tag{6} \end{eqnarray}$

となります。これは、AdaBoostにおいて、 $y$ の重み付き誤差を最小にする分類器を得ることと対応しています。

$\beta$ についての最小化

(6)式を(5)式に代入し、さらに $\beta$ について微分した式 $=0$ とすることで、

$- e^{-\beta} \displaystyle{\sum_{i=1}^N} w_i^{(m)} + (e^{\beta}+e^{-\beta}) \displaystyle{\sum_{i=1}^N} w_i^{(m)} I(y_i \neq G(\boldsymbol{x}_i)) = 0$

となります。これより、

$\begin{eqnarray} \beta_m &=& \dfrac{1}{2} {\rm log} \dfrac{\displaystyle{\sum_{i=1}^N} w_i^{(m)} - \displaystyle{\sum_{i=1}^N} w_i^{(m)}I(y_i \neq G(\boldsymbol{x}_i))}{\displaystyle{\sum_{i=1}^N} w_i^{(m)}I(y_i \neq G(\boldsymbol{x}_i))} \\ &=& \dfrac{1}{2}{\rm log} \cfrac{\left(1- \cfrac{\displaystyle{\sum_{i=1}^N} w_i^{(m)}I(y_i \neq G(\boldsymbol{x}_i))}{\displaystyle{\sum_{i=1}^N} w_i^{(m)}}\right)}{\left(\cfrac{\displaystyle{\sum_{i=1}^N} w_i^{(m)}I(y_i \neq G(\boldsymbol{x}_i))}{\displaystyle{\sum_{i=1}^N} w_i^{(m)}}\right)} \\ &=& \dfrac{1}{2} {\rm log} \dfrac{1-{\rm err}_m}{{\rm err}_m} \end{eqnarray}$

が得られます。ただし、

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

です。

重みの更新式

　ここまでで得られた $\beta_m, G_m$ を用いることでAdaBoostにおける重みの更新式を得ることができます。前向き段階的加法的モデリングの2-2から、 $f_m(\boldsymbol(x)) = f_{m-1}(\boldsymbol(x)) + \beta_m G_m(\boldsymbol(x))$ です。また、重みの定義から $w _ i^{(m)} = {\rm exp}(-y _ i f _ m(\boldsymbol{x} _ i))$ です。この二式を用いると、

$\begin{eqnarray} w_i^{(m+1)} &=& {\rm exp}(-y_i f_{m-1}(\boldsymbol{x}_i) - \beta_m y_i G_m(\boldsymbol{x}_i)) \\ &=& {\rm exp}(-y_i f_{m-1}(\boldsymbol{x}_i)) {\rm exp}(-\beta_m y_i G_m(\boldsymbol{x}_i)) \\ &=& w _ i^{(m)} {\rm exp}(-\beta_m y_i G_m(\boldsymbol{x}_i)) \end{eqnarray}$

が得られます。ここで、 $-y _ i G _ m(\boldsymbol{x} _ i) = 2I(y _ i \neq G _ m(\boldsymbol{x} _ i))-1$ より

$\begin{eqnarray} w_i^{(m+1)} = w_i^{(m)} {\rm exp}(2\beta_m I(y_i \neq G_m(\boldsymbol{x}_i)) {\rm exp}(-\beta_m) \end{eqnarray}$

なる。ここで、 ${\rm exp}(-\beta_m)$ は全ての標本に同じ値を書けているので不要である*2。よって、 $\alpha_m = 2\beta_m$ として重みの更新式は、

$\begin{eqnarray} w_i^{(m+1)} = w_i^{(m)} {\rm exp}(\alpha_m I(y_i \neq G_m(\boldsymbol{x}_i)) \end{eqnarray}$

となる。
　以上より、AdaBoostが前向き段階的加法的モデリングを用いて、指数損失を最小化する問題と同値的であることが証明できました。ちなみに、このことが発見されたのは、AdaBoostが提案されてから5年後のことだったようです。この発見により、AdaBoostの数学的性質を調べることができることになったそうです。