文章目录
  1. 1. Expectation Maximization
    1. 1.1. Jensen 不等式
    2. 1.2. 极大似然估计
    3. 1.3. 算法流程
    4. 1.4. 收敛性
    5. 1.5. 总结
    6. 1.6. References

Expectation Maximization

期望最大化(EM)算法是一种被广泛应用于极大似然估计的迭代型计算方法,对处理大量数据不完整问题十分有效。

Jensen 不等式

${E[f(X)] \geq f(E[X])}$

设 ${f}$ 是定义域为实数的函数,如果对于所有的实数 ${x}$。如果对于所有的实数 ${x}$ ,${f(x)}$ 的二次导数大于等于 ${0}$,那么 ${f}$ 是凸函数。Jensen 不等式表述如下:如果 ${f}$ 是凸函数,${X}$ 是随机变量,那么:

当且仅当 ${X}$ 是常量时,上式取等号;通俗来讲:“函数值的期望大于等于期望的函数值”,凸函数的特性如下:

或者更一般地,两点的连线在曲线的上方或者相等。

极大似然估计

参数估计的一种方式,也是生成模型的原理。根据现有的样本数据,找出使其发生概率最大的模型及其参数。

样本数据,${x=(x^{(1)},x^{(2)},\ldots,x^{(m)})}$ 中,找出样本的模型参数 ${\theta}$, 对数似然函数如下:

我们将极大似然函数取对数,这样可以将连乘转换成连加,单调性也不会改变。

求得使似然函数达到最大值的 ${\theta}$,通过求导使导函数为 ${0}$。

算法流程

内求期望,外求最大化。

EM 算法是一种迭代式求最优解的方式,由于是迭代的方式,当前步的参数值是前一步参数值的函数,即 ${\theta^{(t+1)} = f(\theta^{(t)})}$。

如果 EM 能够收敛到最优解,那么 ${\log P(x|\theta^{(t+1)}) \ge \log P(x|\theta^{(t)})}$,由于在迭代的过程中,保持递增,而似然函数肯定是有最大值,根据 “单调有界,级数收敛”,说明 EM 算法能够收敛到最优解,即使得似然函数取得最大值的参数 ${\theta_{MLE}}$。以当前的隐变量的概率分布为权重,对已观测变量与未观测变量的联合概率分布求期望,最后通过积分消掉隐变量,得到极大似然函数

首先,根据样本 ${x=(x^{(1)}, x^{(2)}, \ldots, x^{(m)})}$,得到极大似然函数:

如果我们得到的观察数据有未观察到的隐含数据 ${z=(z^{(1)},z^{(2)},\ldots,z^{(m)})}$,此时需要极大化的对数似然函数如下:

由于上式无法直接求出 ${\theta}$ 的。所以需要一些特殊的技巧,则首先对这个式子进行如下的放缩:

在上式中,引入了一个未知的新的分布 ${Q_i(z^{(i)})}$,其中 ${\sum{Q_{i}(z^{(i)})[\frac{P(x^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})}]}}$ 为 ${\frac{P(x^{(i)},z^{(i)}|\theta)}{Q_{i}(z^{(i)})}}$ 关于 ${Q_{i}(z^{(i)})}$ 的期望,其中用到了 Jensen 不等式(${\log}$ 函数为凸函数)。上式若要取等,则必须满足下面的等式成立:

其中,${c}$ 为一个固定常数,由于引入的新的分布 ${Q_i(z^{(i)})}$ 在本质上是一个概率,所以有概率之和为一;在满足上面两式的情况下,得知 ${P(x^{(i)},z^{(i)}|\theta)}$ 正比于 ${Q_{i}(z^{(i)})}$,然而概率之和需要等于一,所以分母添加一个归一化的因子,既得到了下面的式子:

引入的分布为 ${P(z^{(i)}|x^{(i)}|\theta)}$。最后,要极大化似然估计 ${L(\theta)}$ 最大,可以通过不断最大化下界 ${J}$, 使其不断提高,来使得 ${L(\theta)}$ 达到最大值。

  • E - step:根据参数 ${\theta}$ 初始值或上一次迭代所得参数值来计算出隐变量的后验概率(即隐变量的期望),作为隐变量的现估计值:
  • M - step:将似然函数最大化以获得新的参数值。

收敛性

单调有界,级数收敛。

由于对数似然函数是有最大值的,${EM}$ 算法不断迭代,如果可以证明每次迭代都大于等于上一次的迭代值,那么根据微积分中级数的相关定理,单调有界,级数收敛。则 ${EM}$ 算法最终会收敛到对数似然函数的最大值,即证明如下等式:

假设 ${H(\theta, \theta^{(t)})}$ 如下,可以看成是引入的概率分布的迭代先后的交叉熵,而 ${L(\theta, \theta^{(t)})}$ 为对数似然函数的下界。

上面两个式子相减可以得到:

如果随着迭代步数 ${t}$ 的增加,${L}$ 在不断增大,${H}$ 在断减小。那么似然函数的值也会在增大。${L}$ 函数可以理解为,以当前参数和观测数据下未观测变量的概率分布 ${p(Z|X, \theta^{(t)})}$ 为权重,求得观测变量和未观测变量的联合概率分布 ${p(X,Z|\theta)}$ 的期望,最后对为观测变量 ${Z}$ 进行积分,得到 ${p(X|\theta)}$,正是极大似然的目标,则保证了 ${L}$ 函数在增加。在上式中分别取 ${\theta}$ 为 ${\theta^{(t)}}$ 和 ${\theta^{(t+1)}}$,并相减得到:

要证明 ${EM}$ 算法的收敛性,我们只需要证明上式是非负的即可。由于在每次的迭代的过程当中,${\theta^{(t+1)}}$ 使得 ${L(\theta,\theta^{(t)})}$ 极大,因此有:

其次,同样适用到了 Jensen 不等式(${\log}$ 函数为凸函数)。

$
H(\theta^{(t+1)}, \theta^{(t)}) - H(\theta^{(t)}, \theta^{(t)}) = \sum_{i=1}^{m} \sum_{z^{(i)}} P(z^{(i)}|x^{(i)},\theta^{(t)}) \log \frac{P(z^{(i)}|x^{(i)}, \theta^{(t+1)})}{P(z^{(i)}|x^{(i)},\theta^{(t)})}
$

$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq \sum_{i=1}^{m} \log \left(\sum_{z^{(i)}}P(z^{(i)}|x^{(i)}, \theta^{(t)})\frac{P(z^{(i)}|x^{(i)}, \theta^{(t+1)})} {P(z^{(i)}|x^{(i)},\theta^{(t)})} \right)
$

$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{i=1}^{m} \log \left(\sum_{z^{(i)}}P(z^{(i)}|x^{(i)}, \theta^{(t+1)}) \right)
$

$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{i=1}^{m} \log 1 = 0
$

说明迭代到第 ${t}$ 次的时候,发现 ${H}$ 达到最大值,则证明了 ${H(\theta, \theta^{(t)})}$ 在减小。如果 ${L}$ 在增大,则极大似然函数值在增大。所以,EM 算法会收敛至最优解。那么可以得到如下结果:

既证明了 ${EM}$ 算法的收敛性。

总结

${EM}$ 算法作为一种迭代式收敛的算法,根据已知的观测数据,并且含有隐含的变量参数,${E-step}$ 与 ${M-step}$ 可以看成两者相互极大似然的过程。

References

  1. EM算法原理总结
  2. 《数学之美》
  3. 《百面机器学习》
  4. 《数据挖掘十大算法》
  5. (EM算法)The EM Algorithm
  6. EM算法(Expectation Maximization Algorithm)详解
  7. 【机器学习】EM算法详细推导和讲解
文章目录
  1. 1. Expectation Maximization
    1. 1.1. Jensen 不等式
    2. 1.2. 极大似然估计
    3. 1.3. 算法流程
    4. 1.4. 收敛性
    5. 1.5. 总结
    6. 1.6. References