next up previous
次へ: 一般的な定式化 上へ: EM アルゴリズム 戻る: EM アルゴリズム

一般的な特徴

EM アルゴリズムは,観測できない隠れたパラメータが存在する時に最尤推定 を行うための汎用手法であり,混合分布以外にも隠れマルコフモデルやグラ フィカルモデルの学習に応用されている. EM アルゴリズムは Newton 法(ある いは Fisher のスコアリング法)や勾配法と同様,反復法によって局所最適解を求めるア ルゴリズムであるが,他の手法に比べて次のような長所をもつ [30,69,53,84].

  1. 尤度が単調に増加することが保証されており,アルゴリズムの振る舞い が安定している. 前節で述べたように,混合分布では尤度が無限大になる無 意味な解が存在するので,アルゴリズムの安定性は重要である.
  2. 速度に関しても収束の初期の段階では Newton 法と同程度の速さになる ことが知られている(ただし,最適解の近傍では 1 次収束なので種々の加速 法が考案されている).
  3. インプリメンテーションが簡単になることが多い. また,これと関係 して 1 ステップに要する計算量が減らせる場合もある. Newton 法では尤度 の Hessian を計算する必要があるが,混合分布などでは一般に複雑な形に なり,多くの計算量を必要とする.

以下ではまず 3.4.2 で, EM アルゴリズムを Dempster らによってまとめられた一般的な 形[30]で説明し,尤度の収束性や収束の速さについて 知られている事柄をまとめる. 次に混合分布に限定してアルゴリズムを導く. 3.4.3 では,独立同分布に従う訓練サンプルが与えられるという 通常学習において仮定される条件に特殊化し, 更に,要素分布が互いに独立な場合を 3.4.4 で述べる. 3.4.5 では,階層的な混合モデルに有用な重み付きの 形でアルゴリズムをまとめる. 続いて 3.4.6 では第 5 章でも用いる EM アルゴリズムの一般化について述べ, 3.4.7 では直観的なイメージを与えるために, Amari[17] によって得られた幾何学的な解釈を述べる.



Shotaro Akaho 平成15年7月22日