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