期望极大化（EM，Expectation Maximization）是一种迭代算法，1977年由Dempster等人总结提出，用于含有隐变量（hidden variable）的概率模型参数的极大似然估计或极大后验概率估计。
概率模型有时既含有观测变量（observable variable）,又含有隐变量或潜变量（latent variable）。如果概率模型的变量都是观测变量，那么给定数据后，可以直接用极大似然估计或贝叶斯估计；但当模型含有隐变量时（如一个词所属的主题，聚类中的样本列表），难以求得参数的解析解，就需要用到EM算法。
EM算的每次迭代由两步组成：
E步：求期望步（expectation）
M步：求极大（maximization）
1 EM算法的引入
1.1 E.g.1 两硬币模型
（1）一般情况
假设有2枚硬币A，B，正面朝上的概率分别为p1 p2。为了估计正面朝上的概率，每次取一枚硬币，连续抛5次，记录结果如下：
则
（2）含有隐变量的情况
若每次使用哪枚硬币抛掷未知，结果如下：
此时相当于增加了隐变量Z = ( z 1 , z 2 , z 3 , z 4 , z 5)，其中，zi= 0代表第i 轮使用硬币A抛掷， zi= 1 代表使用硬币B抛掷。
为了估计出p1 p2首先需要估计出Z ，由于p1p2 未知，可先随机初始化 p1 p2，估计出Z ，再利用Z 估计新的p1 p2。
方法一：
令 p1= 0.2 ,p2 = 0.7 ，则在第一轮掷硬币中，
硬币A，3正2反的概率：0.2 ∗ 0.2 ∗ 0.2 ∗ 0.8 ∗ 0.8 = 0.00512
硬币B，3正2反的概率：0.7 ∗ 0.7 ∗ 0.7 ∗ 0.3 ∗ 0.3 = 0.03087
根据最大似然估计判定得到Z = ( 1 , 0 , 0 , 1 , 0 )硬币A，5正10反；硬币B，6正4反。
则 p1= 0.33 , p2= 0.6 相对于初始值更加接近真实值了。
可按照上述思路，用估计得到的p1p2再来估计Z（E-步），再用Z来估计新的p1p2（M-步），反复迭代下去，直到p1p2的值不再改变。
方法二：
上述方法中，根据每一轮使用A和B的概率，简单判定为非A即B，可不作出判定，而保留使用A和B的概率，即隐变量也是存在分布的。
如第1轮，
使用硬币A的概率：0.00512 / ( 0.00512 + 0.03087 ) = 0.14
使用硬币B的概率：1 − 0.14 = 0.86
依次计算出其他4轮的概率如下：
此时，完成了对于隐变量Z ZZ的概率分布的估计（E-步），再按照极大似然来估计p1p2M-步）。
如针对硬币A，第1轮3正2反，相当于正面概率为0.14*3=0.42，反面概率为0.14 ∗ 2 = 0.28 ，5轮列表如下：
此时，p 1 = 4.22 / ( 4.22 + 7.98 ) = 0.35
Do C B , Batzoglou S 在《What is the expectation maximization algorithm？》中提及的类似例子如下：
1.2 E.g.2 三硬币模型
假设有3枚硬币A，B，C，这些硬币正面向上的概率分别为π , p , q 进行如下抛硬币实验：先抛硬币A，根据其结果选择硬币B或C：正面选B，反面选C；然后抛出选择的硬币，出现正面记作1，出现反面记作2。
独立重复n ( n = 10 ) 次试验，观测结果如下：
1101001011
根据观测结果，估计三枚硬币正面向上的概率，即三枚硬币模型参数θ = ( π , p , q )
上述模型可以表示为：
其中，随机变量x xx是观测变量，表示本次试验观测结果是1或0；随机变量z zz是隐变量，表示未观测到的抛掷硬币A的结果。
注意：随机变量x xx的数据可以观测，随机变量z zz的数据不可观测。
令观测数据X = ( x 1 , x 2 , . . . , x n ) ，未观测数据Z = ( z 1 , z 2 , . . . , z n ) 则观测数据的似然函数：
求参数θ = ( π , p , q )的极大似然估计：
上述问题没有解析解，只能通过迭代的方法求解：选取参数的初始值，记作θ 0 = ( π 0 , p 0 , q 0 ) ，不断迭代计算参数的估计值，直至收敛。第j jj次迭代，参数估计值为θ j = ( π j , p j , q j )。其中，第j + 1 次迭代如下
E步：计算模型在参数θ j = ( π j , p j , q j ) 下观测数据y i 来自硬币B的概率:
M步：计算新的参数估计值:
假设模型参数θ 0 = ( π 0 , p 0 , q 0 ) = ( 0.5 , 0.5 , 0.5 )，对于x i = 1 与 x i = 0 ， i = 1 , 2 , . . . , 10均有μ ( i , 1 ) = 0.5 。
根据迭代，可得到
则
继续迭代得到，
模型收敛，得到参数θ \thetaθ的极大似然估计：
π=0.5表示硬币A均匀，p = 0.6 , q = 0.6符合对于数据的直观观察，10次抛硬币中，正面出现了6次。
如果初始值θ 0 = ( 0.4 , 0.6 , 0.7 ) ，迭代后得到模型参数θ ^ = ( 0.4 , 0.537 , 0.643 ) 说明EM算法与初始值的选择有关。
