アンサンブル法を理解したい #1
まだまだ使う機会の多いアンサンブル法ですが、理論とアルゴリズムからちゃんと追いかけられている人ってどの程度いるのでしょうか?
データサイエンティスト()にならないためにちゃんと理解してきたい記事です。
今回はバギングについてまとめます。
問題設定
以下の関係が成り立つと仮定する。
\begin{align} y_i &= f(x_i) + \varepsilon_i \\ E[\varepsilon_i] &= 0 \\ E[\varepsilon_i^2] &= \sigma_{\varepsilon}^2 \\ \end{align}
ここで は説明変数、 は目的変数、 はホワイトノイズである。
この をうまく近似する関数 を推定したい。つまり、MSE(Mean Square Error; 平均二乗誤差)の期待値
\begin{align} E\left[\left\{y_i - \hat f(x_i)\right\}^2\right] \end{align}
を最小化するような を推定したいということになります。そしてMSEはバイアス、バリアンス、ノイズに分解できることが知られています。
\begin{align} E\left[\left\{y_i - \hat f(x_i)\right\}^2\right]&= \left( f(x_i) - E\left[\hat f(x_i)\right] \right)^2+ E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] + \sigma_i^2 \end{align}
右辺の左から順にバイアス、バリアンス、ノイズです。式変形は本記事の最後に記載しています。バイアスは対象モデルの真のモデルからの乖離度、バリアンスはモデルの安定性、ノイズはモデルで説明できない誤差を表しています。機械学習モデルに限った話ではないですが、理想のモデルに近く(バイアスの最小化)、ノイズをシグナルと勘違いしない(バリアンスの最小化)ようなモデルを作りたいということです。
アンサンブル法とは
アンサンブル法は複数のモデル出力の期待値を取ることで、個別モデルより良い性能を得ようとする手法の総称です。バギングとブースティングが有名です。冒頭で述べた通り、今回はバギングに関するまとめです。
バギングとは
複数のモデルの単純平均をアンサンブルの出力とする方法です。予測がカテゴリカル変数の場合は多数決になります。
バギングはバリアンスを小さくする
バギングはバリアンスを小さくすることが知られています。数式で証明できるので確認してみましょう。
バリアンスは以下の式で与えられました。
\begin{equation} \left( f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \end{equation}
ここで、バギング予測部分(期待値をとっているところ)を、各モデル で明示的に書き下し、真のモデルと各モデルとの誤差をそれぞれ と置きます。
\begin{align} \left( f(x_i) - E\left[\hat f(x_i)\right] \right)^2 &= \left( f(x_i) - \frac{1}{M} \sum_{m=1}^{M} \hat f_m (x_i) \right)^2 \\ &= \left( \frac{1}{M} \sum_{m=1}^{M} \varepsilon (x_i) \right)^2 \end{align}
さて、これでバギングによる平均二乗和誤差が得られたわけですが、個別モデルの平均二乗誤差をすべてのモデルについて平均した
\begin{equation} \frac{1}{M} \sum_{m=1}^{M} E\left[\varepsilon _m (x_i)^2\right] \end{equation}
よりバギング誤差の方が小さくなることが確認できれば、「バギングはバリアンスを小さくする」ということが言えます。これは、Jensenの不等式を利用することで簡単に証明することができ
\begin{align} \left( \frac{1}{M} \sum_{m=1}^{M} \varepsilon (x_i) \right)^2 \le \frac{1}{M} \sum_{m=1}^{M} E\left[\varepsilon _m (x_i)^2\right] \end{align}
が成り立ちます。等号が成り立つのは、誤差間に相関が無いときです。なお、証明は記事の最後に記載しました。
ちなみに、上記ではモデルごとに重複ありのランダムサンプルを用いた場合の議論でしたが、決定木モデルごとに重複なしのランダムサンプリングを行うようにしたのがランダムフォレストです。重複なしにすることで、モデル間の相関を下げる効果が期待されます。
Appendix
バイアス・バリアンス分解
の期待値 を導入することで、MSEを分解します。
\begin{align} E\left[\left\{y_i - \hat f(x_i)\right\}^2\right] &= E\left[\left\{y_i - E\left[\hat f(x_i)\right] - \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right) \right\}^2\right] \\ &= E\left[\left( y_i - E\left[\hat f(x_i)\right] \right)^2 \right] \\ &\quad - 2 E\left[ \left( y_i - E\left[\hat f(x_i)\right] \right) \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right) \right] \\ &\quad + E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] \end{align}
ここで、観測時点で値が確定するものについて期待値 の外に出すと
\begin{align} &= \left( y_i - E\left[\hat f(x_i)\right] \right)^2 \\ &\quad - 2 \left( y_i - E\left[\hat f(x_i)\right] \right) \left(E\left[ \hat f(x_i) \right] - E\left[\hat f(x_i)\right] \right) \\ &\quad + E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] \\ &= \left( y_i - E\left[\hat f(x_i)\right] \right)^2+ E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] \\ &= \left( f(x)_i + \varepsilon_i - E\left[\hat f(x_i)\right] \right)^2+ E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] \label{bb1}\\ &= \left( f(x)_i - E\left[\hat f(x_i)\right] \right)^2+ E\left[ \left(\hat f(x_i) - E\left[\hat f(x_i)\right] \right)^2 \right] + \sigma_i^2 \label{bb2} \end{align}
\eqref{bb1}から\eqref{bb2}のところだけ少し式変形を省略しましたが、ここまで式を追いかけられるなら簡単にわかるかと思います。
バギングによるバリアンス削減
Jensenの不等式は、凸関数 に対して以下が成り立つというものです。
\begin{equation} f\left(\sum_{i=1}^M \lambda_i x_i \right) \le \sum_{i=1}^M \lambda_i f(x_i) \end{equation}
ここで、、、 と置けば
\begin{equation} \left( \frac{1}{M} \sum_{m=1}^{M} \varepsilon (x_i) \right)^2 \le \frac{1}{M} \sum_{m=1}^{M} E\left[\varepsilon _m (x_i)^2\right] \end{equation}
となります。