第9章EM算法及其推广解析

EM算法是一种迭代算法，1977年由Dempster等人总结提出，用于含有隐变量的概率模型参数的极大似然估计，或极大后验概率估计。EM算法的每次迭代由两步组成：E步，求期望；M步，求极大。所以这一算法称为期望极大算法（ExpectationMaximization）,简称EM算法。极大似然估计是概率论在统计学中的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次实验，观察其结果，利用结果推出参数的大概值。似然函数：已知样本集X,X是通过概率密度p(x|θ)抽取。样本集X中各个样本的联合概率：为了便于分析，由于L(θ)是连乘的，还可以定义对数似然函数，将其变成连加的：求极值可以转换为以下方程：θ的极大似然估计量表示为：ln()0dLd^argmax()L9.1EM算法的引入9.1.1EM算法9.1.2EM算法的导出9.1.3EM算法在非监督学习中的应用9.2EM算法的收敛性例9.1（三硬币模型）假设有3枚硬币，分别记作A,B,C.这些硬币正面出现的概率分别是π,p,q.进行如下掷硬币试验：先掷硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后掷选出的硬币，掷硬币的结果，出现正面记作1，出现反面记作0；独立地重复n次试验（这里，n=10），观测结果如下：1,1,0,1,0,0,1,0,1,1假设只能观测到掷硬币的结果，不能观测掷硬币的过程。问如何估计三硬币正面出现的概率，即三硬币模型的参数。解三硬币模型可以写作y:观测变量，表示一次试验观测的结果是1或0z:隐变量，表示未观测到的掷硬币A的结果θ：θ=(π,p,q)是模型参数(|)(,|)(|)(|,)zzPyPyzPzPyz11(1)(1)(1)yyyyppqq将观测数据表示为Y=(Y1,Y2,…,Yn)T,未观测数据表示为Z=(Z1,Z2,…,Zn)T,则观测数据的似然函数为即考虑求模型参数θ=(π,p,q)的极大似然估计，即(|)(|)(|,)zPYPZPYZ111(|)[(1)(1)(1)]jjjjnyyyyjPYppqq^argmaxlog(|)PYEM算法首先选取参数的初值，记作，然后通过下面的步骤迭代计算参数的估计值，直至收敛为止。第i次迭代参数的估计值为。EM算法的第i+1次迭代如下E步：计算在模型参数下观测数据yj来自掷硬币B的概率那么观测数据yj来自硬币C的概率为1-μ(i+1)(0)(0)(0)(0)(,,)pq()()()()(,,)iiiipq()()(),,iiipqM步：先写出期望然后分别求导，计算模型参数的新估计值1(1)(1)(1)(1)(1)1(1)(1)(1)log(1)log1jjjjyyyyniiiijppqq假设模型参数的初值取为由E步公式对yj=1与yj=0均有μj(1)=0.5利用M步迭代公式，得到继续计算μj(2)=0.5，j=1,2,…,10继续迭代，得于是得到模型参数θ的极大似然估计：EM算法与初值的选择有关，选择不同的初值可能得到不同的参数估计值。如果取初值那么得到的模型参数的极大似然估计是(0)(0)(0)0.5,0.5,0.5pq(1)(1)(1)0.5,0.6,0.6pq(2)(2)(2)0.5,0.6,0.6pq^^^0.5,0.6,0.6pq(0)(0)(0)0.4,0.6,0.7pq^^^0.4064,0.5368,0.6432pq算法9.1（EM算法）输入：观测变量数据Y，隐变量数据Z，联合概率分布P(Y,Z|θ)，条件概率分布P(Z,Y|θ)；输出：模型参数θ.（1）选择参数的初值，开始迭代，参数的初值可以任意选择，但需注意EM算法对初值是敏感的；（2）E步：记为第i次迭代参数θ的估计值，在第i+1次迭代得E步，计算这里，是在给定观测数据Y和当前的参数估计下隐变量数据Z的条件概率分布.注意，的第一个变元表示要极大化的参数，第2个变元表示参数的当前估计值.每次迭代实际在求Q函数及其极大；(0)()i()(|,)iPZY()i()(,)iQ（3）M步：求使极大化的θ，确定i+1次迭代得参数的估计值（4）重复第（2）步和第（3）步，直到收敛，这里给出停止迭代得条件，一般是对较小的正数，若满足则停止迭代.()(,)iQ(1)i12,定义9.1（Q函数）完全数据（观测变量数据Y和隐变量数据Z）的对数似然函数关于在给定观测数据Y和当前参数下对未观测数据Z的条件概率分布的期望称为Q函数，即()ilog(,|)PYZ()(,|)iPYZ琴生（Jensen）不等式如果f是凸函数，X是随机变量，那么E[f(X)]≥f(EX)特别地，如果f是严格凸函数,E[f(X)]≥f(EX)那么当且仅当p(x=E[X])=1，也就是说X是常量。这里我们将f(E[X])简写为f(EX)Jensen不等式应用于凹函数时，不等号方向反向，也就是E[f(X)]≤f(EX)下面通过近似求解观测数据的对数似然函数的极大化问题来导出EM算法，由此可以清楚地看出EM算法的作用。假设在第i次迭代后θ的估计值是.我们希望新估计值θ能使L(θ)增加，即L(θ)L(),并逐步达到极大值.为此，考虑两者的差：()i()i利用Jensen不等式得到其下界：令则任何可以使增大的θ，也可以使L(θ)增大.为了使L(θ)有尽可能大的增长，选择使达到极大，即现在求的表达式.省去对θ的极大化而言是常数的项，有上式等价于EM算法的一次迭代，即求Q函数及其极大化.EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的算法.()(,)iB(1)i()(,)iB(1)i有时训练数据只有输入没有对应的输出{(x1,·),(x2,·),…,(xn,·)}，从这样的数据学习模型称为非监督学习问题EM算法可以用于生产模型的非监督学习生成模型由联合概率分布P(X,Y)表示，可以认为非监督学习训练数据是联合概率分布产生的数据.X为观测数据，Y为未观测数据.定理9.1设P(Y|θ)为观测数据的似然函数，(i=1,2,…)为EM算法得到的参数估计序列，则(i=1,2,…)为对应的似然函数序列，则是单调递增的，即()i()(|)iPY()(|)iPY(1)()(|)(|)iiPYPY证明由于取对数有由令于是对数似然函数可以写成只需证明右端为非负值即得出结果，由于使达到极大，所以有其第二项，由得出(1)i()(,)iQ定理9.2设L(θ)=logP(Y|θ)为观测数据的对数似然函数，(i=1,2,…)为EM算法得到的参数估计序列，(i=1,2,…)为对应的对数似然函数序列.（1）如果P(Y|θ)有上界，则收敛到某一值L*；（2）在函数与L(θ)满足一定条件下，由EM算法得到的参数估计序列的收敛值θ*是L(θ)的稳定点。定理9.2关于函数与L(θ)的条件在大多数情况下都是满足的.()i()()()log(|)iiLPY()()iL'(,)Q()i'(,)QEM算法的收敛性包含关于对数似然函数序列的收敛性和关于参数估计序列的收敛性两层意思，前者并不蕴含后者。定理只能保证参数估计序列收敛到对数似然函数序列的稳定点，不能保证收敛到极大值点。在实际应用中，初值的选择非常重要，常用的办法是选取几个不同的初值进行迭代，然后对得到的各个估计值加以比较，从中选择最好的。()()iL()i