EM 算法及推广

1.1 本意概要

1. 含有隐变量的概率模型的数据表示为 $P(Y, Z \mid \theta)$，这里 $Y$ 是观测变量的数据，Z 是隐变量的数据，$\theta$ 是模型参数
2. EM 算法通过迭代求解观测数据的对数似然函数 $L(\theta) = \ln P(Y \mid \theta)$ 的极大化，实现极大似然估计

3. EM 算法的迭代分两步：

   • E 步，求 $\ln P(Y, Z \mid \theta)$ 关于 $P(Z \mid Y, \theta^{(i)})$ 的期望：

     $Q(\theta, \theta^{(i)}) = \sum\limits_{Z} \ln P(Y, Z \mid \theta) P(Z \mid Y, \theta^{(i)})$ 上式称为 $Q$ 函数，其中 $\theta^{(i)}$ 是参数的现估计值

   • M 步，求极大，即极大化 $Q$ 函数得到参数的新估计值：

     $\theta^{(i+1)} = arg \max\limits_{\theta} Q(\theta, \theta^{(i)})$ EM 通过极大化 $Q$ 函数来增大对数似然函数 $L(\theta)$

4. EM 算法每次迭代后均能提高观测数据的似然函数值，即

   $$P(Y \mid \theta^{(i+1)}) \ge P(Y \mid \theta^{(i)})$$
5. EM 算法是收敛的，但不保证收敛到全局最优
6. 高斯混合模型的参数估计是 EM 算法的重要应用，高斯混合模型可以拟合任意的连续函数
7. EM 算法不断可以解释为 $F$ 函数的极大-极大算法
8. EM 算法的变形：GEM 算法

1.2 目录

1. EM 算法的引入
   1.1 EM 算法
   1.2 EM 算法的导出
   1.3 EM 算法在非监督学习中的应用
2. EM 算法的收敛性
3. EM 算法在高斯混合模型学习中的应用
   3.1 高斯混合模型
   3.2 高斯混合模型参数估计的 EM 算法
4. EM 算法的推广
   4.1 F 函数的极大-极大算法
   4.2 GEM 算法

---

2.1 EM 算法的引入

EM 算法由两步组成：E 步，求期望；M 步，求极大。所以 EM 算法称为期望极大算法

当概率模型的变量都是观测变量，那么给定观测数据就可以直接用极大似然估计法或贝叶期法估计模型的参数。但当概率模型还有隐变量时，就需要用 EM 算法来处理

2.1.1 EM 算法

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

• 流程：

  1. 选择参数的初值 $\theta^{(0)}$

  2. E 步：记 $\theta^{(i)}$ 是第 i 次迭代参数 $\theta$ 的估计值，在第 i+1 次迭代的 E 步，计算：

     $$\begin{aligned}Q(\theta, \theta^{(i)}) &= E_Z \left[ \log P(Y, Z\theta) \mid Y, \theta^{(i)}\right] \\&= \sum\limits_{Z} \log P(Y, Z\mid \theta) P(Z \mid Y, \theta^{(i)})\end{aligned}$$

  3. M 步：求使 $Q(\theta, \theta^{(i)})$ 极大化的 $\theta$，确定第 i+1 次迭代的参数的估计值 $\theta^{(i+1)}$

     $$\theta^{(i+1)} = arg \max_limits{\theta} Q(\theta, \theta^{(i)})$$
  4. 重复 2、3，直到收敛

2.1.2 Q 函数

完全数据的对数似然函数 $\log P(Y, Z \mid \theta)$ 关于，在给定观测数据 Y 和当前参数 $\theta^{(i)}$ 下，对未观测数据 Z 的条件概率分布 $P(Z, \mid Y, \theta)$ 的期望，称为 Q 函数：

$$Q(\theta, \theta^{(i)}) = E_Z \left[ \log P(Y, Z \mid \theta) \mid Y, \theta^{(i)} \right]$$

EM 算法的说明：

1. 参数初值可以任意选择，但算法对初值敏感
2. $Q(\theta, \theta^{(i)})$ 的第 1 个元素是要极大化的参数，第 2 个表示当前估计值
3. 停止迭代的条件： $\Vert \theta^{(i+1)} - \theta^{(i)} \Vert < \epsilon_1$ 或 $\Vert Q(\theta^{(i+1)}, \theta^{(i)})\Vert - \Vert Q(\theta^{(i)}, \theta^{(i)}) \Vert < \epsilon_2$

2.1.3 EM 算法的导出

我们面对含有隐变量的概率模型，目标是极大化观测数据（不完全数据） $Y$ 关于参数 $\theta$ 的对数似然函数，即极大化：

$$L(\theta) = \log P(Y \mid \theta) = \log \sum\limits_Z P(Y, Z \mid \theta) = \log \left( \sum\limits_{Z} P(Y \mid Z, \theta) P(Z \mid \theta) \right)$$

困难的是，上式包含有未观测数据，并且有和的对数

EM 算法的思路是通过迭代靠近极大化的 $L(\theta)$。假设第 i 次迭代后 $\theta$ 的估计值是 $\theta^{(i)}$。我们希望估计值使 $L(\theta)$ 增加，所以：

$$\begin{aligned}L(\theta) - L(\theta^{(i)}) &= \log \left(\sum\limits_Z P(Y \mid Z, \theta) \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})} \right) - \log P(Y \mid \theta^{(i)}) \\ &\ge \sum\limits_{Z} P(Z \mid Y, \theta^{(i)}) \frac{P(Y \mid Z, \theta) P(Z \mid \theta)}{P(Z \mid Y, \theta^{(i)})} - \log P(Y \mid \theta^{(i)}) \\ &= \sum\limits_{Z} P(Z \mid Y, \theta^{(i)}) \frac{P(Y \mid Z, \theta)P(Z \mid \theta)}{P(Z \mid Y, \theta^{(i)}) P(Y \mid \theta^{(i)})} \end{aligned}$$

2.2 EM 算法在高斯混合模型学习中的应用

2.2.1 高斯混合模型

高斯混合模型是具有如下概率分布的模型：

$$P(y \mid \theta) = \sum\limits_{k=1}^K \alpha_k /Phi(y \mid \theta_k)$$

其中 $\Phi(y \mid \theta_k)$ 是高斯分布密度， $\theta_k = (\mu_k, \sigma_k^2)$：

$$Phi(y \mid \theta_k) = \frac{1}{\sqrt{2\pi} \sigma_k} \exp \left( - \frac{(y - \mu_k)^2}{2 \sigma_k^2} \right)$$

称为第 $k$ 个分模型

2.2.2 高斯混合模型参数估计的 EM 算法

• 输入
  • 观测数据 $y_1, y_2, …, y_N$
  • 高斯混合模型
• 输出
  • 高斯混合模型参数

• 流程

  1. 取参数初值

  2. E 步：根据当前模型参数，计算分模型 $k$ 对观测数据 $y_j$ 的响应度

     $\hat{\gamma}_{jk} = \frac{\alpha_k}\Phi(y_j \mid \theta_k){\sum\limits_{k=1}^K \alpha_k \Phi(y_j \mid \theta_k)}$ 其中： $j = 1, 2, …., N; k = 1, 2, …, K$

  3. M 步：计算新一轮迭代的模型参数：

     $$\begin{aligned} \hat{\mu_k} &= \frac{\sum\limits_{j=1}^N \hat{\gamma}_{jk} y_j}{\sum\limits_{j=1}^N \hat{\gamma}_{jk}} \\ \hat{\sigma}_k^2 &= \frac{\sum\limits_{j=1}^N \hat{\gamma}_{jk} (y_j - \mu_k)^2}{\sum\limits_{j=1}^N \hat{\gamma}_{jk}} \\ \hat{\alpha_k} &= \frac{\sum\limits_{j=1}^N \hat{\gamma}_{jk}}{N}\end{aligned}$$

     其中 $ k= 1,2,…, K$

  4. 重复 2、3，直到收敛