一、概述

介绍

概率模型有时既包括观测变量（observed variable），又包括隐变量（latent variable）。当概率模型只包括观测变量时，那么给定观测数据，就可以直接运用极大似然估量法或许贝叶斯估量法进行模型参数的求解。然而假如模型包括隐变量，就不能直接运用这些简略的办法了。EM算法便是用来解决这种含有隐变量的概率模型参数的极大似然参数估量法。这儿只讨论极大似然估量，极大后验估量与其相似。

算法

EM算法的输入如下：

$X$ :观测数据

$Z$ : 末观测数据 (隐变量)

$\mid \theta)$ : 联合散布

$\mid x, \theta)$ :后验散布

$\theta$ :parameter

在算法运转开始时需求选择模型的初始化参数 $(0)\theta^{(0)}$ 。EM算法是一种迭代更新的算法，其核算公式为:

t+1=argmax⁡Ez∣x,t[log⁡p(x,z∣)]=argmax⁡∫zlog⁡p(x,z∣)⋅p(z∣x,t)dz\begin{gathered} \theta^{t+1}=\underset{\theta}{\operatorname{argmax} E_{z \mid x, \theta^t}[\log p(x, z \mid \theta)]} \\ =\underset{\theta}{\operatorname{argmax}} \int_z \log p(x, z \mid \theta) \cdot p\left(z \mid x, \theta^t\right) \mathrm{d} z \end{gathered}

这个公式包括了迭代的两步:

①E step: 核算 $\mid \theta)$ 在概率散布 $p(z∣x,t)p\left(z \mid x, \theta^t\right)$ 下的期望；
②M step: 核算使这个期望最大化的参数得到下一个EM进程的输入。

总结来说，EM算法包括以下进程：

①选择初始化参数 $(0)\theta ^{(0)}$ ；
②E step；
③M step；
④重复②③步直至收敛。

二、EM算法的收敛性

现在要证明迭代求得的 $t\theta^t$ 序列会使得对应的 $p(x∣t)p\left(x \mid \theta^t\right)$ 是单调递加的 (假如 $p(x∣t)p\left(x \mid \theta^t\right)$ 是单调递增的，那么训练数据的似然便是单调递加的），也便是说要证明 $p(x∣t)≤p(x∣t+1)p\left(x \mid \theta^t\right) \leq p\left(x \mid \theta^{t+1}\right)$ 。首要咱们有:

log⁡p(x∣)=log⁡p(x,z∣)−log⁡p(z∣x,)\log p(x \mid \theta)=\log p(x, z \mid \theta)-\log p(z \mid x, \theta)

接下来等式两头一起求关于 $p(z∣x,t)p\left(z \mid x, \theta^t\right)$ 的期望:

左面=∫zp(z∣x,t)⋅log⁡p(x∣)dz=log⁡p(x∣)∫zp(z∣x,t)dz=log⁡p(x∣)右边=∫zp(z∣x,t)⋅log⁡p(x,z∣)dz⏟记作Q(,t)−∫zp(z∣x,t)⋅log⁡p(z∣x,)dz⏟记作H(,t)\begin{gathered} \text { 左面 }=\int_z p\left(z \mid x, \theta^t\right) \cdot \log p(x \mid \theta) \mathrm{d} z \\ =\log p(x \mid \theta) \int_z p\left(z \mid x, \theta^t\right) \mathrm{d} z \\ =\log p(x \mid \theta) \\ \text { 右边 }=\underbrace{\int_z p\left(z \mid x, \theta^t\right) \cdot \log p(x, z \mid \theta) \mathrm{d} z}_{\text {记作 } Q\left(\theta, \theta^t\right)}-\underbrace{\int_z p\left(z \mid x, \theta^t\right) \cdot \log p(z \mid x, \theta) \mathrm{d} z}_{\text {记作 } H\left(\theta, \theta^t\right)} \end{gathered}

因而有：

log⁡p(x∣)=∫zp(z∣x,t)⋅p(x,z∣)dz−∫zp(z∣x,t)⋅log⁡p(z∣x,)dz\log p(x \mid \theta)=\int_z p\left(z \mid x, \theta^t\right) \cdot p(x, z \mid \theta) \mathrm{d} z-\int_z p\left(z \mid x, \theta^t\right) \cdot \log p(z \mid x, \theta) \mathrm{d} z

这儿界说了 $Q(,t)Q\left(\theta, \theta^t\right)$ ，称为 $Q\mathrm{Q}$ 函数 ( $Q\mathrm{Q}$ function)，这个函数也便是上面的概述中迭代公式里用到的函数，因而满足 $Q(t+1,t)≥Q(t,t)Q\left(\theta^{t+1}, \theta^t\right) \geq Q\left(\theta^t, \theta^t\right)$ 。

接下来将上面的等式两头 $\theta$ 别离取 $t+1\theta^{t+1}$ 和 $t\theta^t$ 并相减:

log⁡p(x∣t+1)−log⁡p(x∣t)=[Q(t+1,t)−Q(t,t)]−[H(t+1,t)−H(t,t)]\log p\left(x \mid \theta^{t+1}\right)-\log p\left(x \mid \theta^t\right)=\left[Q\left(\theta^{t+1}, \theta^t\right)-Q\left(\theta^t, \theta^t\right)\right]-\left[H\left(\theta^{t+1}, \theta^t\right)-H\left(\theta^t, \theta^t\right)\right]

咱们需求证明 $log⁡p(x∣t+1)−log⁡p(x∣t)≥0\log p\left(x \mid \theta^{t+1}\right)-\log p\left(x \mid \theta^t\right) \geq 0$ ，一起已知 $Q(t+1,t)−Q(t,t)≥0Q\left(\theta^{t+1}, \theta^t\right)-Q\left(\theta^t, \theta^t\right) \geq 0$ ，现在来调查 $H(t+1,t)−H(t,t):H\left(\theta^{t+1}, \theta^t\right)-H\left(\theta^t, \theta^t\right) \text { : }$

$1=0H(\theta ^{t+1},\theta ^{t})-H(\theta ^{t},\theta ^{t})\\ =\int _{z}p(z|x,\theta ^{t})\cdot log\; p(z|x,\theta ^{t+1})\mathrm{d}z-\int _{z}p(z|x,\theta ^{t})\cdot log\; p(z|x,\theta ^{t})\mathrm{d}z\\ =\int _{z}p(z|x,\theta ^{t})\cdot log\frac{p(z|x,\theta ^{t+1})}{p(z|x,\theta ^{t})}\mathrm{d}z\\ \leq log\int _{z}p(z|x,\theta ^{t})\frac{p(z|x,\theta ^{t+1})}{p(z|x,\theta ^{t})}\mathrm{d}z\\ =log\int _{z}p(z|x,\theta ^{t+1})\mathrm{d}z\\ =log\; 1\\ =0$

这儿的不等号使用了Jensen不等式：

yj,其间j≥0，∑jj=1log\sum _{j}\lambda _{j}y_{j}\geq \sum _{j}\lambda _{j}log\; y_{j},其间\lambda _{j}\geq 0，\sum _{j}\lambda _{j}=1

也可以运用KL散度来证明 $∫zp(z∣x,t)⋅log⁡p(z∣x,t+1)p(z∣x,t)dz≤0\int_z p\left(z \mid x, \theta^t\right) \cdot \log \frac{p\left(z \mid x, \theta^{t+1}\right)}{p\left(z \mid x, \theta^t\right)} \mathrm{d} z \leq 0$ ，两个概率散布 $P (x)$ 和 $Q (x)$ 的KL散度是恒 $≥0\geq 0$ 的，界说为:

DKL(P∥Q)=Ex∼P[log⁡P(x)Q(x)]D_{K L}(P \| Q)=E_{x \sim P}\left[\log \frac{P(x)}{Q(x)}\right]

因而有:

∫zp(z∣x,t)⋅log⁡p(z∣x,t+1)p(z∣x,t)dz=−KL(p(z∣x,t)∣∣p(z∣x,t+1))≤0\int_z p\left(z \mid x, \theta^t\right) \cdot \log \frac{p\left(z \mid x, \theta^{t+1}\right)}{p\left(z \mid x, \theta^t\right)} \mathrm{d} z=-K L\left(p\left(z \mid x, \theta^t\right)|| p\left(z \mid x, \theta^{t+1}\right)\right) \leq 0

因而得证 $log⁡p(x∣t+1)−log⁡p(x∣t)≥0\log p\left(x \mid \theta^{t+1}\right)-\log p\left(x \mid \theta^t\right) \geq 0$ 。这说明运用EM算法迭代更新参数可以使得 $log⁡p(x∣)\log p(x \mid \theta)$ 逐渐增大。

另外还有其他定理确保了EM的算法收敛性。首要关于 $)\theta^i(i=1,2, \cdots)$ 序列和其对应的对数似然序列 $)L\left(\theta^t\right)=\log p\left(x \mid \theta^t\right)(t=1,2, \cdots)$ 有如下定理:

①假如 $\mid \theta)$ 有上界，则 $L(t)=log⁡p(x∣t)L\left(\theta^t\right)=\log p\left(x \mid \theta^t\right)$ 收敛到某一值 $L^*$ ；
②在函数 $Q(,′)Q\left(\theta, \theta^{\prime}\right)$ 与 $L()L(\theta)$ 满足必定条件下，由EM算法得到的参数估量序列 $t\theta^t$ 的收敛值 $∗\theta^*$ 是 $L()L(\theta)$ 的稳定点。

三、EM算法的导出

ELBO+KL散度的办法

关于前面用过的式子，首要引进一个新的概率散布 $q (z)$ ：

$q(z)≠0log\; p(x|\theta )=log\; p(x,z|\theta )-log\; p(z|x,\theta )\\ =log\; \frac {p(x,z|\theta )}{q(z)}-log\; \frac{p(z|x,\theta )}{q(z)}\; \; q(z)\neq 0$

以上引进一个关于 $z$ 的概率散布 $q (z)$ ，然后式子两头一起求对 $q (z)$ 的期望：

$p(z∣x,)q(z)dz⏟KL(q(z)∣∣p(z∣x,))左面=\int _{z}q(z)\cdot log\; p(x|\theta )\mathrm{d}z=log\; p(x|\theta )\int _{z}q(z)\mathrm{d}z=log\; p(x|\theta )\\ 右边=\underset{ELBO(evidence\; lower\; bound)}{\underbrace{\int _{z}q(z)log\; \frac{p(x,z|\theta )}{q(z)}\mathrm{d}z}}\underset{KL(q(z)||p(z|x,\theta ))}{\underbrace{-\int _{z}q(z)log\; \frac{p(z|x,\theta )}{q(z)}\mathrm{d}z}}$

因而咱们得出 $log⁡p(x∣)=ELBO+KL(q∥p)\log p(x \mid \theta)=E L B O+K L(q \| p)$ ，由于KL散度恒 $≥0\geq 0$ ，因而 $log⁡p(x∣)≥ELBO\log p(x \mid \theta) \geq E L B O$ ，则 $E L BO$ 便是似然函数 $log⁡p(x∣)\log p(x \mid \theta)$ 的下界。使得 $log⁡p(x∣)=ELBO\log p(x \mid \theta)=E L B O$ 时，就必须有 $\| p)=0$ ，也便是 $\mid x, \theta)$ 时。在

每次迭代中咱们取 $q(z)=p(z∣x,t)q(z)=p\left(z \mid x, \theta^t\right)$ ，就可以确保 $log⁡p(x∣t)\log p\left(x \mid \theta^t\right)$ 与 $E L BO$ 持平，也便是:

$p(z∣x,)p(z∣x,t)dz⏟KL(p(z∣x,t)∣∣p(z∣x,))log\; p(x|\theta )=\underset{ELBO}{\underbrace{\int _{z}p(z|x,\theta ^{t})log\; \frac {p(x,z|\theta )}{p(z|x,\theta ^{t})}\mathrm{d}z}}\underset{KL(p(z|x,\theta ^{t})||p(z|x,\theta ))}{\underbrace{-\int _{z}p(z|x,\theta ^{t})log\; \frac{p(z|x,\theta )}{p(z|x,\theta ^{t})}\mathrm{d}z}}$

当 $=t\theta=\theta^t$ 时， $log⁡p(x∣t)\log p\left(x \mid \theta^t\right)$ 取ELBO，即:

$p(z∣x,t)p(z∣x,t)dz⏟=0=ELBOlog\; p(x|\theta ^{t})=\underset{ELBO}{\underbrace{\int _{z}p(z|x,\theta ^{t})log\; \frac{p(x,z|\theta ^{t})}{p(z|x,\theta ^{t})}\mathrm{d}z}}\underset{=0}{\underbrace{-\int _{z}p(z|x,\theta ^{t})log\; \frac{p(z|x,\theta ^{t})}{p(z|x,\theta ^{t})}\mathrm{d}z}}=ELBO$

也便是说 $log⁡p(x∣)\log p(x \mid \theta)$ 与 $E L BO$ 都是关于 $\theta$ 的函数，且满足 $log⁡p(x∣)≥ELBO\log p(x \mid \theta) \geq E L B O$ ，也就是说 $log⁡p(x∣)\log p(x \mid \theta)$ 的图画总是在 $E L BO$ 的图画的上面。

关于 $q (z)$ ，咱们取 $q(z)=p(z∣x,t)q(z)=p\left(z \mid x, \theta^t\right)$ ，这也就确保了只要在 $=t\theta=\theta^t$ 时 $log⁡p(x∣)\log p(x \mid \theta)$ 与 $E L BO$ 才会持平，因此使 $E L BO$ 取极大值的 $t+1\theta^{t+1}$ 必定能使得 $log⁡p(x∣t+1)≥log⁡p(x∣t)\log p\left(x \mid \theta^{t+1}\right) \geq \log p\left(x \mid \theta^t\right)$ 。该进程如下图所示:

『白板推导系列笔记』11.Expectation_Maximization（EM算法）

然后咱们调查一下 $E L BO$ 取极大值的进程：

$p(x,z∣)]\theta ^{t+1}=\underset{\theta }{argmax}ELBO \\ =\underset{\theta }{argmax}\int _{z}p(z|x,\theta ^{t})log\; \frac{p(x,z|\theta )}{p(z|x,\theta ^{t})}\mathrm{d}z\\ =\underset{\theta }{argmax}\int _{z}p(z|x,\theta ^{t})log\; p(x,z|\theta )\mathrm{d}z-\underset{与\theta 无关}{\underbrace{\underset{\theta }{argmax}\int _{z}p(z|x,\theta ^{t})p(z|x,\theta ^{t})\mathrm{d}z}}\\ {\color{Red}{=\underset{\theta }{argmax}\int _{z}p(z|x,\theta ^{t})log\; p(x,z|\theta )\mathrm{d}z}} \\ {\color{Red}{=\underset{\theta }{argmax}E_{z|x,\theta ^{t}}[log\; p(x,z|\theta )]}}$

由此咱们就导出了EM算法的迭代公式。

ELBO+Jensen不等式的办法

首要要详细介绍一下Jensen不等式：关于一个凹函数 $f (x)$ （国内外对凹凸函数的界说恰好相反，这儿的凹函数指的是国外界说的凹函数)，咱们检查其图画如下：

$t∈[0,1]c=ta+(1−t)b=tf(a)+(1−t)f(b)t\in [0,1]\\ c=ta+(1-t)b\\ \phi =tf(a)+(1-t)f(b)$

凹函数恒有 $\geq \phi ＼mathrm{~ ，也就是 ~} f(t a+(1-t) b) \geq t f(a)+(1-t) f(b)$ ，当 $t=12t=\frac{1}{2}$ 时有 $f(a2+b2)≥f(a)2+f(b)2f\left(\frac{a}{2}+\frac{b}{2}\right) \geq \frac{f(a)}{2}+\frac{f(b)}{2}$ ，可以理解为关于凹函数来说 先求期望再求函数值 恒 $≥\geq$ 先求函数值再求期望，即 $\geq E[f]$ 。

上面的说明只是对Jensen不等式的一个形象的描绘，而非谨慎的证明。接下来使用Jensen不等式来导出EM算法:

$log⁡p(x∣)=log⁡∫zp(x,z∣)dz=log⁡∫zp(x,z∣)q(z)⋅q(z)dz=log⁡Eq(z)[p(x,z∣)q(z)]≥Eq(z)[log⁡p(x,z∣)q(z)]⏟ELBO\begin{gathered} \log p(x \mid \theta)=\log \int_z p(x, z \mid \theta) \mathrm{d} z \\ =\log \int_z \frac{p(x, z \mid \theta)}{q(z)} \cdot q(z) \mathrm{d} z \\ =\log E_{q(z)}\left[\frac{p(x, z \mid \theta)}{q(z)}\right] \\ \geq \underbrace{E_{q(z)}\left[\log \frac{p(x, z \mid \theta)}{q(z)}\right]}_{E L B O} \end{gathered}$

这儿使用了Jensen不等式得到了上面呈现过的 $E L BO$ ，这儿的 $f (x)$ 函数也便是 $log⁡\log$ 函数，明显这是一个凹函数。当 $log⁡P(x,z∣)q(z)\log \frac{P(x, z \mid \theta)}{q(z)}$ 这个函数是一个常数时会取得等号，利用这一点咱们也相同可以得到 $\mid x, \theta)$ 时可以使得 $log⁡p(x∣)=ELBO\log p(x \mid \theta)=E L B O$ 的结论:

$p(x,z∣)q(z)=C⇒q(z)=p(x,z∣)C⇒∫zq(z)dz=∫z1Cp(x,z∣)dz⇒1=1C∫zp(x,z∣)dz⇒C=p(x∣)将C代入q(z)=p(x,z∣)C得q(z)=p(x,z∣)p(x∣)=p(z∣x,)\frac{p(x,z|\theta )}{q(z)}=C\\ \Rightarrow q(z)=\frac{p(x,z|\theta )}{C}\\ \Rightarrow \int _{z}q(z)\mathrm{d}z=\int _{z}\frac{1}{C}p(x,z|\theta )\mathrm{d}z\\ \Rightarrow 1=\frac{1}{C}\int _{z}p(x,z|\theta )\mathrm{d}z\\ \Rightarrow C=p(x|\theta )\\ 将C代入q(z)=\frac{p(x,z|\theta )}{C}得\\ {\color{Red}{q(z)=\frac{p(x,z|\theta )}{p(x|\theta )}=p(z|x,\theta )}}$

这种办法到这儿就和上面的办法相同了，总结来说便是：

$p(x∣)≥Eq(z)[logp(x,z∣)q(z)]⏟ELBOlog\; p(x|\theta )\geq \underset{ELBO}{\underbrace{E_{q(z)}[log\frac{p(x,z|\theta )}{q(z)}]}}$
上面的不等式在 $q(z)=p(z∣x∣)q(z)=p(z|x|\theta )$ 时取等号，因而在迭代更新进程中取 $q(z)=p(z∣x,t)q(z)=p(z|x,\theta ^{t})$ 接下来的推导进程就和第1种办法相同了。

四、广义EM算法

上面介绍的EM算法属于狭义的EM算法，它是广义EM的一个特例。在上面介绍的EM算法的E步中咱们假定 $q(z)=p(z∣x,t)q(z)=p(z|x,\theta ^{t})$ ，但是假如这个后验 $p(z∣x,t)p(z|x,\theta ^{t})$ 无法求解，那么必须使⽤采样（MCMC)或许变分揣度等⽅法来近似揣度这个后验。前面咱们得出了以下联系：

log⁡p(x∣)=∫zq(z)log⁡p(x,z∣)q(z)dz−∫zq(z)log⁡p(z∣x,)q(z)dz=ELBO+KL(q∥p)\log p(x \mid \theta)=\int_z q(z) \log \frac{p(x, z \mid \theta)}{q(z)} \mathrm{d} z-\int_z q(z) \log \frac{p(z \mid x, \theta)}{q(z)} \mathrm{d} z=E L B O+K L(q \| p)

当咱们关于固定的 $\theta$ ，咱们期望 $\| p)$ 越小越好，这样就能使得 $E L BO$ 更大:

$\theta, \hat{q}=\underset{q}{\operatorname{argmin}} K L(q \| p)=\underset{q}{\operatorname{argmax}} E L B O$

$E L BO$ 是关于 $q$ 和 $\theta$ 的函数，写作 $\theta)$ 。以下是广义EM算法的基本思路:

E step: $qt+1=argmax⁡L(q,t)q^{t+1}=\operatorname{argmax} L\left(q, \theta^t\right)$ M step: $t+1=argmax⁡qL(qt+1,)\theta^{t+1}=\underset{q}{\operatorname{argmax}} L\left(q^{t+1}, \theta\right)$

再次调查一下 $E L BO$ :

$q]⏟H[q]ELBO=L(q,\theta )=E_{q}[log\; p(x,z)-log\; q]\\ =E_{q}[log\; p(x,z)]\underset{H[q]}{\underbrace{-E_{q}[log\; q]}}$

因而，咱们看到，⼴义 EM 相当于在本来的式⼦中加⼊熵 $H [q]$ 这⼀项。

五、EM的变种

EM 算法相似于坐标上升法，固定部分坐标，优化其他坐标，再⼀遍⼀遍的迭代。假如在 EM 结构中，⽆法求解 $z$ 后验概率，那么需求采⽤⼀些变种的 EM 来估算这个后验：

①根据平均场的变分揣度，VBEM/VEM

②根据蒙特卡洛的EM，MCEM

“敞开生长之旅！这是我参与「日新方案 2 月更文应战」的第 8 天，点击检查活动概况”

『白板推导系列笔记』11.Expectation_Maximization（EM算法）

一、概述

二、EM算法的收敛性

三、EM算法的导出

四、广义EM算法

五、EM的变种

相关文章

Python 3.11.0 正式发布！主要新特性一览

【云原生】Prometheus 自定义告警规则

能听懂语音的ChatGPT来了：10小时录音扔进去，想问什么问什么

优雅的解决使用fatAar打包.aar时遇到的依赖问题

作者信息