EM算法

EM算法优化的目标是观测数据对参数$\theta$的对数似然函数，如果不存在隐变量的话，可以直接用最大似然法估计，在隐变量存在的情况下，使用EM算法进行迭代估计。本篇是当时学李航的统计学习方法写下的笔记，可能有理解不正确的地方。

EM算法重要之处在于传统的语音识别框架中，HMM和GMM的参数学习是靠EM完成的。

在$MLE$（最大似然估计）中，最大化目标函数

$$P(Y|\Theta) \tag{1}$$

的参数估计，可以通过下式得到

$$\begin{align} \Theta_{MLE} & = \underset{\Theta}{\arg \max}L(\Theta) \notag \\ & = \underset{\Theta}{\arg \max}\prod_YP(Y|\Theta) \tag{2} \end{align}$$

但是在观测不全面的情况下，比如只观测到了训练数据$Y$，为了优化$(1)$中的目标，还需要知道一些隐变量$X$，否则无法进行全面的估计。对于完全数据$(X, Y)$

$$P(X,Y|\Theta) = P(X|Y,\Theta) \cdot P(Y|\Theta) \tag{3}$$

上面已经提到，我们的目标是优化$(1)$，则

$$\log P(Y|\Theta) = \log P(X,Y|\Theta) - \log P(X|Y,\Theta) \tag{4}$$

如果我们现在已知分布参数$\Theta^t$，用它计算$P(Y|\Theta)$在$X$上条件分布的期望

$$\log P(Y|\Theta) = \sum_x \log P(Y|\Theta) \cdot P(X|Y,\Theta^t) \\ = Q(\Theta, \Theta^t) - H(\Theta, \Theta^t)$$

令

$$Q(\Theta,\Theta^t) = \sum_x \log P(X,Y|\Theta) \cdot P(X|Y,\Theta^t) \\ H(\Theta,\Theta^t) = \sum_x \log P(X|Y,\Theta) \cdot P(X|Y,\Theta^t)$$

EM算法的收敛性

EM算法找出

$$\Theta^{t + 1} = \underset{\Theta}{argmax}Q(\Theta, \Theta^t) \tag{8}$$

进行下一轮迭代，收敛性需证明：

$$logP(Y|\Theta^{t + 1}) - \log P(Y|\Theta^t) \ge 0 \tag{9}$$

由$(8)$，已知：

$$Q(\Theta^{t + 1}, \Theta^t) - Q(\Theta^{t}, \Theta^t) \ge 0 \tag{10}$$

只需

$$H(\Theta^{t + 1}, \Theta^t) - H(\Theta^{t}, \Theta^t) \le 0 \tag{11}$$

证明:

$$\begin{align} (11) &= \sum_x \log\frac{P(X|Y,\Theta^{t + 1})}{P(X|Y,\Theta^{t})} \cdot P(X|Y,\Theta^t) \notag \\ & \le \log\sum_x\frac{P(X|Y,\Theta^{t + 1})}{P(X|Y,\Theta^{t})}P(X|Y,\Theta^t) \notag \\ & = \log\sum_xP(X|Y,\Theta^{t + 1}) = 0 \notag \\ \end{align}$$

证明过程使用了Jesson不等式

$Q$函数

$Q$函数是完全数据的对数似然函数关于在观测数据$Y$和已知参数$\Theta^t$对未观测数据$X$的条件分布$P(X|Y,\Theta^t)$的期望，定义如下：

$$Q(\Theta, \Theta^t) = E_X\left[\log P(X,Y|\Theta) | Y, \Theta^t\right]$$

对$Q$函数展开，写成

$$Q(\Theta, \Theta^t) = \sum_X \log P(X,Y|\Theta)P(X|Y,\Theta^t)$$

对于$P(X|Y,\Theta^t)$，理解成隐变量在模型参数$\Theta^t$和观测$Y$下的概率。

推到这里还是比较抽象，下面继续就EM算法在HMM，GMM中的应用做相关说明，这个应该就比较具象了。