EMアルゴリズム（期待値最大化法）とは？仕組みと特徴をわかりやすく解説

EMアルゴリズムの概要

EMアルゴリズム（Expectation-Maximization algorithm、期待値最大化法）は、パラメータ推定を行うための代表的な反復改良アルゴリズムです。k-means法のパラダイムを拡張したものと考えることができます。k-means法では、クラスタ平均に基づいて各オブジェクトを最も類似度の高いクラスタに割り当てますが、EMアルゴリズムでは所属確率を表す重みに従って各オブジェクトをクラスタに割り当てます。

つまり、EMアルゴリズムではクラスタ間に厳密な境界は存在せず、新しい平均値は重み付けされた測定値に基づいて算出されるのが特徴です。

EMアルゴリズムの仕組み

EMアルゴリズムは、混合モデルのパラメータ（パラメータベクトルとして総称される）の初期推定値、いわば「推測」から始まります。その後、パラメータベクトルから作られる混合密度に対して、オブジェクトを反復的に再スコアリングします。再スコアリングされたオブジェクトは、パラメータ推定値の更新に使用されます。各オブジェクトには、特定のクラスタに所属しているという条件下で、特定の属性値の組み合わせを持つ確率が割り当てられます。

アルゴリズムの手順は以下の通りです。

1. パラメータベクトルの初期推測

k個のオブジェクトをランダムに選択してクラスタの平均（中心）を定義し（k-means法による分割と同様）、その他のパラメータについても推測値を設定します。

2. 2つのステップの反復

以下の2つのステップを繰り返すことで、パラメータ（クラスタ）を改良していきます。

(a) Eステップ（Expectation Step）

各オブジェクト x_i を、次の確率でクラスタ C_k に割り当てます。

$$P(x_{i}\epsilon C_{k})=p(C_{k}|x_{i})=\frac{p(C_{k})p(x_{i}|C_{k})}{p(x_{i})}$$

ここで、p(x_i|C_k) = N(m_k, E_k(x_i)) は、平均 m_k、期待値 E_k を中心とする正規分布（ガウス分布）に従います。このステップでは、各クラスタについてオブジェクト x_i のクラスタ所属確率を計算します。これらの確率は、オブジェクト x_i の「期待される」クラスタ所属度を表しています。

(b) Mステップ（Maximization Step）

Eステップで得られた確率推定値を用いて、モデルのパラメータを再推定（改良）します。例えば、次のように計算されます。

$$m_{k}=\frac{1}{n}\sum_{i=1}^{n}\frac{x_{i}P(x_{i}\epsilon C_{k})}{\sum_{j}P(x_{i}\epsilon C_{j})}$$

このフェーズは、与えられたデータに対する割り当ての尤度を「最大化」する段階にあたります。

EMアルゴリズムの特徴

EMアルゴリズムはシンプルで理解しやすく、実装も容易です。収束は速いものの、大域的最適解に到達できない場合がある点には注意が必要です。ただし、特定の形式の最適化関数については収束が保証されています。計算量は、d（入力属性の数）、n（オブジェクトの数）、t（反復回数）に対して線形であり、効率的に処理できます。

ベイジアンクラスタリングとAutoClass

ベイジアンクラスタリング手法は、クラス条件付き確率密度の計算を目的とした手法で、主に統計学の分野で広く利用されています。

産業界では、EMアルゴリズムを改良した有名なベイジアンクラスタリング手法としてAutoClassが知られています。AutoClassでは、オブジェクトの正しいクラスタが与えられたときに、そのオブジェクトの属性を予測する能力を最大化するクラスタリングが「最良」とされます。さらに、AutoClassはクラスタ数の自動推定も可能です。さまざまな分野で活用されており、赤外線天文学のデータに基づいて新しい恒星のクラスを発見した実績でも注目を集めました。