EM Algorithm

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

1 EM 算法

1.1 问题描述

极大似然法是最常用的参数估计方法之一。设观测变量为 \(x\)，模型参数为 \(\theta\)，则极大似然法通过最大化对数似然 \(\log p(x;\theta)\) 来求解最优的参数 \(\theta\). 然而在一些问题中，观测变量 \(x\) 依赖于隐变量 \(z\)，此时根据全概率公式有： \[ p(x;\theta)=\int p(x,z;\theta)\mathrm dz \] 于是对数似然为： \[ L(\theta)=\log p(x;\theta)=\log\left(\int p(x,z;\theta)\mathrm dz\right) \] 如果仍然使用极大似然法，我们会发现 \(L(\theta)\) 的导数将变得非常复杂，要优化的参数之间无法分离，导致无法写出封闭形式的解。这时就需要用到 EM 算法了。

1.2 理论推导

为了解决上述问题，我们为隐变量 \(z\) 引入一个概率分布 \(q(z)\)，则有： \[ L(\theta)=\log\left(\int p(x,z;\theta)\mathrm dz\right) =\log\left(\int q(z)\frac{p(x,z;\theta)}{q(z)}\mathrm dz\right)\geq\int q(z)\log\frac{p(x,z;\theta)}{q(z)}\mathrm dz=J(\theta,q) \] 其中应用了 Jensen 不等式。于是我们找到了“一族” \(L(\theta)\) 的下界 \(J(\theta,q)\)，称为证据下界 (Evidence Lower BOund, ELBO)。“一族”的意思是通过改变 \(q\)，我们能够得到不同的下界函数。特别地，根据 Jensen 不等式的取等条件可知，当 \(q(z)=p(z\vert x;\theta)\) 时等号成立，我们可以代入 \(q^\ast(z)=p(z\vert x;\theta)\) 来验证这一点： \[ J(\theta,q^\ast)=\int p(z\vert x;\theta)\log\frac{p(x,z;\theta)}{p(z\vert x;\theta)}\mathrm dz=\int p(z\vert x;\theta)\log p(x;\theta)\mathrm dz=\log p(x;\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\)，现在要优化两个变量 \(\theta\) 和 \(q\). 同时优化二者比较困难，因此 EM 算法采用交替迭代的方式优化。具体而言，首先初始化 \(\theta^{(0)}\)，然后交替执行 E-step 和 M-step. 在第 \(t\) 轮中：

• 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)})&=\int q^{(t+1)}(z)\log p(x,z;\theta)\mathrm dz-\int q^{(t+1)}(z)\log q^{(t+1)}(z)\mathrm dz\\ &=\underbrace{\int p(z\vert x;\theta^{(t)})\log p(x,z;\theta)\mathrm dz}_{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;\theta)-\int q(z)\log\frac{p(x,z;\theta)}{q(z)}\mathrm dz\\ &=\int q(z)\left[\log p(x;\theta)-\log\frac{p(x,z;\theta)}{q(z)}\right]\mathrm dz\\ &=\int q(z)\log \frac{q(z)}{p(z\vert x;\theta)}\mathrm dz\\ &=\mathrm{KL}(q(z)\|p(z\vert x;\theta)) \end{align} \] 啊！原来是引入的分布 \(q(z)\) 与后验分布 \(p(z\vert x;\theta)\) 之间的 KL 散度。之前推导过程中使用的 Jensen 不等式，其实对应着这里的 KL 散度非负。事实上，我们能避开 Jensen 不等式直接推导出 \(L(\theta)=J(\theta,q)+\mathrm{KL}(q(z)\|p(z\vert x;\theta))\)，过程如下所示：

\[ \begin{align} L(\theta)&=\log p(x;\theta)\\ &=\int q(z)\log p(x;\theta)\mathrm dz\\ &=\int q(z)\log\left(\frac{p(x,z;\theta)}{p(z\vert x;\theta)}\cdot\frac{q(z)}{q(z)} \right)\mathrm dz\\ &=\int q(z)\left[\log\frac{p(x,z;\theta)}{q(z)}+\log\frac{q(z)}{p(z\vert x;\theta)} \right]\mathrm dz\\ &=J(\theta,q)+\mathrm{KL}(q(z)\|p(z\vert x;\theta)) \end{align} \] 观察上式，可以看见 \(L(\theta)\) 被划分成了两部分——ELBO 和 KL 散度。基于这个角度，我们重新审视 EM 算法——在 E-step 中，我们固定 \(\theta\) 并取 \(q(z)=p(z\vert x;\theta)\)，使得 KL 项为零，也就是让 \(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)})=\int p(z\vert x;\theta^{(t)})\log p(x,z;\theta)\mathrm dz \]

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

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

1.5 收敛性

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

1. \(L(\theta)\) 收敛：上文已经说明了 \(L(\theta)\) 在优化过程中单调不减，又它显然有上界，根据单调有界定理，\(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),\qquad p(x,z;\theta)=\prod_{i=1}^np(x_i,z_i;\theta) \] 如果把它们直接代入 \(Q(\theta,\theta^{(t)})\) 之中，会得到非常丑陋的结果： \[ \begin{align} Q(\theta,\theta^{(t)})&=\sum_zp(z\vert x;\theta^{(t)})\log p(x,z;\theta)\\ &=\int\left[\left(\prod_{i=1}^np(z_i\vert x_i;\theta)\right)\log\left(\prod_{j=1}^np(x_j,z_j; \theta)\right)\right]\mathrm d z_1\cdots\mathrm dz_n\\ &=\int\left[\left(\prod_{i=1}^np(z_i\vert x_i;\theta)\right)\sum_{j=1}^n\log\left(p(x_j,z_j; \theta)\right)\right]\mathrm d z_1\cdots\mathrm dz_n\\ \end{align} \] 这是因为我们代入得太晚——在 Jensen 不等式把对数和求和的顺序交换后，再代入就很难化简式子了（当然如果你头够铁，也不是不能化简，见参考资料^[9][10]）。但如果我们在最开始就代入： \[ L(\theta)=\log\prod_{i=1}^np(x_i;\theta)=\sum_{i=1}^n\log p(x_i;\theta)=\sum_{i=1}^n\log\left(\int p(x_i,z_i;\theta)\mathrm dz_i\right) \] 继续推导，会发现只需要在相应地方加上求和 \(\sum_{i=1}^n\)，并给 \(x\) 和 \(z\) 加上下标 \(i\) 即可，整个推导过程没有什么大的变化。最终，优化目标写作： \[ Q(\theta,\theta^{(t)})=\sum_{i=1}^n\int p(z_i\vert x_i;\theta^{(t)})\log p(x_i,z_i;\theta)\mathrm dz_i \]

2 例子：双硬币问题

假设有两枚硬币 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;\hat\theta_A)\cdot P(9H,11T;\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;\theta^{(0)})}{P(x_1;\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;\theta)\\ &=\sum_{i=1}^5P(z_i=A\vert x_i;\theta^{(0)})\log P(x_i,z_i=A;\theta)+P(z_i=B\vert x_i;\theta^{(0)})\log P(x_i,z_i=B;\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;\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. 给定 \(\theta^{(t)}\)，隐变量的后验分布为： \[ P(z_i=k\vert x_i;\theta^{(t)})=\frac{P(x_i,z_i=k;\theta^{(t)})}{P(x_i;\theta^{(t)})}=\frac{\alpha_k^{(t)}\phi(x_i;\mu_k^{(t)},\Sigma_k^{(t)})}{\sum_{j=1}^K\alpha_j^{(t)}\phi(x_i;\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;\theta)\\ &=\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\left(\alpha_k\phi(x_i;\mu_k,\Sigma_k)\right)\\ &=\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\left[\log\alpha_k+\log\phi(x_i;\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&\quad\sum_{i=1}^n\sum_{k=1}^Kp_{ik}\log\alpha_k\\ \text{ s.t. }&\quad\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,\quad 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 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;\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} \]

解得： \[ \mu_k=\frac{\sum_{i=1}^np_{ik}x_i}{\sum_{i=1}^n p_{ik}},\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;\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 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;\mu_k^{(t)},\Sigma_k^{(t)})}{\sum_{j=1}^K\alpha_j^{(t)}\phi(x_i;\mu_j^{(t)},\Sigma_j^{(t)})} \]

3. M-step. 更新参数： \[ \begin{align} &\alpha_k^{(t+1)}=\frac{1}{n}{\sum_{i=1}^np_{ik}}&& 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)\)，从上面两个例子可以看出，这个后验概率可以通过贝叶斯公式计算： \[ p(z\vert x;\theta)=\frac{p(x,z;\theta)}{p(x;\theta)}=\frac{p(x\vert z;\theta)p(z;\theta)}{\sum_{\hat z} p(x\vert\hat z;\theta)p(\hat z\vert \theta)} \] 所以我们并没有避开计算似然 \(p(x;\theta)\). 因此要明晰的一点是，阻碍我们直接使用极大似然法的不是计算似然，而是优化似然，即解令对数似然偏导为零后得到的那个方程组。

这自然带来了一个问题，如果似然本身就是不可解 (intractable) 的，那么 EM 算法就做不下去了。例如，在 GMM 中，隐变量取值是离散的，表示样本来自于哪个高斯分布。倘若我们把高斯分布的数量不断变大乃至无穷，那么隐变量取值就变成连续的，后验概率的分母（似然）变成了一个积分，无法通过枚举计算。为了解决这个问题，人们提出了变分推断的概念，我们在后面的文章中学习。

参考资料

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 ↩︎