前言
EM（期望最大）算法有很多的应用，最广泛的就是混合高斯模型、聚类、HMM等等，本质上就是一种优化算法，不断迭代，获得优值，与梯度下降、牛顿法、共轭梯度法都起到同一类的作用。
本文是对李航《统计学习方法》的第9章复习总结，主要内容如下
EM（期望最大）算法证明有跳跃性的地方全部事无巨细地写出来，
在 三硬币例子解析 这一节将会把这个例子跟公式一一对应起来
GMM（高斯混合模型）迭代公式证明
F函数的极大-极大算法（Maximization-Maximization-algorithm）和GEM 详细证明
当然大家也可以参考 Stanford 吴恩达主讲的 CS299 Machine Learning 的 EM课件 ，相比之下《统计学习方法》这本书在 Jensen‘s inequality（琴声不等式）讲的不够详细，其他都差不多，只是Q函数定义不同，这两种定义都很流行所以后文也会介绍区别。
正文
9.1 EM算法的引入
概率模型有时既含有观测变量（observable variable） ， 又含有隐变量（hidden variable）或潜在变量（latent variable） 。
如果概率模型的变量都是观测变量， 那么给定数据， 可以直接用极大似然估计法或贝叶斯估计法估计模型参数。 但是， 当模型含有隐变量时， 就不能简单地使用这些估计方法。 EM算法就是含有隐变量的概率模型参数的极大似然估计法， 或极大后验概率估计法。 我们仅讨论极大似然估计， 极大后验概率估计与其类似。
9.1.1 EM算法
这里， 随机变量 $y$ 是观测变量， 表示一次试验观测的结果是1或0； 随机变量 $z$ 是隐变量， 表示未观测到的掷硬币 $A$ 的结果； $\theta＝( \pi ,p， q)$ 是模型参数。 这一模型是以上数据的生成模型。 注意， 随机变量 $y$ 的数据可以观测， 随机变量 $z$ 的数据不可观测。
$$
\begin{align}
P(y|\theta) &= \sum\limits_{z}P(y,z|\theta)=\sum\limits_{z}\frac{P(z,\theta)}{P(\theta)}\cdot\frac{P(y,z,\theta)}{P(z, \theta)}=\sum\limits_{z}P(z|\theta)P(y|z,\theta) \
&= P(z=1|\theta)P(y|z=1, \theta) + P(z=0|\theta)P(y|z=0, \theta)\
&= \pi p^y(1-p)^{(1-y)} + (1 - \pi) q^y(1-q)^{(1-y)} \tag{9.1}\
&= \begin{cases} \pi p + (1 - \pi) q, &y=1\ \pi (1-p) + (1-\pi)(1-q), &y=0\end{cases}
\end{align}
$$
将观测数据表示为 $Y＝(Y_1， Y_2,…,Y_n)^T$， 未观测数据表示为 $Z＝(Z_1,Z_2,…,Z_n)^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|\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}
$$
考虑求模型参数 $\theta =(\pi, p, q) $ 的极大似然估计，即：
$$
\begin{align}
\hat{\theta}&=\mathop{\arg\max}{\theta} \mathrm{log}P(Y|\theta) \
&= \mathop{\arg\max}{\theta}\log\prod_{j=1}^{n}P(Y|\theta) \Leftarrow\text{n次抛硬币试验都是独立} \
&= \mathop{\arg\max}{\theta}\sum\limits{j=1}^{n}\log P(Y|\theta) \
&= \mathop{\arg\max}{\theta}\sum\limits{j=1}^{n}\log\left{\sum\limits_{Z}{P(Z|\theta)P(Y|Z,\theta)}\right} \tag{9-3}
\end{align}
$$
问题：这里为什么要取对数？
- 取对数之后累积变为累和，求导更加方便（后面三硬币例子解析将会看到）
- 概率累积会出现数值非常小的情况，比如1e-30，由于计算机的精度是有限的，无法识别这一类数据，取对数之后，更易于计算机的识别(1e-30以10为底取对数后便得到-30)。
这个问题没有解析解，因为隐变量数据无法获得，只有通过迭代的方法求解。 EM算法就是可以用于求解这个问题的一种迭代算法。
一般地， 用 $Y$ 表示观测随机变量的数据， $Z$ 表示隐随机变量的数据。 $Y$ 和 $Z$ 连在一起称为完全数据（complete-data） **， 观测数据 $Y$ 又称为不完全数据（incomplete-data） **。 假设给定观测数据 $Y$， 其概率分布是 $P(Y|\theta)$， 其中是需要估计的模型参数， 那么不完全数据 $Y$ 的似然函数是 $P(Y|\theta)$， 对数似然函数 $L(\theta)＝\mathrm{log}P(Y|\theta)$ ； 假设 $Y$ 和 $Z$ 的联合概率分布是 $P(Y, Z|\theta)$， 那么完全数据的对数似然函数是 $\mathrm{log}P(Y, Z|\theta)$。
9.1.2 EM算法的导出
注：书上给出琴声不等式（$\ln\sum_j\lambda_jy_j\geq \sum_j\lambda_j\log y_j,\quad \lambda_j\ge 0,\sum_j\lambda_j=1$），自行维基百科一下了解详情。最后一步源自于 $Z$ 所有可能取值的概率和为1
$$
\mathrm{log}P(Y|\theta^{(i)})=\mathrm{log}P(Y|\theta^{(i)}) \cdot \sum\limits_{Z}P(Z|Y, \theta^{(i)})
$$
$$
\begin{align}
\theta^{(i+1)} &= \mathop{\arg\max}{\theta} \left{ L(\theta^{(i)}) + \sum\limits{Z}P(Z|Y, \theta^{(i)})\mathrm{log}\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\right} \
&= \mathop{\arg\max}{\theta}\left{ \mathrm{log}P(Y|\theta^{(i)})\sum\limits{Z}P(Z|Y, \theta^{(i)}) + \sum\limits_{Z}P(Z|Y, \theta^{(i)})\mathrm{log}\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})} \right} \
\end{align}
$$
加号右边，利用对数函数的性质得到：
$$
\begin{align}
&\sum\limits_{Z}P(Z|Y, \theta^{(i)})\mathrm{log}\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})} \
&=\sum\limits_{Z}P(Z|Y,\theta^{(i)})\left{\mathrm{log}[P(Y|Z,\theta)P(Z|\theta)] - \mathrm{log}[P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})]\right} \
&=\sum\limits_{Z}P(Z|Y,\theta^{(i)})\left{\mathrm{log}[P(Y|Z,\theta)P(Z|\theta)] - \mathrm{log}P(Z|Y,\theta^{(i)})-\mathrm{log}P(Y|\theta^{(i)})\right} \
&= \sum\limits_{Z}P(Z|Y,\theta^{(i)})\mathrm{log}[P(Y|Z,\theta)P(Z|\theta)] - \sum\limits_{Z}P(Z|Y,\theta^{(i)})\mathrm{log}P(Z|Y,\theta^{(i)})-\sum\limits_{Z}P(Z|Y,\theta^{(i)})\mathrm{log}P(Y|\theta^{(i)}) \
\end{align}
$$
代入上式可得：
$$
\begin{align}
\theta^{(i+1)} &= \mathop{\arg\max}{\theta} \left{ \sum\limits{Z}P(Z|Y, \theta^{(i)})\mathrm{log}[P(Y|Z,\theta)P(Z|\theta)]-\sum\limits_{Z}P(Z|Y,\theta^{(i)})\mathrm{log}P(Z|Y,\theta^{(i)}) \right} \
\end{align}
$$
由于在迭代求第 $i+1$ 步时，$\theta^{(i)}$ 是已知的，那么由训练数据中可以求得 $P(Z|Y,\theta^{(i)})$ ，所以在 $\theta^{(i)}$ 值确定的情况下，$P(Z|Y,\theta^{(i)})$ 的值也是确定的而不是变量，那么对上式极大化等价求解对下面式子的极大化
$$
\begin{align}
\theta^{(i+1)} &= \mathop{\arg\max}{\theta} \left{ \sum\limits{Z}P(Z|Y, \theta^{(i)})\mathrm{log}[P(Y|Z,\theta)P(Z|\theta)]\right} \
&= \mathop{\arg\max}{\theta} \left{ \sum\limits{Z}P(Z|Y, \theta^{(i)})\mathrm{log}P(Y,Z|\theta)\right} \
&= \mathop{\arg\max}_{\theta}Q(\theta, \theta^{(i)}) \tag{9.17}
\end{align}
$$
Q函数
EM算法
EM算法解释
9.1.3 EM算法在非监督学习中的应用
9.2 EM算法的收敛性
这一部分原书讲的比较详细，不画蛇添足，贴上来。
三硬币例子解析
前文讲到抛硬币的例子，现在重新详细推导一下三硬币这个例子。
$j$ 是训练集中的数据编号，实际上书上这里求得是
$$
\begin{align}
P(Z|y_j,\theta^{(i)}) = \cases{P(Z=1|y_j,\theta^{(i)})=\mu_{j}^{(i+1)} \ P(Z=0|y_j,\theta^{(i)})=1- \mu_{j}^{(i+1)}}
\end{align}
$$
前文已知Q函数：
$$
Q(\theta, \theta^{(i)})=\sum\limits_{Z}P(Z|Y, \theta^{(i)})\mathrm{log}P(Y,Z|\theta)
$$
第一步求期望
即求Q函数，由本文开头的 9.1.1 EM算法 这一节的公式 (9-3) 和 Q函数得到，在多个样本情况下 Q 函数为：
$$
\begin{align}
Q(\theta, \theta^{(i)}) &= \sum\limits_{j=1}^{n}\sum\limits_{Z}P(Z|y_j, \theta^{(i)})\log P(y_j,Z|\theta)\
&= \sum\limits_{j=1}^{n}\left{ P(Z=1|y_j, \theta^{(i)})\mathrm{log}P(y_j,Z=1|\theta) + P(Z=0|y_j, \theta^{(i)})\mathrm{log}P(y_j,Z=0|\theta) \right}\
&= \sum\limits_{j=1}^{n}\left{\mu_{j}^{(i+1)}log P(y_j,Z=1|\theta) + (1-\mu_{j}^{(i+1)})\mathrm{log}P(y_j,Z=0|\theta) \right}\
&= \sum\limits_{j=1}^{n}\left{\mu_{j}^{(i+1)}\log [\pi p^{y_j}(1-p)^{1-y_j}]+(1-\mu_{j}^{(i+1)})\log [(1-\pi )q^{y_j}(1-q)^{1-y_j}] \right}\
\end{align}
$$
第二步极大化Q函数
$\begin{align}
\theta^{(i+1)} = \mathop{\arg\max}{\theta}Q(\theta, \theta^{(i)}) = \mathop{\arg\max}{\theta} \left{\sum\limits_{j=1}^{n} \sum\limits_{Z}P(Z|y_j, \theta^{(i)})\log P(y_j,Z|\theta)\right}
\end{align}$ 用微积分求解最大值，先求导数为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}
$$
$$
\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}
$$
$$
\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}
$$
$$
\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}
$$
可以参照书上的结果，一模一样：
CS299 EM算法与《统计学习方法》的表述不同点
《统计学习方法》这部分术语源自于鼎鼎大名的ESL 全称：The Elements of Statistical Learning，这也是Stanford统计经典巨作。
Stanford 吴恩达主讲的 CS299 Machine Learning 的 EM课件
由本文的推导，易得 ESL 中的 $ Q_{ESL} = Q_{CS299}\frac{\log P(X,Z;\theta)}{Q_{CS299}} $
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}
$$
证明过程思路：拉格朗日求有约束的极大值。需要注意，由累加号和均值可以看出这里的 $Z$ 是指 $Z_i, i$ 这里是 $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$ 关于 $P(Z_i)$的求导（这里作者求导的时候把对数函数默认当做自然对数）：
$$
\begin{align}
&\frac{\partial{L}}{\partial{\tilde{P}(Z_i)}}=\log P(Y,Z_i|\theta)-\log \tilde{P}(Z_i)-1-\lambda \
&\because\quad\frac{\partial{L}}{\partial{\tilde{P}(Z_i)}}=0\ &\therefore\quad \lambda=\log P(Y,Z_i|\theta)-\log \tilde{P}(Z_i)-1
\end{align}
$$
上式两端同取对数：
$$
\begin{align}
\lambda+1&=\log P(Y,Z_i|\theta)-\log \tilde{P}(Z_i) \
&\Rightarrow e^{\lambda+1}=\frac{P(Y,Z_i|\theta)}{\tilde{P}(Z_i)} \
&\Rightarrow\tilde{P}(Z_i)=\frac{P(Y,Z_i|\theta)}{e^{\lambda+1}} \tag{9-1}
\end{align}
$$
由离散变量的概率和为1，得到：
$$
\begin{align}
\sum\limits_{Z_i}e^{\lambda+1} &= \frac{\sum\limits_{Z_i}P(Y,Z_i|\theta)}{\sum\limits_{Z_i}\tilde{P}(Z_i)} \Rightarrow\
e^{\lambda+1} &= P(Y|\theta) \tag{9-2}
\end{align}
$$
将 (9-2) 代入 (9-1) 式，得到
$$
\begin{align}
\tilde{P}(Z_i)&=\frac{P(Y,Z_i|\theta)}{P(Y|\theta)} \
&=\frac{P(Y,Z_i,\theta)}{p(\theta)}\frac{P(\theta)}{P(Y,\theta)} \
&= P(Z_i|Y,\theta)
\end{align}
$$
这里前提条件是 $\theta$ 是固定情况下的推导过程，所以原文给上式标记出了 $\theta$ ，又因为每个 $Z_i$ 都符合这个式子，那么可重写上式：
$$
\tilde{P}_{\theta}(Z) = P(Z|Y,\theta)
$$
这样引理9.1证明完毕。
引理9.2如下
由公式 $(9.33)$ 和 $(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)
$$
得到：
$$
\begin{align}
F(\tilde{P}, \theta)&=\sum\limits{Z}{\tilde{P}{\theta}(Z)}\log P(Y,Z|\theta) - \sum\limits{Z}{\tilde{P}{\theta}(Z)}\log \tilde{P}{\theta}(Z) \
&=\sum\limits_{Z} P(Z|Y,\theta)\log P(Y,Z|\theta) - \sum\limits_{Z}P(Z|Y,\theta)\log P(Z|Y,\theta) \
&=\sum\limits_{Z}P(Z|Y,\theta)[\log P(Y,Z|\theta) - \log P(Z|Y,\theta)] \
&=\sum\limits_{Z}P(Z|Y,\theta)\log\frac{P(Y,Z|\theta)}{P(Z|Y,\theta)}\
&=\sum\limits_{Z}P(Z|Y,\theta)\log\left{\frac{P(Y,Z,\theta)}{p(\theta)}\frac{P(Y,\theta)}{P(Y,Z,\theta)}\right}\
&= \sum\limits_{Z}P(Z|Y,\theta)\log P(Y|\theta) \
&= \log P(Y|\theta) \
\end{align}
$$
引理9.2证明完毕
9.4.2 GEM算法
本章概要
引用
The Expectation Maximization Algorithm: A short tutorial - Sean Borman
李航《统计学习方法》
