美文网首页
EM算法推导

EM算法推导

作者: zealscott | 来源:发表于2019-04-18 21:05 被阅读0次

推导EM算法，并证明收敛性。

Jensen’s inequality

定理：若f是凸函数，X是随机变量，我们有：\mathrm{E}[f(X)] \geq f(\mathrm{E} X)

  • 若f是严格凸函数，也就是f^{''} > 0恒成立，同时X=E[X]（也就是概率为1），则等号成立。
  • 若f是凹函数，则该定理也成立，只不过将大于等于换成小于等于。

忽略证明，该定理并不直观，可以用一个简单的例子帮助记忆：

image-20190418202130305

收敛性证明

我们想用模型拟合数据，也就是求似然函数：
\begin{aligned} \ell(\theta) &=\sum_{i=1}^{m} \log p(x ; \theta) \\ &=\sum_{i=1}^{m} \log \sum_{z} p(x, z ; \theta) \end{aligned}
其中，z是隐变量。如果z已知，那么直接用MLE求解即可，如果未知，则需要用EM算法迭代求解。

EM算法分为两步：

  1. E step：每次得到似然函数\ell​的一个下界。
  2. M step：对该下界进行优化。

我们首先可以假设Q是z的分布，也就是满足：\sum_{z} Q_{i}(z)=1, Q_{i}(z) \geq 1

因此可以得到：
\begin{aligned} \sum_{i} \log p\left(x^{(i)} ; \theta\right) &=\sum_{i} \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) \\ &=\sum_{i} \log \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)} \end{aligned}
这里用到了期望就是概率的思想。我们将Q函数看成是在随机变量\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}上的概率分布，将函数f看成是log function。因此，第二个等式可以看作是f(EX)。而由于f函数是凹函数，因此根据Jensen’s inequality，可以得到不等式三。

这样，对于任意的分布Q，我们给出了似然函数的下界。因此，我们如何选择一个合适的Q呢？

我们如果对当前的\theta有一个估计值，那么很自然的思想就是用这个估计值来得到不等式的下界。根据之前Jensen’s inequality不等式的分析，如果我们的随机变量是一个常量，那么等式一定成立，即：
\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}=c
因此，我们只需要Q_{i}\left(z^{(i)}\right) \propto p\left(x^{(i)}, z^{(i)} ; \theta\right)即可。同时，由于\sum_{z} Q_{i}\left(z^{(i)}\right)=1的条件需要满足，因此构造一个Q函数为：
\begin{aligned} Q_{i}\left(z^{(i)}\right) &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z} p\left(x^{(i)}, z ; \theta\right)} \\ &=\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ &=p\left(z^{(i)} | x^{(i)} ; \theta\right) \end{aligned}
实际上，这个Q函数就是我们熟悉的在给定\theta下的后验分布。

如何证明收敛性呢？也就是需要证明\ell\left(\theta^{(t)}\right) \leq \ell\left(\theta^{(t+1)}\right)始终成立。

由于我们选择的Q函数能使得等式成立，因此在第t​次迭代时，有：
\ell\left(\theta^{(t)}\right)=\sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)}
在第t+1次时，我们的\theta^{(t+1)}是最大化右边的式子的来的，因此：
\begin{aligned} \ell\left(\theta^{(t+1)}\right) & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t+1)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ & \geq \sum_{i} \sum_{z^{(i)}} Q_{i}^{(t)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(t)}\right)}{Q_{i}^{(t)}\left(z^{(i)}\right)} \\ &=\ell\left(\theta^{(t)}\right) \end{aligned}
其中，第一个不等式是根据Jensen’s inequality，第二个不等式是根据最大化\theta的性质来的。

如果我们定义：
J(Q, \theta)=\sum_{i} \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_{i}\left(z^{(i)}\right)}
那么，EM算法也可以看作是在J上进行coordinate ascent：

  1. E step 时，固定\theta，根据Q最大化J
    • 实际上是通过Jensen’s inequality的性质，定义Q函数为后验概率满足等式）
  2. M step 时，固定Q，根据\theta最大化J
    • 实际上是通过MLE进行最大化

GMM revisited

GMM的思想不再阐述，这里主要进行推导closed form。

E step

E step相对容易一些，我们对于当前步估计的所有参数值，计算z的后验分布：
w_{j}^{(i)}=Q_{i}\left(z^{(i)}=j\right)=P\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)

M step

根据上一步得到的z的分布，我们最大化\ell的下界：
\begin{aligned} \sum_{i=1}^{m} & \sum_{z^{(i)}} Q_{i}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \phi, \mu, \Sigma\right)}{Q_{i}\left(z^{(i)}\right)} \\ &=\sum_{i=1}^{m} \sum_{j=1}^{k} Q_{i}\left(z^{(i)}=j\right) \log \frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{Q_{i}\left(z^{(i)}=j\right)} \\ &=\sum_{i=1}^{m} \sum_{j=1}^{k} w_{j}^{(i)} \log \frac{\frac{1}{(2 \pi)^{n / 2}\left|\Sigma_{j}\right|^{1 / 2}} \exp \left(-\frac{1}{2}\left(x^{(i)}-\mu_{j}\right)^{T} \Sigma_{j}^{-1}\left(x^{(i)}-\mu_{j}\right)\right) \cdot \phi_{j}}{w_{j}^{(i)}}\end{aligned}
我们只需要分别对三个参数进行求导，即可得到：
\mu_{l} :=\frac{\sum_{i=1}^{m} w_{l}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{l}^{(i)}}\\ \phi_{j} :=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)}\\ \Sigma_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}
这也就是我们上一个博客给出的EM算法的迭代过程。

相关文章

  • EM算法推导

    推导EM算法，并证明收敛性。 Jensen’s inequality 定理：若是凸函数，是随机变量，我们有： 若是...

  • EM算法

    1. 前提推导 2. EM算法 EM算法就是含有隐变量的概率模型参数的极大似然估计法。 延森不等式（Jensen'...

  • <机器学习> EM算法

    文章参考来源： CS229和PRML中关于EM的推导的过程。 文章内容： 1. 不考虑数据点独立性的EM算法 E步...

  • EM 算法

    参考: 从最大似然到EM算法浅解 （EM算法）The EM Algorithm EM算法及其推广学习笔记 EM算法...

  • 序列比对(十五)——EM算法以及Baum-Welch算法的推导

    原创：hxj7 本文介绍了 EM算法 和 Baum-Welch算法的推导过程。 一般地，估算概率模型参数可以用最大...

  • EM算法

    问题 1. 什么是EM 2. EM算法流程是怎么样的 3. EM算法的优缺点 1. EM算法介绍 EM算法...

  • 04 EM算法 - EM算法收敛证明

    03 EM算法 - EM算法流程和直观案例 八、EM算法收敛证明 EM算法的收敛性只要我们能够证明对数似然函数的值...

  • EM算法|机器学习推导系列（十二）

    一、概述 假设有如下数据： :observed data:unobserved data(latent varia...

  • 01 EM算法 - 大纲 - 最大似然估计(MLE)、贝叶斯算法

    EM算法的讲解的内容包括以下几个方面： 1、最大似然估计2、K-means算法3、EM算法4、GMM算法 EM算法...

  • EM算法

    EM算法 EM算法基本思想 ​ 最大期望算法（Expectation-Maximization algorit...

网友评论

      本文标题：EM算法推导

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|EM算法推导|投稿指南|网站地图|RSS订阅|排版工具|手机版

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

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

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

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

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