The windowEM algorithm

「windowEMアルゴリズム」に関するテクニカル・サマリー

問題提起
期待値最大化（EM）アルゴリズムは、潜在変数を含むモデルにおける最大尤度推定の標準的な手法である。しかし、大規模なデータセット（例：数十億のデータ点を含むゲノミクス・データ）の文脈では、標準的なEMアルゴリズムは、毎回の反復でデータセット全体を処理する必要があるため、計算上実用的ではない。加速のために（ミニバッチを用いた）確率的EMアルゴリズムも提案されているが、これらは、パラメータ空間が複雑な場合や、特定の潜在変数がデータ内に疎に存在する場合には、粗い、あるいはノイズの多いパラメータ推定値を生じさせることが多い。このノイズは、推定された分布（サイト周波数スペクトル（SFS）など）における人工的な「隆起（バンプ）」のようなアーティファクトを引き起こし、過学習に寄与する可能性がある。

手法：windowEMアルゴリズム
著者らは、データを$B$個のブロックに分割し、これらのブロックを円状に配置する、EMアルゴリズムの確率的バリアントであるwindowEMを提案している。このアルゴリズムは以下のメカニズムを通じて動作する：

1. ブロック分割： データは$B$個のブロック（$x_1, \dots, x_B$）に分割される。ブロックのサイズや分布は異なっていてもよく、独立であると仮定されない。
2. 逐次的更新： アルゴリズムは一連の更新を実行する。現在のブロック$k$の推定値は、前のブロック$k-1$からの推定値をシードとして用いて導出される。具体的には、現在のパラメータ推定値$\theta_t$を用いて、ブロック$b(t+1)$に対して標準的なEMアルゴリズムを1回実行することで、予備的な推定値$\psi_{t+1}$が得られる：
   $$\psi_{t+1} = f_{b(t+1)}(\theta_t) = \arg\max_{\theta'} Q_{b(t+1)}(\theta' | \theta_t)$$
3. ローリングウィンドウ平均： 単一ブロックの更新に内在するノイズに対処するため、アルゴリズムは推定値の「集団（ポピュレーション）」を保持する。あるステップにおける最終的な推定値$\theta_t$は、サイズ$w$のローリングウィンドウ内における、直近$w$個の予備的推定値の平均である：
   $$\theta_t = \frac{1}{w} \sum_{i=t-w+1}^{t} \psi_i$$
4. 円状反復： ブロックは循環的に配置される。$B$が有限であれば、アルゴリズムはブロックを繰り返し反復する（エポック）。$B = \infty$であれば、アルゴリズムは一連のユニークなブロックの無限列を進む。
5. 最終推定： $B$個の推定値の集団を平均することで、単一の点推定値を生成することができる。

著者らは、本アルゴリズムはPolyak-Ruppert平均化から着想を得ているものの、標準的な確率的勾配降下法のように勾配や更新を平均するのではなく、円状に配置されたデータに対する逐次的EMステップによって生成された「推定値」に対して平均を適用するという点で異なると指摘している。

主な理論的貢献
本論文は、有限の$B$および無限の$B$という2つのシナリオにおけるwindowEMの収束特性を調査している。

• 有限の $B$： 著者らは縮小写像理論（contraction theory）を用いている。更新関数が縮小写像であれば、ブロック推定値の列は収束することを確立している。主要な知見として、あるブロックに対して不動点が存在する場合、すべてのブロックに対して不動点が存在することが挙げられる。これらのブロック推定値の分布はウィンドウサイズ$w$に依存し、経験的に、ウィンドウサイズが大きいほどブロック推定値間の分散は小さくなる。
• 無限の $B$： $B = \infty$（またはブロックが繰り返されないほど十分に大きい場合）のケースでは、著者らは依存データに対するランダム反復理論を適用している。ブロック指数が大きくなるにつれて、推定値が不動点に収束するための条件を提示している。さらに、エルゴディック平均（ergodic average）の収束を保証する条件を確立している。
• 指数型分布族： 本解析は、指数型分布族に対して特に厳密である。著者らは、平均値パラメータ化において、更新関数はしばしば十分統計量の線形関数となることを示している。混合指数型分布族の場合、更新関数は推定されたクラス確率によって重み付けされた、観測統計量の線形関数であり続ける。
• 特殊なケース： $w=1$（平均化を行わない逐次的EMに帰着する）や、$w=B$（更新が全ブロックにわたる平均となり、線形性の仮定の下で標準的なEMの解と等価な不動点を与える可能性がある）といった特定の構成についても分析している。

実証結果
論文は、主に2つの例を用いてアルゴリズムを検証している：

1. 例証的な二項分布の例： 遺伝子頻度の推定問題。結果は、windowEMが最大尤度推定値（MLE）に急速に収束することを示している。推定値の分散は、ウィンドウサイズ$w$が増加するにつれて減少するが、大きな$w$では収束速度がわずかに低下する場合がある。
2. 単変量ガウス混合モデル： ガウス分布の混合モデルに対してテストが行われた。
   • $n=10^5$のデータ点と$B=10$のブロックを用いたシミュレーションにおいて、windowEMは標準的なEMよりも大幅に速く、完全データMLEに近い対数尤度を達成した。
   • 特筆すべきは、標準的なEMは最終的にwindowEMよりも高い対数尤度を達成したが、同時に完全データMLEをも超えてしまった（オーバーフィットを示唆している）点である。集団の推定値を平均することによって得られるwindowEMの推定値は、正則化として機能し、標準的なEMで見られるような「オーバーシュート」を起こすことなく、真の基礎分布により近い状態を維持しているように見えた。
   • 同様の傾向は、より小さい（$n=10^4$）およびより大きい（$n=10^6$）データセットでも観察され、windowEMは標準的なEMよりも早く、完全データMLEに近いところで安定化した。

意義と主張
著者らは、windowEMが、標準的なEMが実行不可能であり、かつ標準的な確率的EMがノイズが多すぎる大規模推論に対する実用的な解決策を提供すると主張している。主な意義は、ローリングウィンドウ内で推定値の集団を平均することによって誘発される正則化効果にある。

• 過学習の防止： ゲノミクス（SFS推定）およびガウス混合モデルに基づく経験的証拠に基づき、著者らはwindowEMが過学習を防ぐのに役立つと推測している。特定のブロックにおける稀なイベントによって人工的に増幅された推定値を平滑化することで、アルゴ更はより安定したパラメータ推定値を生成する。
• 理論的基盤： 本論文は、有限および無限のブロックシナリオの両方について、収束を検討した最初の理論的調査を提供しており、縮小理論およびランダム反復理論を活用している。
• 謙虚な姿勢： 著者らは、windowEMが必ずしも絶対的な最大尤度推定値に到達するわけではなく（標準的なEMよりも対数尤度が低くなることさえある）、結果として得られる推定値は、分散の減少により、より堅牢で統計的に意味のあるものになる可能性があることを指摘し、その主張は控えめである。彼らは、windowEMが大規模データ領域における安定性と速度のトレードオフを重視しており、標準的なEMに対して普遍的な優位性を主張しているのではない。