PRML读书笔记:9.3 EM的另一种观点


本节中,我们介绍另一种看待EM算法的角度,其中隐变量起到重要的作用。

EM算法即计算后验概率+期望最大化

将所有观测数据的集合记为$\boldsymbol{X}$,所有隐变量的集合记为$\boldsymbol{Z}$,所有模型参数的集合记为$\boldsymbol{\theta}$,则对数似然函数为

$$\ln p(\boldsymbol{X} | \boldsymbol{\theta})=\ln \left\{\sum_{\boldsymbol{Z}} p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\theta})\right\}$$

EM算法的目标即找到使这个对数似然函数取最大值的解。

问题在于,对隐变量的求和位于对数内部,这一求和式使得对数运算不能直接作用于联合概率分布,使得最大似然解的形式变得复杂。

因此我们不妨假定,对于$\boldsymbol{X}$,它的隐变量$\boldsymbol{Z}$是已知的,称$\{\boldsymbol{X}, \boldsymbol{Z}\}$为完整(complete)数据集。完整数据集的对数似然函数的形式为$\ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\theta})$,当它为指数族分布函数时,对这个完整数据集的对数似然函数进行最大化是很容易的。

但是我们实际上没有完整数据集,我们对$\boldsymbol{Z}$的取值的知识仅仅来源于后验概率分布$p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta})$。因此我们转而考虑在隐变量的后验分布下完整数据的对数似然函数的期望值。(由于我们不知道隐变量的具体值,只知道一个分布,因此求期望是一个好的选择。在9.4节中将具体介绍使用期望的原因。)这对应于EM算法的E步骤。在接下来的M步骤中,我们最大化这个期望(对参数$\boldsymbol{\theta}$最大化),得到一个修正的对$\boldsymbol{\theta}$的估计。(从直觉上来说,取定后验分布之后再最大化数据对数似然的期望值,相当于使参数和数据更加接近了。)

一般的EM算法总结如下。每个EM循环都会增大不完整数据集的对数似然函数(除非已经达到局部极大值)(9.4节中将会证明)。

给定观测变量$\boldsymbol{X}$和隐变量$\boldsymbol{Z}$上的一个联合概率分布$p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\theta})$,由参数$\boldsymbol{\theta}$控制,目标是关于$\boldsymbol{\theta}$最大化似然函数$p(\boldsymbol{X} | \boldsymbol{\theta})$:

  • 初始化参数$\boldsymbol{\theta}$,记为$\boldsymbol{\theta}^{\text{old}}$
  • E步骤:计算$\boldsymbol{Z}$在$\boldsymbol{\theta}^{\text{old}}$下的后验分布$p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text{old}})$
  • M步骤:计算$\boldsymbol{\theta}^{\text{new}}$
    • $\mathcal{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text{old}}\right)=\sum_{\boldsymbol{Z}} p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text{old}}\right) \ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\theta})$(对数似然的期望)
    • $\boldsymbol{\theta}^{\text{new}}=\underset{\boldsymbol{\theta}}{\arg \max } \mathcal{Q}\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text{old}}\right)$(最大化期望)
  • 检查对数似然函数或者参数值的收敛性。如果不满足收敛准则,则令$\boldsymbol{\theta}^{\text{old}} = \boldsymbol{\theta}^{\text{new}}$,回到E步骤

EM算法的其他用途

  • 寻找模型的MAP(最大后验概率)解
  • 未观测变量对应于数据集中缺失值
  • 数据集随机缺失

9.3.1 重新考察高斯混合模型

我们考虑将EM算法的隐变量观点应用于一个具体的例子,即高斯混合模型。

由于$\boldsymbol{z}$是one-hot变量,因此概率分布可以写作

$$ \begin{aligned} p(\boldsymbol{x}, \boldsymbol{z}) &= p(\boldsymbol{x} | \boldsymbol{z}) p(\boldsymbol{z}) \\ &= \prod_{k=1}^{K} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)^{z_{k}} \prod_{k=1}^{K}\pi_k^{z_k} \\ &= \prod_{k=1}^{K} \pi_k^{z_k} \mathcal{N}\left(\boldsymbol{x} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)^{z_{k}} \end{aligned} $$

因此似然函数的形式为

$$p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})=\prod_{n=1}^{N} \prod_{k=1}^{K} \pi_{k}^{z_{n k}} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}^{k}\right)^{z_{n k}}$$

取对数,有

$$\ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})=\sum_{n=1}^{N} \sum_{k=1}^{K} z_{n k}\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\}$$

为了进行E步骤,求解后验概率分布$p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})$,由贝叶斯定理得到

$$ \begin{aligned} p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi}) &= \frac{p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})}{p(\boldsymbol{X} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})}\\ &\propto p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi}) \\ &= \prod_{n=1}^{N} \prod_{k=1}^{K} \pi_{k}^{z_{n k}} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}^{k}\right)^{z_{n k}} \end{aligned} $$

因此后验概率分布可以在$n$上进行分解,从而$\boldsymbol{z}n$是独立的,$z{nk}$也是独立的,有

$$
p(z_{nk}) \propto \left[ \pi_{k} \mathcal{N}\left(\boldsymbol{x}{n} | \boldsymbol{\mu}{k}, \boldsymbol{\Sigma}^{k}\right) \right]^{z_{nk}}
$$

因此可以计算出$z_{nk}$的期望(用于计算对数似然的期望):

$$ \begin{aligned} \mathbb{E}\left[z_{n k}\right] &=\frac{\sum_{z_{n}} z_{n k} \prod_{k^{\prime}}\left[\pi_{k^{\prime}} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k^{\prime}}, \boldsymbol{\Sigma}_{k^{\prime}}\right)\right]^{z_{n k^{\prime}}}}{\sum_{z_{n}} \prod_{j}\left[\pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)\right]^{z_{n j}}} \\ &=\frac{\pi_{k} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)}\\ &=\gamma\left(z_{n k}\right) \end{aligned} $$

于是完整数据的对数似然函数的期望值为

$$ \begin{aligned} & \mathbb{E}_{\boldsymbol{Z}}[\ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})] \\ =& \mathbb{E}_{\boldsymbol{Z}}\left[\sum_{n=1}^{N} \sum_{k=1}^{K} z_{n k}\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\}\right] \\ =& \sum_{n=1}^{N} \sum_{k=1}^{K} \sum_{z_{nk}} z_{n k}\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\} p(z_{nk}) \\ =& \sum_{n=1}^{N} \sum_{k=1}^{K} \mathbb{E}_{z_{nk}}[z_{n k}]\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\} \\ =& \sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right)\left\{\ln \pi_{k}+\ln \mathcal{N}\left(\boldsymbol{x}_{n} | \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)\right\} \end{aligned} $$

接下来保持$\gamma\left(z_{n k}\right)$固定,关于$\boldsymbol{\mu}{k}$、$\boldsymbol{\Sigma}{k}$和$\pi_k$最大化上式,方法与9.2节中基本相同。

将$\mathbb{E}_{\boldsymbol{Z}}[\ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})]$对$\boldsymbol{\mu}_k$求导,得到

$$ \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \boldsymbol{\Sigma}_{k}^{-1} (\boldsymbol{x}_{n} - \boldsymbol{\mu}_k) = 0 $$

求解得到

$$ \boldsymbol{\mu}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \boldsymbol{x}_{n} $$

将$\mathbb{E}{\boldsymbol{Z}}[\ln p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\mu}, \boldsymbol{\Sigma}, \boldsymbol{\pi})]$对$\boldsymbol{\Sigma}{k}$求导,得到

$$ \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \frac{1}{2} \left[\boldsymbol{\Sigma}_{k}^{-1} (\boldsymbol{x}_{n} - \boldsymbol{\mu}_k) (\boldsymbol{x}_{n} - \boldsymbol{\mu}_k)^\top\boldsymbol{\Sigma}_{k}^{-1} - \boldsymbol{\Sigma}_{k}^{-1} \right] = 0 $$

求解得到

$$ \boldsymbol{\Sigma}_{k}=\frac{1}{N_{k}} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left(\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\boldsymbol{x}-\boldsymbol{\mu}_{k}\right)^{T} $$

考虑到$\sum_{k=1}^K \pi_k = 1$,用拉格朗日乘数法对$\pi_k$求解,得到

$$
\pi_{k}=\frac{N_{k}}{N}
$$

上述推导结果与之前完全相同。

9.3.2 与K-means的关系

K-means算法与高斯混合模型的EM算法有很强的相似性。K-means算法对数据点的聚类进行了“硬”分配,而EM算法基于后验概率分布进行了“软”分配。我们可以将K-means算法看成是高斯混合模型的EM算法的一个特殊的极限情况。

考虑一个高斯混合模型,混合分量的协方差矩阵是$\epsilon \boldsymbol{I}$,$\epsilon$是一个被所有分量共享的固定的方差参数,$\boldsymbol{I}$是单位矩阵,则有

$$ \begin{aligned} p(\boldsymbol{x} | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) &= \frac{1}{(2\pi)^{\frac{D}{2}} |\boldsymbol{\Sigma}_k|^{\frac{1}{2}}} \exp{\left[ -\frac{1}{2} (\boldsymbol{x}-\boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} (\boldsymbol{x}-\boldsymbol{\mu}_k) \right]} \\ &= \frac{1}{(2\pi\epsilon)^{\frac{D}{2}}} \exp{\left[ -\frac{1}{2\epsilon} \left\|\boldsymbol{x}-\boldsymbol{\mu}_k\right\|^2 \right]} \end{aligned} $$

$$ \begin{aligned} \gamma(z_{nk}) &=\frac{p\left(z_{k}=1\right) p\left(\boldsymbol{x} | z_{k}=1\right)}{\sum_{j=1}^{K} p\left(z_{j}=1\right) p\left(\boldsymbol{x} | z_{j}=1\right)} \\ &=\frac{\pi_{k} \frac{1}{(2\pi\epsilon)^{\frac{D}{2}}} \exp{\left[ -\frac{1}{2\epsilon} \left\|\boldsymbol{x}-\boldsymbol{\mu}_k\right\|^2 \right]}}{\sum_{j=1}^{K} \pi_{j} \frac{1}{(2\pi\epsilon)^{\frac{D}{2}}} \exp{\left[ -\frac{1}{2\epsilon} \left\|\boldsymbol{x}-\boldsymbol{\mu}_j\right\|^2 \right]}} \\ &=\frac{\pi_{k} \exp{\left[ -\frac{1}{2\epsilon} \left\|\boldsymbol{x}-\boldsymbol{\mu}_k\right\|^2 \right]}}{\sum_{j=1}^{K} \pi_{j} \exp{\left[ -\frac{1}{2\epsilon} \left\|\boldsymbol{x}-\boldsymbol{\mu}_j\right\|^2 \right]}} \end{aligned} $$

当$\epsilon \rightarrow 0$时,$\gamma(z_{nk}) \rightarrow r_{nk}$,因此,每个数据点都被分配为距离最近的均值的聚类。

9.3.3 伯努利分布的混合


 评论