2013年3月9日土曜日

Gaussian MixtureとEMアルゴリズム

in English

はじめに

Gaussian MixturesとEMアルゴリズムについてまとめます(こちらのページでOpenCVの提供する実装と関連付けします)。

Gaussian Mixturesとは

ある確率分布 が与えられたとき、これをガウス関数の線形結合で近似することを考える。この線形結合をGaussian Mixturesと呼ぶ。

ここで、 は、 平均値(ベクトル) 、共分散(行列) を持つGauss関数である。 は各ガウス関数の重みを表す。

いま、観測点の集合 を考える。これらが同時に実現する確率 は以下のように書くことができる。
先に与えた線形結合の式を代入すると

を得る。右辺に存在する全パラメータ を決定し、できるだけ正確に左辺値(観測結果)を再現する手法の1つがEMアルゴリズムである。

EMアルゴリズム

表記を簡易化するため以下の量を導入する。




このとき、 と書き直すことができる。すなわち、パラメータ が与えれたとき、観測値 が実現する確率とみなすわけである。この量は一般に尤度(likelihood)と呼ばれる。 考えているモデル(確率分布)の尤度が最大になるようにパラメータの値を決めることによって,モデルが真の分布に最も近くなるようにすることを最尤法(maximum likelihood method)と呼ぶ。
以上の議論から我々がすべきことは

を最大化することである。計算を容易にするため、尤度の対数を最大化する。

さて、先に進む前に についての拘束条件を導入しておく。確率分布 は以下のように書けた。

両辺を で積分すると

を得る。ここで、ガウス関数は規格化されていることを使用した。この拘束条件は、Lagrange乗数を使って、最大化すべき対数尤度に取り込むことができる。

あとは常道に従い、 で偏微分し、それぞれを0と置いていけばよい。計算は煩雑なので結果のみを示す。
  1. による偏微分により次式を得る。

    ここで、


    とした。
  2. による偏微分により次式を得る。

    ここで、Tは転置を表す。
  3. による偏微分により次式を得る。
3つのパラメータを決定する式が得られた。これらはお互いに依存し合っている。3つの式を同時に成り立たせるため反復法を採用したのが、EMアルゴリズムである。以下手順を示す。
  1. を適当な値で初期化する。
  2. を計算する。
  3. を使って、3つのパラメータを計算する。


  4. を計算する。
  5. が収束するまで、あるいは、 が収束するまで、手順2から4までを反復する。
手順2は尤度の期待値(Expectation)を計算するステップ、手順3は尤度を最大化(Maximization)するパラメータを計算するステップ であることから、EMアルゴリズムと呼ばれる。 手順1において初期値を決める際、K-meansクラスタリングがしばしば用いられる。K個のクラスタの中心座標を、本解説における とみなせば、 も計算することができる。

参考文献

Pattern Recognition and Machine Learning, Christopher M. Bishop, Springer

0 件のコメント:

コメントを投稿