EMアルゴリズム

EMアルゴリズムについてメモ。

最尤推定とは対数尤度Σ_x logP(x;θ) をパラメータθについて微分し

∂Σ_x logP(x;θ)/∂θ = 0

を満たすθを見つけること。

データに観測できない変数(潜在変数)がある場合はEMアルゴリズムを使う。例えばcを潜在変数とすると対数尤度は

  Σ_x E[logP(x, c;θ)]
= Σ_x { Σ_c P(c|x;θ')logP(x, c;θ) }

というように期待値を使って表現される。この期待値を使った対数尤度はQ(θ, θ')関数と呼ばれる。

EMアルゴリズムはEステップとMステップからなり、E、M、E、M・・・というように繰り返して適用していく。
EステップではP(c|x;θ')を計算する。この計算に必要なθ'は一つ前のMステップで求めた値を使う。初回は適当に決めた初期値を使うが、初期値によっては局所解に収束してしまうので注意。

MステップではEステップで求めたP(c|x;θ')を使ってQ(θ, θ')の最適解を計算する。Q(θ, θ')をパラメータθについて微分し

∂ [ Σ_x { Σ_c P(c|x;θ')logP(x, c;θ) } ] / ∂θ = 0

を満たすθを見つける。ここで求めたθをθ'に代入してEステップに戻る。
θとθ'の差分が閾値以下になるか、規定のループ回数を超えたらアルゴリズム終了。終了時点でのθが求めるべきパラメータ。

実装について。Eステップはベイズの定理を適用して解けるのでそんなに難しくない。問題はMステップで、∂Q(θ) / ∂θ = 0が解析的に求まる場合には問題ないが、そうでない場合はSGDなどの数値計算によって求める必要がある。