EM算法

Posted on 2025-12-20 In Machine Learning Word count in article: 1k Reading time ≈ 4 mins.

EM 算法的目标

先考虑著名的三硬币问题：

假设三枚硬币 A, B, C，其正面朝上的概率分别为 $\pi,p,q$。

先抛 A，若正面朝上抛 B，反之则抛 C。

只记录抛 B，C 的结果，得到一个 01 序列。

要求给出此模型的参数 $\theta=(\pi,p,q)$

抽象出问题实质：

给出观测数据 $Y=[Y_1,\dots,Y_n]^T$ 以及隐变量 $Z=[Z_1,\dots,Z_n]^T$，则给出似然估计： \[ P(Y|\theta) =\sum_Z P(Y|Z,\theta) P(Z|\theta) \]

此问题中可以化简为：

\[ P(Y|\theta) =\prod_{j=1}^n \left[\pi p^{y_j} (1-p)^{1-y_j} +(1-\pi) q^{y_j} (1-q)^{1-y_j} \right] \] 希望给出

\[ \hat{\theta}=\arg \max_{\theta} \log(P(Y|\theta)) \]

下面给出一个用语的约定：

观测数据/不完全数据 $Y=[Y_1,\dots,Y_n]^T$
隐变量/未观测数据/ $\text{Latent Variables}$ $Z=[Z_1,\dots,Z_n]^T$
完全数据：$P(Y,Z|\theta)$
完全数据的对数似然函数：$\log P(Y,Z|\theta)$

EM 算法的导出

设 \[ \begin{align} L(\theta) &=P(Y|\theta)=\sum_Z P(Y|Z,\theta) P(Z|\theta) \\ &=\log \left( \sum_Z P(Y|Z,\theta) P(Z|\theta) \right) \end{align} \]

我们逐步迭代去求出最优化的 $\theta$，设第 $i$ 次求出的解是 $\theta^{(i)}$，则： \[ \begin{align} L(\theta)-L(\theta^{(i)})&=\log \left( \sum_Z P(Y|Z,\theta) P(Z|\theta) \right)-\log P(Y|\theta^{(i)}) \\ &= \log \left(\sum_Z P(Z|Y,\theta^{(i)}) \dfrac{ P(Y|Z,\theta) P(Z|\theta) } {P(Z|Y,\theta^{(i)})} \right)-\log P(Y|\theta^{(i)})\\ &\geq \sum_Z P(Z|Y,\theta^{(i)})\log \left( \dfrac{ P(Y|Z,\theta) P(Z|\theta) } {P(Z|Y,\theta^{(i)})} \right)-\log P(Y|\theta^{(i)})\\ &= \sum_Z P(Z|Y,\theta^{(i)})\log \left( \dfrac{ P(Y|Z,\theta) P(Z|\theta) } {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \right)\\ \end{align} \]

不等号是Jensen不等式给出的

设 $B(\theta,\theta^{(i)})\hat{=}L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)})\log \left( \dfrac{ P(Y|Z,\theta) P(Z|\theta) }{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \right)$

显然有 $L(\theta)\geq B(\theta,\theta^{(i)})$，即 $B$ 为原本函数的一个下界，且 $\theta=\theta^{(i)}$ 时取等。故可以考虑最大化 $B$，从而使得 $L$ 最大。

即： \[ \begin{align} \theta^{(i+1)} &= \arg \max _{\theta} B(\theta,\theta^{(i)}) \\ &=\arg \max_{\theta} \left( L(\theta^{(i)})+\sum_Z P(Z|Y,\theta^{(i)})\log \left( \dfrac{ P(Y|Z,\theta) P(Z|\theta) }{P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \right) \right) \\ &=\arg \max_{\theta} \left( \sum_Z P(Z|Y,\theta^{(i)})\log \left( P(Y|Z,\theta) P(Z|\theta) \right) \right)\\ &=\arg \max_{\theta} \sum_Z P(Z|Y,\theta^{(i)})\log P(Y,Z|\theta) \end{align} \] 上面的等号都是去掉了常数项（上面的变量只有 $\theta$，$\theta^{(i)}$固定）令 $Q(\theta,\theta^{(i)})=\sum_Z P(Z|Y,\theta^{(i)})\log P(Y,Z|\theta)$，则 Q 函数即为：

完全似然函数 $\log P(Y,Z|\theta)$ 关于在给定观测数据 $Y$ 和当前参数估计$\theta^{(i)}$ 下，对于未观测数据 $Z$ 的条件概率分布 $P(Z|Y,\theta^{(i)})$ 的期望。

EM 算法实质上就是找一个凸函数 $B/Q$，让它在 $\theta^{(i)}$ 处严格等于对数似然函数 $\log P(Y,Z|\theta)$，但始终在似然函数下方。我们通过不断增大 B 函数，迫使似然函数上升。

关于 Q 函数更直观的认知，见 Qwen

EM 算法的流程

初始化 $\theta^{(0)}$
E(Expectation): 求出 Q 函数
M(Maximization): 最大化 Q 函数，求出下一轮的 $\theta^{(i+1)}$
重复 E-M 步，直到收敛为止

GMM

GMM，即 Gaussian Mixture Model，刻画了如下的问题：

有 K 个 Gaussian，分别服从 $\theta_k=(\mu_k,\sigma_k)$；第 $k$ 个模型被选择的概率是 $\alpha_k$

即 $P(y)=\sum_{k=1}^K \alpha_k \phi(\mu_k,\sigma_k)$

现在你既不知道各个Gaussian的具体参数，也不知道选择的概率 $\alpha_k$，任务就是根据观测的序列 $y=(y_1,\dots,y_N)$ 求出 $\theta=(\alpha_1,\dots,\alpha_K;\theta_1,\dots,\theta_K)$

使用 EM 算法完成这个任务，逐步分析：

明确隐变量

设 \[ \gamma_{jk}= \begin{cases} 1 & 第 j 个观测来自第 k 个模型\\ 0 & 反之 \end{cases} \]

有了观测数据 $y_j$ 之后，那么完全数据就是

\[ (y_j,\gamma_{j1},\dots,\gamma_{jk}) \]

后面整体算作上文的 $Z$

写出似然函数：

$$ \[\begin{align} P(y,\gamma|\theta) &= \prod_{j=1}^N P(y_j,\gamma_{j1}\dots,\gamma_{jk})\\ &= \prod_{j=1}^N \prod_{k=1}^K [\alpha_k \phi(y_j|\theta_k)]^{\gamma_{jk}}\\ \end{align}\] $$