期望最大（EM）算法推导

fuliang

浏览: 1655913 次
性别:
来自: 北京

最近访客更多访客>>

依然任逍遥

stephenworld

lli

samwalt

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Data/Web Mining

em 期望最大

X是一个随机向量，我们希望找到 $\theta$
使得 $P(X|\theta)$ 取得最大值，这就是关于 $\theta$ 的最大似然估计。
为了方便估计 $\theta$ ，我们一般引入log似然函数：
$L(\theta)=lnP(X|\theta)$
EM算法是一个迭代的过程，假设第n次迭代当前 $\theta$ 的估计是 $\theta_n$ 。由于我们的目标是最大化 $L(\theta)$ ，我们希望新一轮的更新 $\theta$ 使得
$L(\theta)>L(\theta_n)}$
等价的，我们希望最大化他们的不同：
$L(\theta)-L(\theta_n)=lnP(X|\theta)-lnP(x|\theta_n)$
现在我们考虑隐变量的问题，隐变量可能是没有观测到的或者缺失的变量，有时为了计算最大似然函数更容易解决也会引入隐变量，因为可以利用EM框架来方便计算。我们假设隐变量用Z来表示，那么
$P(X|\theta)=\sum_z{P(X|z,\theta)P(z|\theta)$
我们重写一下 $L(\theta)-L(\theta_n)$ 得到：
$L(\theta)-L(\theta_n)=ln(\sum_z{P(X|z,\theta)P(z|\theta)})-lnP(X|\theta_n)$
利用Jensen's不定式：
$ln\sum_{i=1}^n\lambda_ix_i\ge\sum_{i=1}^n\lambda_i{ln(x_i)}$
其中常量 $\lambda_i\ge0$ 并且 $\sum_{i=1}^n\lambda_i=1$
$L(\theta)-L(\theta_n)=ln(\sum_z{P(X|z,\theta)P(z|\theta)})-lnP(X|\theta_n)$
$=ln(\sum_z{P(X|z,\theta)P(z|\theta)}\frac{P(z|X,\theta_n)}{P(z|X,\theta_n)})-lnP(X|\theta_n)$
$=ln(\sum_z{P(z|X,\theta_n)\frac{P(X|z,\theta)P(z|\theta)}{P(z|X,\theta_n)})-lnP(X|\theta_n)$
$\ge\sum_z{P(z|X,\theta_n)}ln({\frac{P(X|z,\theta)P(z|\theta)}{P(z|X,\theta_n)})-lnP(X|\theta_n)$
$\ge\sum_z{P(z|X,\theta_n)}ln({\frac{P(X|z,\theta)P(z|\theta)}{P(z|X,\theta_n)P(X|\theta_n)})$
$\doteq\Delta(\theta|\theta_{n})$
其中由于 $\sum_z{P(z|X,\theta_n)=1$
所以有：
$P(X|\theta_n)=\sum_z{P(z|X,\theta_n)}ln{P(x|\theta_n)}$
我们可以写作：
$L(\theta)\ge{L(\theta_n)+\Delta(\theta|\theta_n)}$
为了方便，我们定义：
$l(\theta|\theta_n)\doteq{L(\theta_n)+\Delta(\theta|\theta_n)}$
这样我们得到
$L(\theta)\ge{l(\theta|\theta_n)}$

现在我们得到了似然函数 $L(\theta)$ 的下界 ${l(\theta|\theta_n)}$
另外我们观察到：
${l(\theta_n|\theta_n)}$
$=L(\theta_n)+\Delta(\theta_n|\theta_n)=L(\theta_n)+\sum_z{P(z|X,\theta_n)ln\frac{P(X|z,\theta_n)P(z|\theta_n)}{P(z|X,\theta_n)P{X|\theta_n)}}$
$=L(\theta_n)+\sum_z{P(z|X,\theta_n)ln\frac{P(X,z|\theta_n)}{P(X,z|\theta_n)}=L(\theta_n)+\sum_z{P(z|X,\theta_n)ln1=L(\theta_n)$
所以当 $\theta=\theta_n$ 时，
${l(\theta|\theta_n)}=L(\theta)$

所以任何能够增加 ${l(\theta_n|\theta_n)}$ 的 $\theta$ 都会增加 $L(\theta)$
所以EM算法选择最大化 ${l(\theta_n|\theta_n)}$

最终我们得到：
$\theta_{n+1}=argmax_{\theta}\{l(\theta|\theta_n)\}$
$=argmax_\theta\{\L(\theta_n)+\sum_z{P(z|X,\theta_n)}ln({\frac{P(X|z,\theta)P(z|\theta)}{P(z|X,\theta_n)P(X|\theta_n)})\}$
去掉相对于 $\theta$ 的常量得到：
$=argmax_\theta\{\sum_z{P(z|X,\theta_n)}ln(P(X|z,\theta)P(z|\theta)\}$
$=argmax_\theta\{\sum_z{P(z|X,\theta_n)}ln\frac{P(X,z,\theta)}{p(z,\theta)}\frac{P(z,\theta)}{p(\theta)}\}$
$=argmax_\theta\{\sum_z{P(z|X,\theta_n)}ln(P(X,z|\theta)\}$
$=argmax_\theta\{E_{Z|X,\theta_n}\{lnP(X,z|\theta)}\}$

所以EM包含以下迭代步骤：
1、E-step: 得到条件期望 $E_{Z|X,\theta_n}\{lnP(X,z|\theta)}$
2、M-step：求解 $\theta$ 最大化该条件期望

分享到：

Deep learning的一些有用链接 | 信息论学习总结（一）基础知识

2012-08-05 19:54
浏览 8432
评论(0)
分类:互联网
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论