概率论拾遗：EM 算法及其收敛性

1 EM 算法

  假设包含待估参数 $\theta$ 的模型包含可观测变量 $X$, $X$ 的生成方式包含隐变量 $Z$. 为了求 $X$ 的极大似然估计, 考虑以下最优化问题

$$\hat \theta = \argmax _\theta \ell (\theta \mid x) = \argmax _\theta (\ell (\theta \mid x, z) - \ln \Pr (z \mid x, \theta))$$

最后一个等号使用了条件概率的定义. 在包含隐变量的情况下, 使用 EM 算法

• E 步: 给定初值 $\hat \theta ^{(0)}$, 计算隐变量的条件分布并求其期望 $\hat z ^{(0)} = \mathrm E(z |x, \theta ^{(0)})$.
• M 步: 给定 $\hat z ^{(0)}$, 计算 $\theta$ 的极大似然估计 $\theta ^{(1)} \gets \argmax _\theta \ell (\theta \mid x, \hat z ^{(0)})$.

进一步, 若不是求隐变量 $Z$ 的期望而求对数似然函数的期望, 则

• E 步: 给定初值 $\hat \theta ^{(0)}$, 计算隐变量的条件分布 $Z|_{x, \theta ^{(0)}}$. 然后直接计算对数似然函数的条件期望

$$\begin{aligned} Q(\theta \mid \theta ^{(t)}) &= \mathrm E_{z | x, \theta ^{(t)}} \ell (\theta \mid x, z)\\ &= \int _{-\infty} ^\infty \ell (\theta \mid x, z) \cdot \Pr (z \mid x, \theta ^{(t)}) \mathrm d z \end{aligned}$$

• M 步: 最大化这个期望 $\theta ^{(t+1)} \gets \argmax _\theta Q(\theta \mid \theta ^{(t)})$.

2 收敛性证明

  根据 Bayes 公式有

$$\ell(\theta \mid x) = \ell(\theta \mid x, z) - \ln \Pr(z \mid x, \theta)$$

考虑等式两边对 $Z$ 的后验期望. 左侧与 $Z$ 无关, 所以

$$\begin{aligned} \int _{-\infty} ^\infty \mathrm{LHS} \cdot \Pr(z \mid x, \theta ^{(t)}) \mathrm d z = \mathrm{LHS} \end{aligned}$$

右侧

$$\begin{aligned} & \quad \int _{-\infty} ^\infty \mathrm{RHS} \cdot \Pr(z \mid x, \theta ^{(t)}) \mathrm d z \\ &= \int _{-\infty} ^\infty \ln \Pr(x, z \mid \theta) \cdot \Pr(z \mid x, \theta ^{(t)}) \mathrm d z - \int _{-\infty} ^\infty \ln \Pr(z \mid x, \theta) \cdot \Pr(z \mid x, \theta ^{(t)}) \mathrm d z \\ &=: Q(\theta \mid \theta ^{(t)}) - H(\theta \mid \theta ^{(t)}) \end{aligned}$$

参考文献

• CSDN: CHEONG_KG. 【机器学习系列】EM算法第一讲：EM算法相关概述及收敛性证明. https://blog.csdn.net/feilong_csdn/article/details/117187834.