Machine Learning-L15-EM算法全解析（上）

期望极大化（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，正面朝上的概率分别为p₁ p₂。为了估计正面朝上的概率，每次取一枚硬币，连续抛5次，记录结果如下：

则

（2）含有隐变量的情况

若每次使用哪枚硬币抛掷未知，结果如下：

此时相当于增加了隐变量Z = ( z _{1 ,} z _{2 ,} z _{3 ,} z _{4 ,} z ₅)，其中，z_i= 0代表第i 轮使用硬币A抛掷， z_i= 1 代表使用硬币B抛掷。

为了估计出p₁ p₂首先需要估计出Z ，由于p₁p₂ 未知，可先随机初始化 p₁ p₂，估计出Z ，再利用Z 估计新的p₁ p₂。

方法一：

令 p₁= 0.2 ,p₂ = 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反。

则 p₁= 0.33 ,  p₂= 0.6 相对于初始值更加接近真实值了。

可按照上述思路，用估计得到的p₁p₂再来估计Z（E-步），再用Z来估计新的p₁p₂（M-步），反复迭代下去，直到p₁p₂的值不再改变。

方法二：

上述方法中，根据每一轮使用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-步），再按照极大似然来估计p₁p₂M-步）。

如针对硬币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算法与初始值的选择有关。