オンライン EMアルゴリズム

ずっとEMアルゴリズムの部分がボトルネックになっていて，システムの遅さに悩んでいたのですが．．．UNIXのgdb，ddd，profileといったツールを使って調べてみると，どうもEMアルゴリズムの縦ループ（各パラメータのアップデート．Eステップ→Mステップ→Eステップ．．．）ではなく，各パラメータのアップデート自体に時間がかかっているらしいことがはっきりしました．僕のシステムの場合は，各パラメータのアップデートは，「混合分布の数×入力サンプル数の数」に比例します．だからどっちかを減らせば良いのですが，分布の数を推定したいのだから分布数を勝手に減らすことはできない．ならば入力サンプル数を減らすしか無いのですが，例えばサンプルからさらに一定量のランダムサンプリングをして入力させても，しょせん分布の数が増えたらランダムサンプリング後のサンプルの数は増えるので，根本的な解決になりません．もし，縦ループが問題だったらComponent-wise EMアルゴリズムでもやってみようかと思ったのですが，横ループが問題なんだったら，例えばオンラインEMアルゴリズムでいけるんちゃいますかねぇ．

要は，例えば入力サンプルが1000個あったら，適当に分ける．200個と500個と300個でも良い．そして，200個のサンプルを使ってパラメータをアップデートする．これで既に十分な収束が見られれば終了．残りのデータは入力しなくてすむ．収束してなければ，次に500個のサンプルでアップデート．以下同文．

実際にはもっと細かく分ければ，入力サンプルを全部使う前に収束してくれるんじゃないでしょうかねぇ．これは明日，実装してみます．