美文网首页统计、学习
期望最大算法(EM)

期望最大算法(EM)

作者: KyoDante | 来源:发表于2020-10-08 16:25 被阅读0次

EM算法

历史

1977年，DempSter首次提出EM算法。

例子（感受隐变量）

假设四种实验结果，发生的概率依次为\frac{1}{2}-\frac{\theta}{4},\frac{1}{4}-\frac{\theta}{4},\frac{1}{4}+\frac{\theta}{4},\frac{\theta}{4}，且发生的次数为y_1,y_2,y_3,y_4，求\theta的估计。
解：使用MLE，得到：

L(\theta)=(\frac{1}{2}-\frac{\theta}{4})^{y_1}(\frac{1}{4}-\frac{\theta}{4})^{y_2} (\frac{1}{4}+\frac{\theta}{4})^{y_3}(\frac{\theta}{4})^{y_4}

\Rightarrow lnL(\theta)=y_1ln\frac{2-\theta}{4}+y_2ln\frac{1-\theta}{4}+y_3ln\frac{1+\theta}{4}+y_4ln\frac{\theta}{4}

\Rightarrow \frac{dlnL(\theta)}{d\theta}=-\frac{y_1}{2-\theta}-\frac{y_2}{1-\theta}+\frac{y_3}{1+\theta}+\frac{y_4}{\theta}=0

上式是关于\theta的一元三次方程，不易解。

因此，以下另作处理（引入隐变量）：

将第一部分\frac{1}{2}-\frac{\theta}{4}分为\frac{1}{4}-\frac{\theta}{4},\frac{1}{4}，且出现次数为z_1,y_1-z_1次

将第三部分\frac{1}{4}+\frac{\theta}{4}分为\frac{\theta}{4},\frac{1}{4}，且出现次数为z_2,y_3-z_2次；

则 L(\theta)=(\frac{1}{4}-\frac{\theta}{4})^{z_1+y_2}(\frac{\theta}{4})^{z_2+y_4}(\frac{1}{4})^{y_1-z_1+y_3-z_2}

\Rightarrow lnL(\theta)=(z_1+y_2)ln\frac{1-\theta}{4}+(z_2+y_4)ln\frac{\theta}{4}+(y_1-z_1+y_3-z_2)ln\frac{1}{4}

\Rightarrow \frac{dlnL(\theta)}{d\theta}=-\frac{z_1+y_2}{1-\theta}+\frac{z_2+y_4}{\theta}=0

\Rightarrow \hat{\theta}=\frac{z_2+y_4}{z_{1}+y_{2}+z_{2}+y_{4}} (1)

现在，并不知道z_1,z_2（隐变量）的值，只能知道分布的信息，z_1, z_2服从的分布为二项分布，概率数值类似于条件概率，第一个的概率是用\frac{1}{4}-\frac{\theta}{4} 除以 \frac{1}{2}-\frac{\theta}{4} 得到的，第二个同理：

其中，z_1 \sim B(y_1,\frac{1-\theta}{2-\theta})，z_2 \sim B(y_3,\frac{\theta}{1+\theta})

第一步（E步）：求期望的目的是为了消去隐变量z_1,z_2。

E(z_1)=\frac{1-\theta}{2-\theta}y_1 ; E(z_2)=\frac{\theta}{1+\theta}y_3

代入(1)式，得到：
\hat{\theta}=\frac{z_2+y_4}{z_1+y_2+z_2+y_4}= \frac{\frac{\theta}{1+\theta}y_3+y_4}{\frac{1-\theta}{2-\theta}y_1+y_2+\frac{\theta}{1+\theta}y_3+y_4}

第二步（M步）：取最大值。

EM算法使用迭代法来更新参数。 （精髓）
\theta^{(i+1)}=\frac{\frac{\theta^{(i)}}{1+\theta^{(i)}}y_3+y_4}{\frac{1-\theta^{(i)}}{2-\theta^{(i)}}y_1+y_2+\frac{\theta^{(i)}}{1+\theta^{(i)}}y_3+y_4}

任意取\theta^{(0)} \in (0,1)，就可以开始按照上面的公式进行迭代了。

收敛性：
DempSter证明：在很一般的条件下，最后会收敛。（可以参考李航老师的《统计学习方法》）

解析解：能列出公式解决的，数值上是更准确的（相比迭代解），比如MLE就是列出公式求解。
迭代解：退而求其次，当解析解难求的时候，通过迭代逼近的方式，可以获得令人满意的解，比如EM就是为了解决当MLE遇到高次方程难以求解的时候，提出的方法。

《统计学习方法》部分

问：给定参数 \theta，观测变量 Y={ y_1,...,y_n }，隐变量 Z={ z_1,...,z_n }，如何估计参数 \theta？

从观测序列，可以获得：
\begin{aligned} P(Y | \theta) &= \sum_Z P(Y,Z | \theta) \\ &= \sum_Z \frac{P(Y,Z,\theta)}{P(\theta)} \\ &= \sum_Z \frac{P(Y | Z,\theta) P(Z, \theta)}{P(\theta)} \\ &= \sum_Z [ P(Y | Z,\theta) P(Z | \theta) ] \end{aligned}

此时，对数似然函数为：
\begin{align} L(\theta) &= log P(Y | \theta) \tag{1}\\ &= log [\sum_Z P(Y | Z,\theta) P(Z | \theta) ] \end{align}

由于包含和（积分）的对数，因此直接求解困难。

解析解困难，转而使用迭代解：假设第i次迭代后的 \hat{\theta} 为 \theta^{(i)}，由于我们希望似然函数 L(\theta)是增大的，即 L(\theta) > L(\theta^{(i)})。

此时，考虑两者的差：

琴生不等式(Jensen inequality):
log \sum_j (\lambda_j y_j) \ge \sum_j \lambda_j logy_j，其中，\lambda_j \ge 0, \sum_j \lambda_j = 1

\begin{align} L(\theta) - L(\theta^{(i)}) &= log \sum_Z P(Y|Z,\theta) P(Z|\theta) - log P(Y | \theta^{(i)}) ----(从(1)得) \\ &= log \sum_Z P(Z | Y,\theta^{(i)}) \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - log P(Y | \theta^{(i)}) \\ &\ge \sum_Z P(Z | Y,\theta^{(i)}) log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - log P(Y | \theta^{(i)}) ----(从琴生不等式得到) \\ &= \sum_Z P(Z | Y,\theta^{(i)}) log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})} - \sum_ZP(Z| Y, \theta^{(i)}) log P(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{align}

\Rightarrow L(\theta) \ge 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)的下界，记为B(\theta, \theta^{(i)})，那么，使得下界尽可能大，即：

\begin{align} \theta^{(i+1)} &= \argmax_\theta B(\theta, \theta^{(i)}) \\ &= \argmax_\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)})} \} \\ &= \argmax_\theta \{ \sum_Z P(Z|Y,\theta^{(i)}) log[P(Y|Z,\theta)P(Z|\theta)] \} \\ &= \argmax_\theta \{ \sum_Z P(Z|Y,\theta^{(i)}) logP(Y,Z|\theta) \} \\ &= \argmax_\theta Q(\theta, \theta^{(i)}) ----(类似于求logP(Y,Z|\theta)关于P(Z|Y,\theta^{(i)})的期望) \\ \end{align}

Algorithm: Estimation Maximum (EM)

  1. 选 \theta^{(0)}，开始迭代：
  2. 计算 Q(\theta, \theta^{(i)})
  3. 将使得 Q(\theta, \theta^{(i)})最大的 \theta作为 \theta^{(i+1)}
  4. 重复2.和3.直到收敛。(收敛条件要么是 \theta的变化小，要么 Q 函数变化小。)

举例：以三硬币模型为例。有A、B、C三枚硬币，分别有\pi,p,q的概率为正面。每次试验为：先投A硬币，如果A为正面，则投B硬币；否则，投C硬币。最终，可以观测到的结果为硬币的正/反面，但是不知道是由B还是C投出的（隐变量）。问：如果某次试验数为10的结果为：{1,1,0,1,0,0,1,0,1,1}，如何估计参数 \theta = \{ \pi,p,q \}？

显然，题目的Z隐变量为A硬币投出的结果，此时可以采用EM解法。
先从“E”入手，求解Q函数：
\begin{aligned} Q(\theta, \theta^{(i)}) &= \sum_Z P(Z | Y, \theta^{(i)}) log P(Y, Z | \theta) \\ & 对数运算，然后对Y的各个观测结果进行展开 \\ &= \sum_Z log \prod_{j=1}^{n}P(y_j, Z | \theta) ^ {P(Z|y_j, \theta{(i)})} \\ &= \sum_{j=1}^{n} \sum_Z P(Z | y_j, \theta^{(i)}) log P(y_j, Z | \theta) \\ &= \sum_{j=1}^{n} \{ P(Z=1 | y_j, \theta^{(i)}) logP(Z=1, y_j | \theta) \\ & + P(Z=0 | y_j, \theta^{(i)}) logP(Z=0, y_j | \theta)\} \\ \end{aligned}

然后，逐一击破：

\begin{aligned} P(Z=1 | y_j, \theta^{(i)}) logP(Z=1, y_j | \theta) &= P(y_j | Z=1, \theta) P(Z=1 | \theta) \\ &= p^{y_j} (1-p)^{1-y_j} \pi \\ \end{aligned}

\begin{aligned} P(Z=0 | y_j, \theta^{(i)}) logP(Z=0, y_j | \theta) &= P(y_j | Z=0, \theta) P(Z=0 | \theta) \\ &= q^{y_j} (1-q)^{1-y_j} (1-\pi) \\ \end{aligned}

\begin{align} P(Z=1 | y_j, \theta^{(i)}) &= \frac{P(Z=1, y_j, \theta^{(i)})}{P(y_j, \theta^{(i)})} \\ &= \frac{P(Z=1, y_j | \theta^{(i)})}{P(y_j | \theta^{(i)})} \\ &= \frac{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)}}{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)} + (q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})} \\ \end{align}

\begin{align} P(Z=0 | y_j, \theta^{(i)}) &= \frac{P(Z=0, y_j, \theta^{(i)})}{P(y_j, \theta^{(i)})} \\ &= \frac{P(Z=0, y_j | \theta^{(i)})}{P(y_j | \theta^{(i)})} \\ &= \frac{(q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})}{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)} + (q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})} \\ \end{align}

回代Q函数：
\begin{aligned} Q(\theta, \theta^{(i)}) &= \sum_{j=1}^{n} \{ P(Z=1 | y_j, \theta^{(i)}) logP(Z=1, y_j | \theta) \\ & + P(Z=0 | y_j, \theta^{(i)}) logP(Z=0, y_j | \theta)\} \\ &= \sum_{j=1}^{n} \{ \frac{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)}}{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)} + (q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})} log[p^{y_j} (1-p)^{1-y_j} \pi] \\ + & \frac{(q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})}{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)} + (q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})} log[q^{y_j} (1-q)^{1-y_j} (1-\pi)]\} \\ &令 \frac{(q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})}{(p^{(i)})^{y_j} (1-p^{(i)})^{1-y_j} \pi^{(i)} + (q^{(i)})^{y_j} (1-q^{(i)})^{1-y_j} (1-\pi^{(i)})} = \mu_j^{(i)} \\ &= \sum_{j=1}^{n} \{ \mu_j^{(i)} log[p^{y_j} (1-p)^{1-y_j} \pi] \\ +& (1 - \mu_j^{(i)}) log[q^{y_j} (1-q)^{1-y_j} (1-\pi)]\} \end{aligned}

极大似然求导数，令其为0，能取得极值点：

\begin{aligned} \frac{\partial Q(\theta,\theta^{(i)})}{\partial \pi} &= \sum_{j=1}^{n} \{ \mu_j^{(i)} \frac{p^{y_j}(1-p)^{(1-y_j)}}{\pi p^{y_j} (1-p)^{1-y_j}} - (1-\mu_j^{(i)}) \frac{q^{y_j}(1-q)^{1-y_j}}{(1-\pi)q^{y_j}(1-q)^{1-y_j}} \} \\ &= \sum_{j=1}^{n} \{ \frac{\mu_j^{(i)}}{\pi} - \frac{1-\mu_j^{(i)}}{1-\pi} \} \end{aligned}

令上式为0 \Rightarrow \sum_{j=1}^{n} \{ (1-\pi) \mu_j^{(i)} - \pi (1-\mu_j^{(i)}) \} = 0

\Rightarrow \pi = \frac{\sum_{j=1}^{n}\mu_j^{(i)}} {n} ------对应书(9.6)式

\begin{aligned} \frac{\partial Q(\theta,\theta^{(i)})}{\partial p} &= \sum_{j=1}^{n} \{ \mu_j^{(i)} \frac{\pi [y_jp^{y_j-1}(1-p)^{1-y_j}-p^{y_j}(1-y_j)(1-p)^{-y_j}]}{\pi p^{y_j}(1-p)^{1-y_j}} \} \\ &= \sum_{j=1}^{n} \{ \mu_j^{(i)} [y_jp^{-1} - (1-y_j)(1-p)^{-1}] \} \\ &= \sum_{j=1}^{n} \{ \mu_j^{(i)} \frac{y_j-p}{p(1-p)} \} \end{aligned}

令上式为0 \Rightarrow \sum_{j=1}^{n} \{ \mu_j^{(i)} (y_j-p) \} = 0

\Rightarrow p = \frac{\sum_{j=1}^{n} (\mu_j^{(i)} y_j)}{\sum_{j=1}^{n} \mu_j^{(i)}} ------对应书(9.7)式

\begin{aligned} \frac{\partial Q(\theta,\theta^{(i)})}{\partial q} &= \sum_{j=1}^{n} \{ (1-\mu_j^{(i)}) \frac{(1-\pi) [y_jq^{y_j-1}(1-q)^{1-y_j}-q^{y_j}(1-y_j)(1-q)^{-y_j}]}{(1-\pi) q^{y_j}(1-q)^{1-y_j}} \} \\ &= \sum_{j=1}^{n} \{ (1-\mu_j^{(i)}) [y_jq^{-1} - (1-y_j)(1-q)^{-1}] \} \\ &= \sum_{j=1}^{n} \{ (1-\mu_j^{(i)}) \frac{y_j-q}{q(1-q)} \} \end{aligned}

令上式为0 \Rightarrow \sum_{j=1}^{n} \{ (1-\mu_j^{(i)}) (y_j-q) \} = 0

\Rightarrow q = \frac{\sum_{j=1}^{n} [(1-\mu_j^{(i)}) y_j]}{\sum_{j=1}^{n} (1-\mu_j^{(i)})} ------对应书(9.8)式

至此，只要根据当前迭代下的 \pi^{(i)}, p^{(i)}, q^{(i)}，就能得到不同 j 下标的 \mu_j^{(i)}，进而得到下一次迭代的\pi, p, q。

相关文章

网友评论

    本文标题：期望最大算法(EM)

    本文链接：https://www.haomeiwen.com/subject/zcqxpktx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    统计、学习

    关于我们|服务条款|联系我们|期望最大算法(EM)|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！