img { border : 1px solid #DADADA ; border-bottom : 1px solid #757575 ; box-shadow : 0 2px 4px rgba(0, 0, 0, 0.2) ; }

マイノート

いろいろ勉強したことをまとめていきます

MENU

【編集中】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アルゴリズムを簡易的なイメージを用いて説明してくれてるスライドがあった

http://yagays.github.io/blog/2013/12/15/mlac-2013-em-algorithm/

もう少し詳しく

\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}

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