【机器学习】EM算法

前言

EM$EM$算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计。

EM$EM$算法的每次迭代由两步组成：

• E$E$步：求期望
• M$M$步：求极大

EM$EM$算法引入

首先介绍一个使用EM$EM$算法的例子：三硬币模型

假设有3枚硬币，分别记作A,B,C$A,B,C$，这些硬币正面出现的概率分别是π,p,q$\pi ,p,q$，进行如下试验：
先掷硬币A$A$根据其结果选出硬币B$B$或者硬币C$C$，正面选硬币B$B$，反面选硬币C$C$；然后掷出选出的硬币，出现正面记为1，反面记为0；独立地重复n$n$次试验（这里n$n$取10），观测结果如下：
1101001101
假设只能观测到掷硬币的结果，不能观测掷硬币的过程，问如何估计三个硬币正面出现的概率，即三硬币模型的参数。

三硬币模型可写为：

这里，随机变量x$x$是观测变量，表示一次试验观测的结果1或0；随机变量z$z$是隐变量，表示未观测到的掷硬币A$A$的结果；θ=(π,p,q)$\theta =(\pi ,p,q)$是模型参数。

下面将观测数据表示为X=(x1,x2,...,xn)T$X=(x_1,x_2,...,x_n{)}^T$，未观测数据表示为Z=(z1,z2,...,zn)T$Z=(z_1,z_2,...,z_n{)}^T$，则观测数据的似然函数为：

即：

考虑求模型参数θ=(π,p,q)$\theta =(\pi ,p,q)$的极大似然估计，取对数似然：

这个问题没有解析，只有通过迭代的方法来求解。EM$EM$算法就是可以用于求解这个问题的一种迭代算法。

EM$EM$算法通过迭代求L(θ)=log p(X|θ)$\mathcal{L}(\theta )=logp(X|\theta )$的极大似然估计。每次迭代包含两步：
E步：求期望；M步：求极大化。

EM$EM$算法

输入： 观测变量数据X$X$，隐变量数据Z$Z$，联合分布p(X,Z|θ)$p(X,Z|\theta )$，条件分布p(Z|X,θ)$p(Z|X,\theta )$;

输出：模型参数θ$\theta$

（1）选择参数的初值θ(0)${\theta }^{(0)}$，开始迭代；
（2）E步：记θ(i)${\theta }^{(i)}$为第i$i$次迭代参数θ$\theta$的估计值，在第i+1$i+1$次迭代的E步，计算：

这里，p(Z|X,θ(i))$p(Z|X,{\theta }^{(i)})$表示在给定观测数据X$X$和当前的参数估计θ(i)${\theta }^{(i)}$下隐变量数据Z$Z$的条件概率分布；
（3）M步：求使Q(θ,θ(i))$Q(\theta ,{\theta }^{(i)})$极大化的θ$\theta$，确定第i+1$i+1$次迭代的参数估计值θ(i+1)${\theta }^{(i+1)}$

（4）重复第（2）步和第（3）步，直到收敛。

注：
函数Q(θ,θ(i))$Q(\theta ,{\theta }^{(i)})$是EM$EM$算法的核心，称为Q函数。
参数的初值可以任意选择，但EM$EM$算法对初值是敏感的
Q(θ,θ(i))$Q(\theta ,{\theta }^{(i)})$中θ$\theta$表示要极大化的参数，θ(i)${\theta }^{(i)}$表示当前估计值，每次迭代实际在求Q函数及其极大化
M步求Q函数的极大化，得到θ(i+1)${\theta }^{(i+1)}$，完成一次迭代
第（4）步给出停止迭代的条件，一般是对较小的正数E1,E2${\mathcal{E}}_1,{\mathcal{E}}_2$，若满足：

||θ(i+1)−θ(i)||⩽E1,或||Q(θ(i+1),θ(i))−Q(θ(i),θ(i))||⩽E2$$||{\theta }^{(i+1)}-{\theta }^{(i)}||⩽{\mathcal{E}}_1,或||Q({\theta }^{(i+1)},{\theta }^{(i)})-Q({\theta }^{(i)},{\theta }^{(i)})||⩽{\mathcal{E}}_2$$

则停止迭代。

导出EM$EM$算法

上面我们给出了EM$EM$算法，那么为什么EM$EM$算法能近似实现对观测数据的极大似然估计呢？下面通过近似求解观测数据的对数似然函数的极大化问题来导出EM$EM$算法。

由上面内容可以知道，极大化观测数据X$X$关于参数θ$\theta$的对数似然函数，即极大化：

注意到：上式中有未观测数据并包含和的对数

事实上，EM$EM$算法通过迭代逐步近似极大化L(θ)$\mathcal{L}(\theta )$的。

假设在第i$i$次迭代后θ$\theta$的估计值是θ(i)${\theta }^{(i)}$，我们希望新估计值θ$\theta$能使L(θ)$\mathcal{L}(\theta )$增加，即L(θ)>L(θ(i))$\mathcal{L}(\theta )>\mathcal{L}({\theta }^{(i)})$，并逐步达到极大值，为此考虑两者的差：

利用Jensen$Jensen$不等式，得到其下界：

log∑jλjyi⩾∑jλjlog yj$$log\sum _j{\lambda }_j{y}_i⩾\sum _j{\lambda }_{j}log{y}_j$$

其中λj⩾0,∑jλj=1${\lambda }_j⩾0,\sum _j{\lambda }_j=1$

令：

则：

即函数B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$是L(θ)$\mathcal{L}(\theta )$的一个下届，因此任何使B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$增大的θ$\theta$都会使L(θ)$\mathcal{L}(\theta )$的下届增大，也即使L(θ)$\mathcal{L}(\theta )$增大，为了使L(θ)$\mathcal{L}(\theta )$尽可能的大，自然选择使B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$达到最大的θ(i+1)${\theta }^{(i+1)}$，即：

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

EM$EM$算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法。

上图给出EM$EM$算法的直观解释。图中上方曲线为L(θ)$\mathcal{L}(\theta )$，下方曲线为B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$，图中两个函数在点θ=θ(i)$\theta ={\theta }^{(i)}$处相等，但此时L(θ)$\mathcal{L}(\theta )$并没用达到极大值，这时使B(θ,θ(i))$B(\theta ,{\theta }^{(i)})$极大化，由于L(θ)⩾B(θ,θ(i))$\mathcal{L}(\theta )⩾B(\theta ,{\theta }^{(i)})$，所以L(θ)$\mathcal{L}(\theta )$在每次迭代中也是增加的。
在这个过程中，L(θ)$\mathcal{L}(\theta )$不断增大，从图中可以看出EM$EM$算法不能保证找到全局最优解。

使用迭代必须保证p(X|θ(i)）$p(X|{\theta }^{(i)}）$单调递增：

证明：
由：

得到：

求期望，连续变量即求积分，离散变量即求和，上面我们用的都是求和，这个使用求积分，是为了让大家理解上面求和符号怎么来的。

上式左端：

上式右端：

上式减号左边的式子与上面θ(i+1)${\theta }^{(i+1)}$中的式子一样，我们将其设为Q(θ,θ(i))$Q(\theta ,{\theta }^{(i)})$，减号后面一项设为H(θ,θ(i))$H(\theta ,{\theta }^{(i)})$

那么对数似然函数（等式）可写为：

因为求得是极大似然函数估计，那么Q(θ(i+1),θ(i))⩾Q(θ,θ(i))$Q({\theta }^{(i+1)},{\theta }^{(i)})⩾Q(\theta ,{\theta }^{(i)})$；

假如对于所有的θ$\theta$都有H(θ(i),θ(i))⩾H(θ,θ(i))$H({\theta }^{(i)},{\theta }^{(i)})⩾H(\theta ,{\theta }^{(i)})$
=> 那么H(θ(i),θ(i))⩾H(θ(i+1),θ(i))$H({\theta }^{(i)},{\theta }^{(i)})⩾H({\theta }^{(i+1)},{\theta }^{(i)})$

这样一来，对数似然函数就会逐渐增大。

那么我们又该如何证明对于所有的θ$\theta$都有H(θ(g),θ(g))⩾H(θ,θ(g))$H({\theta }^{(g)},{\theta }^{(g)})⩾H(\theta ,{\theta }^{(g)})$

证明：

利用Jensen$Jensen$不等式（函数的期望大于等于期望的函数）：

总结

1. EM$EM$算法对初值比较敏感，初值的选择非常重要，通常选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。

2. 一般条件下EM$EM$算法是收敛的，但不能保证收敛到全局最优

参考资料：
李航《统计学习方法》