前言

EM（期望最大）算法有很多的应用，最广泛的就是混合高斯模型、聚类、HMM等等，本质上就是一种优化算法，不断迭代，获得优值，与梯度下降、牛顿法、共轭梯度法都起到同一类的作用。

本文是对李航《统计学习方法》的第9章复习总结，主要内容如下

1. EM（期望最大）算法证明有跳跃性的地方全部事无巨细地写出来，

2. 清晰地梳理网上很多人觉得没看明白的三硬币例子，将会把这个例子跟公式一一对应起来

3. GMM（高斯混合模型）迭代公式证明

4. F函数的极大-极大算法（Maximization-Maximization-algorithm）和GEM 详细证明

当然大家也可以参考Standford CS299 Machine Learning 的 EM课件 ，相比之下李航这本书在 Jensen‘s inequality（琴声不等式：凸优化知识的应用）讲的不够详细，其他都差不多，只是表述上不一样，有兴趣可以综合来看。

本文原文将书上所有证明给出，由于****的公式编辑器公式支持不全，有些公式没法正常显示，欢迎点击此处查看原文, 个人技术博客：SnailDove

正文

9.1 EM算法的引入

概率模型有时既含有观测变量（observable variable） ， 又含有隐变量（hidden variable）或潜在变量（latent variable） 。

如果概率模型的变量都是观测变量， 那么给定数据， 可以直接用极大似然估计法或贝叶斯估计法估计模型参数。 但是， 当模型含有隐变量时， 就不能简单地使用这些估计方法。 EM算法就是含有隐变量的概率模型参数的极大似然估计法， 或极大后验概率估计法。 我们仅讨论极大似然估计， 极大后验概率估计与其类似。

9.1.1 EM算法

这里， 随机变量 $y$y 是观测变量， 表示一次试验观测的结果是1或0； 随机变量 $z$z 是隐变量， 表示未观测到的掷硬币 $A$A 的结果； $\theta＝( \pi ,p， q)$θ＝(π,p，q) 是模型参数。 这一模型是以上数据的生成模型。 注意， 随机变量 $y$y 的数据可以观测， 随机变量 $z$z 的数据不可观测。
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P(y|\theta) &=…
将观测数据表示为 $Y＝(Y_1， Y_2,…,Y_n)^T$Y＝(Y1​，Y2​,…,Yn​)T， 未观测数据表示为 $Z＝(Z_1,Z_2,…,Z_n)^T$Z＝(Z1​,Z2​,…,Zn​)T， 则观测数据的似然函数为
$P(Y|\theta) = \sum\limits_{Z}P(Y,Z|\theta)=\sum\limits_{Z}P(Z|\theta)P(Y|Z,\theta) \tag{9.2}$P(Y∣θ)=Z∑​P(Y,Z∣θ)=Z∑​P(Z∣θ)P(Y∣Z,θ)(9.2)
即：
$P(Y|\theta)= \prod_{j=1}^{n}\left\{\pi p^{y_j}(1-p)^{(1-y_j)} + (1 - \pi) q^{y_j}(1-q)^{(1-y_j)}\right\} \tag{9.3}$P(Y∣θ)=j=1∏n​{πpyj​(1−p)(1−yj​)+(1−π)qyj​(1−q)(1−yj​)}(9.3)
考虑求模型参数 $\theta =(\pi, p, q) $ 的极大似然估计，即：
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \hat{\theta}=\…
这个问题没有解析解，因为隐变量数据无法获得，只有通过迭代的方法求解。 EM算法就是可以用于求解这个问题的一种迭代算法。

一般地， 用 $Y$Y 表示观测随机变量的数据， $Z$Z 表示隐随机变量的数据。 $Y$Y 和 $Z$Z 连在一起称为**完全数据（complete-data） ， 观测数据 $Y$Y 又称为不完全数据（incomplete-data） **。 假设给定观测数据 $Y$Y， 其概率分布是 $P(Y|\theta)$P(Y∣θ)， 其中是需要估计的模型参数， 那么不完全数据 $Y$Y 的似然函数是 $P(Y|\theta)$P(Y∣θ)， 对数似然函数 $L(\theta)＝\mathrm{log}P(Y|\theta)$L(θ)＝logP(Y∣θ) ； 假设 $Y$Y 和 $Z$Z 的联合概率分布是 $P(Y, Z|\theta)$P(Y,Z∣θ)， 那么完全数据的对数似然函数是 $\mathrm{log}P(Y, Z|\theta)$logP(Y,Z∣θ)。

9.1.2 EM算法的导出

注：最后一步源自于 $Z$Z 所有可能取值的概率和为1
$\mathrm{log}P(Y|\theta^{(i)})=\mathrm{log}P(Y|\theta^{(i)}) \cdot \sum\limits_{Z}P(Z|Y, \theta^{(i)})$logP(Y∣θ(i))=logP(Y∣θ(i))⋅Z∑​P(Z∣Y,θ(i))

KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \theta^{(i+1)}…
加号右边，利用对数函数的性质得到：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ &\sum\limits_{…
代入上式可得：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \theta^{(i+1)}…

由于在迭代求第 $i+1$i+1 步时，$\theta^{(i)}$θ(i) 是已知的，那么由训练数据中可以求得 $P(Z|Y,\theta^{(i)})$P(Z∣Y,θ(i)) ，所以在 $\theta^{(i)}$θ(i) 值确定的情况下，$P(Z|Y,\theta^{(i)})$P(Z∣Y,θ(i)) 的值也是确定的而不是变量，那么对上式极大化等价求解对下面式子的极大化
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \theta^{(i+1)}…

Q函数

EM算法

EM算法解释

9.1.3 EM算法在非监督学习中的应用

9.2 EM算法的收敛性

这一部分原书讲的比较详细，不画蛇添足，贴上来。

三硬币例子解析

前文讲到抛硬币的例子，现在重新详细推导一下三硬币这个例子。

$j$j 是训练集中的数据编号，实际上书上这里求得是
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ P(Z|y_j,\theta…
前文已知Q函数：
$Q(\theta, \theta^{(i)})=\sum\limits_{Z}P(Z|Y, \theta^{(i)})\mathrm{log}P(Y,Z|\theta)$Q(θ,θ(i))=Z∑​P(Z∣Y,θ(i))logP(Y,Z∣θ)

第一步求期望

即求Q函数
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ Q(\theta, \the…

第二步极大化Q函数

KaTeX parse error: No such environment: align at position 7: \begin{̲a̲l̲i̲g̲n̲}̲ \theta^{(i+1)}… 用微积分求解最大值，先求导数为0点（为了求导方便另对数的底数为e，即认为此处对数函数为自然对数）：
$\begin{aligned} \frac{\partial Q(\theta,\theta^{(i)})}{\partial \pi}&=\sum_{j=1}^N\{\frac{\mu_{j}^{(i+1)}\ln [\pi p^{y_j}(1-p)^{1-y_j}]+(1-\mu_{j}^{(i+1)})\ln [(1-\pi )q^{y_j}(1-q)^{1-y_j}] }{\partial \pi}\}\\&=\sum_{j=1}^N\{ \mu_{j}^{(i+1)}\frac{p^{y_j}(1-p)^{1-y_j}}{\pi p^{y_j}(1-p)^{1-y_j}}+(1-\mu_{j}^{(i+1)})\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+1)}-\pi }{\pi (1-\pi)}\}\\&=\frac{(\sum_{j=1}^N\mu_{j}^{(i+1)})-n\pi }{\pi (1-\pi)} \end{aligned}$∂π∂Q(θ,θ(i))​​=j=1∑N​{∂πμj(i+1)​ln[πpyj​(1−p)1−yj​]+(1−μj(i+1)​)ln[(1−π)qyj​(1−q)1−yj​]​}=j=1∑N​{μj(i+1)​πpyj​(1−p)1−yj​pyj​(1−p)1−yj​​+(1−μj(i+1)​)(1−π)qyj​(1−q)1−yj​−qyj​(1−q)1−yj​​}=j=1∑N​{π(1−π)μj(i+1)​−π​}=π(1−π)(∑j=1N​μj(i+1)​)−nπ​​

$\begin{aligned} \because \quad\frac{\partial Q(\theta,\theta^{(i)})}{\partial \pi}=0 &\implies \pi =\frac 1n\sum_{j=1}^N\mu_{j}^{(i+1)}\\ \therefore \quad \pi^{(i+1)}&=\frac 1n\sum_{j=1}^N\mu_{j}^{(i+1)} \end{aligned}$∵∂π∂Q(θ,θ(i))​=0∴π(i+1)​⟹π=n1​j=1∑N​μj(i+1)​=n1​j=1∑N​μj(i+1)​​

$\begin{aligned} \frac{\partial Q(\theta,\theta^{(i)})}{\partial p}&=\sum_{j=1}^N\{\frac{\mu_{j}^{(i+1)}\ln [\pi p^{y_j}(1-p)^{1-y_j}]+(1-\mu_{j}^{(i+1)})\ln [(1-\pi )q^{y_j}(1-q)^{1-y_j}] }{\partial p}\}\\&=\sum_{j=1}^N\{\mu_{j}^{(i+1)}\frac{\pi (y_jp^{y_j-1}(1-p)^{1-y_j}+p^{y_j}(-1)(1-y_j)(1-p)^{1-y_j-1})}{\pi p^{y_j}(1-p)^{1-y_j}}+0 \}\\&=\sum_{j=1}^N\{ \frac{\mu_{j}^{(i+1)}(y_j-p) }{p(1-p)}\}\\&=\frac{(\sum_{j=1}^N\mu_{j}^{(i+1)}y_j)-(p\sum_{j=1}^N\mu_{j}^{(i+1)}) }{p(1-p)} \end{aligned}$∂p∂Q(θ,θ(i))​​=j=1∑N​{∂pμj(i+1)​ln[πpyj​(1−p)1−yj​]+(1−μj(i+1)​)ln[(1−π)qyj​(1−q)1−yj​]​}=j=1∑N​{μj(i+1)​πpyj​(1−p)1−yj​π(yj​pyj​−1(1−p)1−yj​+pyj​(−1)(1−yj​)(1−p)1−yj​−1)​+0}=j=1∑N​{p(1−p)μj(i+1)​(yj​−p)​}=p(1−p)(∑j=1N​μj(i+1)​yj​)−(p∑j=1N​μj(i+1)​)​​

$\begin{aligned} \because \quad \frac{\partial Q(\theta,\theta^{(i)})}{\partial p}=0 &\implies p =\frac{\sum_{j=1}^N \mu^{(i+1)}_j y_j}{\sum_{j=1}^N\mu^{(i+1)}_j} \\ \therefore \quad p^{(i+1)}&=\frac{\sum_{j=1}^N\mu^{(i+1)}_j y_j}{\sum_{j=1}^N\mu^{(i+1)}_j} \\ q^{(i+1)}&=\frac{\sum_{j=1}^N(1-\mu^{(i+1)}_j)y_j}{\sum_{j=1}^N(1-\mu^{(i+1)}_j)} \end{aligned}$∵∂p∂Q(θ,θ(i))​=0∴p(i+1)q(i+1)​⟹p=∑j=1N​μj(i+1)​∑j=1N​μj(i+1)​yj​​=∑j=1N​μj(i+1)​∑j=1N​μj(i+1)​yj​​=∑j=1N​(1−μj(i+1)​)∑j=1N​(1−μj(i+1)​)yj​​​
可以参照书上的结果，一模一样：

9.3 EM算法在高斯混合模型学习中的应用

EM算法的一个重要应用是高斯混合模型的参数估计。 高斯混合模型应用广泛， 在许多情况下， EM算法是学习高斯混合模型（Gaussian misture model） 的有效方法。

9.3.1 高斯混合模型

9.3.2 高斯混合模型参数估计的EM算法

注意：上面的极大化的求混合模型参数迭代公式的过程参考： 大牛JerryLead 的 （EM算法）The EM Algorithm

与K-means比较

相同点：都是可用于聚类的算法；都需要指定K值。

不同点：GMM可以给出一个样本属于某类的概率是多少。

9.4 EM算法的推广

EM算法还可以解释为F函数（F function） 的极大-极大算法（maximization maximization algorithm） ， 基于这个解释有若干变形与推广， 如广义期望极大（generalized expectation maximization，GEM） 算法。

注：原文引理(9.1)(9.2)的证明有坑需要注意，先看原文，后面列出详细过程

9.4.1 F函数的极大-极大算法

---

熵这块，不清楚的可以回顾一下我的另一篇总结：《机器学习中的信息论基础》 。

引理9.1需要更详细说明：
$L=E_{\tilde{p}}\log P(Y,Z|\theta) - E_{\tilde{p}}\log \tilde{P}(Z) + \lambda\left\{1-\sum\limits_{Z}\tilde{P}(Z)\right\}$L=Ep~​​logP(Y,Z∣θ)−Ep~​​logP~(Z)+λ{1−Z∑​P~(Z)}
证明过程思路：拉格朗日求有约束的极大值。需要注意，由累加号和均值可以看出这里的 $Z$Z 是指 $Z_i, i$Zi​,i 这里是 $Z$Z 的离散值的标号 ，因此需要**重写公式 (9.35) **比较清楚：
$L=\sum\limits_{Z_i}{\tilde{P}(Z_i)}\log P(Y,Z_i|\theta) - \sum\limits_{Z_i}{\tilde{P}(Z_i)}\log \tilde{P}(Z_i)+\lambda\left\{1-\sum\limits_{Z_i}\tilde{P}(Z_i)\right\}$L=Zi​∑​P~(Zi​)logP(Y,Zi​∣θ)−Zi​∑​P~(Zi​)logP~(Zi​)+λ{1−Zi​∑​P~(Zi​)}
所以这里其实是 $L$L 关于 $P(Z_i)$P(Zi​)的求导（这里作者求导的时候把对数函数默认当做自然对数）：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ &\frac{\partia…
上式两端同取对数：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \lambda+1&=\lo…
由离散变量的概率和为1，得到：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \sum\limits_{Z…
将 (9-2) 代入 (9-1)​ 式，得到
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \tilde{P}(Z_i)…
这里前提条件是 $\theta$θ 是固定情况下的推导过程，所以原文给上式标记出了 $\theta$θ ，又因为每个 $Z_i$Zi​ 都符合这个式子，那么可重写上式：
$\tilde{P}_{\theta}(Z) = P(Z|Y,\theta)$P~θ​(Z)=P(Z∣Y,θ)
这样引理9.1证明完毕。

---

---

引理9.2如下

由公式 $(9.33)$(9.33) 和 $(9.34)$(9.34) :
$F(\tilde{P}, \theta)=E_{\tilde{p}}[\log P(Y,Z|\theta)] + H(\tilde{P}) \\ \tilde{P}_{\theta}(Z) = P(Z|Y,\theta)$F(P~,θ)=Ep~​​[logP(Y,Z∣θ)]+H(P~)P~θ​(Z)=P(Z∣Y,θ)
得到：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ F(\tilde{P}, \…
引理9.2证明完毕

---

9.4.2 GEM算法

本章概要

引用

1. 李航《统计学习方法》
2. 大牛JerryLead 的 （EM算法）The EM Algorithm