Expectation-Maximization Algorithm/zh

    From Marovi AI
    This page is a translated version of the page Expectation-Maximization Algorithm and the translation is 100% complete.
    Other languages:
    Article
    Topic area Machine Learning
    Prerequisites Maximum Likelihood Estimation, Latent Variable Models, Kullback-Leibler Divergence


    期望-最大化（EM）是一種迭代算法，用於在含有未觀測潛變量的統計模型中求解參數的最大似然估計或最大後驗（MAP）估計。每一輪迭代交替執行兩步：在當前潛變量後驗下計算數據的期望對數似然（E 步），以及關於參數最大化該期望（M 步）。EM 是擬合混合模型、隱馬爾可夫模型、因子分析模型以及許多其他潛變量模型的標準工具，也是現代變分推斷理論的基礎。

    概述

    許多具有實際意義的模型都假設每個觀測數據點 $ x $ 是與一個從不直接觀測的潛變量 $ z $ 聯合生成的。例子包括高斯混合模型中的聚類指派、隱馬爾可夫模型中的隱狀態序列、Latent Dirichlet Allocation 中某個詞的主題，以及因子分析中的共享因子。邊際似然

    $ p(x \mid \theta) = \sum_{z} p(x, z \mid \theta) \quad \text{or} \quad \int p(x, z \mid \theta)\, dz $

    通常沒有可處理的閉式表達，而直接對 $ \log p(x \mid \theta) $ 進行梯度上升又很不方便，因為求和或積分被放在對數函數內部。

    EM 通過引入後驗 $ p(z \mid x, \theta) $ 作為耦合分布來繞開這一困難。在每一輪迭代中，算法用當前參數計算（或界定）該後驗，然後優化一個替代目標，在其中潛變量實際上已被「填補」進去。Dempster、Laird 與 Rubin 在 1977 年給出了該方法的命名和一般化表述，但若干特殊情形早在數十年前已出現於遺傳學、信號處理和聚類等文獻中。

    EM 之所以具有吸引力，是因為每次迭代都保證邊際對數似然不會減小，M 步通常可歸結為常見的完全觀測最大似然問題，而且算法既不需要學習率也不需要步長。它是 Majorization-Minimization 類方法的典範，也是現代 Variational Inference 的直接前身。

    直觀理解

    EM 可以通過一個簡單的「雞生蛋、蛋生雞」的觀察來理解。若潛變量 $ z $ 已知，那麼對 $ \theta $ 的擬合就退化為完整數據 $ (x, z) $ 上的標準 Maximum Likelihood Estimation。反過來，若 $ \theta $ 已知，則後驗 $ p(z \mid x, \theta) $ 會告訴我們潛變量最可能是什麼。兩者在一開始都不可得，因此 EM 採用自舉的方式：用當前參數對潛變量做一個軟的猜測，再像該猜測為真那樣重新擬合參數，如此反覆迭代。

    「軟」這一限定詞很關鍵。與k 均值這類經典的硬指派啟發式不同，EM 並不把 $ z $ 鎖定為單一取值，而是計算潛變量上的一個分布，並以該分布對 M 步進行加權。正是這種軟指派使得邊際對數似然非遞減，也使 EM 區別於在硬指派目標上做坐標下降的方法。

    形式化表述

    證據下界

    設 $ q(z) $ 是潛變量上的任意一個分布。由延森不等式可得證據下界（ELBO）：

    $ {\displaystyle \log p(x \mid \theta) \;\geq\; \mathbb{E}_{q(z)}\!\left[\log p(x, z \mid \theta)\right] - \mathbb{E}_{q(z)}\!\left[\log q(z)\right] \;\equiv\; \mathcal{L}(q, \theta).} $

    邊際對數似然與 ELBO 之間的差正好是 $ q(z) $ 到真實後驗之間的 Kullback-Leibler Divergence：

    $ {\displaystyle \log p(x \mid \theta) - \mathcal{L}(q, \theta) = \mathrm{KL}\!\left(q(z) \,\Vert\, p(z \mid x, \theta)\right) \geq 0.} $

    於是 EM 就是對 $ \mathcal{L} $ 的坐標上升：交替地在固定 $ \theta $ 時關於 $ q $ 最大化，以及在固定 $ q $ 時關於 $ \theta $ 最大化。

    E 步

    將 $ \theta $ 固定在當前估計 $ \theta^{(t)} $ 時，ELBO 在 $ q $ 等於後驗時取得最大：

    $ q^{(t+1)}(z) = p(z \mid x, \theta^{(t)}). $

    這使 KL 項歸零並收緊下界。等價地，E 步計算完整數據期望對數似然，通常記作

    $ Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{p(z \mid x, \theta^{(t)})}\!\left[\log p(x, z \mid \theta)\right]. $

    在實際操作中，E 步歸結為計算 $ z $ 在後驗下的充分統計量——例如混合模型中的責任度 $ r_{ik} = p(z_i = k \mid x_i, \theta^{(t)}) $，或在隱馬爾可夫模型中由前向-後向遞歸計算的平滑狀態概率。

    M 步

    在固定 $ q^{(t+1)} $ 的情況下，ELBO 僅相差一個常數即等於完整數據期望對數似然，於是 M 步求解

    $ {\displaystyle \theta^{(t+1)} = \arg\max_{\theta} \; Q(\theta \mid \theta^{(t)}).} $

    由於 $ q^{(t+1)} $ 不依賴於 $ \theta $，潛變量相當於固定權重，整個優化通常可歸約為常見的完全觀測最大似然問題。對指數族而言，M 步往往具有閉式解：加權均值、加權協方差和加權多項式計數分別替代其無權重版本。

    單調改進

    組合後的更新滿足

    $ \log p(x \mid \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t+1)}) \;\geq\; \mathcal{L}(q^{(t+1)}, \theta^{(t)}) \;=\; \log p(x \mid \theta^{(t)}), $

    因此每一迭代中邊際對數似然都不會減小。在適度的正則性條件下，迭代序列會收斂到邊際似然的某個駐點，但未必是全局最優。

    經典示例：高斯混合模型

    對於具有 $ K $ 個分量、參數 $ \theta = \{\pi_k, \mu_k, \Sigma_k\} $ 以及潛在指派 $ z_i \in \{1, \ldots, K\} $ 的高斯混合模型，EM 的更新規則形式格外清晰。

    E 步計算每個分量對每個數據點的責任度：

    $ r_{ik} = \frac{\pi_k \, \mathcal{N}(x_i \mid \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \, \mathcal{N}(x_i \mid \mu_j, \Sigma_j)}. $

    M 步則把這些責任度作為軟計數使用：

    $ {\displaystyle N_k = \sum_{i=1}^{N} r_{ik}, \quad \pi_k^{\text{new}} = \frac{N_k}{N}, \quad \mu_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\, x_i, \quad \Sigma_k^{\text{new}} = \frac{1}{N_k}\sum_{i=1}^{N} r_{ik}\,(x_i - \mu_k^{\text{new}})(x_i - \mu_k^{\text{new}})^{\!\top}.} $

    當每個責任度都退化為一個獨熱向量（例如協方差收縮為各向同性的 $ \sigma^2 I $ 且 $ \sigma \to 0 $）時，該算法恰好退化為 k 均值——因此 k 均值就是球形高斯混合下 EM 的硬指派極限。

    變體與推廣

    對基本方案的若干鬆弛使其在 E 步或 M 步難以處理時仍然可用。

    • 廣義 EM（GEM）：M 步被任何能提高（而不必最大化） $ Q(\theta \mid \theta^{(t)}) $ 的更新所取代，仍然保留邊際對數似然的單調改進性質。
    • 期望-條件最大化（ECM）：將 M 步分解為關於若干互不相交參數塊的條件最大化序列，適用於聯合最大化困難但條件最大化容易的場合。
    • 隨機 EM 與蒙特卡洛 EM：當後驗 $ p(z \mid x, \theta) $ 難以處理時，用採樣代替 E 步。隨機 EM 僅抽取一個樣本；蒙特卡洛 EM 則用樣本均值近似期望。
    • 變分 EM：E 步把 $ q $ 限制在一個可處理的分布族 $ \mathcal{Q} $ 中，並在該族內最小化到真實後驗的KL 散度。這樣得到的邊際對數似然只是被界定但未必被取到，是以精確性換取可處理性。它正是經典 EM 與現代變分方法之間的橋梁。
    • 在線與增量 EM：在小批量數據上以指數加權移動平均的方式更新充分統計量，從而把 EM 擴展到流式數據或大規模數據集。
    • 硬 EM：每個 E 步用其後驗眾數處的點質量替代後驗。這會失去單調改進的保證，但在追求速度或後驗高度集中時仍然有時被採用。

    收斂性質

    EM 是一種局部搜索算法。其單調改進性質保證邊際對數似然序列收斂到某個極限；在標準正則條件下，參數迭代會收斂到某個駐點——通常是局部極大值，但也可能是鞍點或參數空間的邊界點。收斂速度一般是線性的，由 Dempster、Laird 與 Rubin 的「缺失信息原理」所支配：潛變量後驗越接近點質量，EM 的收斂就越快。當缺失信息所占比例較大時，收斂會非常緩慢，因此有時會使用擬牛頓加速方法（Aitken、SQUAREM、參數擴展的 EM）。

    對初始化的敏感性是一個眾所周知的實際問題。對於混合模型，常用策略包括多次隨機重啟、用 k 均值進行初始化，以及確定性退火——後者先以高度平滑的目標開始，再逐步使之變得尖銳。

    關聯

    EM 是 Majorization-Minimization 族的一個特例：每次迭代都構造一個切線下界（即在當前參數處的 ELBO）並最大化該下界。這一視角把 EM 與鄰近方法、最優化中的 MM 算法以及關於非凸問題下界最大化的近期文獻統一了起來。

    EM 同樣是 Variational Inference 與變分自編碼器在概念上的祖先。EM 在 E 步精確求解後驗，而變分方法則用一個可處理的近似來替代；EM 在 M 步優化參數，而攤銷變分推斷則學習一個推斷網絡，從數據直接預測變分後驗。最初作為分析 EM 的工具而提出的 ELBO，如今已成為概率深度生成模型的核心訓練目標。

    在概率主成分分析（PPCA）、因子分析和獨立分量分析中，EM 都是替代直接特徵分解或不動點迭代的可擴展方案。在隱馬爾可夫模型中，EM 算法特化為Baum-Welch 算法，其中 E 步對應前向-後向遞歸，M 步對應轉移概率與發射概率的閉式重新估計。

    局限性

    EM 雖然強大，但並非萬能。其主要的實際局限包括：

    • 局部最優：邊際似然通常是非凸的，EM 只能收斂到一個駐點。尤其在分量分離度差的混合模型中，會存在大量局部極大值和鞍點。
    • 高缺失信息下的緩慢收斂：當後驗較為彌散時，M 步只能產生很小的參數變化，算法可能需要非常多的迭代次數。
    • 奇異性：在協方差不受約束的高斯混合中，似然是無界的——某個分量可能塌縮到單個數據點上並使似然趨於無窮。實際實現通常通過對協方差正則化或施加先驗來避免這種病態。
    • E 步難以處理：對於具有高維離散潛變量或潛變量耦合很強的複雜模型，精確計算後驗不可行，需要使用變分或蒙特卡洛近似。
    • 缺乏不確定性量化：EM 僅給出 $ \theta $ 的點估計，自身並不提供關於參數的後驗分布。引入先驗並使用 MAP-EM 可部分緩解這一點；要做完全的貝葉斯處理則需藉助變分貝葉斯或 MCMC。

    這些局限性也正是現代概率機器學習中更廣闊的近似推斷技術格局的內在動因。

    另見

    參考文獻

    • Dempster, A. P., Laird, N. M. 與 Rubin, D. B. (1977). "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society, Series B, 39(1), 1-38.
    • Wu, C. F. J. (1983). "On the Convergence Properties of the EM Algorithm". The Annals of Statistics, 11(1), 95-103.
    • McLachlan, G. J. 與 Krishnan, T. (2008). The EM Algorithm and Extensions（第 2 版）。Wiley。
    • Neal, R. M. 與 Hinton, G. E. (1998). "A View of the EM Algorithm that Justifies Incremental, Sparse, and Other Variants"。收錄於 Learning in Graphical Models，M. I. Jordan（編），Kluwer，355-368。
    • Bishop, C. M. (2006). Pattern Recognition and Machine Learning。Springer，第 9 章。
    • Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective。MIT Press，第 11 章。
    • Baum, L. E., Petrie, T., Soules, G. 與 Weiss, N. (1970). "A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains". The Annals of Mathematical Statistics, 41(1), 164-171.


    Retrieved from "https://marovi.ai/index.php?title=Expectation-Maximization_Algorithm/zh&oldid=32477"