「機械学習/EM variant」の編集履歴（バックアップ）一覧に戻る

機械学習/EM variant - (2009/11/28 (土) 00:07:21) のソース

#contents(fromhere=true)


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

**概要
EMアルゴリズム（The EM algorithm, [Dempster et al. 1977]）には多くのvariantがあります。

**問題設定
各記号については[[EMアルゴリズム>機械学習/EMアルゴリズム]]の項を参照してください。

**一般化EMアルゴリズム
一般化EMアルゴリズム（Generalized EM algorithm）はEMアルゴリズムのMaximization-stepにおいて、完全な最大化ではなくただ尤度を増加させるようなパラメータを選ぶ手法です。完全な最大化が難しい場合に用いられます。EMアルゴリズムの項で見たように、対数尤度の差$${\rm L}(\theta') - {\rm L}(\theta)$$と期待値の差$${\rm Q}(\theta' \mid \theta) - {\rm Q}(\theta \mid \theta)$$の間には以下の不等式が成り立ちます。

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

現在の確率パラメータ$$\theta$$よりも尤度を増加させるような新しい確率パラメータ$$\theta'$$を得ることが目的なので、必ずしも$${\rm Q}(\theta' \mid \theta)$$を最大化する必要はありません。単純に$${\rm Q}(\theta' \mid \theta) - {\rm Q}(\theta \mid \theta) \geq 0$$となるような$$\theta'$$を求めればよいのです。

**ECM
ECM(Expectation Conditional Maximization [Meng and Rubin 1993]）は、Maximization-stepにおいて、確率パラメータをいくつかのグループにわけ、グループごとに更新していく手法です。確率パラメータ間に依存関係があり、完全な最大化が難しい場合に用いられます。ECME(Expectation Conditional Maximization Either [Liu and Rubin 1994])も同様のアルゴリズムです。

**下限
[Neal and Hinton 1998]によるEMアルゴリズムの定式化は、EMアルゴリズムの二つのステップであるExpectation-stepとMaximization-stepを、どちらも最大化のステップとして考えます（必ずしも最大化する必要はなく、ステップごとに目的関数の値が増加していればよいです）。[Neal and Hinton 1998]ではExpectation-stepを部分的に最適化するincremental EMの話題が主ですが、下限を扱うこの考え方を理解しておくと変分ベイズ（variational Bayes）も理解しやすくなるでしょう。

あるテスト分布$$q(x_t)$$を導入して対数尤度の式を変形します。（実際に$$q(x_t)$$が存在するための条件についての議論はここではしませんが重要な問題です）

#math(){{{{{
\begin{eqnarray}
\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) \\
&=& \sum_{t=1}^{T} \log \sum_{x_{t}} q(x_{t}) \frac{p(x_{t}, y_{t} \mid \theta)}{q(x_{t})} \\
&\geq& \sum_{t=1}^{T} \sum_{x_{t}} q(x_{t}) \log  \frac{p(x_{t}, y_{t} \mid \theta)}{q(x_{t})} \\
&=& \sum_{t=1}^{T} \sum_{x_{t}} q(x_{t}) \log p(x_{t}, y_{t} \mid \theta) - \sum_{t=1}^{T} \sum_{x_{t}} q(x_{t}) \log q(x_{t}) \\
&=& {\rm E}_{q}[\log p(x_t,y_t \mid \theta)] + {\rm H}[q] \\
&=& {\rm B}[q, \theta]
\end{eqnarray}
}}}}}

上の式の途中でJensenの不等式を用いています。$${\rm H}[q]$$はエントロピーです。対数尤度$$\log p(y \mid \theta)$$と下限$${\rm B}[q, \theta]$$の差は$$q(x_t)$$と$$p(x_t \mid y_t , \theta)$$のKullback–Leiblerダイバージェンスとなります。

#math(){{{{{
\begin{eqnarray}
\log p(y \mid \theta) - {\rm B}[q, \theta] = {\rm KL}(q \parallel p_{\theta})
\end{eqnarray}
}}}}}

ここで対数尤度$$\log p(y \mid \theta)$$の代わりにその下限である$${\rm B}[q, \theta]$$を最大化することを考えます。$$q(x_t)$$と$$\theta$$は独立なので、それぞれにおいて最大化していきます。もともとの目的は$$\log p(y \mid \theta)$$を最大化するような$$\theta$$を求めることだったのに、$${\rm B}[q, \theta]$$を最大化するためには$$q(x_t)$$と$$\theta$$の両方を考慮しなければならないことに注意してください。$${\rm B}[q, \theta]$$は$$q(x_t)$$の汎関数なので、一見して問題を故意に複雑にしているように感じるかもしれません。（詳しい説明が必要）

まず$$\theta$$を固定して$$q(x_t)$$において$${\rm B}[q, \theta]$$を最大化します。$$\theta$$が固定されているので$${\rm B}[q, \theta]$$の上限は$$\log p(y \mid \theta)$$です。$${\rm B}[q, \theta]=\log p(y \mid \theta)$$とするにはKullback–Leiblerダイバージェンス$${\rm KL}(q \parallel p_{\theta})=0$$とすればよく、これはつまり$$q(x_t) = p(x_t \mid y_t , \theta)$$を満たせばよいということです。

次に$$q(x_t)$$を固定して$$\theta$$を変化させます。上で$$q(x_t) = p(x_t \mid y_t , \theta)$$としたので、$${\rm B}[p_{\theta} , \theta']$$を$$\theta'$$において最大化します。（$${\rm B}[p_{\theta} , \theta']$$は$${\rm B}[q , \theta]$$の$$q$$を$$p_{\theta}$$に、$$\theta$$を$$\theta'$$としたものです。）

#math(){{{{{
\begin{eqnarray}
{\rm B}[p_{\theta}, \theta'] &=& {\rm E}_{p_{\theta}}[\log p(x_t,y_t \mid \theta')] + {\rm H}(p_{\theta}) \\
&=& \sum_{t=1}^{T} p(x_t \mid y_t , \theta) \log p(x_t,y_t \mid \theta') - \sum_{t=1}^{T} p(x_t \mid y_t , \theta) \log p(x_t \mid y_t , \theta)
\end{eqnarray}
}}}}}

上の右辺の第二項は$$\theta'$$を含まないので最大化には関係ありません。よって第一項のみ最大化すればよいことがわかります。この最大化の対象である第一項はまさにEMアルゴリズムにおける期待値$${\rm Q}(\theta' \mid \theta)$$です。つまり、下限$${\rm B}[q , \theta]$$を$$q(x_t)$$と$$\theta$$のそれぞれにおいて最大化することは、EMアルゴリズムと等しいことが言えます。

**その他
EMアルゴリズムにはとにかく多くのvariantが存在します。variantの中にはlocal maximumへの収束が保障されていないものもあるので注意してください。EM variantについては[McLachlan and Krishnan 1997]が詳しいようです。

-MCEM(Monte Carlo EM [Wei and Tanner 1990])
-SEM(Supplemented EM [Meng and Rubin 1991])
-SAGE(Space-Alternating Generalized EM [Fessler and Hero 1994])
-AECM(Alternating ECM [Meng and van Dyk 1997])
-PX–EM(Parameter-eXpanded EM)
-DAEM(Deterministic Annealing EM [Ueda and Nakano 1998])
-incremental EM([Neal and Hinton 1998])
-sparse EM([Neal and Hinton 1998])
-SMEM(Split Merge EM [Ueda et al. 2000])
-stepwise EM([Sato and Ishii 2000, Cappe and Moulines 2009])
-lazy EM([Thiesson et al. 2001])

----