EM算法的引入

在概率模型中，有时既有观测变量，也有潜在变量，例如在文本挖掘中，具体的字词是观测变量，但是具体的字词背后的词性却是潜在变量。当潜在变量存在的时候，极大似然估计法或者贝叶斯估计模型参数就不能直接使用了，因此有必要使用EM算法。换句话说，EM算法是含有潜在变量的概率模型参数的极大似然估计或者极大后验概率估计。书中仅讨论了极大似然估计。

EM算法

算法

输入：观测变量数据Y，潜在变量数据Z，联合分布$P(Y,Z|\theta)$，条件分布$P(Z|Y,\theta)$。
输出：模型参数$\theta$。
(1) 选择参数的初值$\theta^{(0)}$，开始迭代
(2) E步：求期望
记$\theta^{(i)}$为第i次迭代参数$\theta$的估计值，在第i+1次迭代的E步，计算

$\begin{equation}\begin{split} Q(\theta, \theta^{(i)}) &= E_{Z}[logP(Y,Z|\theta)|Y,\theta^{(i)}]\\ &= \sum_{Z}logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{split}\end{equation}$

这里，$P(Z|Y,\theta^{(i)})$是在给定观测数据Y和当前的参数估计$\theta^{(i)}$下潜在变量数据Z的条件概率分布
(3) M步：求极大化
求是$Q(\theta, \theta^{(i)})$极大化的$\theta$，确定第i+1次迭代的参数的估计值$\theta^{(i+1)}$

$\theta^{(i+1)} = \mathop{argmax}_{\theta}Q(\theta,\theta^{(i)})$

(4) 重复第(2)步和第(3)步，直到收敛。

Q函数

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

$Q(\theta,\theta^{(i)}) = E_Z[logP(Y,Z|\theta)|Y,\theta^{(i)}]$

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

高斯混合模型

高斯混合模型指有如下形式的概率分布模型：

$P(y|\theta) = \sum_{k=1}^{K}\alpha_{k}\phi(y|\theta_k)$

其中，$\alphak$是系数，$\alpha_k \ge 0$，$\sum{k=1}^{K}{\alphak} = 1$，$\phi(y|\theta_k)$是高斯分布密度，$\theta_k=(\mu_k, \sigma{k}^{2})$，$\phi(y|\thetak) = \frac{1}{\sqrt{2\pi}\sigma_k}exp(-\frac{(y - \mu_k)^2}{2\sigma{k}^{2}})$。

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

输入：观测数据$y_1$,$y_2$,…,$y_N$，高斯混合模型；
输出：高斯混合模型参数。
(1) 选择参数的初值，开始迭代
(2) E步：求期望
根据当前模型参数，计算模型k对观测数据$y_j$的响应度

$\hat{\gamma}_{jk} = \frac{\alpha_k \phi(y_j|\theta_k)}{\sum_{k=1}^{K}{\alpha_k \phi(y_j|\theta_k)}}, j=1,2,...,N; k=1,2,...,K$

(3) M步：求极大化
计算新一轮迭代的模型参数

$\hat{\mu}_k = \frac{\sum_{j=1}^{N}{\hat{\gamma}_{jk}y_j}}{\sum_{j=1}^{N}{\hat{\gamma}_{jk}}}, k=1,2,...,K$ $\hat{\sigma}_{k}^{2} = \frac{\sum_{j=1}^{N}{\hat{\gamma}_{jk}{(y_j-\mu_k)}^2}}{\sum_{j=1}^{N}{\hat{\gamma}_{jk}}}, k=1,2,...,K$ $\hat{\alpha}_{k} = \frac{\sum_{j=1}^{N}{\hat{\gamma}_{jk}}}{N}, k=1,2,...,K$

(4) 重复第(2)步和第(3)步，直到收敛。

EM算法的推广

F函数的极大-极大算法

F函数

假设潜在变量数据Z的概率分布为$\widetilde{P}(Z)$，定义分布$\widetilde{P}$与参数$\theta$的函数$F(\widetilde{P},\theta)$如下：

$F(\widetilde{P},\theta) = E_{\widetilde{P}}[logP(Y,Z|\theta)] + H(\widetilde{P})$

称为F函数。式子中$H(\widetilde{P}) = -E_{\widetilde{P}}\log{\widetilde{P}(Z)}$是分布$\widetilde{P}(Z)$的熵

GEM算法

GEM算法1：
输入：观测数据，F函数
输出：模型参数。
(1) 选择参数的初值$\theta^{(0)}$，开始迭代
(2) 第i+1次迭代，第1步：记$\theta^{(i)}$为参数$\theta$的估计值，$\widetilde{P}^{(i)}$为函数$\widetilde{P}$的估计。求$\widetilde{P}^{(i+1)}$使$\widetilde{P}$极大化$F(\widetilde{P},\theta^{(i)})$
(3) 第2步：求$\theta^{(i+1)}$使$F(\widetilde{P}^{(i+1)},\theta)$极大化
(4) 重复第(2)步和第(3)步，直到收敛。

GEM算法2：
输入：观测数据，Q函数
输出：模型参数。
(1) 选择参数的初值$\theta^{(0)}$，开始迭代
(2) 第i+1次迭代，第1步：记$\theta^{(i)}$为参数$\theta$的估计值，计算

$\begin{equation}\begin{split} Q(\theta, \theta^{(i)}) &= E_{Z}[logP(Y,Z|\theta)|Y,\theta^{(i)}]\\ &= \sum_{Z}logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{split}\end{equation}$

(3) 第2步：求$\theta^{(i+1)}$使

$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$

(4) 重复第(2)步和第(3)步，直到收敛。

GEM算法3：
输入：观测数据，Q函数
输出：模型参数。
(1) 选择参数的初值$\theta^{(0)} = (\theta{1}^{(0)},\theta{2}^{(0)},…,\theta{d}^{(0)})$，开始迭代
(2) 第i+1次迭代，第1步：记$\theta^{(i)} = (\theta{1}^{(0)},\theta{2}^{(0)},…,\theta{d}^{(0)})$为参数$\theta = (\theta{1},\theta{2},…,\theta_{d})$的估计值，计算

$\begin{equation}\begin{split} Q(\theta, \theta^{(i)}) &= E_{Z}[logP(Y,Z|\theta)|Y,\theta^{(i)}]\\ &= \sum_{Z}logP(Y,Z|\theta)P(Z|Y,\theta^{(i)}) \end{split}\end{equation}$

(3) 第2步：进行d次条件极大化
首先，在$\theta{2}^{(i)},\theta{3}^{(i)},…,\theta{k}^{(i)}$保持不变的条件下，求使$Q(\theta,\theta^{(i)})$达到极大的$\theta{1}^{(i+1)}$
然后，在$\theta1 = \theta_1^{(i+1)}, \theta_j = \theta_j^{(i+1)}, j=3,4,…,k$的条件下求使$Q(\theta,\theta^{(i)})$达到极大的$\theta{2}^{(i+1)}$
如此继续，经过d次条件极大化，得到$\theta^{(i+1)} = (\theta{1}^{(i+1)},\theta{2}^{(i+1)},…,\theta_{d}^{(i+1)})$使得

$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$

(4) 重复第(2)步和第(3)步，直到收敛。