文章目录
  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 不等式

中点的函数值小于等于函数值的中点。

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

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

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

极大似然估计

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

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

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

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

算法流程

首先,根据样本 ${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^{j})}$ 如下,可以看成是引入的概率分布的迭代先后的交叉熵,而 ${L(\theta, \theta^{j})}$ 为对数似然函数的下界。

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

在上式中分别取 ${\theta}$ 为 ${\theta^{j}}$ 和 ${\theta^{j+1}}$,并相减得到:

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

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

那么可以得到如下结果:

既证明了 ${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