EM アルゴリズムの一般化

EM アルゴリズムは各ステップで尤度が単調増加することが保証されており， 局所最適解または鞍点に収束することが知られている[91]． しかしな がら，要素分布の学習の例で見たように，一般には M ステップにおける最適 化問題が陽に解けるとは限らない． そこで制限を緩め，M ステップでは，

$$Q(\theta\mid x;\ \theta\tth ) \ge Q(\theta\tth\mid x;\ \theta\tth ),$$ (3.39)

なる $\theta$ を見つければよいことにする． この場合でも尤度の単調増加性 は保たれている． この方法を一般化 EM アルゴリズム (Generalized EM)と呼 ぶ． ただし，局所最適解(または鞍点)への収束は一般には成り立たなくなる．

Meng and Rubin[52] は一般化 EM アルゴリズムの一種としてECM (Expectation-Constrained Maximization) アルゴリズムと呼ばれる手法を提 案した． これは，$Q$ の最大化をすべての変数に対して同時に行うのではなく， いくつかの変数のまとまり毎に分けて最適化を行う手法であり，変数の同時最 適化が難しい最適化問題においてしばしば用いられる coordinate descent 法 [93]の一種である． 一般に最適化問題では軸ごとに最適化を行っ ても，被最適化関数の単調増加性は維持されている． また，ECM アルゴリズム では局所最適解(または鞍点)への収束が示されている． 第 5 章では，ECM アルゴリズムを用いて M ステップが陽な 形で得られるようにする．

本論文では扱わないが，一般化 EM アルゴリズムがより有効な場合として， ベイズ推定への拡張について説明しておく． EM アルゴリズムは最尤推定を行うアルゴリズムであるが， ベイズ推定の枠組みにおける MAP (Maximum a posteriori) 推定にも適用可能である． $\theta$ の事前分布 $r(\theta)$ が与えられているとき， 事後分布

$$p(\theta\mid x) \propto r(\theta)\, p(x\mid\theta),$$ (3.40)

を最大にする $\theta$ を MAP 解と呼ぶが，この場合には $Q$ の代わりに，

$$\hat{Q}(\theta\mid x;\ \theta\tth ) = Q(\theta\mid x;\ \theta\tth ) + \log r(\theta),$$ (3.41)

を最大化すればよい． 一般にこの場合はより最適化が困難となるので一般化 EM アルゴリズムを適用することが多い．

さて，一般化 EM アルゴリズムは主に M ステップを一般化する試みであるが， サンプル数が増えたり，複雑なグラフィカルモデルに EM アルゴリズムを適用 する際には E ステップが組合せ的に多くの計算量を要したり，場合によって は数値積分を必要とする場合がある． 本論文では用いていないが，いろいろな 研究がされているので概略を述べておく． 広く用いられているのは E ステッ プにおける積分計算を Monte Carlo 法を用いてサンプリングする方法である． 特に，Markov Chain を用いて Monte Carlo 法を行う Gibbs サンプリングな どの Markov Chain Monte Carlo (MCMC) 法は，実際の応用などで幅広く用い られている[35]． また，その更なる近似解法である変分法や平均 場近似などの研究も盛んである[33]．