最大期望演算法(Expectation-Maximization algorithm，EM)
- 最大期望演算法(Expectation-Maximization algorithm，EM)
- 一、EM演算法的廣義步驟
- 二、先寫出EM的公式
- 三、其收斂性的證明
- 四、公式推導方法1
- 4.1 E-M步驟公式
- 4.2 推導程序
- 五、公式推導方法2（涉及Jensen不等式）
- 5.1 Jensen不等式
- 5.2 關于E-M演算法的理解
- 5.3 推導程序
- 六、廣義EM演算法
- 廣義EM步驟：
- 七、EM演算法的改進
??最大期望演算法，也被譯作最大化演算法（Minorize-Maxization,MM）,是在概率模型中尋找引數最大似然估計或者最大后驗估計的演算法，其中概率模型依賴于無法觀測的隱性變數，
??最大期望演算法就是E-step和M-step交替進行計算，直至滿足收斂條件，所以它是一種迭代演算法，
??EM演算法適用場景：當資料有缺失值時，即資料不完整時，還有很多機器學習模型的求解經常用到Em，比如GMM（高斯混合模型）、HMM（隱馬爾科夫模型）等等，
一、EM演算法的廣義步驟
??E-step:利用可用的資料來估算（猜測）潛在變數的值；
??M-step：根據E步驟中生成的估計值，使用完整的資料更新引數，
二、先寫出EM的公式
??這里以最大似然估計作為準則：
\[ {\hat \theta _{MLE}} = \arg \max \log P(X|\theta ) \]??EM公式
\[{\theta ^{(t + 1)}} = \arg \mathop {\max }\limits_\theta \int_Z {\log } P(X,Z|\theta )P(Z|X,{\theta ^{(t)}})dZ \]??\(\int_Z {\log } P(X,Z|\theta )P(Z|X,{\theta ^{(t)}})dZ\)也可以寫作\({E_{Z|X,{\theta ^{(t)}}}}[\log P(X,Z|\theta )]\)或者\(\sum\limits_Z {\log P(X,Z|\theta )P(Z|X,{\theta ^{(t)}})}\)
三、其收斂性的證明
??此處的證明并不是非常嚴格的證明，要證明其收斂，就是要證明當\({\theta ^{(t)}} \to {\theta ^{(t + 1)}}\)，\(P(X|{\theta ^{(t)}}) \to P(X|{\theta ^{(t + 1)}})\)時\(P(X|{\theta ^{(t)}}) \le P(X|{\theta ^{(t + 1)}})\)，證明程序如下：
??證明：
\[\log P(X|\theta ) = \log P(X,Z|\theta ) - \log P(Z|X,\theta ) \]??等式兩邊關于\({Z|X,{\theta ^{(t)}}}\)分布同時求期望：
??左邊:
\[\begin{array}{l} {E_{Z|X,{\theta ^{(t)}}}}[\log P(X|\theta )]\\ = \int_Z {\log } P(X|\theta )P(Z|X,{\theta ^{(t)}})dZ\\ = \log P(X|\theta )\int_Z {P(Z|X,{\theta ^{(t)}})} dZ\\ = \log P(X|\theta ) \end{array} \]??右邊：
\[\begin{array}{l} {E_{Z|X,{\theta ^{(t)}}}}\left[ {\log P(X,Z|\theta ) - \log P(Z|X,\theta )} \right]\\ = \int_Z {\log P(X,Z|\theta )P(Z|X,{\theta ^{(t)}})dZ - } \int_Z {\log P(Z|X,\theta )P(Z|X,{\theta ^{(t)}})dZ} \end{array} \]??令\(Q（\theta ,{\theta ^{(t)}}) = \int_Z {\log P(X,Z|\theta )P(Z|X,{\theta ^{(t)}})dZ}\)，\(H(\theta ,{\theta ^{(t)}}) = \int_Z {\log P(Z|X,\theta )P(Z|X,{\theta ^{(t)}})dZ}\)，
??則
\[{E_{Z|X,{\theta ^{(t)}}}}\left[ {\log P(X,Z|\theta ) - \log P(Z|X,\theta )} \right] = Q(\theta ,{\theta ^{(t)}}) - H(\theta ,{\theta ^{(t)}}) \]??由EM的演算法公式可得：（因為就是要求滿足要求的最大\(\theta\)作為\(\theta ^{(t+1)}\)）
\[Q({\theta ^{(t + 1)}},{\theta ^{(t)}}) \ge Q(\theta ,{\theta ^{(t)}}) \]??也即：（\(\theta\)取\(\theta ^{(t)}\)時）
\[Q({\theta ^{(t + 1)}},{\theta ^{(t)}}) \ge Q({\theta ^{(t)}},{\theta ^{(t)}}) \]??對于\(H(\theta ,{\theta ^{(t)}})\)：
\[\begin{array}{l} H({\theta ^{(t + 1)}},{\theta ^{(t)}}) - H({\theta ^{(t)}},{\theta ^{(t)}})\\ = \int_Z {\log P(Z|X,{\theta ^{(t + 1)}})} P(Z|X,{\theta ^{(t)}})dZ - \int_Z {\log P(Z|X,{\theta ^t})} P(Z|X,{\theta ^{(t)}})dZ\\ = \int_Z {P(Z|X,{\theta ^{(t)}})} \log \frac{{P(Z|X,{\theta ^{(t + 1)}})}}{{P(Z|X,{\theta ^t})}}dZ\\ = - KL(P(Z|X,{\theta ^{(t)}})||P(Z|X,{\theta ^{(t + 1)}}))\\ \le 0 \end{array} \]??也即\(H({\theta ^{(t + 1)}},{\theta ^{(t)}}) \le H({\theta ^{(t)}},{\theta ^{(t)}})\)
??綜上，\(P(X|{\theta ^{(t)}}) \le P(X|{\theta ^{(t + 1)}})\)，證畢，
四、公式推導方法1
說明下資料：
??X: observed data ??\(X = \{ {x_1},{x_2}, \cdots {x_N}\}\)
??Z: unovserved data(latent data) ?? \(Z = \{ {z_i}\} _{i = 1}^K\)
??(X,Z): complete data
??\(\theta\): parameter
4.1 E-M步驟公式
??E-step:
\[P(Z|X,{\theta ^{(t)}}) \to {E_{Z|X,{\theta ^{(t)}}}}[\log P(X,Z|\theta )] \]??M-step:
\[{\theta ^{(t + 1)}} = \arg \mathop {\max }\limits_\theta {E_{Z|X,{\theta ^{(t)}}}}[\log P(X,Z|\theta )] \]4.2 推導程序
\[\log P(X|\theta ) = \log (X,Z|\theta ) - \log (Z|X,\theta ) \]??等價代換，引入分布\(q(Z)\):
\[\log P(X|\theta ) = \log \frac{{P(X,Z|\theta )}}{{q(z)}} - \log \frac{{P(Z|X,\theta )}}{{q(z)}} , q(Z) \ne 0 \]??兩邊同時關于分布\(q(Z)\)求期望
??對于左邊：
\[\begin{array}{l} {E_{q(Z)}}[\log P(X|\theta )] = \int_Z {\log } P(X|\theta )P(Z|X,{\theta ^{(t)}})dZ\\ = \log P(X|\theta )\int_Z {P(Z|X,{\theta ^{(t)}})} dZ\\ = \log P(X|\theta ) \end{array} \]??對于右邊：
\[\begin{array}{l} {E_{Z|X,{\theta ^{(t)}}}}\left[ {\log \frac{{P(X,Z|\theta )}}{{q(z)}} - \log \frac{{P(Z|X,\theta )}}{{q(z)}}} \right]\\ = \int_Z {\log \frac{{P(X,Z|\theta )}}{{q(z)}}} q(z)dZ - \int_Z {\log \frac{{P(Z|X,\theta )}}{{q(z)}}} q(z)dZ\\ = ELBO + KL\left( {q(Z)||P(Z|X,\theta )} \right) \end{array} \]??其中\({P(Z|X,\theta )}\)為后驗概率，ELBO為evidence lower bound
\[\begin{array}{l} \therefore \log P(X|\theta ) = ELBO + KL\left( {q||P} \right)\\ \because KL\left( {q||P} \right) \ge 0\\ \therefore \log P(X|\theta ) \ge ELBO \end{array} \]??則取最大值，就等價于ELBO取最大值，此時：
\[{{\hat \theta }^{(t + 1)}} = \arg \mathop {\max }\limits_\theta ELBO = \arg \mathop {\max }\limits_\theta \int_Z {\log \frac{{P(X,Z|\theta )}}{{q(z)}}} q(z)dZ \]??\(\because\)當\(q=P\)時，\(KL=0\)，即\(\log P(X|\theta ) = ELBO\)的等號成立，
??則取\(q(z) = P(Z|X,{\theta ^{(t)}})\)，即上一時刻的后驗，
??\(\therefore\)
??此時\(\theta ^{(t)}\)為上一時刻的引數，故在此可視作常數，則減號后面的引數都視作常數，與目標\(\theta\)無關，在求解是無用，故可以省去，
??則此時：
\[{{\hat \theta }^{(t + 1)}} = \arg \mathop {\max }\limits_\theta \int_Z {\log P(X,Z|\theta )} P(Z|X,{\theta ^{(t)}})dZ \]??證畢
五、公式推導方法2（涉及Jensen不等式）
5.1 Jensen不等式
??對于concave function（凹函式），設\(t \in [0,1]\)，則有\(f\left( {t \cdot a + (1 - t) \cdot b} \right) \ge tf\left( a \right) + (1 - t)f\left( b \right)\)，特別的，當\(a = b = \frac{1}{2}\)時，\(f\left( {\frac{{a + b}}{2}} \right) \ge \frac{{f\left( a \right) + f\left( b \right)}}{2}\)，從期望的角度來看就是\(f\left( E \right) \ge E\left( f \right)\)，先期望后函式大于等于先函式后期望，
5.2 關于E-M演算法的理解
??對于E-step： \(\theta ^{(t)}\)是上一次求出的引數，在這一步就是常數，然后對于后驗分布\(Z|X,{\theta ^{(t)}}\)求關于最大似然函式\({\log P(X,Z|\theta )}\)的期望，即寫出一個關于\(\theta\)的函式，
??對于M-step： 針對E-step寫出的期望函式，求使引數\(\theta\)滿足其取最大值的引數作為當前時刻的引數目標\(\theta ^{(t+1)}\).
5.3 推導程序
\[\log P(X|\theta ) = \log \int_Z {P(X,Z|\theta )} dZ \]??引入分布\(q(Z)\):
\[\begin{array}{l}原式= \log \int_Z {\frac{{P(X,Z|\theta )}}{{q(Z)}}} \cdot q(Z)dZ\\ = \log \left[ {{E_{Z|X,{\theta ^{(t)}}}}\left( {\frac{{P(X,Z|\theta )}}{{q(Z)}}} \right)} \right] \end{array} \]??由Jensen不等式:
\[原式\ge {E_{Z|X,{\theta ^{(t)}}}}\left[ {\log \left( {\frac{{P(X,Z|\theta )}}{{q(Z)}}} \right)} \right] = ELBO \]??當\({\frac{{P(X,Z|\theta )}}{{q(Z)}}} = c\),\(c\)為常數時，等號成立，
??則\(q(Z) = \frac{1}{c}P(X,Z|\theta )\)，兩邊同時對\(Z\)求積分：
\[\begin{array}{c} \int_Z {q(Z)dZ = \int_Z {\frac{1}{c}P(X,Z|\theta )dZ} } \\ \\ 1 = \frac{1}{c}P(X|\theta ) \end{array} \]??\(\therefore\)\(q(Z) = P(X|\theta ) \cdot P(X,Z|\theta ) = P(Z|X,\theta )\)
??后續步驟同方法一，
六、廣義EM演算法
??①狹義EM演算法是廣義EM演算法的一種特例；
??②生成模型中如果\(Z\)的復雜度太高，則后驗概率\(P(Z|X,\theta)\)很難求出（intractable），但是像GMM和HNN的\(Z\)是結構化的，相對簡單，所以可以用狹義EM演算法進行優化，
廣義EM步驟：
??\( \left\{ \begin{array}{l} 1.固定\theta :\hat q = \arg \mathop {\min }\limits_q KL(q||P) = \arg \mathop {\max }\limits_q ELBO(\hat q,\theta)\\ 2.固定\hat q:\theta = \arg \mathop {\max }\limits_\theta ELBO(\hat q,\theta) \end{array} \right. \)
??對應的：
??\( \left\{ \begin{array}{l} E-step:{q^{(t + 1)}} = \arg \mathop {\max }\limits_q ELBO(q,{\theta ^{(t)}})\\ M-step:{\theta ^{(t + 1)}} = \arg \mathop {\max }\limits_\theta ELBO({q^{(t + 1)}},{\theta ^{(t)}}) \end{array} \right. \)
\[ELBO(q,\theta ) = {E_{q(Z)}} \log P(X,Z|\theta ) - {E_{q(Z)}}\log q(Z) \]
??其中\(- {E_{q(Z)}}\log q(Z)\)是熵\(H[q(z)]\)，則
\[ELBO(q,\theta ) = {E_{q(Z)}} \log P(X,Z|\theta ) + H[q(z)] \]??廣義EM是先固定一個引數在計算另一個引數，故可以從坐標上升法的角度去看，
七、EM演算法的改進
①變分貝葉斯EM演算法，VBEM/VIEM/VEM，三個簡稱叫法不同，但內容基本一致；
②蒙特卡洛EM演算法，MCEM，
以上內容是在B站上up主的白板推導系列和幾何周志華的西瓜書總結的內容，強烈推薦該系列課程，通俗易懂，還有一定的實時性，附上鏈接機器學習白板推導系列
本人第一次發博，不周之處還請多多批評，歡迎交流，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285809.html
標籤：其他