機械学習/EMアルゴリズム - 鯨飲馬食 @ wiki

メニュー

更新履歴

取得中です。

この項の問題点
概要
問題設定
導出
The EM algorithm
メモ
Maximum A Posteriori

この項の問題点

この項は未完成であり重大な間違いを含んでいる可能性があります。
数学的な厳密さはありません。式変形の途中で確率分布や確率密度関数がきちんと定義されているのか疑わしいです。また全体的に説明不足です。

概要

EMアルゴリズム（The EM algorithm, [Dempster et al. 1977]）は不完全データに対して最尤推定を行うメタアルゴリズムです。Expectation-stepとMaximization-stepの二つのステップを繰り返すことにより、確率パラメータを更新していきます。

問題設定

$x$ は隠れ変数、 $y$ は観測、 $\theta$ は確率パラメータ、 $T$ は観測の数、 ${\rm L}(\theta)$ は対数尤度です。（ $x, y, \theta$ はベクトル）
T回観測された $y = (y_1 , y_2 , \ldots , y_T)$ に対して、 $x = (x_1 , x_2 , \ldots , x_T)$ が対応します。（ $x_t , y_t$ もベクトル）
ここで $y = (y_1 , y_2 , \ldots , y_T)$ はi.i.d（独立同分布）とします。
対数尤度 ${\rm L}(\theta) = \log p(y \mid \theta)$ を最大化するような $\theta$ を求めることが目的です。

$\begin{eqnarray} {\rm L}(\theta) &=& \log p(y \mid \theta) \\ &=& \sum_{t=1}^{T} \log p(y_{t} \mid \theta) \\ &=& \sum_{t=1}^{T} \log \sum_{x_{t}} p(x_{t}, y_{t} \mid \theta) \end{eqnarray}$

上の変形から分かるように ${\rm L}(\theta)$ は対数の中に和を含む形となっています。これを直接最大化するのは困難です。

導出

EMアルゴリズムの導出にはいくつかの種類がありますが、ここでは比較的直感的だと考えられる導出を示します。
尤度を最大化するような確率パラメータを直接求める代わりに、ある $\theta$ よりも対数尤度を大きくするような $\theta'$ を求めることにします。（詳しい説明が必要）
対数尤度の差をとり変形していきます。

$\begin{eqnarray} {\rm L}(\theta') - {\rm L}(\theta) &=& \sum_{t=1}^{T} \log p(y_t \mid \theta') - \sum_{t=1}^{T} \log p(y_t \mid \theta) \\ &=& \sum_{t=1}^{T} \log \frac{p(y_t \mid \theta')}{p(y_t \mid \theta)}\\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log \frac{p(y_t \mid \theta')}{p(y_t \mid \theta)}\\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log \frac{p(x_t, y_t \mid \theta')}{p(x_t, y_t \mid \theta)} \cdot \frac{p(x_t \mid y_t, \theta)}{p(x_t \mid y_t, \theta')} \\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log \frac{p(x_t, y_t \mid \theta')}{p(x_t, y_t \mid \theta)} + \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log \frac{p(x_t \mid y_t, \theta)}{p(x_t \mid y_t, \theta')} \\ &=& {\rm Q}(\theta' \mid \theta) - {\rm Q}(\theta \mid \theta) + {\rm KL}(p_{\theta} \parallel p_{\theta'}) \\ \end{eqnarray}$

ここで ${\rm Q}(\theta' \mid \theta)$ を以下のように定義しました。

$\begin{eqnarray} {\rm Q}(\theta' \mid \theta) &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log p(x_t, y_t \mid \theta') \\ &=& {\rm E}_{p(x_t \mid y_t, \theta)}[\log p(x_t, y_t \mid \theta')] \end{eqnarray}$

また ${\rm KL}(p_{\theta} \parallel p_{\theta'})$ は $p_{\theta}=p(x_t \mid y_t, \theta)$ と $p_{\theta'}=p(x_t \mid y_t, \theta')$ のKullback–Leiblerダイバージェンスであり、これは常に0以上です。（詳しい説明が必要）

$\begin{eqnarray} {\rm KL}(p_{\theta} \parallel p_{\theta'}) &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log \frac{p(x_t \mid y_t, \theta)}{p(x_t \mid y_t, \theta')} &\geq& 0 \end{eqnarray}$

よって下の式が成り立ちます。

$\begin{eqnarray} {\rm L}(\theta') - {\rm L}(\theta) &\geq& {\rm Q}(\theta' \mid \theta) - {\rm Q}(\theta \mid \theta) \end{eqnarray}$

ここから、 ${\rm Q}(\theta' \mid \theta)$ を最大化するような $\theta'$ を求めることにより、ある $\theta$ よりも対数尤度を大きくするような $\theta'$ を求めることができると分かります。（対数尤度は常に0以下。）

The EM algorithm

Initialization
初期パラメータ $\theta^{(0)}$ を与える。

Expectation-step(E-step)
現在（i回目の繰り返し）の確率パラメータ $\theta^{(i)}$ を用いて期待値を計算する。

$\begin{eqnarray} {\rm Q}(\theta \mid \theta^{(i)}) &=& {\rm E}_{p(x_t \mid y_t, \theta^{(i)})}[\log p(x_t, y_t \mid \theta)] \end{eqnarray}$

Maximization-step(M-step)
期待値を最大化する $\theta$ を $\theta^{(i+1)}$ とする。

$\begin{eqnarray} \theta^{(i+1)} = {\rm argmax}_{\theta}{\rm Q}(\theta \mid \theta^{(i)}) \end{eqnarray}$

終了条件を満たすまでE-stepとM-stepを繰り返す。

メモ

EMアルゴリズムの終了条件はある小さな正の値 $\epsilon$ に対して ${\rm L}(\theta^{(i+1)})-{\rm L}(\theta^{(i)})<\epsilon$ とするのが一般的です。
EMアルゴリズムの結果は初期値に依存します。local maximumに収束することは保障されていますが、それはglobal maximumであるとは限りません。そこで初期値を変えて複数回アルゴリズムを実行する手法が一般的です。

Maximum A Posteriori

これまで、対数尤度 ${\rm L}(\theta) = \log p(y \mid \theta)$ を最大化するような $\theta$ を求めることをEMアルゴリズムの目的としてきました。ここでは対数尤度 $\log p(y \mid \theta)$ ではなく対数事後確率 $\log p(\theta \mid y)$ を最大化するような $\theta$ を求めることを目的にします。（詳しい説明が必要）
事後確率を最大化することをMaximum A Posteriori estimation（MAP推定）と呼び、尤度を最大化することをMaximum Likelihood estimation（ML推定）と呼びます。
ベイズの定理から対数事後確率は以下のように変形できます。

$\begin{eqnarray} \log p(\theta \mid y) &=& \log \frac{p(y , \theta)}{p(y)} \\ &=& \log \frac{p(y \mid \theta) p(\theta)}{p(y)} \\ &=& \log p(y \mid \theta) + \log p(\theta) - \log p(y) \\ \end{eqnarray}$

右辺の第一項は対数尤度となっています。
MLの時と同じように $\theta'$ と $\theta$ のそれぞれの対数事後確率の差をとって変形していきます。

$\begin{eqnarray} \log p(\theta' \mid y) - \log p(\theta \mid y) &=& \log p(y \mid \theta') + \log p(\theta') + \log p(y) - \log p(y \mid \theta) - \log p(\theta) - \log p(y) \\ &=& \log p(y \mid \theta') - \log p(y \mid \theta) + \log p(\theta') - \log p(\theta) \\ &=& {\rm Q}_{ML}(\theta' \mid \theta) - {\rm Q}_{ML}(\theta \mid \theta) + {\rm KL}(p_{\theta} \parallel p_{\theta'}) + \log p(\theta') - \log p(\theta) \\ &=& {\rm Q}_{MAP}(\theta' \mid \theta) - {\rm Q}_{MAP}(\theta \mid \theta) + {\rm KL}(p_{\theta} \parallel p_{\theta'}) \end{eqnarray}$

ここで ${\rm Q}_{MAP}(\theta' \mid \theta)$ を以下のように定義しました。

$\begin{eqnarray} {\rm Q}_{MAP}(\theta' \mid \theta) &=& {\rm Q}_{ML}(\theta' \mid \theta) + \log p(\theta') \\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log p(x_t, y_t \mid \theta') + \log p(\theta') \\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log p(x_t, y_t \mid \theta') + \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log p(\theta') \\ &=& \sum_{t=1}^{T} \sum_{x_t} p(x_t \mid y_t, \theta) \log p(x_t, y_t , \theta') \\ &=& {\rm E}_{p(x_t \mid y_t, \theta)}[\log p(x_t, y_t , \theta')] \end{eqnarray}$

MAPの場合は ${\rm Q}_{MAP}(\theta' \mid \theta)$ を最大化するようにパラメータを更新していきます。

「EMアルゴリズム」をウィキ内検索

最終更新：2009年11月20日 10:58