Ng此部分先介绍了EM算法的步骤，然后证明了其一致递增性（收敛性），最后给出了应用于混合高斯的例子。
机器学习的一种任务是求取某个显示变量x的概率分布P(x;θ)，但是鉴于P(x)不属于常见的易于表示的（例如指数型的变形）概率分布，无法通过简易的最大log-likelihood的方式求取。一种方式就是假设存在某种隐变量z，P(x,z;θ)可以表示为简易概率分布的组合，例如P(x|z;θ)与P(z;θ)都是某种常见的概率分布，则可以通过EM算法最大化argmaxθP(X;θ)近似求解x的概率分布。
更一般的，EM算法的目标是最大化P(x;θ)，假设存在隐变量z，通过最大化P(x,z;θ)的某种形式，逐步最大化P(X;θ)，并且保证P(X;θ)在过程中单调递增，即保证了收敛性。值得注意的是通常情况下P(X;θ)是非凸的，所以单调递增只能保证收敛到某个局部极值（甚至是鞍点），即EM算法不保证找到最优值，通常的做法是多次初始化选取使得P(X;θ)最大的参数值。
EM算法
明确目标：最大似然，即采样得到训练集的概率最大。
argmaxθlogP(X;θ)=argmaxθlog∏i=1mP(xi;θ) =argmaxθ∑i=1mlogP(xi;θ)
根据
log函数的性质（
log′(x)=1/x>0以及
log′′(x)=−1/x2<0），可知
logEX≥ElogX（Jensen不等式）。因为
log′′(x)严格小于
0，可知当且仅当
EX=X（即
X为常数）时
logEX=ElogX，否则
logEX>ElogX。
利用Jensen不等式，我们可以构造logP(X;θ)的下部近似（其中xi是样本i的显示变量，而zi是样本i的隐变量，zi的可能取值有k个，样本数为m，Q(zi=j;θ)为zi的某种概率分布）：
l(θ;X)=∑i=1mlogP(xi;θ)=∑i=1mlog∑j=1kP(xi,zi=j;θ)=∑i=1mlog∑j=1kQ(zi=j;θ)P(xi,zi=j;θ)Q(zi=j;θ)≥∑i=1m∑j=1kQ(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)
其中第三个不等式成立的条件是：
∀i∑kj=1Q(zi=j;θ)=1和
Q(zi=j;θ)≥0，等号成立的条件是
∀i,∑kj=1Q(zi=j;θ)P(xi,zi=j;θ)Q(zi=j;θ)=P(xi,zi=j;θ)Q(zi=j;θ)，即
P(xi,zi=j;θ)Q(zi=j;θ)是个常数。
若仅仅需要不等式成立，Q(zi=j;θ)可以是任意概率分布，但是为了保证EM算法的单调递增性（即收敛性），我们需要保证等号在当前θ不变的情况下成立。即P(xi,zi=j;θ)Q(zi=j;θ)=c，结合∑kj=1Q(zi=j;θ)=1，有c=∑kj=1P(xi,zi=j;θ)=P(xi;θ)，进而Q(zi=j;θ)=P(zi=j|xi;θ)。
综上所述，EM算法的具体步骤如下：
E(Estimate)步骤：估计Q(zi=j;θ)=P(zi=j|xi;θ)。
M(Maximize)步骤：最大化l(θ;X)的下部近似：∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)，从而使得l(θ;X)递增。
收敛性验证也就十分直观：
l(θ′;X)≥∑i=1m∑j=1kQ(zi=j;θ′)logP(xi,zi=j;θ′)Q(zi=j;θ′) ≥∑i=1m∑j=1kQ(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)=l(θ;X)
第一个不等式成立的条件是Jensen不等式，第二个不等式成立的条件是M步骤的最大化，第三个等式的成立条件是E步骤中设定
Q(zi=j;θ)使得
P(xi,zi=j;θ)Q(zi=j;θ)是常数。
EM算法的一次迭代过程的图示如下，其中黑线表示的l(θ;X)随θ的变换过程，红线是E步骤近似Q(zi=j;θ)之后∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)随θ的变化过程。图中θ为迭代前的参数值，而θ′是迭代后的参数值。注意到通过E步骤近似Q(zi=j;θ)，得到的红线与黑线在θ处相切，即l(θ;X)=∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)。同时根据Jensen不等式，红线一致位于黑线下方，即∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)是l(θ;X)的下部近似。M步骤最大化红线的取值，并更改参数值为θ′，注意到黑线在θ′处的取值（l(θ′;X)）大于红线在θ′处的取值（∑mi=1∑kj=1Q(zi=j;θ′)logP(xi,zi=j;θ′)Q(zi=j;θ′)）大于红线在θ处的取值（∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)）等于黑线在θ处的取值l(θ;X)，即每次迭代都使得l(θ;X)递增。
Ng还给出了EM算法的另一种看待方式：设J(Q,θ;X)=∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)，则EM算法可以看做是J的坐标轴递增算法。E步骤更新Q(zi=j;θ)使得J(Q′,θ;X)=l(θ;X)≥J(Q,θ;X)；M步骤更新θ使得θ′=argmaxθJ(Q,θ;X)。根据J(Q,θ;X)的单调性，从而证明了EM算法的收敛性。
混合高斯算法
目标：求解argmaxθlogP(X;θ)，其中θ={ϕj=1⋯k,μj=1⋯k,Σj=1⋯k}。
假设：存在隐变量z，其中z服从多项式分布，有P(z=j)=ϕj以及∑ki=1ϕj=1。p(x|z)服从高斯分布，有p(x|z=j)∼N(μj,Σj)。
使用EM算法：
E步骤：估计γij=p(zi=j|xi;θ(t))进而估计∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)。
p(zi=j|xi;θ)=p(zi=j,xi;θ)∑kh=1p(zi=h,xi;θ) =p(zi=j;θ)p(xi|zi=j;θ)∑kh=1p(zi=j;θ)p(xi|zi=j;θ) =ϕj12π|Σj|√exp(−12(xi−μj)TΣj(xi−μj))∑kh=1ϕh12π|Σh|√exp(−12(xi−μh)TΣh(xi−μh))
∑i=1m∑j=1kQ(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)=∑i=1m∑j=1kγijlogP(xi,zi=j;θ)γij=∑i=1m∑j=1kγijlogϕj12π|Σj|√exp(−12(xi−μj)TΣj(xi−μj))γij
M步骤：最大化∑mi=1∑kj=1Q(zi=j;θ)logP(xi,zi=j;θ)Q(zi=j;θ)实际为分别最大化带权重的高斯分布（因为zi的各个取值互不影响）；对ϕj的最优化需要结合∑kj=1ϕj=1，同样是最大化带权重的多项式分布。综上可得：
ϕj=∑mi=1γij∑kh=1∑mi=1γihμj=∑mi=1γijxi∑mi=1γijΣj=∑mi=1γij(xi−μj)(xi−μj)T∑mi=1γij
