EM(Expectation Maximization)算法是一种迭代算法，用于含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计。本文主要讨论该算法以及相关知识。
我们先从最简单的极大似然估计开始说起。以掷硬币为例，对于一个质量分布未知的硬币，投掷$n$次，其正面朝上的次数$k$满足二项分布：$k\sim B(n,p)$，其中$p$为硬币正面朝上的概率。极大似然估计通过观测到的变量，来估计模型参数。对于这个例子，观测变量就是投掷$n$次硬币之后的$n$个结果，而模型参数只有$p$。假设$n=5$，投掷结果为
\[X=[0,1,0,0,1]\]其中1表示正面朝上，0表示反面朝上。对$p$做极大似然估计，应该最大化对数似然：
\[\begin{aligned} LL(p\vert X)&=\ln P(X\vert p)\\ &=\ln p^2(1-p)^3\\ &=2\ln p+3\ln(1-p) \end{aligned}\]对数似然最小化：
\[\begin{aligned} \dfrac{\mathrm d}{\mathrm dp}LL(p\vert X)&=\frac2p+\frac{3}{p-1}=0\\ p&=\frac25 \end{aligned}\]由此，我们估计出了模型中的未知参数。但事情不会如此简单，我们往往并不能观察到所有的变量，这种变量被称作隐变量，相对应的，能被我们观测到的变量（比如掷硬币的结果）被称作观测变量，也被称作不完全数据（隐变量和观测变量合并在一起称作完全数据）。我们往往设观测变量为$\textbf{X}$，隐变量为$\textbf{Z}$，设模型参数为$\Theta$。在这种情况下，若要求模型参数，还是应该最大化对数似然：
\[LL(\Theta\vert\textbf{X},\textbf{Z})=\ln P(\textbf{X},\textbf{Z}\vert\Theta)\]但隐变量是观测不到的，上式无法直接求解。此时我们可以通过计算$\textbf{Z}$的期望，来最大化已观测数据的对数边际似然：
\[LL(\Theta\vert\textbf{X})=\ln P(\textbf{X}\vert\Theta)=\ln\sum_{\textbf{Z}}P(\textbf{X},\textbf{Z}\vert\Theta)\]EM算法的思想是：如果$\Theta$已知，则可以根据训练数据推断出隐变量$\textbf{Z}$的值（E step），反之，若$\textbf{Z}$的值已知，则对参数进行极大似然估计（M step）。于是，给定一个初始参数$\Theta^0$，我们就可以不断进行E步和M步，知道参数收敛。这就是EM算法的原型。
在李航的《统计学习方法》中，有EM算法更形式化的过程：对于第$i+1$次迭代，设此时的模型参数为$\Theta^{i}$，
先进行E步，计算
\[\begin{aligned} Q(\Theta,\Theta^i)&=\mathbb{E}_{\textbf{Z}\vert\textbf{X},\Theta^i}[LL(\Theta\vert\textbf{X})]\\ &=\sum_\textbf{Z}\ln P(\textbf{X},\textbf{Z}\vert\Theta)P(\textbf{Z}\vert\textbf{X},\Theta^i) \end{aligned}\]其中$P(\textbf{Z}\vert\textbf{X},\Theta^i)$是给定观测数据和模型参数下隐变量数据的条件概率分布。
而M步则是极大似然：
\[\Theta^{i+1}=\arg\max_{\Theta}Q(\Theta,\Theta^i)\]重复这两步直到$\Theta$收敛。
这里的Q函数很重要，它被定义为完全数据的对数似然函数关于给定观测数据与参数下对隐变量的条件概率分布的期望，即
\[Q(\Theta,\Theta^{i})=\mathbb{E}_{\textbf{Z}}[\ln P(\textbf{X},\textbf{Z}\vert \Theta)\vert\textbf{X},\Theta^i]\]这里的定义是《统计学习方法》中的写法，上面那个Q函数定义方式是周志华的《机器学习》中的写法。
EM算法的本质还是一种对数似然，只不过是通过一步一步迭代去实现，而不是直接求出解析解。也就说，对于任意的一轮迭代(设为第$i$轮)，新估计值$\Theta$相比于$\Theta^{i}$能够获得更大的对数似然。因此，我们考虑迭代前后对数似然的差：
\[\begin{aligned} LL(\Theta\vert\textbf{X})-LL(\Theta^{i}\vert \textbf{X})&=\ln\sum_{\textbf{Z}}P(\textbf{X},\textbf{Z}\vert\Theta)-\ln P(\textbf{X}\vert\Theta^i)\\ &=\ln\sum_{\textbf{Z}}\bigg(P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)\bigg)-\ln P(\textbf{X}\vert\Theta^i)\\ &=\ln\sum_{\textbf{Z}}\bigg(P(\textbf{Z}\vert\textbf{X},\Theta^i)\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)}\bigg)-\ln P(\textbf{X}\vert\Theta^i)\\ &\geq\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)}-\ln P(\textbf{X}\vert\Theta^i)\\ &=\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)P(\textbf{X}\vert\Theta^i)} \end{aligned}\]这里的放缩利用了Jensen不等式。
令
\[B(\Theta,\Theta^i)=LL(\Theta^i\vert\textbf{X})+\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)P(\textbf{X}\vert\Theta^i)}\]则有
\[LL(\Theta\vert\textbf{X})\geq B(\Theta,\Theta^i)\]也就是说，$B(\Theta,\Theta^i)$是最新参数下对数似然的一个下界。如果一个新的$\Theta$可以让$B(\Theta,\Theta^i)$增大，肯定也可以让新的对数似然增大。现在我们想要在这次迭代中有最大的增长，也就是：
\[\begin{aligned} \Theta^{i+1} &=\arg\max_{\Theta}B(\Theta,\Theta^i)\\ &=\arg\max_{\Theta}LL(\Theta^i\vert\textbf{X})+\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)P(\textbf{X}\vert\Theta^i)}\\ &=\arg\max_{\Theta}\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln\dfrac{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}{P(\textbf{Z}\vert\textbf{X},\Theta^i)P(\textbf{X}\vert\Theta^i)}\\ &=\arg\max_{\Theta}\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln{P(\textbf{X}\vert\textbf{Z},\Theta)P(\textbf{Z}\vert\Theta)}\\ &=\arg\max_{\Theta}\sum_{\textbf{Z}}P(\textbf{Z}\vert\textbf{X},\Theta^i)\ln{P(\textbf{X},\textbf{Z}\vert\Theta)}\\ &=\arg\max_{\Theta}Q(\Theta,\Theta^i)\\ \end{aligned}\]所以EM算法的M步其实是通过最大化下界，来实现对数似然的极大化。
无监督学习下的训练数据只有输入，没有对应的输出：$\{(x_1,\cdot),(x_2,\cdot),\cdots\}$。EM算法可用于无监督学习下的生成式模型，因为这种模型由联合分布$P(X,Y)$表示，可以认为无监督学习的训练数据是联合概率分布产生的数据，其中$X$为观测变量，$Y$是隐变量。
