引用自 NLP-LOVE/ML-NLP
什么是EM算法
数据挖掘十大算法之一的EM算法。
最大期望算法（Expectation-maximization algorithm，又译为期望最大化算法），是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐性变量。
最大期望算法经过两个步骤交替进行计算，
第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
极大似然估计用一句话概括就是：知道结果，反推条件θ。
似然函数
在数理统计学中，似然函数是一种关于统计模型中的参数的函数，表示模型参数中的似然性。“似然性”与“或然性”或“概率”意思相近，都是指某种事件发生的可能性。而极大似然就相当于最大可能的意思。
比如你一位同学和一位猎人一起外出打猎，一只野兔从前方窜过。只听一声枪响，野兔应声到下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于你那位同学命中的概率，从而推断出这一枪应该是猎人射中的。
这个例子所作的推断就体现了最大似然法的基本思想。
多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。
极大似然函数的求解步骤
假定我们要从10万个人当中抽取100个人来做身高统计，那么抽到这100个人的概率就是(概率连乘)：
现在要求的就是这个 $\theta$ 值，也就是使得 $L(\theta)$ 的概率最大化，那么这时的参数 $\theta$ 就是所求。
为了便于分析，我们可以定义对数似然函数，将其变成连加的形式：
对于求一个函数的极值，通过我们在本科所学的微积分知识，最直接的设想是求导，然后让导数为0，那么解这个方程得到的θ就是了（当然，前提是函数L(θ)连续可微）。但，如果θ是包含多个参数的向量那怎么处理呢？当然是求L(θ)对所有参数的偏导数，也就是梯度了，从而n个未知的参数，就有n个方程，方程组的解就是似然函数的极值点了，最终得到这n个参数的值。
求极大似然函数估计值的一般步骤：
- 写出似然函数；
- 对似然函数取对数，并整理；
- 求导数，令导数为0，得到似然方程；
- 解似然方程，得到的参数即为所求；
EM算法
两枚硬币A和B，假定随机抛掷后正面朝上概率分别为PA，PB。为了估计这两个硬币朝上的概率，咱们轮流抛硬币A和B，每一轮都连续抛5次，总共5轮：
| 硬币 | 结果 | 统计 |
|---|---|---|
| A | 正正反正反 | 3正-2反 |
| B | 反反正正反 | 2正-3反 |
| A | 正反反反反 | 1正-4反 |
| B | 正反反正正 | 3正-2反 |
| A | 反正正反反 | 2正-3反 |
硬币A被抛了15次，在第一轮、第三轮、第五轮分别出现了3次正、1次正、2次正，所以很容易估计出PA，类似的，PB也很容易计算出来(真实值)，如下：
PA = （3+1+2）/ 15 = 0.4
PB= （2+3）/10 = 0.5
问题来了，如果我们不知道抛的硬币是A还是B呢（即硬币种类是隐变量），然后再轮流抛五轮，得到如下结果：
| 硬币 | 结果 | 统计 |
|---|---|---|
| Unknown | 正正反正反 | 3正-2反 |
| Unknown | 反反正正反 | 2正-3反 |
| Unknown | 正反反反反 | 1正-4反 |
| Unknown | 正反反正正 | 3正-2反 |
| Unknown | 反正正反反 | 2正-3反 |
OK，问题变得有意思了。现在我们的目标没变，还是估计PA和PB，需要怎么做呢？
显然，此时我们多了一个硬币种类的隐变量，设为z，可以把它认为是一个5维的向量（z1,z2,z3,z4,z5)，代表每次投掷时所使用的硬币，比如z1，就代表第一轮投掷时使用的硬币是A还是B。
- 但是，这个变量z不知道，就无法去估计PA和PB，所以，我们必须先估计出z，然后才能进一步估计PA和PB。
- 可要估计z，我们又得知道PA和PB，这样我们才能用极大似然概率法则去估计z，这不是鸡生蛋和蛋生鸡的问题吗，如何破？
答案就是先随机初始化一个PA和PB，用它来估计z，然后基于z，还是按照最大似然概率法则去估计新的PA和PB，然后依次循环，如果新估计出来的PA和PB和我们真实值差别很大，直到PA和PB收敛到真实值为止。
我们不妨这样，先随便给PA和PB赋一个值，比如：
硬币A正面朝上的概率PA = 0.2
硬币B正面朝上的概率PB = 0.7
然后，我们看看第一轮抛掷最可能是哪个硬币。
如果是硬币A，得出3正2反的概率为 0.2*0.2*0.2*0.8*0.8 = 0.00512
如果是硬币B，得出3正2反的概率为 0.7*0.7*0.7*0.3*0.3=0.03087
然后依次求出其他4轮中的相应概率。做成表格如下：
| 轮数 | 若是硬币A | 若是硬币B |
|---|---|---|
| 1 | 0.00512，即0.2 0.2 0.2 0.8 0.8，3正-2反 | 0.03087，3正-2反 |
| 2 | 0.02048，即0.2 0.2 0.8 0.8 0.8，2正-3反 | 0.01323，2正-3反 |
| 3 | 0.08192，即0.2 0.8 0.8 0.8 0.8，1正-4反 | 0.00567，1正-4反 |
| 4 | 0.00512，即0.2 0.2 0.2 0.8 0.8，3正-2反 | 0.03087，3正-2反 |
| 5 | 0.02048，即0.2 0.2 0.8 0.8 0.8，2正-3反 | 0.01323，2正-3反 |
按照最大似然法则：
第1轮中最有可能的是硬币B
第2轮中最有可能的是硬币A
第3轮中最有可能的是硬币A
第4轮中最有可能的是硬币B
第5轮中最有可能的是硬币A
我们就把概率更大，即更可能是A的，即第2轮、第3轮、第5轮出现正的次数2、1、2相加，除以A被抛的总次数15（A抛了三轮，每轮5次），作为z的估计值，B的计算方法类似。然后我们便可以按照最大似然概率法则来估计新的PA和PB。
PA = （2+1+2）/15 = 0.33
PB =（3+3）/10 = 0.6
设想我们是全知的神，知道每轮抛掷时的硬币就是如本文本节开头标示的那样，那么，PA和PB的最大似然估计就是0.4和0.5（下文中将这两个值称为PA和PB的真实值）。那么对比下我们初始化的PA和PB和新估计出的PA和PB：
| 初始化的PA | 估计出的PA | 真实的PA | 初始化的PB | 估计出的PB | 真实的PB |
|---|---|---|---|---|---|
| 0.2 | 0.33 | 0.4 | 0.7 | 0.6 | 0.5 |
就这样，不断迭代 不断接近真实值，这就是EM算法的奇妙之处。
可以期待，我们继续按照上面的思路，用估计出的PA和PB再来估计z，再用z来估计新的PA和PB，反复迭代下去，就可以最终得到PA = 0.4，PB=0.5，此时无论怎样迭代，PA和PB的值都会保持0.4和0.5不变，于是乎，我们就找到了PA和PB的最大似然估计。
总结一下计算步骤：
随机初始化分布参数θ
E步，求Q函数，对于每一个i，计算根据上一次迭代的模型参数来计算出隐性变量的后验概率（其实就是隐性变量的期望），来作为隐藏变量的现估计值：
M步，求使Q函数获得极大时的参数取值）将似然函数最大化以获得新的参数值
然后循环重复2、3步直到收敛。
详细的推导过程请参考文末的参考文献。
采用 EM 算法求解的模型有哪些？
用EM算法求解的模型一般有GMM或者协同过滤，k-means其实也属于EM。EM算法一定会收敛，但是可能收敛到局部最优，并不一定是极值。由于求和的项数将随着隐变量的数目指数上升，会给梯度计算带来麻烦。
应用
关于EM算法的应用其实很多，最广泛的就是GMM混合高斯模型、聚类、HMM等等。比如：
高斯混合模型 EM 算法
