EM Algorithm

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

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

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

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表示为

对于mixture models,

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

E-step:根据Bayes theorem,有

M-step:代入$r_k$,最大化$Q$,易得

直观的解释是,更新后的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的权重分布

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

其中$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的权重分布

而由M-step可得更新规则

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

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

其中$\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的一种特殊情况。