EM算法 - 簡書

1. EM介紹

EM(Expectation Maximization Algorithm, EM)是Dempster等人于1977年提出的一種迭代算法晕城，用于含有隱變量的概率模型參數(shù)的極大似然估計(jì)(MLE)催植，或極大后驗(yàn)概率估計(jì)(MAP)叠纷。

2. EM算法描述

輸入

$X$ ：觀測變量數(shù)據(jù)

$Z$ ：隱變量數(shù)據(jù)

$P(X,Z|\theta)$ ：聯(lián)合分布

$P(Z|X,\theta)$ ：條件分布刻帚，后驗(yàn)概率
輸出

$\hat{\theta}$ ：模型參數(shù)
迭代過程
- 初始化參數(shù) $\theta^{(0)}$
- $E$ 步：記 $\theta^{(i)}$ 是第 $i$ 次迭代參數(shù) $\theta$ 的估計(jì)值，則第 $i+1$ 次迭代的 $E$ 步：求對(duì)數(shù)聯(lián)合概率在后驗(yàn)上的期望：
  $\begin{eqnarray*} Q(\theta,\theta^{(i)}) &=& E_{Z}\left[\text{log}P(X,Z|\theta)|X,\theta^{(i)} \right] \\ &=& \sum_{Z}\text{log}P(X,Z|\theta)P(Z|X,\theta^{(i)}) \end{eqnarray*}$
- $M$ 步：求 $i+1$ 步的參數(shù)估計(jì)值 $\theta^{(i+1)}$ ：
  $\theta^{(i+1)}=\underset{\theta}{\text{argmax}}Q(\theta,\theta^{(i)})$
- 重復(fù) $E$ 步和 $M$ 步涩嚣，直到收斂：
  $\left\| \theta^{(i+1)} - \theta^{(i)} \right\| < \varepsilon_{1} \\ \left\| Q(\theta^{(i+1)} , \theta^{(i)} ) - Q(\theta^{(i)} , \theta^{(i)} ) \right\| < \varepsilon_{2}$

3. EM公式導(dǎo)出之ELBO+KL Divergence

MLE的做法是最大化似然函數(shù)：
$\begin{eqnarray*} \mathcal{L}{(\theta)} &=& \text{log}P(X|\theta)=\text{log}\sum_{Z}P(X,Z|\theta) \\ &=& \text{log} \left\{\sum_{Z}P(X|Z,\theta)P(Z|\theta) \right\} \end{eqnarray*}$
上面的式子中有隱變量 $Z$ 并且是 $\text{log}\sum$ 形式崇众，不好直接計(jì)算。

EM的做法是求出似然函數(shù)的下界航厚，不斷迭代顷歌，使得下界不斷逼近 $\mathcal{L}{(\theta)}$ .

$\begin{eqnarray*} \mathcal{L}{(\theta)} &=& \text{log}P(X|\theta) \tag{1}\\ &=& \text{log}P(X,Z|\theta) - \text{log}P{(Z|X,\theta)} \tag{2}\\ &=& \text{log}\frac{P(X,Z|\theta)}{q(Z)} - \text{log}\frac{P{(Z|X,\theta)}}{q(Z)} \tag{3} \end{eqnarray*}$
等式兩邊同時(shí)對(duì) $q(Z)$ 求期望：
$\begin{eqnarray*} \text{left} &=& \int_{Z}q(Z)\text{log}P(X|\theta)\text2whssylZ \\ &=& \text{log}P(X|\theta)\int_{Z}q(Z)\text8zdodb2Z \\ &=& \text{log}P(X|\theta) \end{eqnarray*}$

$\begin{eqnarray} \text{right} &=& \int_{Z}q(Z)\text{log}\frac{P(X,Z|\theta)}{q(Z)}\text7ixetz2Z - \int_{Z}q(Z)\text{log}\frac{P{(Z|X,\theta)}}{q(Z)}\text7dnrgm2Z \\ &=& \int_{Z}q(Z)\text{log}P(X,Z|\theta)\textghnrnxcZ -\int_{Z}q(Z)\text{log}q(Z)\text8ggkkb7Z- \int_{Z}q(Z)\text{log}\frac{P{(Z|X,\theta)}}{q(Z)}\text2tbbbdpZ \\ &=& \underbrace { \int_{Z}q(Z)\text{log}P(X,Z|\theta)\textjqujuljZ -\int_{Z}q(Z)\text{log}q(Z)\textzapzzntZ }_{ ELBO } + KL\left(q(Z)||P(Z|X,\theta)\right) \end{eqnarray}$

所以：
$\text{log}P(X|\theta) = \underbrace { \int_{Z}q(Z)\text{log}P(X,Z|\theta)\textdrrrr26Z -\int_{Z}q(Z)\text{log}q(Z)\textvgrng7mZ }_{ ELBO } + KL\left(q(Z)||P(Z|X,\theta)\right) \tag{4}$
上式中， $ELBO(\text{evidence lower bound})$ 是一個(gè)下界阶淘，所以 $\text{log}P(X|\theta) \geq ELBO$ 衙吩，當(dāng) $KL$ 散度為0時(shí)，等式成立溪窒。

也就是說坤塞，不斷最大化 $ELBO$ 等價(jià)于最大化似然函數(shù)。在EM迭代過程中的第 $i$ 步澈蚌，假設(shè) $q(Z)=q(Z|X,\theta^{(i)})$ 摹芙，然后最大化 $ELBO$
$\begin{eqnarray} \hat{\theta}^{(i+1)} &=& \underset{\theta}{\text{argmax}}ELBO \\ &=& \underset{\theta}{\text{argmax}} \int_{Z}q(Z|X,\theta^{(i)})\text{log}P(X,Z|\theta)\textghrvrx7Z -\underbrace{\int_{Z}q(Z|X,\theta^{(i)})\text{log}q(Z|X,\theta^{(i)})\texti7poz22Z}_{\text{independent with } \theta} \\ &=& \color{red}{\underset{\theta}{\text{argmax}} \int_{Z}q(Z|X,\theta^{(i)})\text{log}P(X,Z|\theta)\textqcbqjarZ} \tag{5} \end{eqnarray}$

4. EM公式導(dǎo)出之ELBO+Jensen Inequality

4.1 Jensen Inequality

4.2 EM公式推導(dǎo)

對(duì)log-likelihood做如下變換：
$\begin{eqnarray*} \text{log}P(X|\theta) &=& \text{log}\int_{Z}P(X,Z|\theta)\textmncyyp8Z = \text{log}\int_{Z} q(Z) \frac{P(X,Z|\theta)}{q(Z)}\text2ubmtz7Z \\ &=& \text{log}\mathbb{E}_{q(Z)}\left(\frac{P(X,Z|\theta)}{q(Z)} \right) \\ &\geq& \mathbb{E}_{q(Z)} \left[\text{log}\frac{P(X,Z|\theta)}{q(Z)} \right] \\ &=& ELBO \end{eqnarray*}$
只有當(dāng) $P(X,Z|\theta) = C \cdot q(Z)$ 時(shí)，等號(hào)才成立宛瞄。

5. EM收斂性證明

如果能證明
$P(X|\theta^{(i+1)}) \geq P(X|\theta^{(i)})$
則說明EM是收斂的浮禾，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=P(X%7C%5Ctheta)" alt="P(X|\theta)" mathimg="1">肯定有界，單調(diào)有界函數(shù)必收斂份汗！

$\begin{eqnarray*} \text{log}P(X|\theta) &=& \text{log}P(X,Z|\theta) - \text{log}P{(Z|X,\theta)} \\ &=& \underbrace{\int_{Z}p(Z|X,\theta^{(i)}) \text{log}P(X,Z|\theta) \textaalwl2dZ}_{Q(\theta,\theta^{(i)})} - \underbrace{\int_{Z}p(Z|X,\theta^{(i)}) \text{log}P{(Z|X,\theta)}\textbrryctvZ}_{H(\theta,\theta^{(i)})} \end{eqnarray*}$
由于 $\theta^{(i+1)}$ 使得 $Q(\theta,\theta^{(i)})$ 達(dá)到極大盈电，所以：
$Q(\theta^{(i+1)},\theta^{(i)}) - Q(\theta^{(i)},\theta^{(i)})\geq 0$

$\begin{eqnarray*} H(\theta^{(i+1)},\theta^{(i)}) - H(\theta^{(i)},\theta^{(i)}) &=& \int_{Z}p(Z|X,\theta^{(i)}) \text{log}P{(Z|X,\theta^{(i+1)})}\textaitshy7Z - \int_{Z}p(Z|X,\theta^{(i)}) \text{log}P{(Z|X,\theta^{(i)})}\textietiizqZ \\ &=& \int_{Z}p(Z|X,\theta^{(i)}) \frac{\text{log}P{(Z|X,\theta^{(i+1)})}}{\text{log}P{(Z|X,\theta^{(i)})}}\textvccnjtzZ \\ &=& -KL\left(p(Z|X,\theta^{(i)}) || \text{log}P{(Z|X,\theta^{(i+1)})} \right) \\ &\leq& 0 \end{eqnarray*}$

因此，得到：
$P(X|\theta^{(i+1)}) \geq P(X|\theta^{(i)})$