確定的アニーリングEMアルゴリズム

概要:

EMアルゴリズムは、不完全データから最尤推定値を 数値的に求める汎用アルゴリズムであり、信号処理、画像・音声認識等、 広く用いられている。 EMアルゴリズムは、単純かつ計算量が軽い等の特長を有するが、 勾配型のアルゴリズム故、実用上、局所最適性の問題を有する。 即ち、EMアルゴリズムの性能は、 推定パラメータの初期値設定に大きく左右される(図1(a))。 この問題は多くの研究者により指摘されているものの、有効 な解決法は提案されていなかった。

  

図 1: パラメータ推定結果比較

DAEMでは各温度での探索結果をパラメータm₁,m₂-平面上の $\beta=1$の自由エネルギー関数（$\equiv$ 尤度関数）上 に重畳して表示している

確定的アニーリングEMアルゴリズム

本研究では、この問題を解決すべく、最大エントロピー原理と 統計力学のアナロジーを用いて確定的アニーリングEM (Deterministic Annealing EM: DAEM) アルゴリズムを導 出した[1] [3]。 本アプローチでは、最尤推定、即ち、尤度関数の最大化問題を ''温度''に依存する自由エネルギー関数の最小化問題として 再定式化し、この温度パラメータを用いてアニーリング過程を制御する ことによりEMアルゴリズムの局所最適性の問題に対処している。

図2に示すように、温度が高い($\beta$が小さい)程、自由エネルギ ー関数(F)は尤度関数の大局的構造を具現し、$\beta=1$で尤度関数と 完全に一致する。従って、高温から徐々に温度を下げながら ($\beta$を大きくしながら)各温度で探索を行なうことにより、 広域最適解を探索する。但し、従来の模擬徐冷法(SA)と異なり、 各温度での最適化が確定的に実行されるので、SAに比べ極めて 効率的である。 混合分布に基づく確率ニューラルネットの学習に本DAEMアルゴリズム を適用し、その有効性を確認 した[2] [3]。

  

図 2: 温度パラメータによるアニーリングの制御

各温度での探索はその 前の温度での収束値を初期値として確定的探索(山登り)を行ない$\beta$を1に 近付けながら次第に真の解に誘導する

連絡先：上田 修功, Email: ueda@cslab.kecl.ntt.co.jp

参考文献

1

Ueda, N. and Nakano, R.: Deterministic annealing variant of the EM algorithm, G. Tesauro et al. eds., Advances in Neural Information Processing Systems (NIPS) 7, MIT Press, Cambridge MA, pp. 545-552 (1995).

2

Ueda, N. and Nakano, R.: A new maximum likelihood training and application to probabilistic neural networks, Proc. of Int. Conf. on Artificial Neural Networks (ICANN)'95, pp. 497-502 (1995).

3

Ueda, N. and Nakano, R.: Deterministic annealing EM algorithm, Neural Networks , vol. 11, no. 2, pp. 271-282 (1998).