EM

观测数据表示为 Y=(y1,…,yn)TY=(y_1,\ldots,y_n)^T ,未观测数据表示为 Z=(Z1,…,Zn)TZ=(Z_1,\ldots, Z_n)^T，则观测数据的似然函数为

L(θ)=log⁡∏j=inP(Y∣θ)=∑j=inlog⁡P(Y∣θ)=∑j=inlog⁡∑zP(Z∣θ)P(Y∣Z,θ)L(\theta) = \log \prod_{j=i}^n P(Y|\theta) = \sum_{j=i}^n \log P(Y|\theta) = \sum_{j=i}^n \log \sum_z P(Z|\theta)P(Y|Z,\theta)

EM思路：先是对整体求极大似然估计对数，但因为隐藏变量Z的存在，所以直接最大化L就不可能了。但是可以通过不断的建立L的下界（E步），然后优化下界（M步）。

EM算法一般化分析

每次迭代优化的目标： ln⁡p(Y∣θg+1)≥ln⁡p(Y∣θg)\ln p(Y|\theta^{g+1}) \ge \ln p(Y|\theta^g) 对 ln⁡p(Y∣θ)=ln⁡p(Y,Z∣θ)p(Z∣Yθ)=ln⁡p(Y,Z∣θ)−ln⁡p(Z∣Y,θ)\ln p(Y|\theta) = \ln \frac {p(Y,Z|\theta)} {p(Z|Y\theta)} = \ln p(Y,Z|\theta) - \ln p(Z|Y,\theta) 式子两边求期望。 注意，期望是对某个分布的而言的，这里是对p(Z∣Y,θg)p(Z|Y,\theta^{g})求期望的。

  • 左边： ∫Zln⁡p(Y∣θ)p(Z∣Y,θg)dZ=ln⁡p(Y∣θ)\int_Z \ln p(Y|\theta) p(Z|Y,\theta^g) dZ = \ln p(Y|\theta) 因为不包含Z，所以可以提到积分外，里面的概率分布积分就是1.

  • 右边： ∫Zln⁡p(Y,Z∣θ)p(Z∣Y,θg)dZ−∫Zln⁡p(Z∣Y,θ)p(Z∣Y,θg)dZ\color{Red}{ \int_Z \ln p(Y,Z|\theta) p(Z|Y,\theta^g) dZ } - \int_Z \ln p(Z|Y,\theta) p(Z|Y,\theta^g) dZ 每次迭代只对前面一部分求最大，即θg+1=arg⁡max⁡θ∫Zln⁡p(Y,Z∣θ)p(Z∣Y,θg)dZ\theta^{g+1} = \arg \max_{\theta} \int_Z \ln p(Y,Z|\theta) p(Z|Y,\theta^g) dZ ，这个就是《统计学习方法》中的Q函数。

《统计学习方法》page158,Q函数定义：完全数据的对数似然log⁡P(Y,Z∣θ)\log P(Y,Z|\theta)关于在给定的观测数据Y和当前参数θg\theta^g下对未观测数据Z的条件概率分布P(Z∣Y,θ)P(Z|Y,\theta)的期望

这个式子里面是期望，外面求最大，这就是Expectation Maximization。 在每次迭代后，后面一部分会变小，所以整体保证了迭代目标。

p(X∣θ)=∑Zp(X,Z∣θ)ln⁡p(X∣θ)=L(q,θ)+KL(q∣∣p)KL(q∣∣p)=−∑Zq(Z)ln⁡p(Z∣X,θ)q(Z)L(q,θ)=∑Zq(Z)ln⁡p(X,Z∣θ)q(Z)=∑Zp(Z∣X,θold)ln⁡p(X,Z∣θ)−∑Zp(Z∣X,θold)ln⁡p(Z∣X,θold)\begin{align} p(X|\theta) &= \sum_Z p(X,Z|\theta) \\ \ln p(X|\theta) &= L(q,\theta) + KL(q||p) \\ KL(q||p) &= -\sum_Z q(Z)\ln \frac {p(Z|X,\theta)}{q(Z)} \\ L(q,\theta) &= \sum_Z q(Z)\ln \frac {p(X,Z|\theta)}{q(Z)} = \sum_Z p(Z|X,\theta^{old})\ln p(X,Z|\theta) - \sum_Z p(Z|X,\theta^{old})\ln p(Z|X,\theta^{old}) \\ \end{align}

EM算法框架

  • 选择合适的初始参数

  • E-step，计算隐含变量的后验概率p(Z∣Y,θold)p(Z|Y,\theta^{old})。利用当前参数值计算隐含变量的后验概率，并基于此计算目标函数的期望

  • M-step，优化θold=arg⁡maxθQ(θ,θold)\theta^{old} = \arg max_{\theta} Q(\theta, \theta^{old})，其中Q(θ,θold)=∑Zp(Z∣Y,θold)ln⁡p(Y,Z∣θ)Q(\theta, \theta^{old}) = \sum_Z p(Z|Y,\theta^{old})\ln p(Y,Z|\theta)

  • 收敛性判别，是否终止

以下是以前从jensen不等式看EM算法的，感觉不如EM一般化分析清晰

E步

完全数据的对数似然log⁡P(Y,Z∣θ)\log P(Y,Z|\theta) 关于在给定观测数据YY和当前参数θi\theta_i下对未观测数据ZZ的条件概率分布log⁡P(Z∣Y,θi)\log P(Z|Y,\theta_i)的期望

−L(θ)=−∑j=inlog⁡∑ziP(Y,zi∣θ)=−∑j=inlog⁡∑ziQ(Zi)P(Y,zi∣θ)Q(Zi)≤∑j=in∑ziQ(Zi)(−log⁡∑ziP(Y,zi∣θ)Q(Zi))-L(\theta) = -\sum_{j=i}^n \log \sum_{z_i} P(Y,z_i|\theta) = -\sum_{j=i}^n \log \sum_{z_i} Q(Z_i)\frac{P(Y,z_i|\theta)}{Q(Z_i)} \le \sum_{j=i}^n \sum_{z_i} Q(Z_i) (-\log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)})

其中∑ziQ(Zi)P(Y,zi∣θ)Q(Zi)\sum_{z_i} Q(Z_i)\frac{P(Y,z_i|\theta)}{Q(Z_i)} 就是 P(Y,zi∣θ)Q(Zi)\frac{P(Y,z_i|\theta)}{Q(Z_i)} 的期望，−log⁡-\log是凸函数，所以可以用 jensen 不等式。

将上式简化下，就得到《统计学习方法》上的形式：

L(θ)≥∑j=in∑ziQ(Zi)log⁡∑ziP(Y,zi∣θ)Q(Zi)L(\theta) \ge \sum_{j=i}^n \sum_{z_i} Q(Z_i) \log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)}

期望的 Lazy Statistician 规则

  • x是离散型随机变量，分布律为P(X=xk)=pk,k=1,2,…P(X=x_k)=p_k, k=1,2,\ldots,则：

    E(Y)=∑k=1∞g(xk)pkE(Y)=\sum_{k=1}^{\infty}g(x_k)p_k

  • x是连续型随机变量，概率密度函数为 f(x)f(x)，则有

    E(Y)=∫−∞∞g(x)f(x)dxE(Y) = \int_{-\infty}^\infty g(x)f(x)dx

jensen不等式

如果f是凸函数，则E[f(X)]≥f(E[X])E[f(X)] \ge f(E[X]) 。

其实凸函数的定义就一个jensen不等式。 f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1)+(1-\lambda)f(x_2)

推广到多个变量，得：

f(λ1x1+…+λnxn)≤λf1(x1)+⋯+λnf(xn)λ1…λn≤0λ1+…+λn=1f(\lambda_1 x_1 + \ldots +\lambda_n x_n) \le \lambda f_1(x_1)+ \dots + \lambda_nf(x_n) \\ \lambda_1 \ldots \lambda_n \le 0 \\ \lambda_1 + \ldots +\lambda_n = 1

M步

上式相当于给出了目标函数的下界，提高下界即最大化目标函数。这个不等式的最高就是等式成立，需要让随机变量或函数值为常数, 即 P(Y,zi∣θ)Q(Zi)=C\frac{P(Y,z_i|\theta)}{Q(Z_i)} = C。假设θ\theta给定。 因为∑ZiQ(Zi)=1\sum_{Z_i} Q(Z_i) = 1，所以∑ZiP(Y,zi∣θ)=C\sum_{Z_i} P(Y,z_i|\theta) = C。 则Q(Zi)=P(Y,zi∣θ)C=P(Y,zi∣θ)∑ZiP(Y,zi∣θ)=P(Y,zi∣θ)P(Y∣θ)=P(Zi∣Y,θ)Q(Z_i) = \frac{P(Y,z_i|\theta)}{C} = \frac{P(Y,z_i|\theta)}{\sum_{Z_i} P(Y,z_i|\theta)} = \frac{P(Y,z_i|\theta)}{P(Y|\theta)} = P(Z_i|Y,\theta)

所以EM算法的步骤如下：

  • 初始化参数：θ\theta

  • E步：Q(Zi)=P(Zi∣Y,θ)Q(Z_i) = P(Z_i|Y,\theta)

  • M步：θ=arg⁡max⁡θ∑j=in∑ziQ(Zi)log⁡∑ziP(Y,zi∣θ)Q(Zi)\theta = \arg \max_{\theta} \sum_{j=i}^n \sum_{z_i} Q(Z_i) \log \sum_{z_i} \frac{P(Y,z_i|\theta)}{Q(Z_i)}

  • 收敛判断：若似然函数未收敛，则转至第二步。

半监督EM

网上没找到半监督式的EM，但是我想，在E步算每个样本分类的期望时，不改变已经标注的类别，这样在M步时，这些标注样本依然可以起效。

online EM

参考MLAPP和《Online EM for Unsupervised Models》

有batch EM，incremental EM，stepwise EM。

  • Let ϕ(x,z)\phi(x, z) be a vector of sufficient statistics for a single data case.

  • Let si=∑zp(z∣xi,θ)ϕ(xi,z)s_i = \sum_z p(z|x_i,\theta) \phi (x_i,z) be the expected sufficient statistics for case i, and μ=∑i=1Nsi\mu = \sum_{i=1}^N s_i be the sum of the ESS.

  • let θ(μ)\theta(\mu) denote the ML or MAP estimate of the parameters in the M step.

stepsize 和 mimi_batch_size很重要。 if we take ηk=(k+2)α\eta_k = (k+2)^\alpha , then any 0.5<α≤10.5 \lt \alpha \le 1 is valid. mimi_batch_size越大，则越稳定。

个人理解就是 新来的样本训练出的新参数， 然后跟momentum方式一样结合老参数更新参数

Other EM variants

Variational EM , Monte Carlo EM , Generalized EM

The EM algorithm is simple, but can be much slower than direct gradient methods

EM算法的应用

  • 混合高斯模型

  • 混合朴素贝叶斯模型

  • 因子分析

  • 贝叶斯神经网络

EM算法存在的意义是什么？

PreviousC-SVM求解NextGMM

Last updated

Was this helpful?