统计学习方法-第9章-EM算法

• 适用问题：概率模型参数估计
• 模型特点：含隐变量的概率模型
• 学习策略：极大似然估计，极大后验概率估计
• 损失函数：对数似然损失
• 学习算法：迭代算法

EM 算法精髓

EM 算法是通过不断求解下界得极大化逼近对数似然函数极大化得算法。

构造下界函数（Jessen 不等式），通过巧妙地取 Q 的值而保证在参数的当前迭代点处下界函数与要求解的目标函数数值相等（Jessen 不等式取等号），从而保证优化下界函数后在新的迭代处目标函数是上升的。

Q 函数

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

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

算法推导

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

\[L \left( \theta \right) = \log P \left( Y \mid \theta \right) = \log \sum_Z P \left( Y,Z \mid \theta \right) = \log \left( \sum_Z \left[ P \left( Y,Z \mid \theta \right) P \left( Z \mid \theta \right) \right] \right)\]

对于目标函数，若直接通过导数求解，对数内含有求和项，难以求解。若使用梯度下降法或牛顿法求解，则需保证隐变量满足等式 $\sum _ {z} p \left( z \right) = 1$ 和不等式 $p \left( z \right) \geq 0$，同样难以求解。

EM 算法通过迭代逐步近似极大化 $L \left( \theta \right)$。假设在第 $i$ 次迭代后 $\theta$ 的估计值是 $\theta^{\left( i \right)}$。我们希望新估计值 $\theta$ 能使 $L \left( \theta \right)$ 增加，即 $L \left( \theta \right) > L \left( \theta^{\left( i \right)} \right) $，并逐步达到极大值。

\[L \left( \theta \right) - L \left( \theta^{\left( i \right)} \right) = \log \left( \sum_Z \left[ P \left( Y \mid Z,\theta \right) P \left( Z \mid \theta \right) \right] \right)-\log P \left( Y \mid \theta^{\left( i \right)} \right) \quad \tag{9.1}\] \[= \color {green}{\log} \left( \sum _ {Z} \left[ \color {blue}{P \left( Z \mid Y , \theta ^ {( i )} \right)} \color {red}{\frac {P \left( Y \mid Z , \theta \right) P \left( Z \mid \theta \right)} {P \left( Z \mid Y , \theta ^ {( i )} \right)}} \right] \right) - \log P \left( Y \mid \theta ^ {( i )} \right) \quad \tag{9.2}\] \[\ge \sum_Z \left[ \color {blue}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)} \color {green}{\log} \color {red}{\frac{P \left( Y \mid Z,\theta \right) P \left(Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right)}} \right] - \log P \left(Y \mid \theta^{\left( i \right)} \right) \qquad \tag{9.3}\] \[= \sum_Z \left[ \color{blue}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)} \color{green}{\log} \color{red}{\frac{P \left( Y \mid Z,\theta \right) P \left( Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right)}} \right] - \color {orange}{\sum_Z} \left[ \color{blue}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)} \right] P \left( Y \mid \theta^{\left( i \right)} \right) \tag{9.4}\] \[= \sum_Z \left[ \color{blue}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)} \color{green}{\log} \color{red}{\frac{P \left( Y \mid Z,\theta \right) P \left( Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right)}} \right] - \color {orange}{\sum_Z} \left[ \color{blue}{P \left(Z \mid Y,\theta^{\left( i \right)} \right)} P \left( Y \mid \theta^{\left( i \right)} \right) \right] \tag{9.5}\] \[=\sum_Z P \left( Z \mid Y,\theta^{\left( i \right)} \right) \log \frac{P \left(Y \mid Z,\theta \right) P \left(Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right) P \left(Y \mid \theta^{\left( i \right)} \right)} \qquad \qquad \tag{9.6}\]

说明

• 9.2

  $\color{blue}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)}$ 表示在给定观测数据 $Y$ 和当前参数 $\theta^{\left( i \right)}$ 下对未观测数据 $Z$ 的条件概率分布

  \[\sum _ {Z} \left[ P \left( Z \mid Y,\theta^{\left( i \right)} \right) \frac{P \left(Y \mid Z,\theta \right) P \left( Z \mid \theta \right)}{P \left( Z \mid Y,\theta^{\left( i \right)} \right)} \right] = E_{Z} \left( \frac{P \left(Y \mid Z,\theta \right) P \left( Z \mid \theta \right)}{P \left( Z \mid Y,\theta^{\left( i \right)}\right)} \right)\]

  即函数 $\frac{P \left(Y \mid Z,\theta \right) P \left( Z \mid \theta \right)}{P \left( Z \mid Y,\theta^{\left( i \right)}\right)}$ 关于随机变量 $Z$ 的期望。

• 9.2 → 9.3

  Jessen 不等式（凹函数）：

  \[\color{green}{f} \left( \sum _ {j} \left[ \color{blue}{\lambda _ {j}} \color{red}{y _ {j}} \right] \right) \geq \sum _ {j} \left[ \color{blue}{\lambda _ {j}} \color {green}{f} \left( \color{red}{y _ {j}} \right) \right] \qquad \text{其中} \color{blue}{\lambda _ {j}} \geq 0 , \color {orange}{\sum _ {j}} \color{blue}{\lambda _ {j}} = 1\]

• 9.3 → 9.4

  \[\color{orange}{\sum_Z} \left[ \color{blue}{P \left(Z \mid Y,\theta^{\left( i \right)} \right)} \right] = 1\]

• 9.4 → 9.5

  $P \left( Y \mid \theta^{\left( i \right)} \right)$ 是与 $Z$ 无关相当于常数项。

令

\[B \left( \theta,\theta^{\left( i \right)} \right) = L \left( \theta^{\left( i \right)} \right) + \sum_Z P \left( Z \mid Y,\theta^{\left( i \right)} \right) \log \frac{P \left(Y \mid Z,\theta \right) P \left(Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right) P \left(Y \mid \theta^{\left( i \right)} \right)} \tag{9.7}\]

由 （9.1）和（9.6）得 $L \left( \theta \right) \geq B \left( \theta,\theta^{\left( i \right)} \right)$ 即函数 $B \left( \theta,\theta^{\left( i \right)} \right)$ 是 $L \left( \theta \right)$ 的一个下界，且 $B \left( \theta^{\left( i \right)},\theta^{\left( i \right)} \right) = L \left( \theta \right)$。因此，任何可以使 $B \left( \theta,\theta^{\left( i \right)} \right)$ 增大的 $\theta$，也可以使 $L \left( \theta \right)$ 增大。

为了使 $L \left( \theta \right)$ 有尽可能大的增长，选择 $\theta^{\left( i + 1\right)}$ 使 $B \left( \theta,\theta^{\left( i \right)} \right)$ 达到极大，即

\[\theta^{\left( i + 1\right)} = \arg \max_{\theta} B \left( \theta,\theta^{\left( i \right)} \right)\] \[= \arg \max_{\theta} \left( L \left( \theta^{\left( i \right)} \right) + \sum_Z P \left( Z \mid Y,\theta^{\left( i \right)} \right) \log \frac{P \left(Y \mid Z,\theta \right) P \left(Z \mid \theta \right)}{P \left(Z \mid Y,\theta^{\left( i \right)} \right) P \left(Y \mid \theta^{\left( i \right)} \right)} \right)\] \[= \arg \max_{\theta} \left( \sum_Z P \left( Z \mid Y,\theta^{\left( i \right)} \right) \log \left( P \left(Y \mid Z,\theta \right) P \left(Z \mid \theta \right) \right) \right)\] \[= \arg \max_{\theta} \left( \sum_Z P \left( Z \mid Y,\theta^{\left( i \right)} \right) \log P \left(Y,Z \mid \theta \right) \right)\] \[= \arg \max_{\theta} Q \left( \theta,\theta^{\left( i \right)} \right) \qquad \qquad \qquad \tag{9.8}\]

即 $\quad B \left( \theta,\theta^{\left( i \right)} \right) = Q \left( \theta,\theta^{\left( i \right)} \right) $。

式（9.8）等价于 EM 算法得一次迭代，即求 $Q$ 函数及其极大值。

似然函数 $L \left( \theta \right)$ 与下界 $B \left( \theta,\theta^{\left( i \right)} \right)$ 即 $Q \left( \theta,\theta^{\left( i \right)} \right)$，在 $\theta^{\left( i\right)}$ 处相等，$B \left( \theta,\theta^{\left( i \right)} \right)$ 在 $\theta^{\left( i+1 \right)}$ 处取极大值。似然函数 $L \left( \theta \right)$ 下一个迭代的点为 $\theta^{\left( i \right)}$。

算法过程

输入：观测变量数据 $Y$，隐变量数据 $Z$，联合分布 $P \left( Y, Z \mid \theta \right)$，条件分布 $P \left( Z \mid Y, \theta \right)$；

输出：参数模型 $\theta$。

1. 选择参数的初值 $\theta^{\left( 0 \right)}$，开始迭代

2. E 步：记 $\theta^{\left( i \right)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计值，在第 $i+1$ 次迭代的 $E$ 步，确定 Q 函数

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

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

   \[\theta^{\left(i+1 \right)} = \arg \max_\theta Q \left( \theta, \theta^{\left( i \right)} \right)\]