原理

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

\[\begin{align} L(\theta) &= log P(Y \mid \theta) = log \sum_Z P(Y,Z \mid \theta)\\ &= log(\sum_Z P(Y \mid Z, \theta) P(Z \mid \theta)) \\ \end{align}\]

注意到这一极大化的主要困难是上式中有未观测数据并有包含和（或积分）的对数。

事实上，EM算法是通过迭代逐步近似极大化\(L(\theta)\)的。假设在第i次迭代后\(\theta\)的估计值是\(\theta^{(i)}\)。我们希望新估计值\(\theta\)能使\(L(\theta)\)增加，即\(L(\theta) > L(\theta^{(i)})\)，并逐步达到极大值。为此，考虑两者的差值：

\[L(\theta) - L(\theta^{(i)}) = log(\sum_Z P(Y \mid Z, \theta) P(Z \mid \theta)) - log P(Y \mid \theta^{(i)})\]

利用Jensen不等式（\(log \sum_j \lambda_j y_j \geq \lambda_j log y_j,其中\lambda_j \geq 0, \sum_j \lambda_j =1\)）得到其下界：

\[\begin{align} L(\theta) - L(\theta^{(i)}) &= log(\sum_Z P(Y \mid Z, \theta^{(i)}) \frac{P(Y \mid Z,\theta)P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})}) - log P(Y \mid \theta^{(i)}) \\ &\geq \sum_Z P(Z \mid Y, \theta^{(i)}) log\frac{P(Y \mid Z,\theta)P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})} - log P(Y \mid \theta^{(i)}) \\ &= \sum_Z P(Z \mid Y, \theta^{(i)}) log\frac{P(Y \mid Z,\theta)P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})P(Y \mid \theta^{(i)})} \\ \end{align}\]

令\(B(\theta,\theta^{(i)}) = L(\theta^{(i)}) + \sum_Z P(Z \mid Y, \theta^{(i)}) log\frac{P(Y \mid Z,\theta)P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})P(Y \mid \theta^{(i)})}\)

则

\[L(\theta) \geq B(\theta,\theta^{(i)})\]

即函数\(B(\theta,\theta^{(i)})\)是\(L(\theta)\)的一个下界，且由\(B(\theta,\theta^{(i)})\)的定义可知，

\[L(\theta^{(i)}) = B(\theta^{(i)},\theta^{(i)})\]

因此，任何可以使\(B(\theta,\theta^{(i)})\)增大的\(\theta\)，也可以使\(L(\theta)\)增大，为了使\(L(\theta)\)有尽可能大的增长，选择\(\theta^{(i+1)}\)使\(B(\theta,\theta^{(i)})\)极大，即

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

现在求\(\theta^{(i+1)}\)的表达式，省去对\(\theta\)极大化而言是常数的项，有

\[\begin{align} \theta^{(i+1)} &= arg max_\theta (L(\theta^{(i)}) + \sum_Z P(Z \mid Y, \theta^{(i)}) log\frac{P(Y \mid Z,\theta)P(Z \mid \theta)}{P(Y \mid Z, \theta^{(i)})P(Y \mid \theta^{(i)})}) \\ &= arg max_\theta (L(\theta^{(i)}) + \sum_Z P(Z \mid Y, \theta^{(i)}) log (P(Y \mid Z,\theta)P(Z \mid \theta))) \\ &= arg max_\theta (L(\theta^{(i)}) + \sum_Z P(Z \mid Y, \theta^{(i)}) log (P(Y,Z \mid \theta)) \\ &= arg max_\theta Q(\theta,\theta^{(i)}) \\ \end{align}\]

上式等价于EM算法的一次迭代，即求Q函数及其极大化。EM算法是通过不断求解下界的极大化逼近求解似然函数极大化的算法。

EM算法在非监督学习中的应用

有时候训练数据只有输入没有对应的输出\({(x_1, \bullet), (x_2, \bullet), ..., (x_N, \bullet)}\)，从这一的数据学习模型称为非监督学习问题。EM算法可以用于生成模型的非监督学习。生成模型由联合概率分布\(P(X,Y)\)表示，可以认为非监督学习训练数据是联合概率分布产生的数据。X为观测数据，Y为未观测数据。

EM算法是收敛性

EM算法提供一种近似计算含有隐变量概率模型的极大似然估计的方法。EM算法的最大优点是简单性和普适性。我们很自然地要问：EM算法得到的估计序列是否收敛？如果收敛，是否收敛到全局最大值或局部极大值？

定理1 设\(P(Y\mid \theta)\)为观测数据的似然函数，\(\theta^{(i)} (i=1,2,...)\)为EM算法得到的参数估计序列，\(P(Y\mid \theta^{(i)})(i=1,2,...)\)为对应的似然函数序列，则\(P(Y\mid \theta^{(i)})\)是单调递增的，即

\[P(Y\mid \theta^{(i+1)}) \geq P(Y\mid \theta^{(i)})\]

定理2 设\(L(\theta) = log P(Y\mid \theta)\)为观测数据的对数似然函数，\(\theta^{(i)} (i=1,2,...)\)为EM算法得到的参数估计序列，\(L(\theta^{(i)})(i=1,2,...)\)为对应的对数似然函数序列。

(1) 如果\(P(Y \mid \theta)\)有上界，则\(L(\theta^{(i)}) = log P(Y\mid \theta^{(i)})\)收敛到某一值\(L^*\)。

(2) 在函数\(Q(\theta, \theta')\)与\(L(\theta)\)满足一定条件下，由EM算法得到的参数估计序列\(\theta^{(i)}\)的收敛值\(\theta^*\)是\(L(\theta)\)的稳定点。

定理2关于函数\(Q(\theta, \theta')\)与\(L(\theta)\)的条件在大多数情况下都是满足的。EM算法的收敛性包含关于对数似然函数序列\(L(\theta^{(i)})\)的收敛性和关于参数估计序列\(\theta^{(i)}\)的收敛性两层意思，前者并不蕴含后者。此外，定理只能保证参数估计序列收敛到对数似然函数序列的稳定点，不能保证收敛到极大值点。所以在应用中，初值的选择变得非常重要，常用的办法是选取几个不同的初值进行迭代，然后对得到的各个估值加以比较，从中选择最好的。

参考文献

  • 统计学习方法 李航 第9章