最尤推定と EM アルゴリズム
基本的には、最尤推定の発展バージョンが EM アルゴリズム。
言い換えれば、EM アルゴリズムは最尤推定が基本にあるために、EM アルゴリズムを理解するためには最尤推定を理解することが必須。
最尤推定
最尤という言葉のせいで難しいイメージがあるが、極めて簡単。
表が 0.3 の確率で出るコイン A と表が 0.8 の確率で出るコイン B があるとする。
今、A か B か分からないがどちらかのコインを 3 回続けて投げたら、表、裏、表という順番で出た。
さあ、どっちのコインを投げたでしょう?
このときに最尤推定を使えば簡単に分かる。(というか、最尤推定使わなくても感覚で分かるけど…)
コイン A を使ったときの確率(=尤度)は、
0.3 × (1−0.3) × 0.3 = 0.063
コイン B を使ったときの確率(=尤度)
0.8 × (1−0.8) × 0.8 = 0.128
コイン B を使ったときのほうが確率(=尤度)が高いので正解はコイン B。
これだけ。
EM アルゴリズム
さっきは 3 回とも同じコインで投げたという前提条件があった。
しかし、毎回コイン A、コイン B のどちらも使う可能性がある場合はどうなるだろうか?
A もしくは B が使われる確率を知りたい。
その時に使うのが EM アルゴリズム。
今、コイン A が使われる確率(パラメータ)をθと置く。
θというのはそのモデル(ここではコイン)が使用される確率を指す。
EM アルゴリズムではパラメータの初期値を設定しなければならず、この初期値の決め方が重要である。
普通最適な初期値の決め方は誰にも分からないので、適当(ランダム)に設定する。
ここでは仮に θ=0.6 と設定する。
そうすると、表、裏、表という順番で出たときに、コイン A が使われた回数の期待値は、
つまり、1.56 になる。
これを観測データの個数 3 で割ると 0.52 となる。
これを θ'=0.52 として、再びコイン A が使われた回数の期待値を計算する。
以下同様に計算してくと θ''、θ''' が次々と求まり、真の値に近づいていく。
真の値に近づく(収束する)のは数式で証明されている。
これだけ。
(注釈)
初期値の決め方が重要であると書いたが、初期値の決め方が悪ければ局所解しか求まらない場合がある。
そのときは幾つかの初期値を取って計算する。
EM アルゴリズムの初期値の決定方法が 1 つの論文になるほど、実は奥が深い世界である。