【編集中】EMアルゴリズム

※編集中

概要

  • 2つの変数からなる確率分布p(x,z)が与えられている.

  • しかし、我々が観測可能なのはXのみ観測可能であり、Zは実際には見えない。

  • Xしか観測できないが、p(x,y)の推定を行う

  • 尤度関数 $l(\theta)$ の最大化を行う

\begin{align}
l(\theta) &= \sum_{i} \ln p(x^i;\theta) \\
&= \sum_{i} \ln \sum_{z^i} p(x^i,z^i;\theta)
\end{align}

  • z が観測できないため、上記の尤度関数を単純に最大化することが難しい

  • そこで、以下のような方法を用いる

  • アルゴリズムの概略

    • $l(\theta)$ の最大化を _一度_ で行わず、$l(\theta)$ の _下限_ を求める.

    • 下限を最大化するようなパラメータを求める.

    • 求めたパラメータでその他のパラメータを更新する.

    • 上記の3つの方法を収束するまで繰り返す.

  • EMアルゴリズムを簡易的なイメージを用いて説明してくれてるスライドがあった

MLAC2013 数式を使わずイメージで理解するEMアルゴリズム - Wolfeyes Bioinformatics beta
Tips and hacks about Bioinformatics on Ruby and R.

もう少し詳しく

\begin{equation}
l(\theta) = \sum_{i} \ln \sum_{z^i} p(x^i,z^i;\theta)
\end{equation}

確率分布 $Q_i(z^i)$ を考える

\begin{equation}
l(\theta) = \sum_{i} \ln \sum_{z^i} Q_i(z^i) \frac{p(x^i,z^i;\theta)}{Q_i(z^i)}
\end{equation}

次にイェンゼンの不等式を用いると、尤度の下限を求めることができる。

\begin{equation}
l(\theta) \geq \sum_{i}\sum_{z^i} Q_i(z^i) \ln \frac{p(x^i,z^i;\theta)}{Q_i(z^i)}
\end{equation}

上記の尤度 _$l(\theta)$_ の下限を最大化する。

EMアルゴリズム

Eステップ

$Q_i(z^i)$ は、

\begin{equation}
Q_i(z^i) = \frac{p(x^i,z^i;\theta)}{\sum_z p(x^i,z;\theta)}
\end{equation}

Mステップ

尤度関数の下限を最大化するパラメータを求める

\begin{equation}
\theta := arg max_{\theta} \sum_{i}\sum_{z^i} Q_i(z^i) \ln \frac{p(x^i,z^i;\theta)}{Q_i(z^i)} \tag{2.1}
\end{equation}

EステップとMステップを対数尤度関数の下限、もしくは上記のパラメータが収束するまで、繰り返す.

簡単な証明

尤度が単調増加することを簡単に説明

\begin{equation}
l(\theta^{(t+1)}) \geq \sum_{i}\sum_{z^i} Q_i(z^i) \ln \frac{p(x^i,z^i;\theta^{(t+1)})}{Q_i(z^i)}
\end{equation}

(2.1) から

\begin{equation}
\geq \sum_{i}\sum_{z^i} Q_i(z^i) \ln \frac{p(x^i,z^i;\theta^{t})}{Q_i(z^i)} \\
= l(\theta^{(t)})
\end{equation}

よって、尤度は単調に増加していく

コメント

タイトルとURLをコピーしました