\[\newcommand{\bm}[1]{\boldsymbol{#1}}\]

EM Algorithm

我们用$z$表示latent variable，用$x$表示observed variable。

我们的原始目标是最大化log likelihood

\[l(\theta) = \log{p(x | \theta)} = \log{\sum_z{p(x, z | \theta)}}\]

但是当$z$的维度很高时，将其marginalize是不现实的。EM的思路是将其表示为

\[Q(\theta, \theta^{(t-1)}) = \mathbb{E}_{\hat{z} \sim p(z | x, \theta^{(t-1)})}{[\log{p(x, \hat{z} | \theta)}]}\]

EM算法不断重复两步操作：Expectation (E-step) 和Maximization (M-step). 在E-step中，我们按照已有的的参数猜测$z$的posterior，并以此计算expected complete-data log likelihood. 而在M-step中，我们计算最优化这个likelihood的参数，用它更新已有的的参数。

应用：Parameter Estimation in GMMs

下面举例EM如何应用在GMM中。GMM表示为

\[p(x | \theta) = \sum_{k}{\pi_k \mathcal{N}(x | \mu_k, \sigma_k)}\]

对于mixture models，

\[\begin{align*} Q(\theta, \theta^{(t-1)}) &= \mathbb{E} \big[ \log{p(x, z | \theta)} \big] \\ &= \mathbb{E} \big[ \log{\prod_k{[\pi_k p(x | \theta_k)]^{\mathbb{I}(z=k)}}} \big] \\ &= \sum_k{\mathbb{E}[\mathbb{I}(z=k)] \log[\pi_k p(x | \theta_k)]} \\ &= \sum_k{p(z=k | x, \theta^{(t-1)}) \log[\pi_k p(x | \theta_k)]} \\ &= \sum_k{r_k \log[\pi_k p(x | \theta_k)]} \\ \end{align*}\]

其中，可以把$r_k$理解为该$x$在计算$z$的expectation时分配给$z=k$的权重。E-step即是计算这个值。

E-step：根据Bayes theorem，有

\[r_k = p(z=k | x, \theta^{(t-1)}) = \frac{\pi^{(t-1)}_k p(x | \theta^{(t-1)}_k)}{\sum_{k'}{\pi^{(t-1)}_{k'} p(x | \theta^{(t-1)}_{k'})}}\]

M-step：代入$r_k$，最大化$Q$，易得

\[\pi^{(t)}_k \leftarrow r_k\]

直观的解释是，更新后的mixing weights等于在E-step中分配的权重，当有多组数据时，取权重的平均值。

延伸：K-means Algorithm

K-means其实是GMM的一种特殊情况，它作出了以下限制：

$\pi_k = 1/K$：所有base model的prior均相等
$\Sigma_k = \sigma^2 I_D$：所有Gaussian的covariance matrix均相同且为identity
Hard EM：在E-step中，对posterior使用delta function approximation，使得给$z$的权重为one-hot。因为这一点，K-means退化为了一个non-probabilistic model，它不能用来计算data的likelihood。

应用：Topic Mining with Mixture of ULMs

Adapted from Text Mining and Analytics Week 3 by ChengXiang Zhai

Topic Mining即是从文档中提取话题，最简单的形式为从单一文档中提取单一话题。考虑使用由两个Unigram Language Model (ULM) 组成的mixture model对文档进行建模，其中一个ULM对文档$d$的话题进行建模，表示为$p(w \mid \theta_d)$；另一个ULM对background进行建模，表示为$p(w \mid \theta_B)$。Mixture weights为$\lambda_d, \lambda_B$，满足$\lambda_d +\lambda_B = 1$。这定义了一个generative process：生成文档的每个词时，首先根据mixture weights sample出一个base model，然后根据该model的ULM sample出一个词。

将background model提取出来的好处是，可以用它capture自然语言中通用的distribution，这样可以使topic model更有效地表示文档的独特特征。Topic model不必去capture那些本来出现频率就比较大的词语，避免了mixture model之间的competition。

在对这个mixture model进行estimation时，可以将文档中的每一个词看作observed variable $w$，对应的生成这个词的base model视为latent variable $z \in {d, B}$。我们假设$\lambda_d, \lambda_B$固定，background ULM可从large corpus估计得出，因而需要估计的参数为topic ULM $p(w \mid \theta_d)$。

由E-step可得每个词对所有base model的权重分布

\[p(z=d | w) = \frac{\lambda^{(t-1)}_d p^{(t-1)}(w | \theta_d)}{\lambda^{(t-1)}_d p^{(t-1)}(w | \theta_d) + \lambda^{(t-1)}_B p(w | \theta_B)}\]

而由M-step可得topic ULM的更新规则

\[\begin{align*} p^{(t)}(w | \theta_d) &= \frac{\sum_{w' \in d}{\mathbb{I}(w'=w) p(z=d | w')}}{\sum_{w' \in d}{p(z=d | w')}} \\ &= \frac{c(w) p(z=d | w)}{\sum_{w' \in V}{c(w') p(z=d | w')}} \end{align*}\]

其中$c(w)$为词$w$在文档中出现的频数。

延伸：Probabilistic Latent Semantic Analysis (PLSA)

PLSA将上面的问题扩展到：给定$n$个文档，我们的目标是寻找$k$个话题，并给出文档的topic coverage。我们保留background ULM，同时使用$k$个topic ULM对每个话题进行建模，表示为$p(w \mid \theta_1), \dots, p(w \mid \theta_k)$。Mixture weights为$\lambda_B, \pi_{d1}, \dots, \pi_{dk} \forall d \in C$，其中$\lambda_B$表示从background生成的概率，$\pi_{di}$表示在文档$d$中，在非background生成的前提下，从第$i$个topic生成的概率，满足$\forall d \in C, \sum_i{\pi_{di}} = 1$ 。$\pi_{di}$代表了topic $i$在文档$d$中的coverage。

在这个问题中，latent variable $z \in {1, \dots, k, B}$。同样，我们假设$\lambda_B$固定，因而需要估计的参数为topic ULM $p(w mid \theta_1), \dots, p(w \mid \theta_k)$以及mixture weights $\pi_{d1}, \dots, \pi_{dk} \forall d \in C$。

由E-step可得每个词对所有base model的权重分布

\[\begin{align*} p(z=i | w, d) &= \frac{\pi_{di} p(w | \theta_i)}{\sum_{j}{\pi_{dj} p(w | \theta_j)}} \\ p(z=B | w, d) &= \frac{\lambda_B p(w | \theta_B)}{\lambda_B p(w | \theta_B) + (1 - \lambda_B) \sum_j{\pi_{dj} p(w | \theta_j)}} \end{align*}\]

而由M-step可得更新规则

\[\begin{align*} \pi_{di} &= \frac{\sum_{w \in V}{c(w, d) (1 - p(z=B | w, d)) p(z=i | w, d)}}{\sum_j{\sum_{w \in V}{c(w, d) (1 - p(z=B | w, d)) p(z=j | w, d)}}} \\ p(w | \theta_i) &= \frac{\sum_{d \in C}{c(w, d) (1 - p(z=B | w, d)) p(z=i | w, d)}}{\sum_{w' \in V}{\sum_{d \in C}{c(w', d) (1 - p(z=B | w', d)) p(z=i | w', d)}}} \end{align*}\]

其中$c(w, d)$为词$w$在文档$d$中出现的频数。为了简洁，我们略去了角标$(t), (t-1)$。

如果想要控制提取的topic的内容，可以给topic models提供一些prior。这样我们就需要用MAP estimation做EM。其实唯一的变动就是在M-step中给topic model的更新规则加一个pseudo count

\[p(w | \theta_i) = \frac{\sum_{d \in C}{c(w, d) (1 - p(z=B | w, d)) p(z=i | w, d)} + \mu Pr(w | \theta_i)}{\sum_{w' \in V}{\sum_{d \in C}{c(w', d) (1 - p(z=B | w', d)) p(z=i | w', d)}} + \mu}\]

其中$\mu$控制prior的强度。

Latent Dirichlet Allocation (LDA) 是PLSA的Bayesian版本，它给topic model和mixture weights都施加了Dirichlet Prior，使得模型的参数量更小。

其它

在机器翻译中，IBM Alignment Model用到了EM。https://courses.engr.illinois.edu/cs447/fa2018/Slides/Lecture22HO.pdf

HMM的forwards-backwards算法是EM的一种特殊情况。