最大期望算法(Expectation-Maximization algorithm，EM)
最大期望算法，也被译作最大化算法（Minorize-Maxization,MM）,是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐性变量。
一、EM算法的广义步骤
E-step:利用可用的数据来估算（猜测）潜在变量的值；
二、先写出EM的公式
这里以最大似然估计作为准则：
[ {hat theta _{MLE}} = arg max log P(X|theta )
]
EM公式
[{theta ^{(t + 1)}} = arg mathop {max }limits_theta int_Z {log } P(X,Z|theta )P(Z|X,{theta ^{(t)}})dZ
]
(int_Z {log } P(X,Z|theta )P(Z|X,{theta ^{(t)}})dZ) 也可以写作({E_{Z|X,{theta ^{(t)}}}}[log P(X,Z|theta )]) 或者(sumlimits_Z {log P(X,Z|theta )P(Z|X,{theta ^{(t)}})})
三、其收敛性的证明
此处的证明并不是非常严格的证明。要证明其收敛，就是要证明当({theta ^{(t)}} to {theta ^{(t + 1)}}) ，(P(X|{theta ^{(t)}}) to P(X|{theta ^{(t + 1)}})) 时(P(X|{theta ^{(t)}}) le P(X|{theta ^{(t + 1)}})) 。证明过程如下：
证明：
[log P(X|theta ) = log P(X,Z|theta ) - log P(Z|X,theta )
]
等式两边关于({Z|X,{theta ^{(t)}}}) 分布同时求期望：
左边:
[begin{array}{l}
{E_{Z|X,{theta ^{(t)}}}}[log P(X|theta )]\ = int_Z {log } P(X|theta )P(Z|X,{theta ^{(t)}})dZ\
= log P(X|theta )int_Z {P(Z|X,{theta ^{(t)}})} dZ\
= log P(X|theta )
end{array}
]
右边：
[begin{array}{l}
{E_{Z|X,{theta ^{(t)}}}}left[ {log P(X,Z|theta ) - log P(Z|X,theta )} right]\
= int_Z {log P(X,Z|theta )P(Z|X,{theta ^{(t)}})dZ - } int_Z {log P(Z|X,theta )P(Z|X,{theta ^{(t)}})dZ}
end{array}
]
令(Q（theta ,{theta ^{(t)}}) = int_Z {log P(X,Z|theta )P(Z|X,{theta ^{(t)}})dZ}) ，(H(theta ,{theta ^{(t)}}) = int_Z {log P(Z|X,theta )P(Z|X,{theta ^{(t)}})dZ}) 。
则
[{E_{Z|X,{theta ^{(t)}}}}left[ {log P(X,Z|theta ) - log P(Z|X,theta )} right] = Q(theta ,{theta ^{(t)}}) - H(theta ,{theta ^{(t)}})
]
由EM的算法公式可得：（因为就是要求满足要求的最大(theta) 作为(theta ^{(t+1)}) ）
[Q({theta ^{(t + 1)}},{theta ^{(t)}}) ge Q(theta ,{theta ^{(t)}})
]
也即：（(theta) 取(theta ^{(t)}) 时）
[Q({theta ^{(t + 1)}},{theta ^{(t)}}) ge Q({theta ^{(t)}},{theta ^{(t)}})
]
对于(H(theta ,{theta ^{(t)}})) ：
[begin{array}{l}
H({theta ^{(t + 1)}},{theta ^{(t)}}) - H({theta ^{(t)}},{theta ^{(t)}})\
= int_Z {log P(Z|X,{theta ^{(t + 1)}})} P(Z|X,{theta ^{(t)}})dZ - int_Z {log P(Z|X,{theta ^t})} P(Z|X,{theta ^{(t)}})dZ\
= int_Z {P(Z|X,{theta ^{(t)}})} log frac{{P(Z|X,{theta ^{(t + 1)}})}}{{P(Z|X,{theta ^t})}}dZ\
= - KL(P(Z|X,{theta ^{(t)}})||P(Z|X,{theta ^{(t + 1)}}))\
le 0
end{array}
]
也即(H({theta ^{(t + 1)}},{theta ^{(t)}}) le H({theta ^{(t)}},{theta ^{(t)}})) (P(X|{theta ^{(t)}}) le P(X|{theta ^{(t + 1)}})) ，证毕。
四、公式推导方法1
说明下数据：(X = { {x_1},{x_2}, cdots {x_N}}) (Z = { {z_i}} _{i = 1}^K) (theta) : parameter
4.1 E-M步骤公式
E-step:
[P(Z|X,{theta ^{(t)}}) to {E_{Z|X,{theta ^{(t)}}}}[log P(X,Z|theta )]
]
M-step:
[{theta ^{(t + 1)}} = arg mathop {max }limits_theta {E_{Z|X,{theta ^{(t)}}}}[log P(X,Z|theta )]
]
4.2 推导过程
[log P(X|theta ) = log (X,Z|theta ) - log (Z|X,theta )
]
等价代换，引入分布(q(Z)) :
[log P(X|theta ) = log frac{{P(X,Z|theta )}}{{q(z)}} - log frac{{P(Z|X,theta )}}{{q(z)}} , q(Z) ne 0
]
两边同时关于分布(q(Z)) 求期望
对于左边：
[begin{array}{l}
{E_{q(Z)}}[log P(X|theta )] = int_Z {log } P(X|theta )P(Z|X,{theta ^{(t)}})dZ\
= log P(X|theta )int_Z {P(Z|X,{theta ^{(t)}})} dZ\
= log P(X|theta )
end{array}
]
对于右边：
[begin{array}{l}
{E_{Z|X,{theta ^{(t)}}}}left[ {log frac{{P(X,Z|theta )}}{{q(z)}} - log frac{{P(Z|X,theta )}}{{q(z)}}} right]\
= int_Z {log frac{{P(X,Z|theta )}}{{q(z)}}} q(z)dZ - int_Z {log frac{{P(Z|X,theta )}}{{q(z)}}} q(z)dZ\
= ELBO + KLleft( {q(Z)||P(Z|X,theta )} right)
end{array}
]
其中({P(Z|X,theta )}) 为后验概率。ELBO为evidence lower bound
[begin{array}{l}
therefore log P(X|theta ) = ELBO + KLleft( {q||P} right)\
because KLleft( {q||P} right) ge 0\
therefore log P(X|theta ) ge ELBO
end{array}
]
则取最大值，就等价于ELBO取最大值，此时：
[{{hat theta }^{(t + 1)}} = arg mathop {max }limits_theta ELBO = arg mathop {max }limits_theta int_Z {log frac{{P(X,Z|theta )}}{{q(z)}}} q(z)dZ
]
(because) 当(q=P) 时，(KL=0) ，即(log P(X|theta ) = ELBO) 的等号成立。
则取(q(z) = P(Z|X,{theta ^{(t)}})) ，即上一时刻的后验。(therefore)
[begin{array}{l}
{{hat theta }^{(t + 1)}} = arg mathop {max }limits_theta int_Z {log frac{{P(X,Z|theta )}}{{P(Z|X,{theta ^{(t)}})}}} P(Z|X,{theta ^{(t)}})dZ\
= arg mathop {max }limits_theta int_Z {left[ {log P(X,Z|theta ) - log P(Z|X,{theta ^{(t)}})} right]} P(Z|X,{theta ^{(t)}})dZ
end{array}
]
此时(theta ^{(t)}) 为上一时刻的参数，故在此可视作常数，则减号后面的参数都视作常数，与目标(theta) 无关，在求解是无用，故可以省去。
则此时：
[{{hat theta }^{(t + 1)}} = arg mathop {max }limits_theta int_Z {log P(X,Z|theta )} P(Z|X,{theta ^{(t)}})dZ
]
证毕
五、公式推导方法2（涉及Jensen不等式）
5.1 Jensen不等式
对于concave function（凹函数），设(t in [0,1]) ，则有(fleft( {t cdot a + (1 - t) cdot b} right) ge tfleft( a right) + (1 - t)fleft( b right)) 。特别的，当(a = b = frac{1}{2}) 时，(fleft( {frac{{a + b}}{2}} right) ge frac{{fleft( a right) + fleft( b right)}}{2}) 。从期望的角度来看就是(fleft( E right) ge Eleft( f right)) ，先期望后函数大于等于先函数后期望。
5.2 关于E-M算法的理解
对于E-step ： (theta ^{(t)}) 是上一次求出的参数，在这一步就是常数，然后对于后验分布(Z|X,{theta ^{(t)}}) 求关于最大似然函数({log P(X,Z|theta )}) 的期望，即写出一个关于(theta) 的函数。M-step ： 针对E-step写出的期望函数，求使参数(theta) 满足其取最大值的参数作为当前时刻的参数目标(theta ^{(t+1)}) .
5.3 推导过程
[log P(X|theta ) = log int_Z {P(X,Z|theta )} dZ
]
联合分布的边缘积分=边缘概率分布
引入分布(q(Z)) :
[begin{array}{l}原式=
log int_Z {frac{{P(X,Z|theta )}}{{q(Z)}}} cdot q(Z)dZ\
= log left[ {{E_{Z|X,{theta ^{(t)}}}}left( {frac{{P(X,Z|theta )}}{{q(Z)}}} right)} right]
end{array}
]
由Jensen不等式:
[原式ge {E_{Z|X,{theta ^{(t)}}}}left[ {log left( {frac{{P(X,Z|theta )}}{{q(Z)}}} right)} right] = ELBO
]
当({frac{{P(X,Z|theta )}}{{q(Z)}}} = c) ,(c) 为常数时，等号成立。
则(q(Z) = frac{1}{c}P(X,Z|theta )) ，两边同时对(Z) 求积分：
[begin{array}{c}
int_Z {q(Z)dZ = int_Z {frac{1}{c}P(X,Z|theta )dZ} } \ \
1 = frac{1}{c}P(X|theta )
end{array}
]
(therefore) (q(Z) = P(X|theta ) cdot P(X,Z|theta ) = P(Z|X,theta ))
后续步骤同方法一。
六、广义EM算法
①狭义EM算法是广义EM算法的一种特例；(Z) 的复杂度太高，则后验概率(P(Z|X,theta)) 很难求出（intractable）。但是像GMM和HNN的(Z) 是结构化的，相对简单，所以可以用狭义EM算法进行优化。
[begin{array}{l}
log P(X|theta ) = ELBO + KL(q||P)\
= {E_{q(Z)}}left[ {log frac{{P(X,Z|theta )}}{{q(Z)}}} right] - {E_{q(Z)}}left[ {log frac{{P(Z|X,theta )}}{{q(Z)}}} right]
end{array}
]
广义EM步骤：
(
left{ begin{array}{l}
1.固定theta :hat q = arg mathop {min }limits_q KL(q||P) = arg mathop {max }limits_q ELBO(hat q,theta)\
2.固定hat q:theta = arg mathop {max }limits_theta ELBO(hat q,theta)
end{array} right.
)
对应的：
(
left{ begin{array}{l}
E-step:{q^{(t + 1)}} = arg mathop {max }limits_q ELBO(q,{theta ^{(t)}})\
M-step:{theta ^{(t + 1)}} = arg mathop {max }limits_theta ELBO({q^{(t + 1)}},{theta ^{(t)}})
end{array} right.
)
[ELBO(q,theta ) = {E_{q(Z)}} log P(X,Z|theta ) - {E_{q(Z)}}log q(Z)
]
其中(- {E_{q(Z)}}log q(Z)) 是熵(H[q(z)]) ，则
[ELBO(q,theta ) = {E_{q(Z)}} log P(X,Z|theta ) + H[q(z)]
]
广义EM是先固定一个参数在计算另一个参数，故可以从坐标上升法的角度去看。
七、EM算法的改进
①变分贝叶斯EM算法，VBEM/VIEM/VEM，三个简称叫法不同，但内容基本一致；
以上内容是在B站上up主的白板推导系列和几何周志华的西瓜书总结的内容，强烈推荐该系列课程，通俗易懂，还有一定的实时性，附上链接机器学习白板推导系列
内容来源于网络如有侵权请私信删除
客服
