一：EM算法简介
EM算法简单来说就是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为求期望步（E步），另一个为求极大值步M步），所以算法被称为EM算法（Expectation Maximization
Algorithm）。EM算法适用于求解那些含有隐变量的问题，也就是说你待求解的样本中含有无法观测到的记录值。要学习EM算法，我们需要先了解两个概念：极大似然估计和Jensen不等式。
二：极大似然估计
首先来了解一下极大似然估计。这个时候就需要小明友情客串一下了。假如小明今年刚考入大学，他在校园里闲逛，发现从身边经过的每十个人里有八个都是女生，他就想说：妥了，我指定能找到女朋友！那为什么小明会产生“能找到女朋友”这样的想法呢？其实这里就用到了极大似然估计的思想——根据观测到的样本结果推测使该结果出现的最大可能。也就是说，我们可以把极大似然看作一个反推，即根据结果推算使该结果出现的可能性最大的条件。
再举一个例子：现在我们从学校为数不多的男生中随机抽取100个男生，加入这些男生的身高服从同一个高斯分布：X~N（ u, ∂ ）。分别记录他们的身高数据为X={x1,x2,x3,…,x100}，但是我们不知道他们身高服从的高斯模型的参数是多少，所以我们的目标就是求解参数：θ=[u, ∂]T。在这里我们记抽到第i个男生身高的概率为?(x?|?)，假设这100个男生的身高是独立同分布的，也就是说我抽到第1个男生的身高对我抽到其他男生的身高是没有影响的，那么抽到这100个男生的身高的概率就是抽到各个男生身高概率的乘积了（即?(x1|?)?(x2|?)····*?(x100|?)，我们把这个式子定义为似然函数L(?),即L(?)是一个概率累乘的形式。
我们再来想，全校那么多男生那么多的身高，为什么我偏偏就抽到了这100个身高呢？是不是可以理解成这100个身高在全校所有的男生身高中所占的比例是最大的，以至于我随便一抽就抽到了它们呢。当然可以这样理解了，所以我只要求这100个男生身高的概率乘积的最大值就好了，也就是说要求这个似然函数的最大值。求最大值避免不了要求倒数，对累乘的式子求导运算量大的难以想像，所以我们一般通过取对数把累乘变成累加的形式：
现在我们只需要对似然函数求导，令倒数为0，就可以求解得到?的值了。好了，我们来回顾一下，极大似然函数就是一种反推的过程，已知了样本满足的分布（这里就是高斯分布）和样本数据（这里是男生的身高数据），要根据这样的结果反推使该结果出现的最大的可能（也就是求解一个最可能的参数?来使我们抽到这样的100个身高数据）。
三：EM算法引入
现在问题难度升级了，在这100个身高数据中不止有男生的身高，还有女生的身高，也就是说现在我们要新引入一个性别属性，相当于多了一个变量Z（隐变量）,并且更糟糕的是，我们不知道哪些数据是男生的身高数据，哪些数据是女生的身高数据。假设男生和女生的身高分别服从各自的高斯分布，那么现在我们就要分别求解男生的身高服从的参数?1和女生身高服从的参数?2。如果我们想继续使用上例中对似然函数求导的方法求解两个?值，就需要知道每一个人的身高属于哪个性别属性；而要想知道每一个身高属于哪个性别，我们需要先有两个性别各自的高斯分布模型，才能将各个身高对号入座，也就是要先知道男生身高和女生身高各自的参数?。因此，这个时候就形成了一个相互依赖的矛盾局面。
为了打破这样的矛盾局面，我们不妨先预测一个θ值出来，假设当前预测θ1 ，然后根据θ1的值对样本进行分布，也就是将那些更符合θ1的身高数据分到男生（比如这里我们先估计θ1=[1.8,0.1]T，那么对于1.9这个身高很显然更可能属于θ1这个分布），余下的就是女生，那自然就可以根据余下的身高数据计算出θ2的值（E步）。根据E步的分布样本重新估计θ的值（M步），如此循环迭代直到收敛。这就是EM算法的基本思想。
现在，我们的完全数据就包括观测数据X和隐变量Z，即完全数据（X,Z)，（X，Z）的似然函数为P（X，Z|θ）。则似然函数变成了：
这里每个样本对应的Z（i）是未知的，所以很难用极大似然估计求解；再加上log后面还有求和（因为需要分别考虑这个身高是男生的可能性和是女生的可能性），这就变的更难解了。这时候就需要EM算法了。
四：EM算法和Jensen不等式
先贴出EM算法求解的方法：
从（1）式到（2）式大家肯定就很费解了，对概率先除以Q(z)再乘以Q(z）是有什么意义吗？再看从（2）式到（3）式就更疑惑了，为什么log函数一下子就跑到第二个求和符号里面去了？而且等号也变成了>=？这就要用到Jensen不等式来答疑解惑了。
f（x）是定义域为实数的函数，若对于全体实数x，f（x）`` >0，那么f（x）是凸函数，反之则为凹函数。若f是凸函数，有随机变量X，那么E[f(X)] >= f(E[X]) ， 对于凹函数结论相反。对于下图，我们不妨假设函数f(x),x为a和b的概率都是0.5，那么E(X)就等于0.5a+0.5b，即a，b的中值，E(X)的函数值如图所示。E(f（X))就等于0.5f（a）+0.5f（b），即f（a）和f（b）的中值，如图，显然E[f(x)]>f[E(X)]。
对于凸函数，所有的x都有这样的结论成立：函数值的期望>=期望的函数值。在这里似然函数是log，二阶导小于0，所以有结论：函数值的期望<=期望的函数值。
说完Jensen不等式，我们回到EM算法的公式推导部分，在这里（2）式乘以的Q(Z)其实是关于z的分布函数（Q(z) = p(Z<=z)）,那么(p(x?,?;?) )/? (? ) 就是一个数，Q(z）*(p(x?,?;?) )/? (? ) 的累加和就是期望值，所以（2）式可以理解为是期望的函数值，（3）式就是函数的期望值，这个变换我们就不难理解了。
别忘记我们最初的目的是为了求θ值，即求（2）式的极大值，因为（2）式恒>=(3)式，所以只要求出（3）式的最大值，然后对（2）式和（3）式取等号就可以得到（2）式的最大值了。
也就是说我们通过取不同的θ值，来不断优化上图所示的下界，而L(θ)是恒大于下界的，当下界能取到最大时，L(θ)自然就是最大了。
那什么时候能够取等号呢？在Jensen不等式中规定，只有当 (p(x?,?;?) )/? (? ) 是一个常数值时等号成立，在这里我们不妨假定Y= (p(x?,?;?) )/? (? ) ，那么当Y=C时（2）式和（3）式取等号。因为Q(Z)是z的分布函数，所以Q(Z)关于z求和是等于1的，结合分布函数的这个性质对Y做一个变形得到：
由上式可知，C其实就是p(xi,z|?)对z所有的情况求和，相当于没有了隐变量Z，只剩下p(x?|?)。（结合男生女生身高的例子，对于一个身高数据，把它是男生身高和是女生身高的两种情况都考虑进去做一个加和，不就相当于没有了性别属性Z这个隐变量吗）有了这个结论，我们再对Q(z)变形：
很显然，Q(z)代表的就是在参数?的情况下，第i个数据来自类别z的 概率。求出了Q（z），这其实也是E步需要做的事情。
EM算法的流程如下：
- 初始化分布参数?。
- E-step:根据参数?计算每个样本属于Zi的概率。
- M-step:根据计算的概率，求出含有?的似然函数的下界并最大化它，得到新的?
- 不断的迭代更新下去直至收敛。