¶引言
最近看的一篇文献里用到了GMM模型以及EM算法，之前的课程学习中有讲过这两种算法，但是都是浅尝辄止，并未设计算法的数学原理。今天既然用到了，就在网上搜集了资料，想要比较彻底地学习。本文会结合资料以及我的一些理解对算法进行总结。
以及文献：
Xintao Wu, Jianping Fan, and Kalpathi R. Subramanian. 2002. B-EM: a classifier incorporating bootstrap with EM approach for data mining. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '02). Association for Computing Machinery, New York, NY, USA, 670–675. DOI:https://doi.org/10.1145/775047.775147
¶EM算法介绍
期望最大化(Expectation Maximization, EM)算法是机器学习中使用的一种算法，用来处理存在未观察到变量的问题。
以下这段话摘自《机器学习》，作者是Tom M. Mitchell：
EM算法( Dempster et al. 1977)是存在隐含变量时广泛使用的一种方法。EM算法可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知。
EM算法已被用于训练贝叶斯网以及镜像基函数网络。EM算法还是很多非监督聚类算法的基础，而且它是用于学习部分可观察马尔可夫模型的广泛使用的Baum-Welch前向后向算法的基础。
¶EM算法公式导出及ELMO&KL divergence
架设有一个实际问题，给定观测数据$X$，要求构建模型以达到对模型最好的解释。
假设构建的模型包含参数$\Theta$以及隐数据$Z$。因此模型对数据达到最好的解释等价于：
$$
\Theta = {\underset {\Theta} {\operatorname {argmax}}} P(X|\Theta) \tag 1
$$
我们引入隐变量$Z$得到：
$$
\begin{aligned}
\log P(X|\Theta) &= \log P(X,Z|\Theta) - \log P(Z|X, \Theta)\\
&= \log \frac{ P(X,Z|\Theta)}{q(Z)} - \log \frac{P(Z|X, \Theta)}{q(Z)}\\
\end{aligned}
\tag 2
$$
其中$q(Z)$是引入的一个概率分布。我们对等式进行变换，对两边同时对$q(Z)$加权有：
$$
\begin{aligned}
左边&=\int _Z q(Z)\log P(X|\Theta)dZ\\
&=\log P(X|\Theta) \int _Z q(Z)dZ\\
&=\log P(X|\Theta)
\end{aligned}
$$
$$
\begin{aligned}
右边&=\int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)} - q(Z)\log \frac{P(Z|X, \Theta)}{q(Z)} dZ\\
&=\int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)}dZ + \int _Z q(Z)\log \frac{q(Z)}{P(Z|X, \Theta)} dZ\\
\end{aligned}
\tag 3
$$
可以看到，左边依然是需要进行$argmax$的对象，右边得到了两个积分的和。我们令：
$$
\begin{aligned}
ELBO &= \int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)}dZ\\
KL(q(Z)||P(Z|X,\Theta)) &= \int _Z q(Z)\log \frac{q(Z)}{P(Z|X, \Theta)} dZ
\end{aligned}
\tag 4
$$
ELBO(Evidence Lower Bound )这里插入KL散度的定义：
因此：
$$
右边 = ELBO + KL(q(Z)||P(Z|X,\Theta)) \tag 5
$$
由KL散度的性质可知，当$q(Z)$与$P(Z|X,\Theta)$越接近时，KL散度就越接近0。于是有$\log P(X|\Theta) \geq ELBO$，当且仅当$q(Z)=P(Z|X,\Theta)$时等号成立。
因此我们有
$$
\begin{aligned}
\Theta&={\underset {\Theta} {\operatorname {argmax}}}P(X|\Theta)\\
&={\underset {\Theta} {\operatorname {argmax}}}{ELBO+KL(q(Z)||P(Z|X,\Theta))}\\
&={\underset {\Theta} {\operatorname {argmax}}}ELBO\\
&={\underset {\Theta} {\operatorname {argmax}}}
\int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)}dZ
\quad ,q(Z)=P(Z|X,\Theta)
\end{aligned}
\tag 5
$$
得到EM算法基本流程：
E-step: 计算$q(Z)=P(Z|X,\Theta^t)$
M-step: 代入q(Z)并计算$\Theta^{t+1}={\underset {\Theta} {\operatorname argmax}} ELBO$
¶广义EM算法
前面叙述的EM算法中假设$q(Z)=P(Z|X,\Thetat)$，但是在实际应用中，后验概率$P(Z|X,\Thetat)$有时难以求解，这时该如何求得最优参数$\Theta$呢？
前面得到：
$$
\log P(X|\Theta)=ELBO+KL(q||p)
$$
这里对KL进行简写，我们希望KL部分能够尽量小，这样$\Theta$不变时ELBO就能够越大：
$$
固定\Theta \\
ELBO + KL(q||p) = \log P(X|\Theta)=constant\\
{\underset {q(Z)} {argmin}}KL(q(Z)||P(Z|X,\Theta))=
{\underset {q(Z)} {argmax}}ELBO
$$
$ELBO=\int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)}dZ$是关于$q$与$\Theta$的函数，这里记$ELBO=L(q,\Theta)$。于是有广义的EM算法：
E-step: 计算$q^{t+1}(Z) = {\underset {q(Z)} {argmax}}L(q(Z),\Theta^t)$
M-step: 计算$\Theta^{t+1} = {\underset {\Theta} {argmax}} L(q^{t+1}(Z),\Theta)$
最后再次观察以下$ELBO$：
$$
\begin{aligned}
ELBO &= L(q,\Theta)\\
&=\int_Z q(Z)\log \frac{P(X,Z|\Theta)}{q(Z)}dZ\\
&=E_{q(Z)}[\log \frac{P(X,Z|\Theta)}{q(Z)}]\\
&=E_{q(Z)}[\log P(X,Z|\Theta) - \log q(Z)]\\
&=E_{q(Z)}[\log P(X,Z|\Theta)]-\underbrace{E_{q(Z)}[\log q(Z)}_{H(q)}]
\end{aligned}
$$
广义EM相当于在原式加入熵这一项。