EM算法

作者: 单调不减 | 来源:发表于2019-06-10 15:56 被阅读0次

EM算法作为数据挖掘领域十大经典算法之一，在统计学习领域也有诸多应用。EM算法（Expectation-maximization algorithm，期望极大算法）在统计中被用于寻找依赖于不可观察的隐性变量的概率模型中参数的最大似然估计。

期望极大算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是极大化（M），极大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

1、EM算法引入

在引入EM算法之前，我们先回顾一下最大似然估计方法。

(https://web.stanford.edu/class/cs109/lectureNotes/21%20-%20MLE.pdf)

最大似然法（MLE）的思想很朴素，首先假设参数为 $\theta$ ，然后写出在 $\theta$ 下生成当前各独立样本的可能性（Likelihood），上图解释了这里的Likelihood是什么含义——联合概率（离散）或联合概率密度（连续）。然后我们求使得这个Likelihood最大的参数值 $\theta$ 作为我们的参数估计。

最大似然法可以发挥作用的隐含前提是我们可以观测到各独立样本，且这些样本就是从服从依赖于 $\theta$ 的分布中生成的。

那么EM算法是用来解决什么问题呢？EM算法用来解决既含有观测变量又含有隐变量或潜在变量的参数估计问题。所谓隐变量，就是无法直接观测到的变量，但它又与可观测变量的生成密切相关，比如混合高斯模型中某个变量（样本）属于各个高斯成分的概率就是隐变量。《统计学习方法》中举了一个很生动的例子：

假设有3枚硬币，分别记作A，B，C。这些硬币正面出现的概率分别是 $\pi$ ，p和q。进行如下掷硬币试验：先掷硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后掷选出的硬币，掷硬币的结果出现正面记作1，出现反面记作0；独立地重复n次试验（这里，n＝10），观测结果如下：

$1,1,0,1,0,0,1,0,1,1$

假设只能观测到掷硬币的结果，不能观测掷硬币的过程。问如何估计三硬币正面出现的概率，即三硬币模型的参数。

下面我们试着写出其似然函数。记 $\theta=(\pi,p,q)$ 是模型参数， $y$ 是观测变量，表示一次实验的观测结果是1或0， $z$ 是隐变量，表示为观测到的掷硬币 $A$ 的结果。则Likelihood可写作：

$\begin{aligned} P(y|\theta)&=\sum_{z}P(y,z|\theta)=\sum_{z}P(z|\theta)P(y|z,\theta)\\ &=\pi p^y(1-p)^{1-y}+(1-\pi)q^y(1-q)^{1-y}\\ \end{aligned}$

观测数据 $Y＝(Y_1,Y_2,\dots,Y_n)^T$ 未观测数据 $Z＝(Z_1,Z_2,\dots,Z_n)^T$ 则观测数据的似然函数为：

$\begin{aligned} P(Y|\theta)&=\Pi_{j=1}^nP(y|\theta)\\ &=\Pi_{j=1}^n[\pi p^{y_j}(1-p)^{1-y_j}+(1-\pi)q^{y_j}(1-q)^{1-y_j}] \end{aligned}$

《统计学习方法》一书上说这个似然函数的极大似然估计是没有解析解的，因此我们就需要用更巧妙的方法来逼近这个解。EM算法就是通过逼近的过程来解决这样的问题。

2、EM算法导出

现在我们把问题从三硬币问题中抽象出来： $Y$ 表示观测变量， $Z$ 表示隐随机变量， $Y$ 和 $Z$ 一起称为完全数据， $Y$ 称为不完全数据。 $\theta$ 表示模型参数。给定观测数据 $Y$ ，我们的目标是极大化 $Y$ 关于参数 $\theta$ 的对数似然函数，即极大化：

$L(\theta)=logP(Y|\theta)=log\sum_Z P(Y,Z|\theta)=log(\sum_Z P(Y|Z,\theta)P(Z|\theta))$

这一极大化的主要困难在于：

上式中有未观测数据
上式中包含和（或积分）的对数

既然不能直接极大化似然函数，那么我们就希望可以通过某种迭代的方式使得 $L(\theta)$ 不断增大。假设在第 $i$ 次之后的 $\theta$ 估计值为 $\theta^{(i)}$ ，则我们希望新估计值 $\theta$ 满足：

$L(\theta)>L(\theta^{(i)})$

为此，考虑两者之差并利用Jensen不等式得到其下界：

$\begin{aligned} L(\theta)-L(\theta^{(i)}) &=log(\sum_Z P(Z|Y,\theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})})-logP(Y|\theta^{(i)})\\ &\geq \sum_Z P(Z|Y,\theta^{(i)})log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}-logP(Y|\theta^{(i)})\\ &=\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ \end{aligned}$

从而有：

$L(\theta)\geq L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$

定义这个下界为：

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

则有：

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

若我们取 $\theta=\theta^{(i)}$ 可以得到：

$\begin{aligned} B(\theta^{(i)},\theta^{(i)})&=L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y|Z,\theta^{(i)})P(Z|\theta^{(i)})}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\\ &=L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)}))log\frac{P(Y,Z|\theta^{(i)})}{P(Y,Z|\theta^{(i)})}=L(\theta^{(i)})\\ \end{aligned}$

因此任何可以使 $B(\theta,\theta^{(i)})$ 增大的 $\theta$ ，都可以使 $L(\theta)$ 增大。为了使 $L(\theta)$ 有尽可能大的增长，我们应该选择使得 $B(\theta,\theta^{(i)})$ 达到极大的值，即：

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

下面我们省去对 $\theta$ 的极大化而言是常数的项：

$\begin{aligned} \theta^{(i+1)}&=arg \max_{\theta} (L(\theta^{(i)}+\sum_Z P(Z|Y,\theta^{(i)})log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})})\\ &=arg \max_{\theta}(\sum_Z P(Z|Y,\theta^{(i)})logP(Y|Z,\theta)P(Z|\theta))\\ &=arg \max_{\theta}(\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta))\\ \end{aligned}$

我们定义 $Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$ ，则：

$\theta^{(i+1)}=arg \max_{\theta} Q(\theta,\theta^{(i)})$

从而我们就可以迭代地更新参数 $\theta$ ，使得对数似然函数 $L(\theta)$ 不断增大。总结成EM算法如下：

（1）选择模型参数初始值 $\theta^{(0)}$
（2）E步：计算 $Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
（3）M步： $\theta^{(i+1)}=arg \max_{\theta} Q(\theta,\theta^{(i)})$
（4）重复E步M步直至收敛。

我们看到（4）默认了EM算法的收敛性，下面我们来证明这一点。

3、EM算法的收敛性

为了证明EM算法的收敛性，我们首先说明由EM算法估计得到的似然函数序列 $P(Y|\theta^{(i)})$ 是单调递增的，即：

$P(Y|\theta^{(i+1)})\geq P(Y|\theta^{(i)})$

由

$P(Y|\theta)=\frac{P(Y,Z|\theta)}{P(Z|Y,\theta)}$

取对数有

$\log P(Y|\theta)=\log P(Y,Z|\theta)-\log P(Z|Y,\theta)$

令

$Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Y,Z|\theta)$
$H(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})logP(Z|Y,\theta)$

则对数似然函数可以写成：

$\log P(Y|\theta)=Q(\theta,\theta^{(i)})-H(\theta,\theta^{(i)})$

从而

$\begin{aligned} & \log P(Y|\theta^{(i+1)})-log P(Y|\theta^{(i)})\\ & =[Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})]-[H(\theta^{(i+1)},\theta^{(i)})-H(\theta^{(i)},\theta^{(i)})] \end{aligned}$

我们知道 $\theta^{(i+1)}$ 使得 $Q(\theta,\theta^{(i)})$ 达到极大，因此

$Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})\geq 0$

又

$\begin{aligned} &H(\theta,\theta^{(i+1)})-H(\theta,\theta^{(i)})\\ &=\sum_Z P(Z|Y,\theta^{(i)})log(\frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})})\\ & \leq log(\sum_Z \frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})}P(Z|Y,\theta^{(i)}))\\ &=log(\sum_Z P(Z|Y,\theta^{(i+1)}))\\ &=0 \end{aligned}$

故

$logP(Y|\theta^{(i+1)})-logP(Y|\theta^{(i)})\geq 0$

因此，如果 $P(Y|\theta^{(i)})$ 有上界，则 $L(\theta^{(i)})=logP(Y|\theta^{(i)})$ 收敛到某个值 $L^*$ 。

EM算法

1、EM算法引入

2、EM算法导出

3、EM算法的收敛性

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读