查看全课大纲(第 59 / 82 节)
  1. 1.函数与数据泛化
  2. 2.向量:从几何直觉到高维空间
  3. 3.矩阵与张量
  4. 4.特征值与特征向量:矩阵变换的不动方向
  5. 5.凸函数:从向量求导的矩阵记号到好优化的函数形状
  6. 6.概率与统计:机器学习的数学基础
  7. 7.独立性与随机变量:贝叶斯公式与二项分布
  8. 8.期望、方差与协方差:随机变量的数字画像
  9. 9.联合概率:当一条轴不够用的时候
  10. 10.概率分布(一):从伯努利到伽马函数
  11. 11.概率分布(二):贝塔、泊松、正态与两个贝叶斯故事
  12. 12.机器学习的模型:找输入与输出的关系
  13. 13.机器学习的应用
  14. 14.过拟合
  15. 15.机器学习的分类
  16. 16.有监督学习:从房价预测说起
  17. 17.损失函数
  18. 18.梯度下降(上):更新规则与学习速率
  19. 19.梯度下降(2)
  20. 20.牛顿方法
  21. 21.KNN简介
  22. 22.距离测算
  23. 23.朴素贝叶斯
  24. 24.朴素贝叶斯的实际应用
  25. 25.信息熵:决策树构建的度量基础
  26. 26.信息增益与决策树的构建
  27. 27.ID3算法
  28. 28.决策树节点的划分
  29. 29.CART树
  30. 30.Bagging
  31. 31.Boosting:自适应提升算法
  32. 32.Gradient Boosting
  33. 33.线性模型:回归与分类的同一副骨架
  34. 34.最小二乘:把最优参数直接解出来
  35. 35.最小二乘法的几何与概率视角
  36. 36.极大似然:给最小二乘一个概率出身
  37. 37.逻辑回归(1):把线性模型接到分类上
  38. 38.逻辑回归(2):损失函数与多分类
  39. 39.---- 手造数据: 5 个样本, 2 个特征; x2 几乎 = 2*x1 (偏差手工指定, 无随机) ----
  40. 40.讲师例: 向量 "23014" -- 三把范数尺子量同一个向量
  41. 41.优化方法(1):坐标下降与前向选择
  42. 42.优化方法(2):前向策略与最小角回归
  43. 43.拉格朗日乘子法(1):从无约束到等式约束
  44. 44.拉格朗日乘子法(2):等式约束下的平行条件与拉格朗日函数
  45. 45.拉格朗日乘子法(3):不等式约束与 KKT 条件
  46. 46.最大间隔:把分类问题变成优化问题
  47. 47.拉格朗日对偶问题:把 w 和 b 全部换成 α
  48. 48.支持向量:边界上的少数派
  49. 49.SVM 计算过程:一笔到底算完,再走进核方法
  50. 50.贝叶斯公式:概率即信念
  51. 51.隐含变量和概率模型:给看不见的原因建模
  52. 52.EM 算法:期望与最大化的迭代
  53. 53.琴生不等式:EM 的数学钥匙
  54. 54.三个硬币问题:EM 的复盘与衔接
  55. 55.高斯混合模型:用隐变量解释双峰数据
  56. 56.隐马尔可夫模型
  57. 57.隐马尔可夫模型(2):前向算法与动态混合模型
  58. 58.隐马尔可夫模型在 NLP 中的运用
  59. 59.EM 算法:把「为什么收敛」推到底
  60. 60.HMM 在 NLP 中的运用:从分词到机器翻译
  61. 61.HMM 参数估计:Baum-Welch 的三块拉格朗日
  62. 62.高维下的高斯模型
  63. 63.主题模型:从词袋到隐含主题
  64. 64.Dirichlet 分布(1)
  65. 65.Dirichlet 分布(2)
  66. 66.统计学习内容回顾
  67. 67.K-means 算法
  68. 68.PCA 降维
  69. 69.SVD 降维
  70. 70.从聚类到流形
  71. 71.局部线性嵌入
  72. 72.随机邻域嵌入:SNE 与 t-SNE
  73. 73.无参模型:让数据自己说话
  74. 74.高斯过程:函数空间里的正态分布
  75. 75.高斯过程(2):噪声、正则化与核的线性组合
  76. 76.神经网络简介:从感知器到自编码器
  77. 77.反向传播:把误差一层层传回去
  78. 78.卷积神经网络(CNN):让特征自己学出来
  79. 79.循环神经网络(RNN):给网络装上记忆
  80. 80.深度学习回顾:静态一类,动态一类
  81. 81.增强学习(1):蒙特卡洛、树搜索与 Q-learning
  82. 82.强化学习(2):从乌鸦吃核桃到井字棋的 value 回传

EM 算法:把「为什么收敛」推到底

约 27 分钟

📺 正在播放小象官方高清录播(支持倍速与清晰度调节)

小象实战讲义 · 机器学习算法精讲

上一节结尾我们留了一个问题:EM 算法为什么是收敛的。本节讲师开场就把任务挑明——「我们接着说上次关于 EM 算法的、最底层的这个部分。我给大家用点时间,更清晰地用数学公式去描述一下,请大家跟着稍稍紧一点。」这是全课数学密度最高的一节:12.2/12.3 用三硬币把 EM 的每一步「数」了出来,12.4 用琴生不等式看到了「下界贴着似然往上抬」的图景,本节把图景背后的公式从头到尾正式写全。主角是一个新对象大 Q 函数,外加把下界拆成「两块死数 + 一块可调」的三块分解——EM 为什么每轮迭代都不亏,答案全在这三块里。

💡 核心导读

  • 大 Q 函数:Q(θ∣θt)=EZ∼P(Z∣X,θt)[log⁡P(X,Z∣θ)]Q(\theta|\theta^t) = \mathbb{E}_{Z \sim P(Z|X,\theta^t)}[\log P(X,Z|\theta)]——M 步真正要最大化的那个函数。
  • 记号课:上角标 tt 是「第 tt 轮更新」,不是数据个数;θ0\theta^0 随便给一组随机数就能启动。
  • 下界三步:比上一个再乘上一个(乘除同值)→ 求和认出期望 → 琴生不等式(log⁡\log 是凹函数)。
  • 三块分解:ℓ(θt)\ell(\theta^t) 是死数、被减的 Q(θt∣θt)Q(\theta^t|\theta^t) 是死数、Q(θ∣θt)Q(\theta|\theta^t) 是 M 步唯一能推大的可调块。
  • 收敛的真相:下界永远压在似然下面,每轮 M 步只可能把下界往上推——似然想降都没有地方降。

把问题重新摆上桌

开场先把老问题重述一遍。很多机器学习问题最后都可以变成一个求极大似然的问题:高维空间里有一组数据,这组数据有它的生成机制——无论多复杂的系统,你观察到的数据总跟系统里给定的系数 θ\theta 直接相关,θ\theta 就是生成模型里的重要参数;而 xx 是随机变量(random variable)。我们想通过给定的一组数据,得到对 θ\theta 的一个好的估计。讲师讲到「想知道他们的后验概率」时自己刹住纠正:「sorry,不是后验概率——对这个极大似然的估计。」(这个口误自纠值得记下:这一章从头到尾咬住的就是极大似然,不是后验。)

为什么会有隐变量?因为我们研究的复杂概率图模型,一般都有一个隐含变量 ZZ 存在。三硬币里它就是那个「A 硬币掷完决定走 B 还是 C」的选择——A 实际上代表一种混合权重;如果是隐马尔可夫链,这个动态、跟时序相关的隐变量就是我们记过的状态 QQ——「把 ZZ 换成 QQ,两者是一回事」,只是 HMM 的 QQ 与 QQ 之间还多了一个状态转移矩阵(时序关系 + 马尔可夫特性),普通的隐含模型用下面这一个公式就能描述。

想做的事情,是把它构造成两个乘积的关系:给定 ZZ 时 XX 的分布知道,再补一个关于 ZZ 的先验分布——

P(X,Z∣θ)=P(X∣Z,θ) P(Z∣θ)P(X, Z|\theta) = P(X|Z, \theta)\, P(Z|\theta)

「这就是我们对于那个硬币的问题的算法,我们就是这么算的。」另外,严格说多个观测的似然原则上是对不同 ii 的乘积,取了 log⁡\log 才变成加和——讲师板书到这里补了一句「我少写了一个 PP,Sorry」,顺手把联合概率的每一项补齐。

先构造「大 Q 函数」

在往下推之前,讲师先郑重构造一个函数——这是本节真正的主角:

Q(θ∣θt)≜EZ∼P(Z∣X,θt)[log⁡P(X,Z∣θ)]Q(\theta|\theta^t) \triangleq \mathbb{E}_{Z \sim P(Z|X,\theta^t)}\big[\log P(X,Z|\theta)\big]

直读一遍:给定了 XX 和 θt\theta^t 的时候,在 ZZ 的(后验)分布下,对 log⁡\log 联合似然取的数学期望。这里有一节必上的记号课——上角标 tt:

θt\theta^t 的 tt(t=1,…,Tt = 1, \dots, T)代表不同更新时刻的参数值,不代表数据的数量 X1,…,XNX_1, \dots, X_N。t=0t=0 时 θ0\theta^0 就是一个给定的随机数——「像我们以前三硬币的概率那样,0.3、0.5、0.36 随机给定一组就行」。

有了它,E 步和 M 步一句话说清:

  • E 步:给定 θt\theta^t,把期望算出来——想知道 ZZ 有什么样的分布时这个 QQ 最大。三硬币里算的 μ\mu(每个观测属于每个状态的估计)干的就是这件事;
  • M 步:不断地调整 θ\theta 使这个函数最大,把最大值点赋给下一时刻——

θt+1=arg⁡max⁡θ  Q(θ∣θt)\theta^{t+1} = \arg\max_{\theta}\; Q(\theta|\theta^t)

跟 12.4 辨析一下:12.4 的 Qi(z(i))Q_i(z^{(i)}) 是一条分布;本节的 Q(θ∣θt)Q(\theta|\theta^t) 是一个关于 θ\theta 的函数。同一个字母、两层身份——分布决定「期望在哪取」,函数才是「M 步要推大的那个东西」。

下界是怎么来的:三步快走

这一段 12.4 已经用课件详细走过(弦与碗的图就在那里),本节快步重走、把它接到新的展开上。目标函数:

ℓ(θ)=log⁡∑ZP(X,Z∣θ)\ell(\theta) = \log \sum_{Z} P(X, Z|\theta)

第一步,乘除同值。 在 log⁡\log 里的求和中,给联合概率比上一个、再乘上一个 P(Z∣X,θt)P(Z|X,\theta^t)——它是关于 ZZ 的分布(跟当前的 XX、θt\theta^t 有关)。一比一乘,相乘为一,公式还是对的,但形态变了:

ℓ(θ)=log⁡∑ZP(Z∣X,θt)⋅P(X,Z∣θ)P(Z∣X,θt)=log⁡EZ∼P(Z∣X,θt)[P(X,Z∣θ)P(Z∣X,θt)]\ell(\theta) = \log \sum_{Z} P(Z|X,\theta^t)\cdot\frac{P(X,Z|\theta)}{P(Z|X,\theta^t)} = \log \mathbb{E}_{Z \sim P(Z|X,\theta^t)}\left[\frac{P(X,Z|\theta)}{P(Z|X,\theta^t)}\right]

第二步,认出期望。 带权重的求和就是期望——讲师顺手复习了期望的写法:∑xP(x) f(x)=E[f(X)]\sum_x P(x)\,f(x) = \mathbb{E}[f(X)],也常写成「X∼P(X)X \sim P(X) 时 f(X)f(X) 的期望」。于是「ZZ 的分布乘 ZZ 的函数」自然合成为期望,log⁡\log 仍罩在最外层。

第三步,琴生不等式。 log⁡\log 是凹函数(concave),12.4 的结论直接拿来:期望的函数 ≥\ge 函数的期望——

ℓ(θ)≥EZ∼P(Z∣X,θt)[log⁡P(X,Z∣θ)P(Z∣X,θt)]\ell(\theta) \ge \mathbb{E}_{Z \sim P(Z|X,\theta^t)}\left[\log \frac{P(X,Z|\theta)}{P(Z|X,\theta^t)}\right]

这一步的形态变化要看清:log⁡\log 从「套着求和」变成了「咬着每一项」——右边就是似然函数的下界。

展开、约掉、拆成三块

现在做本节的主菜。往下推之前,讲师先标出两个情况:

  1. XX 直接跟 ZZ 相关、间接跟 θ\theta 相关:θ\theta 是高层的参数,控制着隐含变量 ZZ;ZZ 才直接作用到能观察的 XX 上。「就像刚开始描述的隐马尔可夫链——P(X∣Z,θ)P(X|Z,\theta) 其实就等于 P(X∣Z)P(X|Z),因为 XX 只跟单一状态直接相关。」
  2. 分母可以用贝叶斯公式展开(讲师口误自纠彩蛋:「分子这样——分母的部分,Sorry,这个分母的这个部分」):

P(Z∣X,θt)=P(X∣Z,θt) P(Z∣θt)P(X∣θt)P(Z|X,\theta^t) = \frac{P(X|Z,\theta^t)\, P(Z|\theta^t)}{P(X|\theta^t)}

这个展开可以自检:把上标 tt 全去掉,右边就是 P(X∣Z)P(Z)/P(X)=P(Z∣X)P(X|Z)P(Z)/P(X) = P(Z|X)——分子分母都是 xx 与 zz 的联合概率拆装,「所以这个公式是肯定对的」。

把贝叶斯展开代入下界的分式,联合概率再按第一节的乘积分解开,分数变成:

P(X,Z∣θ)P(Z∣X,θt)  ⇒  P(X∣Z)  P(Z∣θ)  P(X∣θt)P(X∣Z,θt)  P(Z∣θt)\frac{P(X,Z|\theta)}{P(Z|X,\theta^t)} \;\Rightarrow\; \frac{P(X|Z)\; P(Z|\theta)\; P(X|\theta^t)}{P(X|Z,\theta^t)\; P(Z|\theta^t)}

约掉。 P(X∣Z,θ)P(X|Z,\theta) 与 P(X∣Z,θt)P(X|Z,\theta^t) 对 XX 的影响是一样的——「因为 XX 直接相关的就是 ZZ,跟 θ\theta 是间接相关,所以它们俩是一样的。一样的就可以约掉。」上下两个发射项一约,分式只剩三样东西:P(Z∣θ)P(Z|\theta)、P(X∣θt)P(X|\theta^t)、P(Z∣θt)P(Z|\theta^t)。log⁡\log 一拆,下界分解成三块:

ℓ(θ)  ≥  EZ[log⁡P(Z∣θ)]  +  ℓ(θt)  −  EZ[log⁡P(Z∣θt)]\ell(\theta) \;\ge\; \mathbb{E}_{Z}[\log P(Z|\theta)] \;+\; \ell(\theta^t) \;-\; \mathbb{E}_{Z}[\log P(Z|\theta^t)]

逐块定性(讲师在板书上换了三种颜色):

  • 中间块 ℓ(θt)\ell(\theta^t)——死数。 它以 ZZ 的分布求 log⁡P(X∣θt)\log P(X|\theta^t),跟 ZZ 没有直接关系;它就是给定 θt\theta^t 时的极大似然值(正态分布的话,就是给定均值方差后 XX 的概率)。数据固定、θt\theta^t 给定,这个数就定死了。
  • 末块 −EZ[log⁡P(Z∣θt)]-\mathbb{E}_Z[\log P(Z|\theta^t)]——死数(被减)。 给定 θt\theta^t 后 ZZ 的分布可以求出来,里面的概率密度也都是给定的非负数——它整体是一个被减掉的固定项,只能往下拽,我们动不了它。
  • 首块 EZ[log⁡P(Z∣θ)]\mathbb{E}_Z[\log P(Z|\theta)]——唯一可调。 θt\theta^t 代表上一时刻的参数值,而当前的 θ\theta 是可以根据它调整的。「怎么调整?就不断地调整 θ\theta,使这个值越来越大——我们在不断地把 ℓ\ell 的下界不断提高,因为另外两个部分我们做不了什么事情。」

再把首末两块认出来:加的这块正是 Q(θ∣θt)Q(\theta|\theta^t),减的这块正是 Q(θt∣θt)Q(\theta^t|\theta^t)(「跟刚才定义的公式比——就是它」)。于是三块分解写成正式形态:

ℓ(θ)  ≥  Q(θ∣θt)  −  Q(θt∣θt)  +  ℓ(θt)\ell(\theta) \;\ge\; Q(\theta|\theta^t)\; -\; Q(\theta^t|\theta^t)\; +\; \ell(\theta^t)

诚实框(一般情形):上面「约掉发射项」用到了第 1 个情况的前提——发射侧不带参数。但三硬币的 pp、qq 和 HMM 的释放矩阵 BB 本身也是参数:把它们也放进 θ\theta 时,P(X∣Z,θ)≠P(X∣Z,θt)P(X|Z,\theta) \ne P(X|Z,\theta^t),两项约不得。别慌——不约就行:被约掉的两项会自动并回完整的 Q(θ∣θt)=E[log⁡P(X,Z∣θ)]Q(\theta|\theta^t) = \mathbb{E}[\log P(X,Z|\theta)] 里,上式的最终形态在一般情形下照样成立(本节开头定义大 Q 用的就是完整联合似然)。变化只有一处:「唯一可调」从 E[log⁡P(Z∣θ)]\mathbb{E}[\log P(Z|\theta)] 升级成完整的 Q(θ∣θt)Q(\theta|\theta^t),M 步与收敛的结论一字不变。下面块 1 跑的就是完整版(pp、qq 都在 θ\theta 里)——三块分解照样精确成立。

顺带与 12.4 对个账:12.4 的下界 L(Q,θ)L(Q,\theta) 把分布 Q(z)Q(z) 写在分数线下,本节的大 Q 把它挪了出去——两者相差一个与 θ\theta 无关的熵项,所以哪个 θ\theta 更好,两边给出的答案相同。

为什么每一轮都不亏

三块分解在手,收敛性就是一行链条。每一轮 M 步把可调块推大、两块死数纹丝不动,于是下界只可能升不可能降;而下界又永远压在似然下面。把三个式子连起来:

ℓ(θt+1)  ≥  Q(θt+1∣θt)−Q(θt∣θt)+ℓ(θt)⏟step1  ≥  Q(θt∣θt)−Q(θt∣θt)+ℓ(θt)⏟step2  =  ℓ(θt)\ell(\theta^{t+1}) \;\ge\; \underbrace{Q(\theta^{t+1}|\theta^t) - Q(\theta^t|\theta^t) + \ell(\theta^t)}_{\text{step1}} \;\ge\; \underbrace{Q(\theta^t|\theta^t) - Q(\theta^t|\theta^t) + \ell(\theta^t)}_{\text{step2}} \;=\; \ell(\theta^t)

  • 第一个 ≥\ge 是琴生不等式:似然永远压在下界上方;
  • 第二个 ≥\ge 是 M 步的定义:θt+1\theta^{t+1} 是让 QQ 最大的参数,至少不比原地不动的 θt\theta^t 差;
  • 最后的 == 是取等:θ=θt\theta = \theta^t 时分式比值恰为 P(X∣θt)P(X|\theta^t)、与 ZZ 无关——期望取在常数上,琴生取等号(12.4「E 步把下界贴住似然」的代数形态)。

讲师的收口原话,也是本节的全部要点:「这就是我们比较详细的 EM 算法背后的道理——我们为什么认为每次它会收敛、会提到这个下界:因为我们每次所做的优化,都是把这个下界不断地提高。因为我每一次在 E 步的时候,就算得出来这个 QQ。」

在三硬币上把三块拆开看

还是那串 21 掷观测、那组「随便给」的初值 (0.3,0.4,0.7)(0.3, 0.4, 0.7)——12.4 从「绿色曲线」看过一遍 E 取等、M 抬升;本节换个视角,把下界拆成三块看每一块的数。先跑完整版(pp、qq 都算 θ\theta 的成分,对应诚实框里的一般情形):

import math

# 同一串观测、同一组初值: 12.4 用过的 21 掷记录 HTHHTTHHTHTHTTTHTHTTH (H=1, T=0)
obs = [1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1]

def ell(pi, p, q):
    """对数似然 ell(theta): log 里面套着求和——直接优化的困难之源"""
    total = 0.0
    for y in obs:
        jb = pi * p**y * (1 - p)**(1 - y)
        jc = (1 - pi) * q**y * (1 - q)**(1 - y)
        total += math.log(jb + jc)
    return total

def posterior(pi, p, q):
    """E 步: mu_i = P(Z=B|y_i, theta)——大 Q 函数里那个期望所用的分布"""
    mu = []
    for y in obs:
        jb = pi * p**y * (1 - p)**(1 - y)
        jc = (1 - pi) * q**y * (1 - q)**(1 - y)
        mu.append(jb / (jb + jc))
    return mu

def Qfun(theta, mu):
    """大 Q 函数: Q(theta|theta_t) = E_{Z~P(Z|X,theta_t)}[log P(X,Z|theta)]"""
    pi, p, q = theta
    total = 0.0
    for y, m in zip(obs, mu):
        jb = pi * p**y * (1 - p)**(1 - y)
        jc = (1 - pi) * q**y * (1 - q)**(1 - y)
        total += m * math.log(jb) + (1 - m) * math.log(jc)
    return total

# theta_t: 沿用 12.3/12.4「随便给」的初值
theta_t = (0.3, 0.4, 0.7)
mu = posterior(*theta_t)

def bound(theta):
    """三块分解: ell(theta) >= Q(theta|theta_t) - Q(theta_t|theta_t) + ell(theta_t)"""
    return Qfun(theta, mu) - Qfun(theta_t, mu) + ell(*theta_t)

print(f"观测 {len(obs)} 次(正面 {sum(obs)}), theta_t = {theta_t}")
print(f"E 步: 正面 mu = {mu[0]:.4f}, 反面 mu = {mu[1]:.4f}")
print()
print("[三块分解] 两块死数 + 一块可调:")
print(f"  死数一: ell(theta_t)       = {ell(*theta_t):.4f}   <- 当前似然, 定死")
print(f"  死数二: Q(theta_t|theta_t) = {Qfun(theta_t, mu):.4f}   <- 被减项, 同样定死")
print(f"  可调块: Q(theta|theta_t)   <- M 步唯一能推大的部分")
print()
print(f"[验证 1] theta = theta_t: 下界 = {bound(theta_t):.4f}, 似然 = {ell(*theta_t):.4f}   <- 琴生取等")
theta2 = (0.5, 0.6, 0.2)
print(f"[验证 2] 换个 theta' = {theta2}:")
print(f"  下界 = {bound(theta2):.4f} < 似然 = {ell(*theta2):.4f}   <- 严格压在下面, 差 {ell(*theta2) - bound(theta2):.4f}")
print()
# M 步: 12.3 的闭式解 = 把可调块 Q 推到最大
sum_mu = sum(mu)
theta_new = (sum_mu / len(obs),
             sum(m * y for m, y in zip(mu, obs)) / sum_mu,
             sum((1 - m) * y for m, y in zip(mu, obs)) / (len(obs) - sum_mu))
print(f"[M 步] argmax Q -> theta_new = ({theta_new[0]:.4f}, {theta_new[1]:.4f}, {theta_new[2]:.4f})")
print(f"  可调块 Q: {Qfun(theta_t, mu):.4f} -> {Qfun(theta_new, mu):.4f}")
print(f"  下界:     {bound(theta_t):.4f} -> {bound(theta_new):.4f}")
print(f"  似然 ell: {ell(*theta_t):.4f} -> {ell(*theta_new):.4f}")
print(f"  链条: ell(new) >= 下界(new) >= 下界(t) = ell(t): {ell(*theta_new):.4f} >= {bound(theta_new):.4f} >= {ell(*theta_t):.4f}")
观测 21 次(正面 10), theta_t = (0.3, 0.4, 0.7)
E 步: 正面 mu = 0.1967, 反面 mu = 0.4615

[三块分解] 两块死数 + 一块可调:
  死数一: ell(theta_t)       = -15.3007   <- 当前似然, 定死
  死数二: Q(theta_t|theta_t) = -27.8509   <- 被减项, 同样定死
  可调块: Q(theta|theta_t)   <- M 步唯一能推大的部分

[验证 1] theta = theta_t: 下界 = -15.3007, 似然 = -15.3007   <- 琴生取等
[验证 2] 换个 theta' = (0.5, 0.6, 0.2):
  下界 = -21.9126 < 似然 = -14.7820   <- 严格压在下面, 差 7.1306

[M 步] argmax Q -> theta_new = (0.3354, 0.2793, 0.5756)
  可调块 Q: -27.8509 -> -27.0825
  下界:     -15.3007 -> -14.5323
  似然 ell: -15.3007 -> -14.5323
  链条: ell(new) >= 下界(new) >= 下界(t) = ell(t): -14.5323 >= -14.5323 >= -15.3007

三件事读出来:取等亲眼看到(θ=θt\theta = \theta^t 时下界与似然都是 −15.3007-15.3007);换烂参数下界塌得深(θ′\theta' 处差了 7.13067.1306——参数越不对劲,下界离似然越远);M 步只动可调块(QQ 从 −27.8509-27.8509 推到 −27.0825-27.0825,两块死数一动不动,下界整体抬升 0.76840.7684,似然同步到达 −14.5323-14.5323——12.4 发现的「一步到顶」结构在这里再次显形:后验不变,新点的下界又贴住了似然)。

再把讲师推导的前提如实落地跑一遍:pp、qq 视为已知的发射特性(不进 θ\theta),θ\theta 里只剩控制 ZZ 先验的高层参数 π\pi——此时「约掉发射项」严格成立,三块分解逐项精确对上:

import math

# 讲师推导的前提如实落地: p、q 视为已知的发射特性(不进 theta),
# theta 里只剩控制 Z 先验的高层参数 pi——此时「约掉发射项」严格成立
obs = [1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1]
p_fix, q_fix = 0.4, 0.7
pi_t = 0.3

# E 步(与块 1 相同的 mu)
mu = []
for y in obs:
    jb = pi_t * p_fix**y * (1 - p_fix)**(1 - y)
    jc = (1 - pi_t) * q_fix**y * (1 - q_fix)**(1 - y)
    mu.append(jb / (jb + jc))

def ell_pi(pi):
    """只有 pi 可调时的对数似然"""
    return sum(math.log(pi * p_fix**y * (1 - p_fix)**(1 - y)
                        + (1 - pi) * q_fix**y * (1 - q_fix)**(1 - y)) for y in obs)

def A(pi):
    """可调块: E_Z[log P(Z|theta)] = sum[mu*log(pi) + (1-mu)*log(1-pi)]"""
    return sum(m * math.log(pi) + (1 - m) * math.log(1 - pi) for m in mu)

def bound_pi(pi):
    """三块版下界: A(pi) + ell(pi_t) - A(pi_t)"""
    return A(pi) + ell_pi(pi_t) - A(pi_t)

pi_hat = sum(mu) / len(mu)   # 可调块的最大值点(解析解)

print(f"p={p_fix}, q={q_fix} 固定; pi_t = {pi_t}; 正面 mu = {mu[0]:.4f}, 反面 mu = {mu[1]:.4f}")
print(f"死数: ell(pi_t) = {ell_pi(pi_t):.4f}, A(pi_t) = {A(pi_t):.4f}")
print()
print(f"{'pi':>7} | {'下界':>10} | {'似然':>10} |  差")
for pi in [0.1, 0.2, pi_t, pi_hat, 0.5, 0.8]:
    b, e = bound_pi(pi), ell_pi(pi)
    tag = "  <- 取等" if abs(pi - pi_t) < 1e-12 else ("  <- 下界的最高点" if abs(pi - pi_hat) < 1e-12 else "")
    print(f"{pi:7.4f} | {b:10.4f} | {e:10.4f} |  {e - b:.4f}{tag}")
print()
print(f"可调块 A(pi) 求导归零: pi_hat = sum(mu)/n = {sum(mu):.4f}/21 = {pi_hat:.4f}")
print(f"这正是 12.3 的 M 步数数公式: 红色总份数 / 总次数")
p=0.4, q=0.7 固定; pi_t = 0.3; 正面 mu = 0.1967, 反面 mu = 0.4615
死数: ell(pi_t) = -15.3007, A(pi_t) = -13.4587

     pi |         下界 |         似然 |  差
 0.1000 |   -19.5321 |   -16.2001 |  3.3321
 0.2000 |   -16.2933 |   -15.7010 |  0.5922
 0.3000 |   -15.3007 |   -15.3007 |  0.0000  <- 取等
 0.3354 |   -15.2392 |   -15.1806 |  0.0585  <- 下界的最高点
 0.5000 |   -16.3981 |   -14.7620 |  1.6361
 0.8000 |   -25.8750 |   -14.5433 |  11.3316

可调块 A(pi) 求导归零: pi_hat = sum(mu)/n = 7.0441/21 = 0.3354
这正是 12.3 的 M 步数数公式: 红色总份数 / 总次数

表格把讲师那支彩色的粉笔变成了数:取等只发生在 πt\pi_t(差恰为 0.00000.0000);下界的最高点恰在 π=0.3354\pi = 0.3354——对可调块 A(π)A(\pi) 求导归零,解出来 π=∑μ/n\pi = \sum\mu/n,正是 12.3 里「红色总份数 / 总次数」的数数公式。当时的直觉「按比例数数」,在这节课里露出了它的真身:把 EZ[log⁡P(Z∣θ)]\mathbb{E}_Z[\log P(Z|\theta)] 这个可调块最大化。至于 π=0.8\pi = 0.8 那行——下界差了 11.3311.33,松得一塌糊涂:参数离谱的程度,就写在下界与似然的缝里。

📝 动手练一练

  1. 三块分解与收敛链:给定分解式 ℓ(θ)≥Q(θ∣θt)−Q(θt∣θt)+ℓ(θt)\ell(\theta) \ge Q(\theta|\theta^t) - Q(\theta^t|\theta^t) + \ell(\theta^t),回答四问:(a) 哪两块在 θt\theta^t 给定后是「动不了」的死数?M 步唯一能推大的是哪一块?(b) 为什么 θ=θt\theta = \theta^t 时恰好取等号?(c) 把「每一轮似然不降」的完整链条写出来,并注明三个不等号各自的来源。(d) 上角标 tt 代表什么——数据个数,还是更新时刻?
👉 点击查看参考答案

(a) ℓ(θt)\ell(\theta^t) 与被减的 Q(θt∣θt)Q(\theta^t|\theta^t) 是死数(数据固定、θt\theta^t 给定后就定了);可调的是 Q(θ∣θt)Q(\theta|\theta^t)。 (b) 取等条件是琴生的「期望取在常数上」:θ=θt\theta=\theta^t 时分式比值 P(X,Z∣θt)/P(Z∣X,θt)=P(X∣θt)P(X,Z|\theta^t)/P(Z|X,\theta^t) = P(X|\theta^t),与 ZZ 无关——分子分母成正比,比例恰为当前似然。 (c) ℓ(θt+1)≥Q(θt+1∣θt)−Q(θt∣θt)+ℓ(θt)≥Q(θt∣θt)−Q(θt∣θt)+ℓ(θt)=ℓ(θt)\ell(\theta^{t+1}) \ge Q(\theta^{t+1}|\theta^t) - Q(\theta^t|\theta^t) + \ell(\theta^t) \ge Q(\theta^t|\theta^t) - Q(\theta^t|\theta^t) + \ell(\theta^t) = \ell(\theta^t)。第一个 ≥\ge 来自琴生(似然压在下界上方);第二个 ≥\ge 来自 M 步的 argmax(θt+1\theta^{t+1} 至少不差于原地取 θt\theta^t);最后的 == 就是 (b) 的取等。 (d) 更新时刻(t=1,…,Tt = 1, \dots, T 是迭代的轮数),不是数据个数 X1,…,XNX_1, \dots, X_N。θ0\theta^0 是随机初值,每轮 E 步都用最新的 θt\theta^t 重算期望。

  1. 把数数公式重推一遍:固定 μi\mu_i(E 步算出的后验),可调块为 A(π)=∑i=1n[μilog⁡π+(1−μi)log⁡(1−π)]A(\pi) = \sum_{i=1}^{n}\big[\mu_i \log \pi + (1-\mu_i)\log(1-\pi)\big]。对 π\pi 求导并令其为零,解出最大值点 π^\hat{\pi},并说明它与 12.3 的「红色总份数 / 总次数」是同一件事。
👉 点击查看参考答案

求导:dAdπ=∑iμiπ−∑i(1−μi)1−π=0\dfrac{dA}{d\pi} = \dfrac{\sum_i \mu_i}{\pi} - \dfrac{\sum_i (1-\mu_i)}{1-\pi} = 0。移项整理:(∑iμi)(1−π)=(n−∑iμi)π\big(\sum_i \mu_i\big)(1-\pi) = \big(n - \sum_i \mu_i\big)\pi,展开消项得 nπ=∑iμin\pi = \sum_i \mu_i,所以

π^=1n∑i=1nμi\hat{\pi} = \frac{1}{n}\sum_{i=1}^{n}\mu_i

代入块 2 的数字:7.0441/21=0.33547.0441/21 = 0.3354。12.3 里它读作「红色总份数除以总次数」——每个观测按 μi\mu_i 拆成红色份数,加起来就是总份数。直觉的数数与代数的求导,给的是同一个 π^\hat{\pi}:M 步就是把可调块最大化。

本章小结

本节把 EM 的数学底层正式写全:先构造大 Q 函数 Q(θ∣θt)=EZ∼P(Z∣X,θt)[log⁡P(X,Z∣θ)]Q(\theta|\theta^t) = \mathbb{E}_{Z \sim P(Z|X,\theta^t)}[\log P(X,Z|\theta)](E 步求期望、M 步 argmax,上角标 tt 是更新时刻、θ0\theta^0 随机给定);再经乘除同值、认出期望、琴生不等式三步得到似然的下界;用贝叶斯展开分母、约掉发射项,把下界拆成三块——两块死数(当前似然 ℓ(θt)\ell(\theta^t) 与被减的 Q(θt∣θt)Q(\theta^t|\theta^t))加一块唯一可调的 Q(θ∣θt)Q(\theta|\theta^t)。收敛性的全部秘密就在这:M 步每轮只能把可调块往上推,下界抬升、又永远压在似然下面,于是 ℓ(θt+1)≥ℓ(θt)\ell(\theta^{t+1}) \ge \ell(\theta^t) 逐轮成立。发射侧也带参数的一般情形,被约掉的项并回完整的大 Q,结论不变;而在三硬币上,可调块求导归零解出的 π^=∑μ/n\hat{\pi} = \sum\mu/n,正是 12.3 那条「按比例数数」公式的真身。

📋 行动清单

  • 把板书推导亲手重走一遍:乘除同值 → 认出期望 → 琴生 → 贝叶斯展开 → 约掉 → 三块——讲师预告「跟着稍稍紧一点」,值得慢速重放。
  • 回到 12.3 的三硬币迭代,把每一步标注成「算 QQ(E 步)」或「argmax QQ(M 步)」。
  • 对照 12.4 的 L(Q,θ)L(Q,\theta) 与本节大 QQ:确认两者只差一个与 θ\theta 无关的熵项、argmax 相同。
  • 预习下一节:同一套 HMM 骨架怎么装下分词、词性、语音三档难度,以及它如何收尾到「HMM 的参数怎么估」。

—— 小象教研组

配套资料 · 直接下载

课件、代码、数据集等配套资料全部免费,点击即可直接下载,无需分享或解锁。

  • 第14章笔记:隐马尔可夫模型(HMM)
    下载