期待値最大化アルゴリズム

統計学において、期待値最大化（EM）アルゴリズムは、観測されていない潜在変数に依存する統計モデルにおけるパラメータの（局所）最尤推定値または最大事後確率（MAP）推定値を求める反復法である。^{[ 1 ]} EM反復では、パラメータの現在の推定値を用いて評価した対数尤度の期待値の関数を作成する期待値（E）ステップと、 Eステップで得られた期待対数尤度を最大化するパラメータを計算する最大化（M）ステップが交互に実行される。これらのパラメータ推定値は、次のEステップで潜在変数の分布を決定するために使用される。例えば、ガウス分布の混合を推定したり、重回帰問題を解いたりするために使用できる。 ^{[ 2 ]}

EM アルゴリズムは、1977 年のアーサー・デンプスター、ナン・レアード、ドナルド・ルービンによる古典的な論文で説明され、その名前が付けられました。^{[ 3 ]}彼らは、この方法は以前の著者によって「特別な状況で何度も提案されてきた」と指摘しました。最も初期のものの 1 つは、セドリック・スミスによる対立遺伝子頻度を推定するための遺伝子計数法です。^{[ 4 ]}もう 1 つは 1958 年にHO ハートレーによって、また 1977 年にハートレーとホッキングによって提案され、デンプスター、レアード、ルービンの論文の多くのアイデアはそこから派生しました。^{[ 5 ]}もう 1 つは 1977 年に SK ン、スリヤンバカム・クリシュナン、GJ マクラクランによって提案されました。 ^{[ 6 ]}ハートレーのアイデアは、任意のグループ化された離散分布に拡張できます。指数型分布族に対する EM 法の非常に詳細な扱いは、ロルフ・サンドバーグがペル・マルティン＝レーフとアンダース・マルティン＝レーフとの共同研究の後、彼の学位論文といくつかの論文で発表し^た。 [ 7 ] [ ^{8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] 1977年のデンプスター・レアード・ルービン論文は、この方法を一般化し、より広いクラスの問題に対する収束解析の概要を示した。デンプスター・レアード・ルービン論文は、EM 法を}統計解析の重要なツールとして確立した。メンとファン・ダイク (1997) も参照のこと。

デンプスター・レアード・ルービンアルゴリズムの収束解析は欠陥があり、1983年にCFジェフ・ウーによって正しい収束解析が発表された。 ^{[ 15 ]} ウーの証明は、デンプスター・レアード・ルービンが主張したように、EM法が指数族の外側でも収束することを示した。^{[ 15 ]}

EMアルゴリズムは、方程式を直接解くことができない場合に、統計モデルの（局所）最尤パラメータを求めるために使用されます。通常、これらのモデルには、未知のパラメータと既知のデータ観測値に加えて、潜在変数が含まれます。つまり、データに欠損値が存在するか、あるいは、さらに観測されていないデータ点が存在すると仮定することで、モデルをより単純に定式化できます。たとえば、混合モデルは、各観測データ点に対応する観測されていないデータ点、つまり潜在変数があり、各データ点が属する混合成分を指定すると仮定することで、より単純に記述できます。

最尤解を求めるには、通常、尤度関数をすべての未知数、パラメータ、潜在変数に関して微分し、得られた方程式を同時に解く必要があります。潜在変数を含む統計モデルでは、これは通常不可能です。その代わりに、結果として得られるのは、パラメータの解には潜在変数の値が必要であり、その逆もまた然りであるような、相互に関連し合う方程式のセットですが、一方の方程式のセットを他方の方程式のセットに代入すると、解けない方程式が生成されます。

EM アルゴリズムは、これら 2 つの方程式を数値的に解く方法があるという観察から出発します。2 つの未知数の 1 つのセットに対して任意の値を選択し、それらを使用して 2 番目のセットを推定し、次にこれらの新しい値を使用して最初のセットのより良い推定値を見つけ、結果として得られる値が両方とも固定点に収束するまで 2 つを交互に繰り返します。これが機能することは明らかではありませんが、この文脈では証明できます。さらに、その点で尤度の導関数が (任意に) ゼロに近づくことが証明でき、これはその点が局所最大値または鞍点であることを意味します。^{[ 15 ]}一般に、複数の最大値が発生する可能性があり、グローバル最大値が見つかる保証はありません。一部の尤度には特異点、つまり意味のない最大値もあります。たとえば、混合モデルで EM によって見つかる可能性のある解の 1 つは、コンポーネントの 1 つを分散ゼロに設定し、同じコンポーネントの平均パラメータをデータ ポイントの 1 つに等しくすることです。

EM反復によって観測データ（すなわち周辺）尤度関数は増加するものの、そのシーケンスが最尤推定量に収束するという保証はない。多峰性分布の場合、これはEMアルゴリズムが初期値によっては観測データ尤度関数の局所最大値に収束する可能性があることを意味する。局所最大値から脱却するための様々なヒューリスティックまたはメタヒューリスティックなアプローチが存在する。例えば、ランダム再起動ヒルクライミング（複数の異なるランダムな初期推定値から開始する）などである。$\displaystyle {\boldsymbol {\theta }}^{(t)}}$⁠ )、またはシミュレーテッドアニーリング法を適用する。

EM は、尤度が指数族である場合に特に有用です。包括的な扱いについては、Sundberg (2019、第 8 章) を参照してください。^{[ 16 ]} E ステップは十分統計量の期待値の合計になり、M ステップは線形関数の最大化を伴います。このような場合、通常は、Sundberg の公式^{[ 17 ]} ( Per Martin-LöfとAnders Martin-Löfの未発表の結果に基づいて Rolf Sundberg によって証明および発表)を使用して、各ステップの閉形式の式の更新を導出できます。 ^{[ 8 ] [ 9 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]}

EM法は、デンプスター、レアード、ルービンによる原著論文において、ベイズ推論のための最大事後確率（MAP）推定値を計算するように修正された。

最尤推定値を求めるには、勾配降下法、共役勾配法、ガウス・ニュートン法の変種など、他の方法も存在する。EMアルゴリズムとは異なり、これらの方法では通常、尤度関数の1階微分および/または2階微分の評価が必要となる。

期待値最大化法は、${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$直接改善するのではなく${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$ここで、前者の改善は後者の改善を意味することが示されている。^{[ 18 ]}

いかなる場合でも${\displaystyle \mathbf {Z} }$非ゼロの確率で${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}$⁠、私たちは書くことができます $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}).}$$ 未知データの取りうる値に対する期待値を取る${\displaystyle \mathbf {Z} }$現在のパラメータ推定値の下で$\displaystyle \theta ^{(t)}}$両辺に${\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}$そして、合計（または積分）する${\displaystyle \mathbf {Z} }$左辺は定数の期待値なので、次のようになります。 $${\displaystyle {\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)}),\end{aligned}}}$$ どこ${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$は、それが置き換える負の和によって定義されます。この最後の式は、すべての値に対して成り立ちます。${\displaystyle {\boldsymbol {\theta }}}$含む${\displaystyle {\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}}$、 $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),}$$ そして、この最後の式を前の式から引くと、 $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$$ しかし、ギブスの不等式によれば、${\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})}$したがって、 $${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).}$$ 言葉で言うと、選択する${\displaystyle {\boldsymbol {\theta }}}$改善する${\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}$原因${\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}$少なくとも同程度には改善する。

EMアルゴリズムは、2つの交互の最大化ステップ、すなわち座標降下法の例として見なすことができる。^{[ 19 ] [ 20 ]}次の関数を考えてみよう。 $${\displaystyle F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),}$$ ここで、qは未観測データzに対する任意の確率分布であり、H ( q )は分布qのエントロピーである。この関数は次のように記述できる。 $${\displaystyle F(q,\theta )=-D_{\mathrm {KL} }{\big (}q\parallel p_{Z\mid X}(\cdot \mid x;\theta ){\big )}+\log L(\theta ;x),}$$ どこ ${\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )}$これは、観測されたデータが与えられた場合の、観測されていないデータの条件付き分布である。${\displaystyle x}$そして${\displaystyle D_{KL}}$はカルバック・ライブラー情報量です。

EMアルゴリズムの手順は、次のように考えることができます。

• 期待されるステップ：選択${\displaystyle q}$最大化するために${\displaystyle F}$⁠ :$${\displaystyle q^{(t)}=\mathop {\arg \max } _{q}F{\left(q,\theta ^{(t)}\right)}}$$
• 最大化ステップ：選択${\displaystyle \theta }$最大化するために${\displaystyle F}$⁠ :$${\displaystyle \theta ^{(t+1)}=\mathop {\arg \max } _{\theta }F{\left(q^{(t)},\theta \right)}}$$

• EMは混合モデルのパラメータ推定によく使用され、^{[ 21 ] [ 22 ]}特に量的遺伝学でよく使用されます。^{[ 23 ]}
• 心理測定学において、EMは項目反応理論モデルの項目パラメータと潜在能力を推定するための重要なツールである。
• 欠損データへの対応や未確認変数の観測が可能なEM（進化モデル）は、ポートフォリオの価格設定やリスク管理において有用なツールになりつつある。
• EMアルゴリズム（およびその高速版である順序付き部分集合期待値最大化法）は、医用画像再構成、特に陽電子放出断層撮影（PET）、単光子放出コンピュータ断層撮影（SPECT）、およびX線コンピュータ断層撮影（CT）において広く用いられています。EMアルゴリズムのその他の高速版については、下記を参照してください。
• 構造工学では、期待値最大化を用いた構造同定（STRIDE）^{[ 24 ]}アルゴリズムは、センサーデータを使用して構造システムの固有振動特性を同定するための出力のみの方法です（運用モーダル解析を参照）。
• EMアルゴリズムはデータクラスタリングにも使用されます。自然言語処理においては、隠れマルコフモデルのためのバウム・ウェルチアルゴリズムと、確率的文脈自由文法の教師なし誘導のためのインサイド・アウトサイドアルゴリズムという、このアルゴリズムの代表的な例が挙げられます。
• 取引間の待ち時間の分析において、EMアルゴリズムは非常に有用であることが証明されている。^{[ 25 ]}

オンライン状態推定には通常カルマンフィルタが用いられ、オフラインまたはバッチ状態推定には最小分散平滑化器が用いられる。しかし、これらの最小分散解法では状態空間モデルパラメータの推定値が必要となる。状態推定とパラメータ推定を同時に行う問題にはEMアルゴリズムを用いることができる。

フィルタリングと平滑化のEMアルゴリズムは、この2段階の手順を繰り返すことによって得られます。

Eステップ

現在のパラメータ推定値を用いて設計されたカルマンフィルタまたは最小分散スムーザーを動作させ、更新された状態推定値を取得します。

Mステップ

フィルタリングまたは平滑化された状態推定値を最尤推定計算に使用して、更新されたパラメータ推定値を取得する。

カルマンフィルタまたは最小分散平滑化器が、加法性白色雑音を含む単入力単出力システムの測定値に対して動作すると仮定します。更新された測定雑音分散推定値は、最尤計算 から得られます。$${\displaystyle {\widehat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\widehat {x}}_{k})}^{2},}$$

どこ${\displaystyle {\widehat {x}}_{k}}$スカラー出力推定値は、N 個のスカラー測定値からフィルターまたはスムーザーによって計算されます。${\displaystyle z_{k}}$上記の更新は、ポアソン測定ノイズ強度の更新にも適用できます。同様に、1次自己回帰プロセスの場合、更新されたプロセスノイズ分散推定値は次のように計算できます。 $${\displaystyle {\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},}$$

どこ${\displaystyle {\widehat {x}}_{k}}$そして${\displaystyle {\widehat {x}}_{k+1}}$は、フィルタまたはスムーザーによって計算されるスカラー状態推定値です。更新されたモデル係数推定値は、次の方法で取得されます。 $${\displaystyle {\widehat {F}}={\frac {\sum \limits _{k=1}^{N}{\left({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k}\right)}^{2}}{\sum \limits _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}$$

上記のようなパラメータ推定値の収束についてはよく研究されている。^{[ 26 ] [ 27 ] [ 28 ] [ 29 ]}

EMアルゴリズムの収束が遅い場合があるため、その収束を加速するための方法として、共役勾配法や修正ニュートン法（ニュートン・ラフソン法）を用いる方法など、いくつかの方法が提案されている。 ^{[ 30 ]}また、EMは制約付き推定法と併用することもできる。

パラメータ拡張期待値最大化（PX-EM）アルゴリズムは、「共分散調整を使用してMステップの分析を修正し、補完された完全データで捉えられた追加情報を活用する」ことで、しばしば高速化を実現する。^{[ 31 ]}

期待条件付き最大化 (ECM)は、各 M ステップを、他のパラメータが固定されたままであることを条件として各パラメータθ _iを個別に最大化する条件付き最大化 (CM) ステップのシーケンスに置き換えます。^{[ 32 ]}それ自体は、期待条件付き最大化 (ECME)アルゴリズムに拡張できます。^{[ 33 ]}

このアイデアは、一般化期待値最大化（GEM）アルゴリズムでさらに拡張され、最大化-最大化手順のセクションで説明されているように、E ステップと M ステップの両方で目的関数Fの増加のみが求められます。^{[ 19 ]} GEM は分散環境でさらに開発され、有望な結果を示しています。^{[ 34 ]}

EMアルゴリズムはMM（文脈に応じてMajorize/MinimizeまたはMinorize/Maximize）アルゴリズムのサブクラスとみなすことも可能であり^{[ 35 ]}、より一般的なケースで開発されたあらゆる仕組みを使用できる。

EM は部分的に非ベイズ的な最尤法です。最終結果は、潜在変数の確率分布(ベイズ的スタイル) とθの点推定値(最尤推定値または事後モード) を与えます。θと潜在変数の確率分布を与える完全なベイズ版が必要になる場合があります。推論に対するベイズ的アプローチは、 θ を別の潜在変数として扱うだけです。このパラダイムでは、E ステップと M ステップの区別がなくなります。上記のように因数分解された Q 近似 (変分ベイズ) を使用する場合、解法は各潜在変数 ( θを含む) を反復して、一度に 1 つずつ最適化できます。この場合、反復ごとにkステップが必要で、kは潜在変数の数です。グラフィカル モデルの場合、各変数の新しいQはマルコフ ブランケットのみに依存するため、効率的な推論のためにローカルメッセージ パッシングを使用できます。

情報幾何学において、EステップとMステップは、e接続とm接続と呼ばれる双対アフィン接続による射影として解釈されます。カルバック・ライブラー情報量も、これらの観点から理解することができます。

EM は通常、必ずしも大域的最適解ではなく局所的最適解に収束し、収束速度には一般的に上限がありません。高次元では任意に悪くなる可能性があり、局所的最適解が指数関数的に増加する可能性があります。したがって、特に高次元の設定では、学習を保証する代替手法が必要です。一貫性の保証がより優れた EM の代替手法が存在し、これらはモーメントベースのアプローチ^{[ 39 ]}またはいわゆるスペクトル技術^{[ 40 ] [ 41 ]}と呼ばれています。確率モデルのパラメータを学習するためのモーメントベースのアプローチは、局所的最適解に陥る問題に悩まされることが多い EM とは異なり、特定の条件下で大域的収束などの保証を得ています。混合モデル、HMM など、多くの重要なモデルに対して学習の保証付きアルゴリズムを導出できます。これらのスペクトル法では、偽の局所的最適解は発生せず、いくつかの正則条件の下で真のパラメータを一貫して推定できます。

• 混合分布
• 化合物分布
• 密度推定
• 主成分分析
• 全吸収分光法
• EMアルゴリズムは、主化最小化（MM）アルゴリズムの特殊なケースと見なすことができる。^{[ 42 ]}

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005).数理統計学入門. Upper Saddle River, NJ: Pearson Prentice Hall. pp. 359–364 . 
• デラート、フランク（2002年2月）。期待値最大化アルゴリズム（PDF）（技術報告書番号GIT-GVU-02-20）。ジョージア工科大学コンピューティング学部。下限値最大化の観点からEMアルゴリズムをより分かりやすく説明する。
• ビショップ、クリストファー・M. (2006).パターン認識と機械学習. Springer. ISBN 978-0-387-31073-2。
• Gupta, MR; Chen, Y. (2010). "EMアルゴリズムの理論と使用". Foundations and Trends in Signal Processing . 4 (3): 223– 296. CiteSeerX 10.1.1.219.6830 . doi : 10.1561/2000000034 . EMアルゴリズムに関する分かりやすく書かれた短い書籍で、GMM、HMM、およびディリクレ分布に対するEMアルゴリズムの詳細な導出も含まれています。
• Bilmes, Jeff (1997). EMアルゴリズムの簡単なチュートリアルと、ガウス混合モデルおよび隠れマルコフモデルのパラメータ推定への応用（技術報告書 TR-97-021）。国際コンピュータ科学研究所。本書には、ガウス混合モデルおよびガウス混合隠れマルコフモデルに対するEM方程式の簡略化された導出が含まれています。
• マクラクラン、ジェフリー・J.、クリシュナン、スリヤンバカム（2008）。EMアルゴリズムとその拡張（第2 版）。ホーボーケン：ワイリー。ISBN 978-0-471-20170-0。

• SOCRの活動とアプレットには、 EMアルゴリズムと混合モデルを組み合わせた1次元、2次元、3次元の様々なデモンストレーションが用意されています。これらのアプレットと活動を通して、多様な環境におけるパラメータ推定のためのEMアルゴリズムの特性を実証的に学ぶことができます。
• C++ (GPL)におけるクラス階層（ガウス混合モデルを含む）
• David JC MacKay著のオンライン教科書「情報理論、推論、学習アルゴリズム」には、ソフトk平均法を用いたクラスタリングなど、EMアルゴリズムの簡単な例が含まれており、バージョン7.2（第4版）の第33.7章で説明されているEMアルゴリズムの変分的な観点が強調されています。
• MJ Beal 著のVariational Algorithms for Approximate Bayesian Inference には、EM と Variational Bayesian EM の比較、および Variational Bayesian HMM を含むいくつかのモデルの導出 (章) が含まれています。
• 期待値最大化アルゴリズム：簡単なチュートリアル、Sean BormanによるEMアルゴリズムの自己完結的な導出。
• EM アルゴリズム、Xiaojin Zhu 著。
• EMアルゴリズムとその派生アルゴリズム：アレクシス・ロッシュによる非公式チュートリアル。EMアルゴリズムとその多くの興味深い派生アルゴリズムについて、簡潔かつ非常に分かりやすく解説しています。