本文共 2524 字，大约阅读时间需要 8 分钟。
1，EM算法简介
最大期望算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin算法 ，是一类通过迭代进行极大似然估计（Maximum Likelihood Estimation, MLE）的优化算法 ，通常作为牛顿迭代法（Newton-Raphson method）的替代用于对包含隐变量（latent variable）或缺失数据（incomplete-data）的概率模型进行参数估计。
由于迭代规则容易实现并可以灵活考虑隐变量 ，EM算法被广泛应用于处理数据的缺测值 ，以及很多机器学习（machine learning）算法，包括高斯混合模型（Gaussian Mixture Model, GMM）和隐马尔可夫模型（Hidden Markov Model, HMM）的参数估计。
2，最大似然估计
简单的举例：
假如你去赌场，但是不知道能不能赚钱，你就在门口堵着出来一个人就问一个赚了还是赔了，如果问了9个人都说赚了，那么你就会认为，赚钱的概率肯定是非常大的。已知：（1）样本服从分布的模型， （2）观测到的样本
求解：模型的参数。总的来说：极大似然估计就是用来估计模型参数的统计学方法
以100名学生的身高问题为例说明最大似然数学问题：
（1）样本集：X={x1,x2,…,xN} ，N=100
（2）概率密度：p(xi|θ)抽到男生i（的身高）的概率 （3）θ是服从分布的参数 （4）独立同分布：同时抽到这100个男生的概率就是他们各自概率的乘积 最大似然函数（对数是为了乘法转加法）：
现在问题又难了一步：
现在这100个人中，不光有男生，还有女生（2个类别，2种参数），男生和女生的身高都服从高斯分布，但是参数不同（均值，方差），即抽取得到的每个样本都不知道是从哪个分布抽取的。求解目标的是男生和女生对应的身高的高斯分布的参数是多少。加入隐变量Z：用Z=0或Z=1标记样本来自哪个分布，则Z就是隐变量，则此时最大似然函数为：
在给定初始值情况下进行迭代求解，如下图实例： 有两枚硬币（A,B），其中一枚更易正面向上（A），现在随意拿一枚硬币投掷10次，目标是用实验结果来确定拿的是哪一枚硬币，接下来选择5组投币试验，每组随意选1枚硬币投掷10次，并记录每组的正反面的次数，然后对每枚硬币求平均的正面次数
首先我们看一下如果事先我们知道投掷的是哪一枚硬币，我们可以很容易计算出每枚硬币平均的正面次数，如下图（T（tails），H（heads））
但是，假如只知道投掷的结果，如何去求每个硬币的正面率，甚至每组试验投掷的是哪一枚？ 对上面过程可以迭代求解假设A有0.6的几率为正面 ，B有0.5的几率为正面， 在每次迭代中求出硬币的正面率，然后就可以得到这些试验属于每个硬币的概率（在一组10次投掷中，出现60%的正面，就可以很自然地认为这个硬币是A）。 利用类似的原理，以下是求解示例：
两个硬币的初始假设的分布：
A：0.6几率正面 （更易得到正面） B：0.5几率正面投掷出5正5反的概率（第一组，计算每次事件（共5组）来自A或者B的概率）：
pA=C(10,5) * (0.6^5) * (0.4^5) （二项分布的概率公式，在n=10次试验中k=5次是成功的） pB=C(10,5) * (0.5^5) * (0.5^5)
然后进行归一化处理（得到第一组试验选择哪一枚硬币的概率大小（权重），对剩下4组进行相同的处理）如下：
选择硬币A的概率（以该值作为权重乘以正面次数计算A的期望值(2.2)并记录下来）： pA/(pA+pB)=0.45 选择硬币B的概率：（以该值作为权重乘以正面次数计算B的期望值(2.8)并记录下来） 1- pA=0.55然后，利用上述5组得到期望值求出A和B的新的平均正面次数置为最初的假设分布值，通过不断迭代最后会收敛到A和B真实的正面朝上的概率，一旦得到这些概率值就可以通过E-step计算事件来自A或者B，结合E-step和M-step得知A和B的成功率
3，EM算法推导
问题：样本集{x(1),…,x(m)}，包含m个独立的样本。其中每个样本i对应的类别z(i)是未知的，所以很难用最大似然求解
上式中，要考虑每个样本在各个分布中的情况。本来正常求偏导就可以了，但是现在log后面还有求和，这就难解了。对上式中的一部分做变换如下（要凑-Jensen不等式）： 
3.1 Jensen不等式
设f是定义域为实数的函数，如果对于所有的实数x，f(x)的二次导数大于等于0，那么f是凸函数。如果f是凸函数，X是随机变量，那么：E[f(X)]>=f(E[X])
实线f是凸函数，X有0.5的概率是a，有0.5的概率是bX的期望值就是a和b的中值。Jensen不等式应用于凹函数时，不等号方向反向 
令： 
则有： 
由Jensen不等式可得： 
即 
下界比较好求，所以我们要优化这个下界来使得似然函数最大。优化下界，迭代到收敛 
Jensen中等式成立的条件是随机变量是常数 
Q（z）是z的分布函数 
即所有的分子和等于常数C（和分母相同）由上式： 
Q(z)代表第i个数据是来自zi的概率。 4，EM算法流程
（1）初始化分布参数θ
（2）E-step：根据参数θ计算每个样本属于zi的概率(也就是我们的Q) （3）M-Step：根据Q，求出含有θ的似然函数的下界并最大化它，得到新的参数θ （4）不断的迭代更新下去5，GMM（高斯混合模型）
（1）数据可以看作是从数个 Gaussian Distribution 中生成出来的；
（2）GMM 由 K 个 Gaussian 分布组成，每个 Gaussian 称为一个“Component” （3）类似k-means方法，求解方式跟EM一样 （4）不断的迭代更新下去转载地址：http://eahwi.baihongyu.com/