オンラインEM(OnlineEM)論文
オンラインEMアルゴリズムの論文を読んだ。というか結構前に読んでいたのだが、何かと忙しくて記事にするのを忘れていた。そろそろ私の頭からも消えかかっていたので忘れないうちにメモ。
オンラインEM(OnlineEM)はEMアルゴリズムのオンライン版。オンラインアルゴリズムとはデータ全体をメモリに乗せずに、データを一件ずつ使ってパラメータを順次更新していく方法。なので一般にオンラインアルゴリズムではメモリ効率が良くなる。
しかしオンラインEMの場合は状況が異なる。EMアルゴリズムではパラメータ推定の際に十分統計量とよばれる値を保持しておけばよく、そもそもデータ全体を保持する必要がない。
では何が嬉しいのか、というとオンラインEMは通常のEMに比べて収束が早いという点。ただ論文の実験結果をみると、精度では本来のEMには及ばないみたい(うまくパラメータ設定すればEMと同等な場合もある)。
通常のEMではMステップの度にパラメータが更新される。オンラインEMではパラメータ更新を新しいデータが来るタイミングで行う。これによって頻繁にパラメータが更新されるので収束が速まるよ、という仕組み。
以下、大ざっぱに内容にふれる。通常のEMが
Eステップ
foreach (x) {
P(z|x;θ') を計算
μ += Σ_x { Σ_z P(z|x;θ')φ(x,z)}
}
Mステップ
Q'(μ)を最大化するパラメータθを求める。
θ' = θであるのに対して、オンラインEMアルゴリズムは
foreach (x) {
Eステップ
P(z|x;θ') を計算
s = Σ_x { Σ_z P(z|x;θ')φ(x,z)}
sを使ってμを更新 -(1)
Mステップ
Q'(μ)を最大化するパラメータθを求める。
θ' = θ
}となる。xに関するループがEステップ、Mステップの外にでておりデータ1件ごとにパラメータ更新が行われているのがわかる。なお(1)の「sを使ってμを更新」の方式には2通りあって、それぞれ論文でIncrementalEM、StepwiseEMとして紹介されている。
補足：
- Q'(μ)は元論文ではθ(μ)だったが紛らわしいのでQ'()とした。
- μはEMにおける十分統計量で、最尤推定での十分統計量Σ_x φ(x)をEM版に拡張したものだと考えるとよい。
十分統計量については
を参照。
