Learning the game 2010 -: Statistic modeling : EM algorithm

モデルの推定方法－EM algorithmの部分についてのまとめ。（サイトからのつぎはぎ）

ある確率変数 X = {Y , Z} があり，その一部 Y のみが観測でき，残り Z （＝潜在変数。下に説明）は観測できない状況を考える．観測データ {y1, y2, . . ., yT } が得られたときに，確率モデル p(x; θ) = p(y, z; θ)のパラメタ θ を推定したいとする（取り扱っている分布が、混合ガウス分布であればθはμ,Σ,πの3つ）。パラメータは、Xの分布からして、最もよさげなもの、というふに考える（最尤法）。p(y; θ) =∫p(y, z; θ)dz

最尤推定値を数値計算で求める代表的な方法
1．ニュートン・ラプソン法
2．Fisherのスコア法
3．EM algorithm

とあるが、Zの存在のために、これが簡単に解けず、EMアルゴリズムを使う（1や2では無理？）。モデルが混合分布でない場合は、このサイトで示しているように、反復なしで解がもとまる。

ステップ0．尤度関数をつくる

最初に、現象を式で表す必要がある。

観測された現象の起こる確率、イコール、観測されたデータについての尤度関数Lをつくる。

Given a statistical model consisting of a set $\mathbf{X}$ of observed data, a set of unobserved latent data or missing values $\mathbf{Z}$ , and a vector of unknown parameters $\boldsymbol\theta$ , along with a likelihood function $L(\boldsymbol\theta; \mathbf{X}, \mathbf{Z}) = p(\mathbf{X}, \mathbf{Z}|\boldsymbol\theta)$ , the maximum likelihood estimate (MLE) of the unknown parameters is determined by the marginal likelihood of the observed data

$L(\boldsymbol\theta; \mathbf{X}) = p(\mathbf{X}|\boldsymbol\theta) = \sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z}|\boldsymbol\theta)$

However, this quantity is often intractable(解決困難な)^{[citation needed]}.

The EM algorithm seeks to find the MLE of the marginal likelihood by iteratively applying the following two steps:

ステップ1．E step

Eステップでは、完全データの対数尤度関数ln p(X, Z|θ)の期待値を計算する。最初の試行ではθに初期値を与える必要がある。また、この期待値を計算するために、潜在変数の事後分布p(Z|X, θold)を用いる。

対数尤度関数の期待値、という概念が分かりにくいので、追加説明。

確率論において、確率変数の期待値とは確率と確率変数を掛けた総和を取ったものである（高校数学）。ここでは、確率変数がln p(X, Z|θ)であり、その確率変数が出る確率が、p(Z|X, θold)となる。

wikiでは、
1/ Expectation step (E step): Calculate the expected value of the log likelihood function, with respect to the conditional distribution of $\mathbf{Z}$ given $\mathbf{X}$ under the current estimate of the parameters $\boldsymbol\theta^{(t)}$ :

$Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) = \operatorname{E}_{\mathbf{Z}|\mathbf{X},\boldsymbol\theta^{(t)}}\left[ \log L (\boldsymbol\theta;\mathbf{X},\mathbf{Z}) \right] \,$

となっているが、

この表現よりもPRML(equation 9.30, p156)の方が分かりやすい。つまり、

Q(θ, θold) = Σ p(Z|X, θold) ln p(X, Z|θ)

ステップ2．M step

Mステップでは、E ステップで求まった尤度の期待値を最大化するようなパラメータを求める。 M ステップで求まったパラメータは、次の E ステップで使われる潜在変数の分布を決定するために用いられる。

具体的には、θで偏微分した式イコール0となる等式を解く。

2/ Maximization step (M step): Find the parameter that maximizes this quantity

$\boldsymbol\theta^{(t+1)} = \underset{\boldsymbol\theta}{\operatorname{arg\,max}} \ Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) \,$ 　

*不完全データ（または隠れ変数、潜在変数）

通常Zで表す。
一般的にZとは、観測できている確率変数Xと区別される、観測できてない確率変数（XとZは対等）。とくに混合分布では、あるデータがどの分布に属するかという情報（ここではとりあえずこの意味に限る）。この場合、zは各xに与えられるK次元ベクトル（Kを分布の数）で、データxがどのガウス分布から生成されたかを表す。属する分布番号のみ1、他は0。

例1．2 次元の正規分布が 6 つ重なった正規混合分布を例に考えよう．この確率分布からデータが得られているとする．この場合，出力されるデータのみからはどの正規分布によって出力されたかが分らない．すなわち，どの正規分布から出力されたかという情報は観測できない．この「どの正規分布から発生したか」という情報が隠れ変数となる．正規混合分布の場合は隠れている確率変数は離散的な確率変数である．

例2．今、何カ国かの男性の身長データのサンプルがN個混在してあります。ただし、N個のデータはすべて、どの国の男性の身長データなのか分かっていません(不完全データ)。このとき、EMアルゴリズムを用いて、「何カ国のデータが混在しているのか※1」と、「各国の身長の平均値と分散※2」を同時に求めたいのですが、・・・（省略）