next up previous
次へ: 正規混合分布の汎化バイアスの非単調性について 上へ: EM アルゴリズム 戻る: EM アルゴリズムの一般化


EM アルゴリズムの幾何学的解釈

Amari[17] は EM アルゴリズムの幾何学的な意味を情 報幾何学の観点から明らかにした. 一般に EM アルゴリズムがどういったこと をしているのかについての直観的理解の助けとなると考えられるのでここにま とめておく.

最尤推定は,サンプル点からモデルへの m-射影を取ることと解釈できるが, 一般にモデルの空間が曲がっているとその推定も難しくなる. このとき,サン プルを不完全データとみなし,完全変数の分布の空間でみたときにモデルが e-平坦(あるいはそれに準ずる空間)だったとしたら,その空間で推定を行った 方が有利になる. ただし,その場合にはサンプル点は完全変数の分布の空間 の 1 点ではなく,観測されない自由度の分多様体となる. これをデータ多様 体と呼ぶ.

ここで,データ多様体とモデル多様体を反復して,その間の Kullback-Leibler ダイバージェンスを最小にする点を求めるアルゴリズムを考 えよう(図 3.1).

  1. (e-ステップ) モデル多様体からデータ多様体への e-射影をとる.
  2. (m-ステップ) その点からモデル多様体への m-射影をとる.
このアルゴリズムは em アルゴリズムと呼ばれ,もともと Csiszárら [28] によって提案され,Amari[17] で整理された ものである.

em アルゴリズムは必ずしも不完全変数の最尤推定量に収束するとは限らない が,多くの問題ではデータ多様体が m-平坦であることから,e-射影を取るの が幾何学的には自然であり,Amari[17] は em アルゴリズムがEM アルゴリズムに一致する条件を調べ,異なる場合でも両者が漸近的には等価と なることを示した. 指数分布族に対する EM アルゴリズムが簡単な形で得ら れるのも,完全変数の空間ではモデル多様体が平坦であるからであると解釈できる.

特に,分布の空間として関数空間を考えると,EM アルゴリズムと em アルゴリズム の一致が容易に導けるのでここではそれについて簡単に示しておく. 関数空間は一般に多様体ではないが,em アルゴリズムは形式的に行うことが できるので,以下では多様体として取り扱う.

定理 2 (Amari[17])   分布の空間として関数空間をとって em アルゴリズムを構成すると, それは EM アルゴリズムに一致する.

これは以下のように示すことができる. まず,関数空間を考えているので,与えられたサンプル $x$ に対応する分布は, $x$ の分布の空間の上の $\delta(x)$ という点になる. これに対応する完全変数の分布の空間の中でのデータ多様体 $D$ は,
\begin{displaymath}
p(y) = 0, \qquad y \not\in Y(x),
\end{displaymath} (3.42)

を満たす $p(y)$ 全体の集合として表される. 今,完全変数のモデルの空間を $M$ とすると, $D$ への e-射影は $p(y)\in D$ $p(y;\ \theta\tth )\in M$ との Kullback-Leibler ダイバージェンス,
\begin{displaymath}
K(p(y)\,\Vert\,p(y;\ \theta\tth )) = \int p(y)\log {p(y)\over p(y;\ \theta\tth )}
\,{\rm d}y,
\end{displaymath} (3.43)

を最小にする $p(y)$ として与えられ,
\begin{displaymath}
p(y) = \left\{\begin{array}{ll} p(y;\ \theta\tth )/p(x;\ \t...
... ),
& y\in Y(x),\\
0, & y \not\in Y(x),
\end{array}\right.
\end{displaymath} (3.44)

となる. 一方,この $p(y)$ から $M$ への m-射影は,$p(y)\in D$ $p(y;\ \theta)\in M$ との Kullback-Leibler ダイバージェンス $K(p(y)\,\Vert\,p(y;\ \theta))$ を最小にする $\theta$ として与えられる. これは式 (3.45) から,
\begin{displaymath}
\int_{Y(x)} {p(y;\ \theta\tth )\over p(x;\ \theta\tth )}
\log p(y;\ \theta)\, {\rm d}y,
\end{displaymath} (3.45)

を最大にする $\theta$ と同じであるが,上式はまさに EM アルゴリズムで 最大化する $Q(y\mid x;\ \theta\tth )$ に他ならない.

図 3.1: EM アルゴリズムの幾何学的イメージ
\begin{figure}\begin{center}
\leavevmode
\begin{epsfeq}{120}{120}
\putepsf{fil...
...put(28,51){m} \put(46,51){m} \put(59,51){m}
\end{epsfeq}\end{center}\end{figure}



Shotaro Akaho 平成15年7月22日