离散隐藏变量下期望最大化（EM）算法的简化

先导：一般情况下的期望最大化（EM）算法

---

期望-最大化（EM 算法）是在有“隐藏”变量的模型中实现最大似然估计。EM 算法是一种迭代算法，它保证收敛到似然函数的局部最大值。

用$X$表示观测随机变量，$Z$表示隐随机变量。$X$和$Z$一起称为完全数据（complete-data），观测数据$X$又称为不完全数据（incomplete-data）。假设给定观测数据$X$，其概率分布是$P(X\mid \theta )$，其中$\theta$是需要估计的模型参数，那么不完全数据$X$的似然函数是$P(X\mid \theta )$，对数似然函数$L(\theta ;X)=\ln P(X\mid \theta )$；假设$X$和$Z$的联合概率分布是$P(X,Z\mid \theta )$，那么完全数据的对数似然函数是$L(\theta ;X,Z)=\ln P(X,Z\mid \theta )$。

EM 算法通过迭代求$L(\theta )=\ln P(X\mid \theta )$的极大似然估计。每次迭代包含两步：E 步，求期望；M 步，求极大化。

为了简化，假设$Z$ 是离散的（这是 GMM 中的情况）。

由于$Z$ 不可直接获得，因此完全似然$P(X,Z\mid \theta )$ 也不是直接可用的，EM 算法提出考虑替代函数

$$\begin{array}{rl}Q(\theta \mid X,{\theta }^{(i)})& =E_Z(L(\theta ;X,Z)\mid X,{\theta }^{(i)})\\ & =E_Z[\ln P(X,Z\mid \theta )\mid X,{\theta }^{(i)}]\\ & =\sum _Z\ln P(X,Z\mid \theta )P(Z\mid X,{\theta }^{(i)})\end{array}\text{\hspace{1em}(13)}$$

其中，${\theta }^{(i)}$ 是$\theta$ 的当前估计。式 (13) 中的分数$Q(\theta \mid X,{\theta }^{(i)})$是$P(X,Z\mid \theta )$ 在当前的估计值${\theta }^{(i)}$ 下，对于给定$X$ 的$Z$ 的条件分布的期望值。因此，未知的隐藏变量$Z$ 被期望“平均化”了。

---

式 (9) 的函数$Q(\theta \mid X,{\theta }^{(i)})$是 EM 算法的核心，称为$Q$函数 ($Q$ function)。

定义 1 ($Q$函数) 完全数据的对数似然函数$\ln P(X,Z\mid \theta )$关于在给定观测数据$X$和当前参数${\theta }^{(i)}$下对未观测数据$Z$的条件概率分布$P(Z\mid X,{\theta }^{(i)})$的期望称为$Q$函数，即
$$Q(\theta \mid X,{\theta }^{(i)})=E_Z[\ln P(X,Z\mid \theta )\mid X,{\theta }^{(i)}]\text{\hspace{1em}(11)}$$

---

式 (13) 关于$\theta$ 的最大化：

$${\theta }^{(i+1)}=\arg \underset{\theta }{\max }Q(\theta \mid X,{\theta }^{(i)})\text{\hspace{1em}(14)}$$

${\theta }^{(i+1)}$必然提高了对数似然（待证明），即$L({\theta }^{(i+1)})>L({\theta }^{(i)})$，除非其已经达到$L(\theta )$ 的局部最大值，在这种情况下，$L({\theta }^{(i+1)})=L({\theta }^{(i)})$。

EM 算法最初猜想$\theta ={\theta }^{(0)}$，然后在估计${\theta }^{(i)}$ 的当前值计算式 (13)（称为“E 步”）和最大化式 (14) 这两个步骤之间迭代，以得到下一个估计${\theta }^{(i+1)}$。

---

算法 离散隐藏变量下的期望-最大化 (EM)算法

输入: 观测变量数据$X$, 隐变量数据$Z$, 联合分布$P(X,Z\mid \theta )$, 条件分布$P(Z\mid X,\theta )$;
输出: 模型参数$\theta$。

1. 初始化${\theta }^{(0)}$ 和$\tau >0$
2. repeat
3. E 步：计算$Q(\theta \mid X,{\theta }^{(i)})$

$$\begin{array}{rl}Q(\theta \mid X,{\theta }^{(i)})& =E_Z[\ln P(X,Z\mid \theta )\mid X,{\theta }^{(i)}]\\ & =\sum _Z\ln P(X,Z\mid \theta )P(Z\mid X,{\theta }^{(i)})\end{array}$$

这里，$P(Z\mid X,{\theta }^{(i)})$是在给定观测数据$X$和当前的参数估计${\theta }^{(i)}$下隐变量数据$Z$的条件概率分布；

4. M 步：求使$Q(\theta \mid X,{\theta }^{(i)})$极大化的$\theta$，更新参数

$${\theta }^{(i+1)}=\arg \underset{\theta }{\max }Q(\theta \mid X,{\theta }^{(i)})$$

5. 计算对数似然：

$$L({\theta }^{(i+1)})=\ln P(X\mid {\theta }^{(i+1)})$$

6. until$|L({\theta }^{(i+1)})-L({\theta }^{(i)})|<\tau$

---