高斯混合模型和概率潜在语义分析
Published:
而本文旨在从高斯混合模型和概率潜在语义分析模型出发，展现EM算法有趣的灵魂。
在博文 EM算法 中，从最大化证据下界ELBO的角度，介绍了该统计机器学习中的经典算法。
而本文将基于另外一个角度，剖析EM算法。
Three-Coins Model
EM算法通常用于估计含有隐变量的模型，此时极大似然估计通常难以运用。简单的可以考虑如下的三硬币模型，假设有ABC三枚硬币，正面朝上的概率分别为$\pi,p,q$，先掷硬币A,若正面朝上，则掷硬币B，反面朝上，则掷硬币C，记录硬币B或C的结果，作为观测变量$Y$（显变量），而硬币A的结果是未知变量$Z$（隐变量）, 用示性函数$\gamma$表示。
E-Step E步需要利用参数$\theta’$计算该参数下的条件概率$P(Z \vert Y)$，
\[\begin{align} P(Z_i \vert Y_i) &= \frac{\pi p^{y_i} (1-p)^{1-y_i}}{\pi p^{y_i} (1-p)^{1-y_i} + (1-\pi) q^{y_i} (1-q)^{1-y_i}}\\ \end{align}\]M-Step M步希望最大化给定隐变量的示性函数$\gamma$下的对数似然函数，
\[\begin{align} \log L(\theta) &= \log \prod_i(\pi p^{y_i} (1-p)^{1-y_i})^{\gamma_i}((1-\pi) q^{y_i} (1-q)^{1-y_i})^{1-\gamma_i} \\ \end{align}\]EM算法使用E步估计得到的条件概率对上式中的示性函数$\gamma$，也即令$\gamma = P(Z \vert Y, \theta’)$
嵌入后的对数似然函数也被称为Q函数，后文将证明其为对数似然函数的一个下界，因此最大化Q函数某种意义上也是在最大化对数似然函数，证明将在后文详细展开，或者参见 EM算法 中的算法收敛性证明。
为了最大化Q函数，对其求导，
\[\begin{align} \frac{\partial Q}{\partial \pi} &= \frac{\sum_i \gamma_i}{\pi} - \frac{\sum_i (1-\gamma_i)}{1-\pi} \\ \frac{\partial Q}{\partial p} &= \frac{\sum_i \gamma_i y_i}{p} - \frac{\sum_i \gamma_i(1- y_i)}{1-p} \\ \frac{\partial Q}{\partial q} &= \frac{\sum_i (1-\gamma_i) y_i}{q} - \frac{\sum_i (1-\gamma_i)(1- y_i)}{1-q} \\ \end{align}\]令其导数为0可以解得，
\[\begin{align} \pi &= \frac{\gamma_i}{N} \\ p &= \frac{\sum_i \gamma_i y_i}{\sum_i \gamma_i} \\ q &= \frac{\sum_i (1-\gamma_i) y_i}{\sum_i (1-\gamma_i)} \end{align}\]GMM(Gaussian Mixture Model)
下面介绍高斯混合模型GMM，关于该模型的定义可以参见 EM算法 中的GMM一节。
假设来自每个高斯模型的概率为$\alpha_k$,每个高斯分布对应的均值和方差为$\mu_k,\sigma_k^2$
隐变量为示性函数，$\gamma_{ik}$表示数据$i$是否来自第$k$个高斯。
E-Step E步计算条件概率$P(Z \vert Y)$，在GMM中通常也可以叫做响应度， \(\begin{align} \gamma_{ik} &= \frac{\alpha_k \Phi(y_i \vert \mu_k,\sigma_k^2)}{\sum_k \alpha_k \Phi(y_i \vert \mu_k,\sigma_k^2)} \\ \end{align}\)
M-Step M步最大化Q函数，
\[\begin{align} Q &= \log \prod_{ik} (\alpha_k \Phi(y_i \vert \mu_k,\sigma_k^2))^{\gamma_{ik}} \end{align}\]由于有$\sum_k \alpha_k=1$的约束，使用Lagrange乘子法，
\[Q = \sum_{ik} \gamma_{ik} \log \alpha_k + \gamma_{ik} \log \Phi(y_i \vert \mu_k,\sigma_k^2) + \lambda (1-\sum_k\alpha_k)\]同样对Q函数求导，
\[\begin{align} \frac{\partial Q}{\partial \alpha_k} &= \frac{\sum_i \gamma_{ik}}{\alpha_k} - \lambda \\ \frac{\partial Q}{\partial \mu_k} &= \frac{\sum_i\gamma_{ik}(y_i - \mu_k)}{\sigma_k^2} \\ \frac{\partial Q}{\partial \sigma_k^2} &= \frac{\sum_{i} \gamma_{ik}( y_i - \mu_{ik})^2}{2 \sigma^4} - \frac{\sum_{i} \gamma_{ik}}{2 \sigma^2} \\ \end{align}\]可以解得，
\[\begin{align} \alpha_k & = \frac{\sum_i\gamma_{ik}}{N} \\ \mu_k &= \frac{\sum_i \gamma_{ik}y_i}{\sum_{i} \gamma_{ik}} \\ \sigma_k^2 &= \frac{\sum_i \gamma_{ik} (y_i - \mu_k)^2}{\sum_i \gamma_{ik}} \\ \end{align}\]上式的结果具有明显的意义，也即只要计算响应度$\gamma_{ik}$下的样本均值和样本方差即可，这与正态分布的极大似然估计本质上是一致的。
Convergence
本章证明EM算法收敛到极大似然估计，利用Jesson不等式对对数似然函数进行放缩，
\[\begin{align} \max L(\theta) &= \max \log \sum_Z P(Z) P(Y \vert Z) \\ &= \max \log \sum_Z \frac{P(Z \vert Y, \theta')}{P(Z \vert Y, \theta')} P(Z) P(Y \vert Z) \\ &= \max \log E_{Z \sim P(Z \vert Y, \theta')}\frac{P(Z) P(Y \vert Z)}{P(Z \vert Y, \theta')}\\ &\ge \max E_{Z \sim P(Z \vert Y, \theta')} \log \frac{P(Z) P(Y \vert Z)}{P(Z \vert Y, \theta')} \\ &= \max E_{Z \sim P(Z \vert Y, \theta')}\log P(Y,Z) \\ &= \max Q(\theta) \end{align}\]其中倒数第二个等式是因为含$P(Z \vert Y, \theta’)$的项与待优化的参数$\theta$无关。
从上面的推导可以看出，最大化Q函数$Q(\theta)$也是在最大化对数似然函数$\log L(\theta)$,
再经过简单的推导，可以得到，$L(\theta) \ge L(\theta’)$，也即EM算法不断地抬升对数似然函数，证明如下：
根据Bayes公式，
\[\begin{align} p(x \vert \theta ) &= \frac{p(x,z \vert \theta)}{p(z \vert x ,\theta)} \\ \log p(x \vert \theta ) &= \log p(x,z \vert \theta) - \log p(z \vert x ,\theta) \\ E_{z \vert x,\theta'}[\log p(x \vert \theta)] &= E_{z \vert x,\theta'}[\log p(x,z \vert \theta)] - E_{z \vert x,\theta'}[\log p(z \vert x ,\theta)] \\ \log L(x \vert \theta) &= Q(\theta \vert \theta') - E_{z \vert x,\theta'}[\log p(z \vert x ,\theta)] \\ \end{align}\]计算对数似然函数$\log L(x \vert \theta)$的增量，
\[\begin{align} \log L(x \vert \theta) - \log L(x \vert \theta') &= Q(\theta \vert \theta')- Q(\theta' \vert \theta') - E_{z \vert x,\theta'}[\frac{\log p(z \vert x ,\theta)}{\log p(z \vert x,\theta')}] \\ &\ge Q(\theta \vert \theta')- Q(\theta' \vert \theta') + KL(p(z \vert x,\theta) \Vert p(z\vert x,\theta')) \\ &\ge 0 \end{align}\]在最大似然函数（MLE）有界的时候，EM算法一定是收敛的。
Probabilistic latent semantic analysis(PLSA)
下面介绍EM算法在自然语言处理（Natural Language Processing，NLP）中的一个应用，概率潜在语义分析（Probabilistic latent semantic analysis，PLSA）。
考虑文档的集合$d_j$和单词的集合$w_i$，可以观测到文档-单词的共现频率，可以直接进行建模。
\[P = \prod_{ij}P(w_i,d_j)^{n(w_i,d_j)}\]但由于单词很多，上述共现概率矩阵$P(w_i,d_j)$通常很大，难以直接计算，通常引入隐变量话题$z_k$，首先由文档$d_j$生成话题$z_k$,再由话题$z_k$生成文档中的单词$w_i$,此时的概率为，
\[P = \prod_{ij} \sum_{z_k} (P(d_j) P(z_k \vert d_j) P(w_i \vert z_k))^{n(w_i,d_j)}\]定义示性函数隐变量，$\gamma_{ijk}$表示文档$d_j$中的单词$w_i$由话题$z_k$生成，则Q函数为，
\[\begin{align} Q &= \log \prod_{ijk} ((P(z_k \vert d_j) P(w_i \vert z_k))^{\gamma_{ijk}} P(d_j))^{n(w_i,d_j)} \\ &= \sum_{ij} n(w_i,d_j) \log P(d_j) + \sum_{ijk} n(w_i,d_j) \gamma_{ijk} \log P(z_k \vert d_j) + \sum_{ijk} n(w_i,d_j) \gamma_{ijk} \log P(w_i \vert z_k) \\ & = \sum_{ij} n(w_i,d_j) \log P(d_j) + \sum_{ijk} n(w_i,d_j) \gamma_{ijk} \log \alpha_{jk} + \sum_{ijk} n(w_i,d_j) \gamma_{ijk} \log \beta_{ki} \\ \text{Let } \alpha_{jk} &= P(z_k \vert d_j), \beta_{ki} = P(w_i \vert z_k) \end{align}\]上式的$\alpha,\beta$即为待估参数，并且考虑到约束条件，同样引入Lagrange乘子，
\[\begin{align} Q' &= Q + \sum_j \lambda_j(1-\sum_k\alpha_{jk} ) + \sum_k \mu_k (1- \sum_i \beta_{ki}) \end{align}\]对其求导， \(\begin{align} \frac{\partial Q'}{\partial \alpha_{jk}} &= \frac{\sum_i n(w_i,d_j) \gamma_{ijk}}{\alpha_{jk}} - \lambda_j \\ \frac{\partial Q'}{\partial \beta_{ki}} &= \frac{\sum_j n(w_i,d_j) \gamma_{ijk}}{\beta_{ki}} - \lambda_k \\ \end{align}\)
令其导数为0可以解得，
\[\begin{align} \alpha_{jk} &= \frac{\sum_i n(w_i,d_j) \gamma_{ijk}}{\sum_{ik} n(w_i,d_j) \gamma_{ijk}} \\ \beta_{ki} &= \frac{\sum_j n(w_i,d_j) \gamma_{ijk}}{\sum_{ji} n(w_i,d_j) \gamma_{ijk}} \\ \end{align}\]上面的解也有明显的含义，表示在某些条件下，使用相应的频率估计概率。这实际上是多项分布的极大似然估计的性质，回归模型可以可以看到模型本质上的确做了多项分布的假设。
最后反过来考虑$\gamma_{ijk}$的计算，
\[\begin{align} \gamma_{ijk} &= P(z_k \vert d_j,w_i) \\ &= \frac{P(z_k \vert d_j) P(w_i \vert z_k)}{\sum_{z_k} P(z_k \vert d_j) P(w_i \vert z_k)} (\text{By Bayes Rule})\\ &= \frac{\alpha_{jk} \beta_{ik}}{\sum_z \alpha_{jk} \beta_{ik}} \end{align}\]