EM算法推导

参考：李航《统计学习方法》

在初识EM算法里，我们对什么是EM算法有了一个大体的认识，这一章，我们需要对EM算法进一步的学习，涉及一些数学公式，不要害怕，没有那么恐怖~
本章，我们用Y表示观测数据，Z表示隐数据，(Y,Z)一起称为完全数据，Y则称为不完全数据。
EM算法的目标是：
θ^=argmaxθlogP(Y|θ)

EM算法：
输入：Y, P(Y,Z|θ), P(Z|Y,θ)
输出：θ

• 初始化θ(0) (注意：EM算法与初值的选择有关，选择不同的初值可能得到不同的参数估计值)

• E步：θ(i)为第i次迭代参数θ的估计值，在第i+1次迭代的E步，计算
  Q(θ,θ(i))=EZ[logP(Y,Z|θ)|Y,θ(i)]=∑ZlogP(Y,Z|θ)P(Z|Y,θ(i))

• M步：θ(i+1)=argmaxθQ(θ,θ(i))

• 重复2和3步，直至收敛

  Q(θ,θ(i))是Q函数,它是EM算法的核心，其定义是：完全数据的对数似然函数logP(Y,Z|θ)关于在给定观测数据Y和当前参数θ(i)下对隐数据Z的条件概率分布P(Z|Y,θ(i))的期望称为Q函数。

  关于EM算法的几点说明：

• EM算法对初值是敏感的，不同的初始值可能使得最后的参数估计值不同

• 停止迭代的条件是：|θ(i+1)−θ(i)|<ξ1 或者 |Q(θ(i+1),θ(i))−Q(θ(i),θ(i))|<ξ2
• 每次迭代使logP(Y|θ)增大或者达到局部极值

从前面知道，我们的目标是极大化对数似然函数argmaxθlogP(Y|θ)，因为隐变量的存在，我们无法直接求其进行求解。采用的EM算法也仅仅是近似实现对观测数据的极大似然估计。

接下来讲解如何一步一步从目标推出EM算法。
目标：极大化L(θ)=logP(Y|θ)=log(∑ZP(Y,Z|θ))=log(∑ZP(Z|θ)P(Y|Z,θ))
上式的困难是：1.有隐变量 2.包含和的对数

EM算法是通过迭代逐步近似极大化L(θ)。
预备：Jensen不等式
对于凸函数： E(f(x))>=f(E(x))
我们期望新的估计值能使对数似然函数增加，即
L(θ)>L(θ(i))

这里我们得到L(θ)的下界，并且L(θ(i))=B(θ(i),θ(i))
任何可以使B(θ(i),θ(i))增大的θ，也可以使L(θ)增大。为了使L(θ)尽可能大的增长，我们让θ(i+1)=argmaxθB(θ,θ(i))。
省去对θ极大化而言是常数的项：
θ(i+1)=argmaxθ∑ZlogP(Y,Z|θ)P(Z|Y,θ(i))=argmaxθQ(θ,θ(i))
EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法。