初めてのEMアルゴリズム

EMアルゴリズムとは

今日の自然言語処理特論の内容はEMアルゴリズム。N-gram言語モデルを作るときには、未知語に関連して0頻度問題がつきまとう。TrigramからBigram、BigramからUnigramと切り替えていくback-offなどの方法もあるが、今日やったのは線形補完法というもの。切り替えるのではなく、「この単語列はTrigramから何%、Bigramから何%」という具合にモデルに確率を割り振っていくというような方法である。もちろん、「この単語列はTrigramからきたもの」というようなラベルはついていない。こういうものを隠れ変数と呼んだりする。このような状況で尤度関数を(局所的には)最大にしてパラメータを推定するような方法をEMアルゴリズムという。

EMアルゴリズムはその名前の通りExpectationをMaximazationするアルゴリズム。何のExpectationかと言えば「完全データの対数尤度」の期待値。これをMaximazationしていく。このiterationの操作というのは(微分不可能であるような)関数のlower boundを最大化していくととらえると分かりやすかった。

EMアルゴリズムの特徴

線形補完法の例では、尤度関数が凸関数になっているという性質から、EMアルゴリズムを使って局所最適解ではなく大域的最適解を求めることができる!一般の場合だとさすがにそういうわけにはいかないが、局所最適解のようなところにいくまで尤度関数の値を毎回大きくするという性質があるのがEMアルゴリズムのよいところ。ニュートン法や共役勾配法などの最適化手法は二次関数なら関数値を毎回下げる or 上げるような方向に動くことができるが、二次ではない関数だとこれは保証されない。EMアルゴリズムは毎回大きくなる方向に動ける。また、ステップ幅のようなパラメータチューニングの手間が若干はぶけるということもあって、統計系の人たちには人気がある手法のようだ。

まあ、いいところばかりではなく、収束のスピードが遅いというのは欠点としてある(ニュートン法のように局所二次収束のような性質はない)。ただ、EMアルゴリズムを使いながら、途中からニュートン法に切り替えるというようなものも研究がおこなわれているようである。

思っていたよりは難しい感じではなさそうで、EMアルゴリズムの入門として線形補完法は分かりやすい例だなーと思った。