EM algorithm（EMアルゴリズム、Expectation Maximization algorithm）について

EMアルゴリズムはいろんなところで使われます。

基本的には未知パラメータの推定方法の一種です。

とりあえず箇条書でまとめます。

提案論文：Maximun likelihood from incomplete data via the EM algorithm.

Dempster AP, Laird NM and Rubin DB. JRSS B. 39,1-38. 1977.

提案者のRubinは欠測分野、因果推論の権威で次の教科書も書いています。

教科書：The EM algorithm and its extensions.

McLachlan GJ and Krishnan T. Wiley. (1997)

EMアルゴリズムだけで一冊の本が出ているわけですが、この本はBishop本で紹介されてたので良本なのでしょう（@doryokujinさんはこの本で勉強したらしいです）。

残念ながら日本語で分かりやすく説明されている本はありませんでした。

日本語の本を読むより、Bishop本とHastie本を英語のまま読んだ方が分かりやすかったです笑

また@doryokujinさんお勧めのPDF資料はこちらです。

• http://bit.ly/eXqDGA
• http://www2.isye.gatech.edu/~brani/isyebayes/bank/handout12.pdf

以下、EMアルゴリズムの説明です。

【EMアルゴリズム】

• 最初の提案：欠測のあるデータからどうやって同時分布のパラメータを推定するか
• 一般化：未観測のデータを含む分布のパラメータの推定方法
  • 欠測データ
  • 潜在変数を仮定したデータ

【計算アルゴリズム】

1. パラメータの初期値を決める
2. Expectationステップ：未観測データの期待値を求める
   • 未観測データのパラメータを計算する
3. Maximizationステップ：未観測データを動かして目的関数を最大にするパラメータを求める
4. 2と3を繰り返す

混合正規分布の具体例

• この例はBishop本とHastie本の両方でEMアルゴリズムの導入で説明されていました。
• 目的：観測データに平均と分散の違う2つの正規分布を混合した分布を仮定し、パラメータを推定したい。
  • mixture model
  • 混合効果モデル（mixed model）とは似て非なるものなので注意！
• パラメータ：平均2つ、分散2つ、混合割合1つ

1. 5つのパラメータの初期値を決める
2. Eステップ：responsibilityを計算する
3. Mステップ：パラメータの更新式にresponsibilityを代入してパラメータを更新する
4. 対数尤度を評価して収束するまで2と3を繰り返す

• Responsibility：同時分布に潜在変数を入れて表現し直す。その潜在変数の期待値。
  • この潜在変数が未観測データの意味を持つ

【幾何的イメージ】

• Newton-Raphson method（ニュートンラフソン法）
  • 知ってる人が多いと思うのでこの方法でまずイメージを掴む

• EMアルゴリズム
  • 収束がうまく行く例

• 局所解に落ちてしまう例

• このように描けばイメージは付きやすいのですが、そもそも目的関数が複雑な場合にEMアルゴリズムを適用するので、どのような関数か図示できない場合が多いです。

【Rでの例】

• EMアルゴリズムはパラメータ推定のための計算手順の1つ
• 「EMアルゴリズム」というパッケージがあるわけではなく、いろいろな場面で使われている
• phmmパッケージ
  • Cox回帰に混合効果モデルを当てはめて、EステップでMCMCを使ったEMアルゴリズムで推定する
  • Vaida, F. and Xu, R. "Proportional hazards model with random effects", Statistics in Medicine, 19:3309-3324, 2000.
• mlmmmパッケージ
  • 欠測のあるデータに混合効果モデルを当てはめて、EMアルゴリズムとスコア法を組み合わせた方法で推定する
  • Schafer, J.L. and Yucel, R.M. (2002) Computational strategies for multivariate linear mixed-effects models with missing values. Journal of the Computational and Graphical Statistics, Volume 11, Number 2, 437–457.
• MFDAパッケージ
  • 0関数クラスタリング（混合モデルを仮定したクラスタリング？）のパラメータ推定にEMアルゴリズムを使う

【EMアルゴリズムとギブスサンプリングの関係】

• 事後確率のパラメータを求めるという文脈で密接な関係がある
• EM：目的関数を最大化する
• Gibbs：条件付分布からサンプリングする

【小ネタ】

• 私の教室の2008年あたりの博士論文が「因果推論モデル（principal stratum）のパラメータをEMアルゴリズムを使ってSASで推定する」というものでした。

つまり、、、

EMアルゴリズムをプログラムで実装できれば博士号をとれる！？

かもしれません笑

しかし、、、

• プログラミングしてもうまく収束しないことが多い
  • 初期値が問題なのか？
  • プログラミングが上手く行ってないのか？
  • そもそも収束するような関数ではないのか？

原因をつきとめるのがこれまた困難だったりします。