1. EM算法的基本思想 目录
要解决的问题：
我们经常会从样本观察数据中，找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。
但是在一些情况下，我们得到的观察数据有未观察到的隐含数据，此时我们未知的有隐含数据和模型参数，因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢？这就是EM算法可以派上用场的地方了。
EM算法的解决策略：
EM算法解决这个的思路是使用启发式的迭代方法
既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含数据（EM算法的E步），接着基于观察数据和猜测的隐含数据一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐藏数据是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。不过没关系，我们基于当前得到的模型参数，继续猜测隐含数据（EM算法的E步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。
从上面的描述可以看出，EM算法是迭代求解最大值的算法，同时算法在每一次迭代时分为两步，E步和M步。一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。
EM算法的直观理解的例子——K-Means算法：
一个最直观了解EM算法思路的是K-Means算法，见之前写的K-Means聚类算法原理。在K-Means聚类时，每个聚类簇的质心是隐含数据。我们会假设K个初始化质心，即EM算法的E步；然后计算得到每个样本最近的质心，并把样本聚类到最近的这个质心，即EM算法的M步。重复这个E步和M步，直到质心不再变化为止，这样就完成了K-Means聚类。
当然，K-Means算法是比较简单的，实际中的问题往往没有这么简单。上面对EM算法的描述还很粗糙，我们需要用数学的语言精准描述。
2. EM算法的数学推导 目录
对于m个样本观察数据x=(x(1),x(2),...x(m))中，找出样本的模型参数θ, 极大化模型分布的对数似然函数如下：
如果我们得到的观察数据有未观察到的隐含数据z=(z(1),z(2),...z(m))，其中隐含数据的类型空间为Z(j), j=1,2,...,n，此时我们的极大化模型分布的对数似然函数如下：
注：
这里解释一下等式最后部分的式子是如何推出来的，即以下公式为什么成立：
其实这就是简单的全概率公式的应用：
上面这个式子是没有办法直接求出θ的。因此需要一些特殊的技巧，我们首先对这个式子进行缩放如下：
上面第(1)式引入了一个未知的新的分布Qi(z(i))，第(2)式用到了Jensen不等式：
对Jensen不等式的直观理解：
对于凸函数（抛物线开口向下，线条向上凸起），
f(E(x)) ≥ E(f(x))因为对数函数是凸函数所以，Jensen不等式成立，Jensen不等式是由这个性质的推出的一个定量而已
下面举一个简单的例子来证明：
对于凸函数 f(x)，x1 < x2，则如下图：
所以，
f(E(x)) ≥ E(f(x))
第(2)式是我们的包含隐藏数据的对数似然的一个下界。如果我们能极大化这个下界，则也在尝试极大化我们的对数似然。
但是，这里又冒出了一个新的问题：我们在前面的操作中引入了未知的新的分布Qi(z(i))，那如何求出Qi(z(i))的表达式呢？
理论上，随便取Qi(z(i))带入（2）作为（1）的下界，然后这个下界每一次迭代都增大，而且满足这样条件的Qi(z(i))可能有很多，但是获得Qi(z(i))表达式最简便的方法是利用Jensen不等式取等的条件
求解Qi(z(i))表达式：
如果要满足Jensen不等式的等号，则有(该式记为公式①）：
由于Qi(z(i))是一个分布，所以满足(该式记为公式②）：
将①代入②中得(该式记为公式③）：
则
因此我们的优化目标变成了
由于目标函数中
则前面的目标函数可以简化为：
3. EM算法的收敛性 目录
要证明EM算法收敛，则我们需要证明我们的对数似然函数的值在迭代的过程中一直在增大。即：
由于
令：
上两式相减得到：
上面的公式的用到了Jensen不等式，之所以取等号是因为这里取的是使等式成立的情况
在上式中分别取θ为θ j 和θ j+1 ，并相减得到：
要证明EM算法的收敛性，我们只需要证明上式的右边是非负的即可。
由于θj+1使得L(θ,θj)极大，因此有:
而对于第二部分，我们有：
其中第（4）式用到了Jensen不等式，只不过和第二节的使用相反而已，第（5）式用到了概率分布累积为1的性质。
至此，我们证明了EM算法的收敛性
4. EM算法的实际应用情景 目录
4.1. HMM的参数估计：鲍姆-韦尔奇算法 目录
参考资料：