EM演算法之不同的推導方法和自己的理解

一、前言

EM演算法主要針對概率生成模型解決具有隱變數的混合模型的引數估計問題，
對于簡單的模型，根據極大似然估計的方法可以直接得到決議解；可以在具有隱變數的復雜模型中，用MLE很難直接得到決議解，此時EM演算法就發揮作用了，
E步解決隱變數的問題，M步求解模型的引數值，也就是極大似然的方法求取模型的引數值，

自己的理解：走一步看一步，走了看，看了再走，迭代程序，
首先使用估計的方式直接設定一組模型的引數值，這組模型的引數值是先驗的，甚至可以說是我們瞎設的，這么設肯定不夠準確呀，我們期望得到更更精確的引數值，那么就用現在的這組引數值去解決隱變數的問題，得到的隱變數，再根據隱變數得到后驗的引數值，后驗是根據觀測到的資料在先驗的基礎上進行修正，以使得引數值更匹配這組資料，

二、概覽

假設一組資料，\(X=\{x^i,x^2 \cdots ,x^n\}\), 包含 \(n\) 個獨立的樣本，這組樣本由一組混合模型生成而來，我們希望 \(\theta\) 滿足：

\[\arg\max_{\theta} logP(X|\theta) \]

可是X是由一組混合模型而來，與隱變數 \(Z\) 有關，\(Z\) 表示樣本歸屬于哪一個模型，
直接使用極大似然估計的方法求取上式很難由決議解，通過EM演算法，轉而求解：

\[\theta^{(t+1)} = \arg\max_{\theta} \int_Z \; P(Z|X,\theta^{(t)})\;logP(X,Z|\theta) \]

通過不斷的迭代求解，求得的\(\theta\) 可以使得 \(logP(X|\theta)\) 不斷增大，達到我們的目的，

如果把已知的資料當成由一個概率模型生成的，那么 \(P(X|\theta)\) 可能會非常復雜，而且我們不知道 \(P(X|\theta)\) 的形式，兩眼一抹黑，啥都不知道，因此就使用了歸納偏置，假定它服從于某個模型，對于生成模型，假設存在一個隱變數 \(Z\)， \(Z\) 負責了 \(X\) 的生成，有了假設，那么\(P(X)\) 就有了一種結構，有了結構就好具體處理了，此時
\(P(X)=\int_{Z}P(X,Z)dZ\)，把 \(P(X)\) 分解處理，
引入隱變數 \(Z\) 求取 \(\theta\)，

三、收斂性

通過上述方式得到的 \(\theta\) 真的可以達到我們的目的嗎？即使得 \(logP(X|\theta)\) 極大，

\[\begin{aligned} logP(X|\theta) &=log \frac {P(X,Z|\theta)}{P(Z|X,\theta)}\\ &=log {P(X,Z|\theta)} - log{P(Z|X,\theta)} \end{aligned} \]

左右兩邊同時對 \(P(Z|X,\theta^{(t)})\) 求取積分：

\[\begin{aligned} 左邊&=\int_{Z}P(Z|X,\theta^{(t)}) log {P(X|\theta)} dZ\\ &=log {P(X|\theta)} \int_{Z}P(Z|X,\theta^{(t)})dZ\\ &=log {P(X|\theta)} \end{aligned} \]

\[\begin{aligned} 右邊&=\int_{Z}P(Z|X,\theta^{(t)}) \left[log {P(X,Z|\theta)} - log{P(Z|X,\theta)}\right] dZ\\ &=\int_{Z}P(Z|X,\theta^{(t)}) log {P(X,Z|\theta)} dZ - \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta)} dZ\\ &Q(\theta,\theta^{(t)}) = \int_{Z}P(Z|X,\theta^{(t)}) log {P(X,Z|\theta)} dZ\\ &H(\theta,\theta^{(t)}) = \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta)} dZ\\ &log {P(X|\theta^{(t+1)})} -log {P(X|\theta^{(t)})} = Q(\theta^{(t+1)},\theta^{(t)}) -Q(\theta^{(t)},\theta^{(t)}) + H(\theta^{(t)},\theta^{(t)}) -H(\theta^{(t+1)},\theta^{(t)}) \end{aligned} \]

根據\(\theta^{(t+1)}\) 的求取公式，直接得出：

\[Q(\theta^{(t+1)},\theta^{(t)})\geq Q(\theta,\theta^{(t)}) \]

此時令\(\theta = \theta^{(t)}\),則：

\[Q(\theta^{(t+1)},\theta^{(t)})\geq Q(\theta^{(t)},\theta^{(t)}) \]

\[\begin{aligned} H(\theta^{(t)},\theta^{(t)}) -H(\theta^{(t+1)},\theta^{(t)}&=\int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta^{(t)})}- \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta^{(t+1)})}dZ\\ &=\int_{Z}P(Z|X,\theta^{(t)}) [log{P(Z|X,\theta^{(t)})}-log{P(Z|X,\theta^{(t+1)})}]dZ\\ &=\int_{Z}P(Z|X,\theta^{(t)})log \frac{P(Z|X,\theta^{(t)})}{P(Z|X,\theta^{(t+1)})}dZ\\ &=KL(P(Z|X,\theta^{(t)}) \;||\; P(Z|X,\theta^{(t+1)})) \geq 0 \end{aligned} \]

所以 $$log {P(X|\theta^{(t+1)})} -log {P(X|\theta^{(t)})} \geq 0$$

\[log {P(X|\theta^{(t+1)})} \geq log {P(X|\theta^{(t)})} \]

四、完整的推導

Jesen不等式：當f是凹函式時：$$f[E] \geq E[f]$$

其中 \(f\) 表示凹函式，\(E\) 表示期望，比如說\(log[E(x)] \geq E[log(x)]\)

第一種推導方法

\[\begin{aligned} log {P(X|\theta)} &= log \int_{Z}P(X,Z|\theta)dZ=log \int_{Z} \frac{P(X,Z|\theta)}{q(Z)}q(Z)dZ\\ &=log E_{q(Z)}[\frac{P(X,Z|\theta)}{q(Z)}] \geq E_{q(Z)}[log \frac{P(X,Z|\theta)}{q(Z)}] \end{aligned} \]

取等號時是\(\frac{P(X,Z|\theta)}{q(Z)}=C\)
我們把\(E_{q(Z)}[log \frac{P(X,Z|\theta)}{q(Z)}]\)叫做 \(ELBO\)
換句話說就是 \(ELBO\) 是 \(log {P(X|\theta)}\) 的下界,不停的增大ELBO，就可以不斷的增大 \(log {P(X|\theta)}\)

在后面我們可以看到 $ \int_Z ; P(Z|X,\theta^{(t)});logP(X,Z|\theta)$ 就是這里的 \(ELBO\)

第二種推導方法

\[\begin{aligned} log {P(X|\theta)} &=log\frac{P(X,Z|\theta)}{P(Z|X,\theta)}\\ &=log P(X,Z|\theta) - log P(Z|X,\theta)\\ &=log \frac {P(X,Z|\theta)}{q(Z)} - \frac {log P(Z|X,\theta)}{q(Z)} \end{aligned} \]

等式兩邊同時關于分布 \(q(Z)\) 求期望（兩邊同時對 \(q(Z)\) 求積分）
左邊還是等于左邊（具體步驟參考上面）

\[\begin{aligned} 右邊 &= \int_{Z}q(Z)log \frac {P(X,Z|\theta)}{q(Z)}dZ-\int_{Z}q(Z)log \frac {log P(Z|X,\theta)}{q(Z)}dZ\\ & = ELBO+KL(q(Z)\;||\;P(Z|X,\theta)) \end{aligned} \]

當 \(q(Z)與P(Z|X,\theta)\) 同分布時取等號，

因此：
E步：找到一個q = p
M步：(多種不同的形式)

\[\begin{aligned} &\arg\max_{\theta} \int_{Z}q(Z)log \frac {P(X,Z|\theta)}{q(Z)}dZ \\ &\arg\max_{\theta}\int_{Z}q(Z)log {P(X,Z|\theta)}dZ\\ &\arg\max_{\theta}\int_{Z}P(Z|X,\theta^{(t)})log {P(X,Z|\theta)}dZ\\ &\arg\max_{\theta}\sum_{Z}P(Z|X,\theta^{(t)})log {P(X,Z|\theta)} \end{aligned} \]

題外話：在GMM中，我們直接把 \(q(Z)\) 寫為 \(P(Z|X,\theta)\),也就是Z的后驗，此時

\[log P(X|\theta) = ELBO \]

當我們不停的極大化 \(ELBO\) 時，就是在極大化 $ log P(X|\theta)$，
自己的理解就是從極大化 \(log P(X|\theta)\) 這個任務 變成了 極大化 \(log P(X,Z|\theta)\)這個任務，
因為直接極大化 \(log P(X|\theta)\) 這個任務我們做不出來，然后引入了隱變數 \(Z\)(對應樣本屬于哪個模型的分布) 來幫助我們解決問題，從一階段變成了二階段：求他們的聯合分布的概率最大化，

五、廣義EM

\[logP(X|\theta) = ELBO+KL(q(Z)||P(Z|X,\theta)) \]

令

\[L(q,\theta)=ELBO = E_{q(Z)}[ log\frac{P(X,Z|\theta)} {q(Z)}] \]

發散一下
\(logP(X|\theta) = E_{q(Z)}[ log{P(X,Z|\theta)}]-E_{q(Z)}[log \;q(Z)]+KL(q(Z)||P(Z|X,\theta))\)
\(= E_{q(Z)}[ log{P(X,Z|\theta)}]+H(q(Z))+KL(q(Z)||P(Z|X,\theta))\)
\(= E_{q(Z)}[ log{P(X,Z|\theta)}]+H(q(Z),P(Z|X,\theta))\)

E-step:固定 \(\theta\),找出q,此時 \(logP(X|\theta)\)是定值：

\[\begin{aligned} q^{(t+1)} &= \arg\min_{q}KL(q||P) = \arg\max_{q}ELBO\\& = \arg\max_{q} L(q,\theta^{(t)})\\&=\arg\max_{\theta} E_{q(Z)}[ log\frac{P(X,Z|\theta^{(t)})} {q(Z)}] \end{aligned} \]

M-step:固定 \(q\),找出 \(\theta\)：

\[\begin{aligned} \theta^{(t+1)} &= \arg\max_{\theta}ELBO =\arg\max_{\theta} L(q^{(t+1)},\theta)\\&= \arg\max_{\theta} E_{q^{(t+1)}(Z)}[ log\frac{P(X,Z|\theta)} {q^{(t+1)}(Z)}]\\&= \arg\max_{\theta} E_{q^{(t+1)}(Z)}[ log{P(X,Z|\theta)} ] \end{aligned} \]

標籤：其他

上一篇：證明xcosx無周期

下一篇：遵循統一的機器學習框架理解高斯混合模型（GMM）