机器学习数学基础 120 章

交替优化、Jensen 下界与 EM 算法

层级：B｜按需

1. 隐变量让似然中出现“log of sum”

混合模型中只观察 xx，不知道它来自哪个隐类别 zz：

p(x∣θ)=∑zp(x,z∣θ).p(x|\theta)=\sum_zp(x,z|\theta).

对数似然

log⁡∑zp(x,z∣θ)\log\sum_zp(x,z|\theta)

难以直接优化，因为对数外有求和。EM 通过构造可优化下界，交替估计隐变量分布与参数。

2. 交替优化的一般思想

若目标 F(x,y)F(x,y) 联合难优化，但固定一块后另一块容易：

xt+1=arg⁡min⁡xF(x,yt),x_{t+1}=\arg\min_xF(x,y_t), yt+1=arg⁡min⁡yF(xt+1,y).y_{t+1}=\arg\min_yF(x_{t+1},y).

若每步精确最小化，目标不增。但联合非凸时通常只收敛到坐标驻点/局部解，初始化重要。

k-means 就是交替优化：固定中心分配样本，固定分配取簇均值。

3. Jensen 下界

对任意分布 q(z)q(z)：

log⁡p(x∣θ)=log⁡∑zq(z)p(x,z∣θ)q(z).\log p(x|\theta) =\log\sum_zq(z)\frac{p(x,z|\theta)}{q(z)}.

因 log⁡\log 凹：

log⁡p(x∣θ)≥∑zq(z)log⁡p(x,z∣θ)q(z).\log p(x|\theta) \ge\sum_zq(z) \log\frac{p(x,z|\theta)}{q(z)}.

定义

L(q,θ)=Eq[log⁡p(x,z∣θ)]+H(q),\mathcal L(q,\theta) =\mathbb E_q[\log p(x,z|\theta)] +H(q),

其中

H(q)=−Eqlog⁡q(z).H(q)=-\mathbb E_q\log q(z).

这就是 evidence lower bound（ELBO）。

4. 下界差距是 KL 散度

可证明

log⁡p(x∣θ)=L(q,θ)+DKL(q(z)∥p(z∣x,θ)).\log p(x|\theta) =\mathcal L(q,\theta) +D_{KL}(q(z)\|p(z|x,\theta)).

KL 非负，所以是下界；当

q(z)=p(z∣x,θ)q(z)=p(z|x,\theta)

时 KL 为 0，下界与对数似然贴紧。

5. E 步

固定当前参数 θt\theta_t，选择

qt+1(z)=p(z∣x,θt).q_{t+1}(z)=p(z|x,\theta_t).

这使下界在当前参数处等于真实对数似然。E 是 expectation，因为后续使用隐变量充分统计量的后验期望。

若精确后验难算，可限制 qq 的族并最大化 ELBO，得到变分 EM；此时下界通常无法完全贴紧。

6. M 步

固定 qt+1q_{t+1}：

θt+1=arg⁡max⁡θEqt+1[log⁡p(x,z∣θ)].\theta_{t+1} =\arg\max_\theta \mathbb E_{q_{t+1}} [\log p(x,z|\theta)].

熵 H(q)H(q) 与 θ\theta 无关，可忽略。M 是 maximization。若只提高而不精确最大化，称 generalized EM，只要保证下界不降，仍有单调性。

7. 单调性链条

E 步使

L(qt+1,θt)=log⁡p(x∣θt).\mathcal L(q_{t+1},\theta_t) =\log p(x|\theta_t).

M 步提高下界：

L(qt+1,θt+1)≥L(qt+1,θt).\mathcal L(q_{t+1},\theta_{t+1}) \ge\mathcal L(q_{t+1},\theta_t).

而真实似然总在下界上方，所以

log⁡p(x∣θt+1)≥log⁡p(x∣θt).\log p(x|\theta_{t+1}) \ge\log p(x|\theta_t).

单调不降不保证到全局最大，也不保证参数序列唯一。

8. 高斯混合模型 E 步

p(xi)=∑k=1KπkN(xi∣μk,Σk).p(x_i)=\sum_{k=1}^{K}\pi_k \mathcal N(x_i|\mu_k,\Sigma_k).

责任度：

γik=P(zi=k∣xi)=πkN(xi∣μk,Σk)∑jπjN(xi∣μj,Σj).\gamma_{ik}=P(z_i=k|x_i) =\frac{\pi_k\mathcal N(x_i|\mu_k,\Sigma_k)} {\sum_j\pi_j\mathcal N(x_i|\mu_j,\Sigma_j)}.

它是样本 ii 属于分量 kk 的后验软分配，每行和为 1。数值上应在 log 域用 LogSumExp 计算。

9. GMM M 步

令

Nk=∑iγik.N_k=\sum_i\gamma_{ik}.

更新：

πk=Nkn,\pi_k=\frac{N_k}{n}, μk=1Nk∑iγikxi,\mu_k=\frac1{N_k}\sum_i\gamma_{ik}x_i, Σk=1Nk∑iγik(xi−μk)(xi−μk)T.\Sigma_k=\frac1{N_k} \sum_i\gamma_{ik}(x_i-\mu_k)(x_i-\mu_k)^T.

即按软分配权重计算比例、均值与协方差。

10. 退化与局部最优

GMM 似然可能无界：某个分量均值对准单个样本、协方差趋零，密度趋无穷。实践需协方差下界、先验、共享/对角结构、删除空分量或 MAP 估计。

多个随机初始化、k-means 初始化和验证模型选择很重要。似然高也不自动保证聚类语义符合业务。

11. EM、k-means 与软硬分配

k-means 可视为球形等方差 GMM 在方差趋小极限下的硬分配近似。EM 使用责任度软分配；k-means 每个样本只属于最近中心。二者都交替优化并可能局部最优。

12. 缺失数据

把缺失值视为隐变量，E 步计算其条件分布/充分统计量期望，M 步更新参数。但“缺失机制”很重要：MCAR、MAR、MNAR 需要不同假设，盲目 EM 不会自动修复非随机缺失偏差。

易错点

  1. EM 单调提高似然，不保证全局最优。
  2. E 步计算后验/期望，不是直接填一个最可能标签。
  3. M 步最大化期望完整数据对数似然，不是原似然的简单替换。
  4. GMM 可能协方差塌缩导致似然无界。
  5. 责任度计算要用 log-domain 稳定形式。

常见问答

Q1：EM 是优化算法还是统计模型？

它是针对含隐变量概率模型的一类优化框架，不是具体模型；GMM、HMM 等都可使用。

Q2：EM 与变分推断有什么关系？

EM 的 E 步允许在所有分布中选精确后验；变分推断把 qq 限制在可计算族，直接优化同类 ELBO。

Q3：为什么 EM 看起来没有学习率？

标准 EM 每步精确优化一个块，通过下界保证单调。可用阻尼、在线 EM 或广义 EM 引入部分更新。

练习

  1. 写出 ELBO 与 log evidence 的 KL 分解。
  2. E 步何时使下界贴紧？
  3. GMM 责任度为何每个样本上和为 1？
  4. EM 单调性为何不意味着全局最优？
  5. GMM 协方差塌缩如何处理？

答案与提示

  1. log⁡p(x)=L(q,θ)+KL(q∥p(z∣x,θ))\log p(x)=\mathcal L(q,\theta)+KL(q\|p(z|x,\theta))。
  2. qq 等于当前参数下真实后验。
  3. 它是对离散隐类别的归一化后验概率。
  4. 非凸似然可有多个局部极大/鞍点，单调序列可能停在任一处。
  5. 加协方差正则/下界、先验、结构限制并使用多初始化。