EM算法，即最大期望算法（Expectation-maximization algorithm），是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型 依赖于无法观测的隐性变量。
最大期望算法经过两个步骤交替进行计算，
第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。
多数情况下我们是根据已知条件来推算结果，而最大似然估计是已经知道了结果，然后寻求使该结果出现的可能性最大的条件，以此作为估计值。似然描述的是结果已知的情况下，该事件在不同条件下发生的可能性，似然函数的值越大说明该事件在对应的条件下发生的可能性越大。
算法推导
对于(m)个样本观察数据({x^{(1)},x^{(2)},x^{(3)}…,x^{(m)}})，找出样本的模型参数(θ), 极大化模型分布的对数似然函数如下
[egin{aligned}
θ={argmax}_θ sum_i log {P(x^i;θ)}
end{aligned}
]
如果我们得到的观察数据有未观察到的隐含数据(z={z^{(1)},z^{(2)},z^{(3)}…,z^{(m)}})，此时我们的极大化模型分布的对数似然函数如下：
[θ={argmax}_θ sum_i log {P(x^i; heta)}={argmax}_θ sum_i log sum_z {p(x^i,z^i; heta)}
]
第一步是对极大似然取对数，第二步是对每个样例的每个可能类别(z)求联合分布概率和。
首先，我们把分子分母同乘以一个相等的函数（即隐变量(Z)的概率分布(Q_i {(z^{(i)})})，其概率之和等于1，即(sum_z Q_i {(z^{(i)})}=1)。其次，利用Jensen不等式（即，在凸函数中，有函数的期望大于等于期望的函数，即(E[f(X)]>=f(E[X]))；当(f)是（严格）凹函数当且仅当(-f)是（严格）凸函数，不等号方向反向），我们将上式进行缩放，可得：
[egin{aligned}
sum_i log p(x^{(i)}; heta)=sum_t log sum_{z^{(i)}} p(x^{(i)},z^{(i)}; heta) \
=sum_i log sum_{z^{(i)}} Q_i {(z^{(i)})} frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}} \
geq sum_i sum_{z^{(i)}} Q_i {(z^{(i)})} log frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}}
end{aligned}
]
其中(sum_{z^{(i)}} Q_i {(z^{(i)})} frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}})就是(frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}})的期望，(log)函数为凹函数（其二次导数为(frac{−1}{x^2}<0)）。
此时如果要满足Jensen不等式的等号，则有：
[frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}}=c,c为常数
]
对该式做个变换，并对所有的z求和，得到
[sum_z p(x^{(i)},z^{(i)}; heta)=sum_z Q_i {(z^{(i)})}c
]
由于(Q_i {(z^{(i)})})是一个分布，所以满足$sum_z Q_i {(z^{(i)})}=1 $
可得：
[sum_z p(x^{(i)},z^{(i)}; heta) = c \
Q_i {(z^{(i)})}=frac{p(x^{(i)},z^{(i)}; heta)}{c}=
frac{p(x^{(i)},z^{(i)}; heta)}{sum_z p(x^{(i)},z^{(i)}; heta)}=frac{p(x^{(i)},z^{(i)}; heta)}{p(x^{(i)}; heta)} = p(z^{(i)}|x^{(i)}; heta)
]
至此，我们推出了在固定参数(θ)后，使下界拉升的(Q_i {(z^{(i)})})的计算公式就是条件概率，解决了(Q_i {(z^{(i)})})如何选择的问题。这一步就是E步，建立(L(θ))的下界。接下来的M步，就是在给定(Q_i {(z^{(i)})})后，调整(θ)：
[egin{aligned}
{argmax}_θ sum_i sum_{z^{(i)}} Q_i {(z^{(i)})} log
frac{p(x^{(i)},z^{(i)}; heta)}{Q_i {(z^{(i)})}}
end{aligned}
]
去掉上式中为常数的部分，则我们需要极大化的对数似然下界为：
[egin{aligned}
{argmax}_θ sum_i sum_{z^{(i)}} Q_i {(z^{(i)})} log
{p(x^{(i)},z^{(i)}; heta)}
end{aligned}
]
上式也就是我们的EM算法的M步。
EM算法能保证收敛吗？如果收敛，那么能保证收敛到全局最大值吗？
要证明EM算法收敛，则我们需要证明我们的 对数似然函数的值在迭代的过程中一直在增大。
[sum_{i=1}^m log {P(x^i; heta^{j+1})} geq sum_{i=1}^m log {P(x^i; heta^{j})}
]
由于：
[L( heta; heta^{j})=sum_{i=1}^m sum_{z^i} P(z^{(i)}|x^i; heta^j) log P(x^{(i)},z^{(i)}; heta)
]
令：
[H( heta; heta^{j})=sum_{i=1}^m sum_{z^i} P(z^{(i)}|x^i; heta^j) log P(z^{(i)}|x^i; heta^j)
]
上两式相减得到：
[sum_{i=1}^m log P(x^i; heta)=L( heta; heta^{j})-H( heta; heta^{j})
]
在上式中分别取(θ)为(θ^j)和(θ^(j+1))，并相减得到
[sum_{i=1}^m log P(x^i; heta^{j+1})-sum_{i=1}^m log P(x^i; heta^{j})=[L( heta^{j+1}; heta^{j})-L( heta^{j}; heta^{j})]-[H( heta^{j+1}; heta^{j})-H( heta^{j}; heta^{j})]
]
要证明EM算法的收敛性，我们只需要证明上式的右边是非负的即可。
由于(θ^{j+1})使得$ L(θ,θ^j )$极大，因此有:
[L( heta^{j+1}; heta^{j})-L( heta^{j}; heta^{j}) geq 0
]
而对于第二部分，我们有：
[egin{aligned}
H( heta^{j+1}; heta^{j})-H( heta^{j}; heta^{j})=& sum_{i=1}^m sum_{z^i} P(z^{(i)}|x^i; heta^j) log frac {P(z^{(i)}|x^i; heta^{j+1}) }{P(z^{(i)}|x^i; heta^{j}) } \
leq &sum_{i=1}^m log (sum_{z^i} P(z^{(i)}|x^i; heta^{j}) frac{P(z^{(i)}|x^i; heta^{j+1})}{P(z^{(i)}|x^i; heta^{j})}) \
=& sum_{i=1}^m log (sum_{z^i} P(z^{(i)}|x^i; heta^{j+1}))=0
end{aligned}
]
其中第2式用到了Jensen不等式，只不过和之前使用相反而已，第3式用到了概率分布累积为1的性质。
至此，我们得到了
[sum_{i=1}^m log {P(x^i; heta^{j+1})} - sum_{i=1}^m log {P(x^i; heta^{j})} geq 0
]
证明了EM算法的收敛性。从上面的推导可以看出，EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标(L(θ,θ^j))是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。如果我们从算法思想的角度来思考EM算法，我们可以发现我们的算法里已知的是观察数据，未知的是隐含数据和模型参数，在E步，我们所做的事情是固定模型参数的值，优化隐含数据的分布，而在M步，我们所做的事情是固定隐含数据分布，优化模型参数的值。比较下其他的机器学习算法，其实很多算法都有类似的思想。比如SMO算法，坐标轴下降法(Lasso回归算法), 都使用了类似的思想来求解问题。