EM算法

EM 算法是极大似然法的推广，用于解决存在隐变量（hidden variables / latent factors）的参数估计问题。

1 EM 算法

1.1 问题描述

极大似然法是最常用的参数估计方法之一。设观测变量为 \(x\)，模型参数为 \(\theta\)，则极大似然法通过最大化似然函数 \(P(x\vert\theta)\) 或对数似然 \(\log P(x\vert\theta)\) 来求解最优的 \(\theta\). 然而在一些问题中，观测变量 \(x\) 依赖于隐变量 \(z\)，此时根据全概率公式有： \[ P(x\vert\theta)=\sum_zP(x,z\vert\theta) \] （这里假设隐变量是离散的，连续情形只需将求和改为积分即可）那么对数似然为： \[ L(\theta)=\log P(x\vert \theta)=\log\left(\sum_{z} P(x,z\vert\theta)\right) \] 如果仍然使用极大似然法，我们会发现 \(L(\theta)\) 的导数将变得非常复杂，要优化的参数之间无法分离，导致无法写出封闭形式的解。这时就需要用到 EM 算法了。

1.2 理论推导

为了解决上述问题，我们为隐变量 \(z\) 引入一个概率分布 \(q(z)\)，则有： \[ L(\theta)=\log\left(\sum_{z} P(x,z\vert\theta)\right) =\log\left(\sum_z q(z)\frac{P(x,z\vert \theta)}{q(z)}\right)\geq\sum_zq(z)\log\frac{P(x,z\vert \theta)}{q(z)}=J(\theta,q) \] 其中不等式应用了 Jensen's inequality. 于是我们找到了“一族” \(L(\theta)\) 的下界 \(J(\theta,q)\)，称为证据下界 ELBO (Evidence Lower BOund)。“一族”的意思是通过改变 \(q\)，我们能够得到不同的下界函数。特别地，根据 Jensen's inequality 的取等条件，可以知道当 \(q(z)=P(z\vert x,\theta)\) 时等号成立。的确，把 \(q^\ast(z)=P(z\vert x,\theta)\) 代入上式即可验证这一点： \[ J(\theta,q^\ast)=\sum_z P(z\vert x,\theta)\log \frac{P(x,z\vert \theta)}{P(z\vert x,\theta)}=\sum_zP(z\vert x,\theta)\log P(x\vert \theta)=\log P(x\vert \theta)=L(\theta) \]

因此，\(J(\theta,q)\) 是 \(L(\theta)\) 的紧的下界，所以我们可以通过优化 \(J(\theta,q)\) 达到优化 \(L(\theta)\) 的目的，即： \[ \max_\theta L(\theta)\iff\max_{\theta,q}J(\theta,q) \] 不过，同时优化 \(\theta\) 和 \(q\) 依旧非常困难，因此 EM 算法采用交替迭代的方式优化：

• E-step 固定 \(\theta\) 优化 \(q\)： \[ q^{(t+1)}=\arg\max_q J(\theta^{(t)},q) \] 根据上面的讨论，这一步的最优解就是取 \(q^{(t+1)}(z)=P(z\vert x,\theta^{(t)})\)，以使得 \(J(\theta^{(t)},q^{(t+1)})=L(\theta^{(t)})\)；

• M-step 固定 \(q\) 优化 \(\theta\)： \[ \theta^{(t+1)}=\arg\max_\theta J(\theta,q^{(t+1)}) \] 注意上述优化目标可以拆出一个与 \(\theta\) 无关的常数项： \[ \begin{align} J(\theta,q^{(t+1)})&=\sum_zq^{(t+1)}(z)\log P(x,z\vert\theta)-\sum_zq^{(t+1)}(z)\log q^{(t+1)}(z)\\ &=\underbrace{\sum_z P(z\vert x,\theta^{(t)})\log P(x,z\vert\theta)}_{Q(\theta,\theta^{(t)})}+\underbrace{H(q^{(t+1)}(z))}_\text{constant} \end{align} \] 因此只需要优化 \(Q(\theta,\theta^{(t)})\) 即可： \[ \theta^{(t+1)}=\arg\max_\theta Q(\theta,\theta^{(t)}) \]

经过一轮 E-step 和 M-step，有： \[ L(\theta^{(t+1)})\geq J(\theta^{(t+1)},q^{(t+1)})\geq J(\theta^{(t)},q^{(t+1)})=L(\theta^{(t)}) \] 因此 \(L(\theta)\) 的确得到了优化。下图可视化了这样一轮迭代过程：

可以看见，红色线条是要优化的目标，蓝色线条是在当前 \(\theta^{(t)}\) 下通过 E-step 找到的下界，M-step 找到了蓝色线条的最高点 \(\theta^{(t+1)}\)，然后下一轮的 E-step 将改变 \(q\) 使得下界在 \(\theta^{(t+1)}\) 处与红色线条相等，即得到绿色线条……如此迭代即可。

1.3 进一步分析

在上一节中，我们推出了 \(L(\theta)\geq J(\theta,q)\)，那他俩之间究竟差了个什么呢？ \[ \begin{align} L(\theta)-J(\theta,q)&=\log P(x\vert \theta)-\sum_zq(z)\log\frac{P(x,z\vert\theta)}{q(z)}\\ &=\sum_zq(z)\left[\log P(x\vert \theta)-\log\frac{P(x,z\vert \theta)}{q(z)}\right]\\ &=\sum_z q(z)\log \frac{q(z)}{P(z\vert x,\theta)}\\ &=\mathrm{KL}(q(z)\|P(z\vert x,\theta)) \end{align} \] 啊！原来是引入的分布 \(q(z)\) 与后验分布 \(P(z\vert x,\theta)\) 之间的 KL 散度。之前推导过程中的 Jensen's inequality，其实对应着这里的 KL 散度非负。事实上，存在其他的推导方法能直接写出 \(L(\theta)=J(\theta,q)+\mathrm{KL}(q(z)\|P(z\vert x,\theta))\) 这个等式而避开 Jensen's inequality 的，如下所示：

\[ \begin{align} L(\theta)&=\log P(x\vert \theta)\\ &=\sum_z q(z)\log P(x\vert \theta)\\ &=\sum_z q(z)\log\left(\frac{P(x,z\vert \theta)}{P(z\vert x,\theta)}\cdot\frac{q(z)}{q(z)} \right)\\ &=\sum_z q(z)\left[\log\frac{P(x,z\vert \theta)}{q(z)}+\log\frac{q(z)}{P(z\vert x,\theta)} \right]\\ &=J(\theta,q)+\mathrm{KL}(q(z)\|P(z\vert x,\theta)) \end{align} \] 从等式的角度看，\(L(\theta)\) 被划分成了两部分——ELBO 和 KL 散度. 在 E-step 中，我们让 \(\mathrm{KL}=0\)，也就是让 \(L(\theta)=J(\theta,q)\)；在 M-step 中，固定 \(q\) 优化 \(J(\theta,q)\)，进而优化了 \(L(\theta)\)；这时由于 \(\theta\) 变了，KL 散度不再是零，我们便继续下一轮迭代，如下图所示：

1.4 算法步骤

综上所述，EM 算法的步骤如下：

1. 随机初始化 \(\theta^{(0)}\)；

2. E-step：给定 \(\theta^{(t)}\)，求隐变量的后验分布： \[ P(z\vert x,\theta^{(t)}) \] 然后计算优化目标： \[ Q(\theta,\theta^{(t)})=\sum_zP(z\vert x,\theta^{(t)})\log P(x,z\vert \theta) \]

3. M-step：优化上式： \[ \theta^{(t+1)}=\arg\max_\theta Q(\theta,\theta^{(t)}) \]

4. 迭代执行 2、3 步直至收敛。

1.5 收敛性

EM 算法一定收敛吗？这里的收敛其实包含两层意思：\(L(\theta)\) 收敛和 \(\theta\) 收敛，前者并不能蕴含后者。

1. \(L(\theta)\) 收敛：上文已经说明了 \(L(\theta)\) 在优化过程中单调不减，又它显然有上界 \(0\)，根据单调有界定理，\(L(\theta)\) 必然收敛。
2. \(\theta\) 收敛：见参考文献^[5]。

注意，虽然 EM 算法一定收敛，但是可能收敛到局部最优解。因此实践中往往选取不同的初值多跑几次，选择最佳的结果。

1.6 关于独立重复试验的注解

在上面的推导中，我们把所有的观测结果直接记作 \(x\)，这使得结论具有普适性。但实践中我们往往做的是独立重复试验，有 \(n\) 个相互独立的样本 \(x=(x_1,\ldots,x_n)\)，各样本对应各自的隐变量 \(z=(z_1,\ldots,z_n)\).

基于独立性，有： \[ P(z\vert x,\theta)=\prod_{i=1}^nP(z_i\vert x_i,\theta)\quad\quad P(x,z\vert\theta)=\prod_{i=1}^nP(x_i,z_i\vert \theta) \] 如果把它们直接代入 \(Q(\theta,\theta^{(t)})\) 之中，会得到非常丑陋的结果： \[ \begin{align} Q(\theta,\theta^{(t)})&=\sum_zP(z\vert x,\theta^{(t)})\log P(x,z\vert \theta)\\ &=\sum_{z_1,\ldots,z_n}\left[\left(\prod_{i=1}^nP(z_i\vert x_i,\theta)\right)\log\left(\prod_{j=1}^nP(x_j,z_j\vert \theta)\right)\right]\\ &=\sum_{z_1,\ldots,z_n}\left[\left(\prod_{i=1}^nP(z_i\vert x_i,\theta)\right)\sum_{j=1}^n\log\left(P(x_j,z_j\vert \theta)\right)\right]\\ \end{align} \] 这是因为我们代入得太晚——在 Jensen's inequality 把对数和求和的顺序交换后，再代入就很难化简式子了（当然如果你头够铁，也不是不能化简，见参考资料^[9][10]）。如果我们在最开始就代入： \[ L(\theta)=\log\prod_{i=1}^nP(x_i\vert\theta)=\sum_{i=1}^n\log P(x_i\vert\theta)=\sum_{i=1}^n\log\left(\sum_{z_i}P(x_i,z_i\vert\theta)\right) \] 继续推导，会发现只需要在相应地方加上求和 \(\sum_{i=1}^n\)、给 \(x\) 和 \(z\) 加上下标 \(i\) 即可，整个推导过程没有什么大的变化。最终优化目标写作： \[ Q(\theta,\theta^{(t)})=\sum_{i=1}^n\sum_{z_i}P(z_i\vert x_i,\theta^{(t)})\log P(x_i,z_i\vert \theta) \]

2 例子：双硬币问题

本例来源于参考资料^[1].

假设有两枚硬币 A,B，它们正面朝上的概率未知，分别记作 \(\theta_A,\theta_B\). 为了估计 \(\theta_A,\theta_B\)​，考虑做如下试验：首先等概率地随机选取一枚硬币，然后抛掷这枚硬币 10 次。假设我们一共做了 5 次试验，得到的结果如下：

试验 id	选取的硬币	试验结果
1	B	5 H, 5 T
2	A	9 H, 1 T
3	A	8 H, 2 T
4	B	4 H, 6 T
5	A	7 H, 3 T

可以看见，综合 5 次试验，硬币 A 一共 24 次正面朝上、6 次反面朝上，硬币 B 一共 9 次正面朝上、11 次反面朝上，所以 \(\theta_A,\theta_B\) 的估计值为： \[ \begin{align} &\hat\theta_A=24/30=0.8\\ &\hat\theta_B=9/20=0.45 \end{align} \] 值得注意的是，虽然这个结果直观上很容易理解，但本质上是极大似然估计。其对数似然为： \[ \begin{align} L(\hat\theta_A,\hat\theta_B)&=\log\left[P(24H,6T\vert \hat\theta_A)\cdot P(9H,11T\vert\hat\theta_B)\right]\\ &=\log\left[(\hat\theta_A)^{24}(1-\hat\theta_A)^6\right]+\log\left[(\hat\theta_B)^9(1-\hat\theta_B)^{11}\right]\\ &=24\log(\hat\theta_A)+6\log(1-\hat\theta_A)+9\log(\hat\theta_B)+11\log(1-\hat\theta_B) \end{align} \] 注意 \(\hat\theta_A\) 和 \(\hat\theta_B\) 可以分开考虑，因此分别求导并令为零，有： \[ \begin{gather} \frac{24}{\hat\theta_A}-\frac{6}{1-\hat\theta_A}=0\implies\hat\theta_A=\frac{24}{30}\\ \frac{9}{\hat\theta_B}-\frac{11}{1-\hat\theta_B}=0\implies\hat\theta_B=\frac{9}{20} \end{gather} \] 现在考虑一个更有挑战性的问题——我们并不知道每一次试验选的是哪枚硬币，只知道投掷结果，即：

试验 id	选取的硬币	试验结果
1	\(z_1=?\)	5 H, 5 T \((x_1=5)\)
2	\(z_2=?\)	9 H, 1 T \((x_2=9)\)
3	\(z_3=?\)	8 H, 2 T \((x_3=8)\)
4	\(z_4=?\)	4 H, 6 T \((x_4=4)\)
5	\(z_5=?\)	7 H, 3 T \((x_5=7)\)

其中 \(x_i\) 表示第 \(i\) 次试验中正面朝上的次数，\(z_i\in\{A,B\}\) 表示选取的硬币，是隐变量。应用 EM 算法：

1. 随机初始化 \(\theta^{(0)}=(\theta_A^{(0)},\theta_B^{(0)})=(0.60,0.50)\)；

2. E-step：求隐变量的后验分布 \(P(z_i\vert x_i,\theta^{(0)})\)，以第一次试验为例： \[ \begin{align} &P(z_1=A\vert x_1,\theta^{(0)})=\frac{P(z_1=A,x_1\vert\theta^{(0)})}{P(x_1\vert \theta^{(0)})}=\frac{(0.6)^5\times (0.4)^5}{(0.6)^5\times (0.4)^5+(0.5)^{10}}=0.45\\ &P(z_1=B\vert x_1,\theta^{(0)})=1-P(z_1=A\vert x_1,\theta^{(0)})=0.55 \end{align} \] 为了书写方便，以下将 \(P(z_i=A\vert x_i,\theta^{(0)})\) 和 \(P(z_i=B\vert x_i,\theta^{(0)})\) 分别简记为 \(p_i\) 和 \((1-p_i)\). 计算优化目标 \(Q(\theta,\theta^{(0)})\)： \[ \begin{align} Q(\theta,\theta^{(0)})&=\sum_{i=1}^5\sum_{z_i\in\{A,B\}}P(z_i\vert x_i,\theta^{(0)})\log P(x_i,z_i\vert \theta)\\ &=\sum_{i=1}^5P(z_i=A\vert x_i,\theta^{(0)})\log P(x_i,z_i=A\vert \theta)+P(z_i=B\vert x_i,\theta^{(0)})\log P(x_i,z_i=B\vert \theta)\\ &=\sum_{i=1}^5 p_{i}\log\left[\theta_A^{x_i}(1-\theta_A)^{10-x_i}\right]+(1-p_i)\log\left[\theta_B^{x_i}(1-\theta_B)^{10-x_i}\right] \end{align} \]

3. M-step：优化上述目标，求偏导并令为零： \[ \frac{\partial Q}{\partial \theta_A}=\sum_{i=1}^5 p_i\left(\frac{x_i}{\theta_A}-\frac{10-x_i}{1-\theta_A}\right)=\sum_{i=1}^5 p_i\frac{x_i-10\theta_A}{\theta_A(1-\theta_A)}=0 \] 解得： \[ \theta_A=\frac{\sum_{i=1}^5 p_ix_i}{10\sum_{i=1}^5 p_i}=\frac{2.25+7.2+5.84+1.4+4.55}{10\times(0.45+0.80+0.73+0.35+0.65)}\approx0.71 \] \(\theta_B\) 同理求解。

4. 迭代执行 2、3 步直至收敛。

3 应用：高斯混合模型（GMM）

设有 \(K\) 个 \(d\) 维高斯分布： \[ \phi(x\vert \mu_k,\Sigma_k)=\frac{1}{(2\pi)^{d/2}|\Sigma_k|^{1/2} }\exp\left(-\frac{1}{2}(x-\mu_k)^T\Sigma_k^{-1}(x-\mu_k)\right),\quad k=1,\ldots,K \] 样本 \(\{x_1,\ldots,x_n:x_i\in\mathbb R^d\}\) 是由如下过程产生的：首先随机选取一个高斯分布（第 \(k\) 个高斯分布被选中的概率是 \(\alpha_k\)，其中 \(\sum_{k=1}^K\alpha_k=1\)），再从被选中的高斯分布中采样。试估计这 \(K\) 个高斯分布的参数 \(\theta=\{(\alpha_k,\mu_k,\Sigma_k)\mid k=1,\ldots,K\}\).

和双硬币问题非常相似，这个问题中我们不知道每次采样究竟选取的是哪个高斯分布，所以可以定义隐变量 \(z_i\in\{1,\ldots,K\}\) 表示第 \(i\) 个样本来自哪个高斯分布。使用 EM 算法求解：

E-step：隐变量的后验分布为： \[ P(z_i=k\vert x_i,\theta^{(t)})=\frac{P(x_i,z_i=k\vert \theta^{(t)})}{P(x_i\vert\theta^{(t)})}=\frac{\alpha_k^{(t)}\phi(x_i\vert \mu_k^{(t)},\Sigma_k^{(t)})}{\sum_{j=1}^K\alpha_j^{(t)}\phi(x_i\vert \mu_j^{(t)},\Sigma_j^{(t)})} \]

为书写方便，以下将其简记为 \(p_{ik}\)，注意这是一个常数。计算优化目标 \(Q(\theta,\theta^{(t)})\)： \[ \begin{align} Q(\theta,\theta^{(t)})&=\sum_{i=1}^n\sum_{k=1}^KP(z_i=k\vert x_i,\theta^{(t)})\log P(x_i,z_i=k\vert \theta)\\ &=\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\left(\alpha_k\phi(x_i\vert \mu_k,\Sigma_k)\right)\\ &=\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\left[\log\alpha_k+\log\phi(x_i\vert \mu_k,\Sigma_k)\right] \end{align} \] M-step（大计算量警告，不想看可略过）：

首先解 \(\alpha\)：结合条件 \(\sum_{k=1}^K\alpha_k=1\)，去掉 \(Q(\theta,\theta^{(t)})\) 中与 \(\alpha\) 无关的部分，优化问题化作： \[ \begin{align} &\max_\theta \sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\alpha_k\\ &\text{ s.t. }\sum_{k=1}^K\alpha_k=1 \end{align} \] 引入 Lagrange 乘子： \[ L(\theta)=\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\alpha_k+\lambda\left(\sum_{k=1}^K\alpha_k-1\right) \] 求偏导并令为零： \[ \begin{align} &\frac{\partial L}{\partial \alpha_k}=\sum_{i=1}^n\frac{p_{ik}}{\alpha_k}+\lambda=0&&k=1,\ldots,K\\ &\frac{\partial L}{\partial \lambda}=\sum_{k=1}^K\alpha_k-1=0 \end{align} \] 解得： \[ \alpha_k=\frac{\sum_{i=1}^np_{ik}}{\sum_{i=1}^n\sum_{k=1}^Kp_{ik}}=\frac{1}{n}\sum_{i=1}^np_{ik}\quad\quad k=1,\ldots,K \]

然后解 \(\mu\)：去掉 \(Q(\theta,\theta^{(t)})\) 中与 \(\mu\)​ 无关的部分，优化目标化作： \[ \begin{align} Q(\theta,\theta^{(t)})&\to\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\phi(x_i\vert\mu_i,\Sigma_i)\\ &=\sum_{i=1}^n\sum_{k=1}^K p_{ik}\left(\log\frac{1}{ {(\sqrt{2\pi})}^d|\Sigma_k|^{1/2} }-\frac{1}{2}(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)\right)\\ &\to\sum_{i=1}^n\sum_{k=1}^K p_{ik}\left(\frac{1}{2}(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)\right)=\mathrel{\vcenter{:}}Q'(\theta,\theta^{(t)}) \end{align} \] 求导令为零： \[ \begin{align}\frac{\partial Q'}{\partial \mu_k}&=\sum_{i=1}^n\frac{1}{2}p_{ik}\frac{\partial (x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)}{\partial \mu_k}\\ &=\sum_{i=1}^np_{ik}\Sigma_k^{-1}(x_i-\mu_k)\\ &=\Sigma_k^{-1}\sum_{i=1}^np_{ik}(x_i-\mu_k)=\vec 0 \end{align} \]

注：第二个等号应用了矩阵求导结论 \(\mathrm d(x^TAx)/\mathrm dx=(A+A^T)x\) 和协方差矩阵对称的特性。

解得： \[ \mu_k=\frac{\sum_{i=1}^np_{ik}x_i}{\sum_{i=1}^n p_{ik}}\quad\quad k=1,\ldots,K \]

最后解 \(\Sigma\)：去掉 \(Q(\theta,\theta^{(t)})\) 中与 \(\Sigma\) 无关的部分，优化目标化作： \[ \begin{align} Q(\theta,\theta^{(t)})&\to\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\phi(x_i\vert\mu_i,\Sigma_i)\\ &=\sum_{i=1}^n\sum_{k=1}^K p_{ik}\left(\log\frac{1}{ {(\sqrt{2\pi})}^d}-\frac{1}{2}\log|\Sigma_k|-\frac{(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)}{2}\right)\\ &\to\sum_{i=1}^n\sum_{k=1}^K p_{ik}\left(\log|\Sigma_k|+(x_i-\mu_k)^T\Sigma_k^{-1}(x_i-\mu_k)\right)=\mathrel{\vcenter{:}}Q''(\theta,\theta^{(t)}) \end{align} \] 求导令为零： \[ \begin{align}\frac{\partial Q''}{\partial \Sigma_k}&=\sum_{i=1}^np_{ik}\left(\Sigma_k^{-1}-(x_i-\mu_k)(x_i-\mu_k)^T\Sigma_{k}^{-2} \right)=\mathbf 0 \end{align} \] 解得： \[ \Sigma_k=\frac{\sum_{i=1}^np_{ik}(x_i-\mu_k)(x_i-\mu_k)^T}{\sum_{i=1}^np_{ik}}\quad\quad k=1,\ldots,K \]

总结一下，用 EM 算法解 GMM 模型的步骤如下：

1. 随机初始化模型参数 \(\alpha_k,\mu_k,\Sigma_k,\,k=1,\ldots,K\).

2. E-step：计算隐变量的概率分布： \[ p_{ik}=\frac{\alpha_k^{(t)}\phi(x_i\vert \mu_k^{(t)},\Sigma_k^{(t)})}{\sum_{j=1}^K\alpha_j^{(t)}\phi(x_i\vert \mu_j^{(t)},\Sigma_j^{(t)})} \]

3. M-step：计算新参数： \[ \begin{align} &\alpha_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}}{n}&& k=1,\ldots,K\\ &\mu_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}x_i}{\sum_{i=1}^n p_{ik}}&& k=1,\ldots,K\\ &\Sigma_k^{(t+1)}=\frac{\sum_{i=1}^np_{ik}(x_i-\mu_k)(x_i-\mu_k)^T}{\sum_{i=1}^np_{ik}}&& k=1,\ldots,K \end{align} \]

4. 迭代执行第 2、3 步。

4 一点注记

EM 算法在 E-step 要求我们能表达出隐变量的后验概率 \(P(z\vert x,\theta)\)，从上面两个例子（双硬币问题、GMM）可以看出，可以通过贝叶斯公式计算之： \[ P(z\vert x,\theta)=\frac{P(x,z\vert \theta)}{P(x\vert \theta)}=\frac{P(x\vert z,\theta)P(z\vert\theta)}{\sum_\hat z P(x\vert\hat z,\theta)P(\hat z\vert \theta)} \] 所以说我们终究没有避开计算似然 \(P(x\vert \theta)\)，因此要明晰的一点是，阻碍我们直接使用极大似然法的不是计算似然本身，而是解令对数似然偏导为零后得到的那个方程组。

这自然带来了一个问题，如果似然本身就是 intractable 的，那么我们也无法计算后验概率 \(P(z\vert x,\theta)\)，那么 EM 算法就做不下去了，典型的例子就是 VAE。至于 VAE 怎么解决这个问题的，留给后文吧。

参考资料

1. Do, Chuong B., and Serafim Batzoglou. What is the expectation maximization algorithm?. Nature biotechnology 26, no. 8 (2008): 897-899. ↩︎
2. Borman, Sean. The expectation maximization algorithm-a short tutorial. https://www.lri.fr/~sebag/COURS/EM_algorithm.pdf ↩︎
3. Tengyu Ma and Andrew Ng. CS229 Lecture notes: The EM algorithm. https://cs229.stanford.edu/notes2021fall/cs229-notes8.pdf ↩︎
4. Bishop, Christopher. "Pattern recognition and machine learning." Springer google schola 2 (2006): 531-537. ↩︎
5. Wu, CF Jeff. On the convergence properties of the EM algorithm. The Annals of statistics (1983): 95-103. ↩︎
6. 李航.统计学习方法 ↩︎
7. 人人都懂EM算法 - August的文章 - 知乎 https://zhuanlan.zhihu.com/p/36331115 ↩︎
8. 【机器学习】EM——期望最大（非常详细） - 阿泽的文章 - 知乎 https://zhuanlan.zhihu.com/p/78311644 ↩︎
9. 高斯混合模型（GMM）推导及实现 - 永远在你身后的文章 - 知乎 https://zhuanlan.zhihu.com/p/85338773 ↩︎
10. 机器学习-白板推导系列(十一)-高斯混合模型GMM（Gaussian Mixture Model）https://www.bilibili.com/video/BV13b411w7Xj?p=3&share_source=copy_web&vd_source=a43b4442e295a96065c7ae919b4866d3 ↩︎