Expectation-Maximization 算法是统计学中用来给带隐含变量的模型做最大似然（和最大后验概率）的一种方法。EM 的应用特别广泛，经典的比如做概率密度估计用的 Gaussian Mixture Model。这两天我或许还会写 p 的笔记放上来，也是 EM 应用的例子。

## 问题

\begin{equation*} \theta=\arg\max_\theta{L(\theta;X)} \end{equation*}

\begin{equation*} L(\theta;X)=log{P(X;\theta)}=\log{\sum_Z P(X,Z;\theta)} \end{equation*}

\begin{equation*} L(\theta;X,Z)=\log{P(X, Z;\theta)} \end{equation*}

## 算法

Repeat until converge {

1. (E-step) 计算 $$P(Z|X;\theta_t)$$ 以得到

\begin{align*} E_{Z|X;\theta_t}[L(\theta;X,Z)] &:= E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \\ &= \sum_Z P(Z|X;\theta_t) \log{P(X,Z;\theta)} \end{align*}
2. (M-step)

\begin{equation*} \theta_{t+1} := \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{equation*}

}

\begin{align*} \sum_i E_{z^{(i)}|x^{(i)};\theta_t}[L(\theta;x^{(i)},z^{(i)}] &:= \sum_i E_{z^{(i)}|x^{(i)};\theta_t}[\log{P(x^{(i)},z^{(i)};\theta)}] \\ &= \sum_i \sum_{z^{(i)}} P(z^{(i)}|x^{(i)};\theta_t) \log{P(x^{(i)},z^{(i)};\theta)} \end{align*}

## 原理

\begin{equation*} F(\theta_{t+1}) \geq G_{\theta_t}(\theta_{t+1}) \geq G_{\theta_t}(\theta_t) = F(\theta_t) \end{equation*}

Repeat until converge {

1. 找到函数 $$F(\theta)$$ 的“在 $$\theta_t$$ 处相等的下界函数” $$G_{\theta_t}(\theta)$$

2. 更新参数

\begin{equation*} \theta_{t+1} := \arg\max_\theta G_{\theta_t}(\theta) \end{equation*}

}

\begin{align*} L(\theta) &= \log{P(X;\theta)} \\ &= \log{\sum_Z P(X,Z;\theta)} \end{align*}

\begin{align*} L(\theta) &= \log{\sum_Z P(X,Z;\theta)} \\ &= \log{\sum_Z Q(Z) \frac{P(X,Z;\theta)}{Q(Z)}} \\ &= \log E_{Z \sim Q}\left[ \frac{P(X,Z;\theta)}{Q(Z)} \right] \end{align*}

\begin{equation*} L(\theta) = \log E_{Z \sim Q}\left[ \frac{P(X,Z;\theta)}{Q(Z)} \right] \geq E_{Z \sim Q}\left[ \log\frac{P(X,Z;\theta)}{Q(Z)} \right] \end{equation*}

\begin{equation*} L(\theta) \geq E_{Z|X;\theta_t}\left[ \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \right] \end{equation*}

\begin{align*} \theta_{t+1} &:= \arg\max_\theta E_{Z|X;\theta_t}\left[ \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \right] \\ &\equiv \arg\max_\theta \sum_{Z} P(Z|X;\theta_t) \log\frac{P(X,Z;\theta)}{P(Z|X;\theta_t)} \\ &= \arg\max_\theta \sum_{Z} [P(Z|X;\theta_t)\log P(X,Z;\theta) - P(Z|X;\theta_t) \log P(Z|X;\theta_t)] \\ &= \arg\max_\theta \sum_{Z} P(Z|X;\theta_t)\log P(X,Z;\theta) \\ &\equiv \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{align*}

p.s. MathJax 很神嘛。

p.p.s. 这篇笔记竟然断断续续写写改改了两天多，我对 EM 的认识也越来越清晰。“‘教’是最好的‘学’”真是一点没错。

 [1] 一般可以利用贝叶斯定理： \begin{equation*} P(z|x;\theta) = \frac{P(x|z;\theta)P(z;\theta)}{\sum_z{P(x|z;\theta)P(z;\theta)}} \end{equation*} 而 $$P(x|z;\theta)$$ 和 $$P(z;\theta)$$ 往往是模型假设的一部分。
 [2] 实际上在某些特殊情况下，$$\theta$$ 还可能收敛在局部最优点或鞍点上。这时可以多跑几次算法，每次随机不同的 $$\theta_0$$，最后取最好的结果。为简明起见，本文忽略这种情况。
 [3] $$Q(Z)$$ 为概率分布，意即需满足 $$\sum_Z Q(Z) = 1$$ 且 $$Q(Z) \geq 0$$
 [4] Jensen 不等式： $$f$$ 为凸函数，$$X$$ 为随机变量。则 \begin{equation*} E[f(X)]\geq f(E[X]) \end{equation*} 若 $$f$$ 是严格凸的，则上式取等号当前仅当 $$X$$ 为常数。 在这里 $$\log$$ 函数是严格凹的，所以要把上面的不等号方向调转。