この項の問題点
この項は未完成であり重大な間違いを含んでいる可能性があります。
数学的な厳密さはありません。式変形の途中で確率分布や確率密度関数がきちんと定義されているのか疑わしいです。また全体的に説明不足です。
概要
EMアルゴリズム(The EM algorithm, [Dempster et al. 1977])は不完全データに対して最尤推定を行うメタアルゴリズムです。Expectation-stepとMaximization-stepの二つのステップを繰り返すことにより、確率パラメータを更新していきます。
問題設定
は隠れ変数、
は観測、
は確率パラメータ、
は観測の数、
は対数尤度です。(
はベクトル)
T回観測された
に対して、
が対応します。(
もベクトル)
ここで
はi.i.d(独立同分布)とします。
対数尤度
を最大化するような
を求めることが目的です。
上の変形から分かるように
は対数の中に和を含む形となっています。これを直接最大化するのは困難です。
導出
EMアルゴリズムの導出にはいくつかの種類がありますが、ここでは比較的直感的だと考えられる導出を示します。
尤度を最大化するような確率パラメータを直接求める代わりに、ある
よりも対数尤度を大きくするような
を求めることにします。(詳しい説明が必要)
対数尤度の差をとり変形していきます。
ここで
を以下のように定義しました。
また
は
と
のKullback–Leiblerダイバージェンスであり、これは常に0以上です。(詳しい説明が必要)
よって下の式が成り立ちます。
ここから、
を最大化するような
を求めることにより、ある
よりも対数尤度を大きくするような
を求めることができると分かります。(対数尤度は常に0以下。)
The EM algorithm
Initialization
初期パラメータ
を与える。
Expectation-step(E-step)
現在(i回目の繰り返し)の確率パラメータ
を用いて期待値を計算する。
Maximization-step(M-step)
期待値を最大化する
を
とする。
終了条件を満たすまでE-stepとM-stepを繰り返す。
メモ
EMアルゴリズムの終了条件はある小さな正の値
に対して
とするのが一般的です。
EMアルゴリズムの結果は初期値に依存します。local maximumに収束することは保障されていますが、それはglobal maximumであるとは限りません。そこで初期値を変えて複数回アルゴリズムを実行する手法が一般的です。
Maximum A Posteriori
これまで、対数尤度
を最大化するような
を求めることをEMアルゴリズムの目的としてきました。ここでは対数尤度
ではなく対数事後確率
を最大化するような
を求めることを目的にします。(詳しい説明が必要)
事後確率を最大化することをMaximum A Posteriori estimation(MAP推定)と呼び、尤度を最大化することをMaximum Likelihood estimation(ML推定)と呼びます。
ベイズの定理から対数事後確率は以下のように変形できます。
右辺の第一項は対数尤度となっています。
MLの時と同じように
と
のそれぞれの対数事後確率の差をとって変形していきます。
ここで
を以下のように定義しました。
MAPの場合は
を最大化するようにパラメータを更新していきます。
最終更新:2009年11月20日 10:58