EM算法定义及推导

EM算法是一种迭代算法,传说中的上帝算法,俗人可望不可及。用以含有隐变量的概率模型参数的极大似然估计,或极大后验概率估计

EM算法定义

输入:观测变量数据X,隐变量数据Z,联合分布\(P(X,Z|\theta)\)

输出:模型参数\(\theta\)

(1)选择初始模型参数\(\theta^{(0)}\),开始迭代

(2)E步:记\(\theta^{i}\)为第i次迭代参数\(\theta\)的估计值,计算在第i次迭代的期望\[Q(\theta,\theta^{(i)}) = E(logP(x,z|\theta)|x,\theta^{(i)}))=\int_zlogp(x,z|\theta)p(z|\theta^{(i)})\]
(3)M步:求使\(\theta^{(i+1)} = Q(\theta,\theta^{(i)})的最大值\)

(4)重复第(2)步和第(3)步

EM算法几点说明

(1)参数的初值可以任意选择,但需注意EM算法初始是敏感的

(2)E步求\(Q(\theta,\theta^{(i)})\),Q函数种的Z是为观测数据,X是观测数据,\(Q(\theta,\theta^{(i)})\)中的第一个变元表示要极大化的参数,第二个变元表示参数的当前估计值,每次迭代实际在求Q的极大值

(3)给出停止迭代的条件,一般是对较小的正数\(\xi_i,\xi_2\),若满足\(||\theta^{(i+1)} - \theta^{(i)} < \xi_i||或||Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})|| < \xi_2\)

EM算法推导

\[L(\theta)= argmaxlogP(x|\theta) = argmaxlog\int_zp(x,z|\theta)dz\]

\[L(\theta) = argmaxlog\int_z\frac{p(x,z|\theta)}{p(z|\theta^{(i)})}p(z|\theta^{(i)})dz\]

由于log函数为凹函数,则\[L(\theta) \geq \int_zlog\frac{p(x,z|\theta)}{p(z|\theta^{(i)})}p(z|\theta^{(i)})dz\]

\[L(\theta) \geq \int_zlogp(x,z|\theta)p(z|\theta^{(i)})dz - \int_zlog(p(z|\theta^{(i)}))p(z|\theta^{(i)})dz\]

由于减式后面与模型参数\(\theta\)无关,\(P(z|\theta^{(i)})是已知的\),所以只需关注减式前面的式自,令\[Q(\theta,\theta^{(i)})=\int_zlogp(x,z|\theta)p(z|\theta^{(i)})\]

和算法定义中的步骤(2)相同,将原L的优化问题转换为求原问题下界\(Q(\theta,\theta^{(i)})\)的最大值

因此,任何可以使\(Q(\theta,\theta^{(i)})\)增大的\(\theta\)都可以使\(L(\theta)\)增大,为了使\(L(\theta)\)有尽可能的增长,选择使\(Q(\theta,\theta^{(i)})\)达到最大,即\[\theta^{(i+1)} = argmaxQ(\theta,\theta^{(i)})\]

EM算法收敛性

定理1:\(设P(x|\theta)为观测数据的似然函数,\theta^{(i)}为EM算法得到的参数估计序列,P(x|\theta^{(i)})为对应的似然函数序列,则P(x|\theta^{(i)})单调递增\)

定理2:\(设L(\theta) = logP(x|\theta)为观测数据的似然函数,\theta^{(i)}为EM算法得到的参数估计序列,L(\theta^{(i)})为对应的似然函数序列\)

(1)\(如果P(x|\theta)有上界,则L(\theta^{(i)})收敛到某一值L^*\)
(2)\(在函数Q(\theta,\theta^{(i)})与L(\theta)满足一定条件下,由EM算法得到的参数估计序列\theta^{(i)}的收敛值\theta^*是L(\theta)的稳定值\)

上一篇:ionic 接触的第一个Hybrid项目


下一篇:Inverted bipolar transistor doubles as a signal clamp