查看全课大纲(第 59 / 82 节)
- 1.函数与数据泛化
- 2.向量:从几何直觉到高维空间
- 3.矩阵与张量
- 4.特征值与特征向量:矩阵变换的不动方向
- 5.凸函数:从向量求导的矩阵记号到好优化的函数形状
- 6.概率与统计:机器学习的数学基础
- 7.独立性与随机变量:贝叶斯公式与二项分布
- 8.期望、方差与协方差:随机变量的数字画像
- 9.联合概率:当一条轴不够用的时候
- 10.概率分布(一):从伯努利到伽马函数
- 11.概率分布(二):贝塔、泊松、正态与两个贝叶斯故事
- 12.机器学习的模型:找输入与输出的关系
- 13.机器学习的应用
- 14.过拟合
- 15.机器学习的分类
- 16.有监督学习:从房价预测说起
- 17.损失函数
- 18.梯度下降(上):更新规则与学习速率
- 19.梯度下降(2)
- 20.牛顿方法
- 21.KNN简介
- 22.距离测算
- 23.朴素贝叶斯
- 24.朴素贝叶斯的实际应用
- 25.信息熵:决策树构建的度量基础
- 26.信息增益与决策树的构建
- 27.ID3算法
- 28.决策树节点的划分
- 29.CART树
- 30.Bagging
- 31.Boosting:自适应提升算法
- 32.Gradient Boosting
- 33.线性模型:回归与分类的同一副骨架
- 34.最小二乘:把最优参数直接解出来
- 35.最小二乘法的几何与概率视角
- 36.极大似然:给最小二乘一个概率出身
- 37.逻辑回归(1):把线性模型接到分类上
- 38.逻辑回归(2):损失函数与多分类
- 39.---- 手造数据: 5 个样本, 2 个特征; x2 几乎 = 2*x1 (偏差手工指定, 无随机) ----
- 40.讲师例: 向量 "23014" -- 三把范数尺子量同一个向量
- 41.优化方法(1):坐标下降与前向选择
- 42.优化方法(2):前向策略与最小角回归
- 43.拉格朗日乘子法(1):从无约束到等式约束
- 44.拉格朗日乘子法(2):等式约束下的平行条件与拉格朗日函数
- 45.拉格朗日乘子法(3):不等式约束与 KKT 条件
- 46.最大间隔:把分类问题变成优化问题
- 47.拉格朗日对偶问题:把 w 和 b 全部换成 α
- 48.支持向量:边界上的少数派
- 49.SVM 计算过程:一笔到底算完,再走进核方法
- 50.贝叶斯公式:概率即信念
- 51.隐含变量和概率模型:给看不见的原因建模
- 52.EM 算法:期望与最大化的迭代
- 53.琴生不等式:EM 的数学钥匙
- 54.三个硬币问题:EM 的复盘与衔接
- 55.高斯混合模型:用隐变量解释双峰数据
- 56.隐马尔可夫模型
- 57.隐马尔可夫模型(2):前向算法与动态混合模型
- 58.隐马尔可夫模型在 NLP 中的运用
- 59.EM 算法:把「为什么收敛」推到底
- 60.HMM 在 NLP 中的运用:从分词到机器翻译
- 61.HMM 参数估计:Baum-Welch 的三块拉格朗日
- 62.高维下的高斯模型
- 63.主题模型:从词袋到隐含主题
- 64.Dirichlet 分布(1)
- 65.Dirichlet 分布(2)
- 66.统计学习内容回顾
- 67.K-means 算法
- 68.PCA 降维
- 69.SVD 降维
- 70.从聚类到流形
- 71.局部线性嵌入
- 72.随机邻域嵌入:SNE 与 t-SNE
- 73.无参模型:让数据自己说话
- 74.高斯过程:函数空间里的正态分布
- 75.高斯过程(2):噪声、正则化与核的线性组合
- 76.神经网络简介:从感知器到自编码器
- 77.反向传播:把误差一层层传回去
- 78.卷积神经网络(CNN):让特征自己学出来
- 79.循环神经网络(RNN):给网络装上记忆
- 80.深度学习回顾:静态一类,动态一类
- 81.增强学习(1):蒙特卡洛、树搜索与 Q-learning
- 82.强化学习(2):从乌鸦吃核桃到井字棋的 value 回传
EM 算法:把「为什么收敛」推到底
约 27 分钟
小象实战讲义 · 机器学习算法精讲
上一节结尾我们留了一个问题:EM 算法为什么是收敛的。本节讲师开场就把任务挑明——「我们接着说上次关于 EM 算法的、最底层的这个部分。我给大家用点时间,更清晰地用数学公式去描述一下,请大家跟着稍稍紧一点。」这是全课数学密度最高的一节:12.2/12.3 用三硬币把 EM 的每一步「数」了出来,12.4 用琴生不等式看到了「下界贴着似然往上抬」的图景,本节把图景背后的公式从头到尾正式写全。主角是一个新对象大 Q 函数,外加把下界拆成「两块死数 + 一块可调」的三块分解——EM 为什么每轮迭代都不亏,答案全在这三块里。
💡 核心导读
- 大 Q 函数:——M 步真正要最大化的那个函数。
- 记号课:上角标 是「第 轮更新」,不是数据个数; 随便给一组随机数就能启动。
- 下界三步:比上一个再乘上一个(乘除同值)→ 求和认出期望 → 琴生不等式( 是凹函数)。
- 三块分解: 是死数、被减的 是死数、 是 M 步唯一能推大的可调块。
- 收敛的真相:下界永远压在似然下面,每轮 M 步只可能把下界往上推——似然想降都没有地方降。
把问题重新摆上桌
开场先把老问题重述一遍。很多机器学习问题最后都可以变成一个求极大似然的问题:高维空间里有一组数据,这组数据有它的生成机制——无论多复杂的系统,你观察到的数据总跟系统里给定的系数 直接相关, 就是生成模型里的重要参数;而 是随机变量(random variable)。我们想通过给定的一组数据,得到对 的一个好的估计。讲师讲到「想知道他们的后验概率」时自己刹住纠正:「sorry,不是后验概率——对这个极大似然的估计。」(这个口误自纠值得记下:这一章从头到尾咬住的就是极大似然,不是后验。)
为什么会有隐变量?因为我们研究的复杂概率图模型,一般都有一个隐含变量 存在。三硬币里它就是那个「A 硬币掷完决定走 B 还是 C」的选择——A 实际上代表一种混合权重;如果是隐马尔可夫链,这个动态、跟时序相关的隐变量就是我们记过的状态 ——「把 换成 ,两者是一回事」,只是 HMM 的 与 之间还多了一个状态转移矩阵(时序关系 + 马尔可夫特性),普通的隐含模型用下面这一个公式就能描述。
想做的事情,是把它构造成两个乘积的关系:给定 时 的分布知道,再补一个关于 的先验分布——
「这就是我们对于那个硬币的问题的算法,我们就是这么算的。」另外,严格说多个观测的似然原则上是对不同 的乘积,取了 才变成加和——讲师板书到这里补了一句「我少写了一个 ,Sorry」,顺手把联合概率的每一项补齐。
先构造「大 Q 函数」
在往下推之前,讲师先郑重构造一个函数——这是本节真正的主角:
直读一遍:给定了 和 的时候,在 的(后验)分布下,对 联合似然取的数学期望。这里有一节必上的记号课——上角标 :
的 ()代表不同更新时刻的参数值,不代表数据的数量 。 时 就是一个给定的随机数——「像我们以前三硬币的概率那样,0.3、0.5、0.36 随机给定一组就行」。
有了它,E 步和 M 步一句话说清:
- E 步:给定 ,把期望算出来——想知道 有什么样的分布时这个 最大。三硬币里算的 (每个观测属于每个状态的估计)干的就是这件事;
- M 步:不断地调整 使这个函数最大,把最大值点赋给下一时刻——
跟 12.4 辨析一下:12.4 的 是一条分布;本节的 是一个关于 的函数。同一个字母、两层身份——分布决定「期望在哪取」,函数才是「M 步要推大的那个东西」。
下界是怎么来的:三步快走
这一段 12.4 已经用课件详细走过(弦与碗的图就在那里),本节快步重走、把它接到新的展开上。目标函数:
第一步,乘除同值。 在 里的求和中,给联合概率比上一个、再乘上一个 ——它是关于 的分布(跟当前的 、 有关)。一比一乘,相乘为一,公式还是对的,但形态变了:
第二步,认出期望。 带权重的求和就是期望——讲师顺手复习了期望的写法:,也常写成「 时 的期望」。于是「 的分布乘 的函数」自然合成为期望, 仍罩在最外层。
第三步,琴生不等式。 是凹函数(concave),12.4 的结论直接拿来:期望的函数 函数的期望——
这一步的形态变化要看清: 从「套着求和」变成了「咬着每一项」——右边就是似然函数的下界。
展开、约掉、拆成三块
现在做本节的主菜。往下推之前,讲师先标出两个情况:
- 直接跟 相关、间接跟 相关: 是高层的参数,控制着隐含变量 ; 才直接作用到能观察的 上。「就像刚开始描述的隐马尔可夫链—— 其实就等于 ,因为 只跟单一状态直接相关。」
- 分母可以用贝叶斯公式展开(讲师口误自纠彩蛋:「分子这样——分母的部分,Sorry,这个分母的这个部分」):
这个展开可以自检:把上标 全去掉,右边就是 ——分子分母都是 与 的联合概率拆装,「所以这个公式是肯定对的」。
把贝叶斯展开代入下界的分式,联合概率再按第一节的乘积分解开,分数变成:
约掉。 与 对 的影响是一样的——「因为 直接相关的就是 ,跟 是间接相关,所以它们俩是一样的。一样的就可以约掉。」上下两个发射项一约,分式只剩三样东西:、、。 一拆,下界分解成三块:
逐块定性(讲师在板书上换了三种颜色):
- 中间块 ——死数。 它以 的分布求 ,跟 没有直接关系;它就是给定 时的极大似然值(正态分布的话,就是给定均值方差后 的概率)。数据固定、 给定,这个数就定死了。
- 末块 ——死数(被减)。 给定 后 的分布可以求出来,里面的概率密度也都是给定的非负数——它整体是一个被减掉的固定项,只能往下拽,我们动不了它。
- 首块 ——唯一可调。 代表上一时刻的参数值,而当前的 是可以根据它调整的。「怎么调整?就不断地调整 ,使这个值越来越大——我们在不断地把 的下界不断提高,因为另外两个部分我们做不了什么事情。」
再把首末两块认出来:加的这块正是 ,减的这块正是 (「跟刚才定义的公式比——就是它」)。于是三块分解写成正式形态:
诚实框(一般情形):上面「约掉发射项」用到了第 1 个情况的前提——发射侧不带参数。但三硬币的 、 和 HMM 的释放矩阵 本身也是参数:把它们也放进 时,,两项约不得。别慌——不约就行:被约掉的两项会自动并回完整的 里,上式的最终形态在一般情形下照样成立(本节开头定义大 Q 用的就是完整联合似然)。变化只有一处:「唯一可调」从 升级成完整的 ,M 步与收敛的结论一字不变。下面块 1 跑的就是完整版(、 都在 里)——三块分解照样精确成立。
顺带与 12.4 对个账:12.4 的下界 把分布 写在分数线下,本节的大 Q 把它挪了出去——两者相差一个与 无关的熵项,所以哪个 更好,两边给出的答案相同。
为什么每一轮都不亏
三块分解在手,收敛性就是一行链条。每一轮 M 步把可调块推大、两块死数纹丝不动,于是下界只可能升不可能降;而下界又永远压在似然下面。把三个式子连起来:
- 第一个 是琴生不等式:似然永远压在下界上方;
- 第二个 是 M 步的定义: 是让 最大的参数,至少不比原地不动的 差;
- 最后的 是取等: 时分式比值恰为 、与 无关——期望取在常数上,琴生取等号(12.4「E 步把下界贴住似然」的代数形态)。
讲师的收口原话,也是本节的全部要点:「这就是我们比较详细的 EM 算法背后的道理——我们为什么认为每次它会收敛、会提到这个下界:因为我们每次所做的优化,都是把这个下界不断地提高。因为我每一次在 E 步的时候,就算得出来这个 。」
在三硬币上把三块拆开看
还是那串 21 掷观测、那组「随便给」的初值 ——12.4 从「绿色曲线」看过一遍 E 取等、M 抬升;本节换个视角,把下界拆成三块看每一块的数。先跑完整版(、 都算 的成分,对应诚实框里的一般情形):
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三件事读出来:取等亲眼看到( 时下界与似然都是 );换烂参数下界塌得深( 处差了 ——参数越不对劲,下界离似然越远);M 步只动可调块( 从 推到 ,两块死数一动不动,下界整体抬升 ,似然同步到达 ——12.4 发现的「一步到顶」结构在这里再次显形:后验不变,新点的下界又贴住了似然)。
再把讲师推导的前提如实落地跑一遍:、 视为已知的发射特性(不进 ), 里只剩控制 先验的高层参数 ——此时「约掉发射项」严格成立,三块分解逐项精确对上:
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 步数数公式: 红色总份数 / 总次数表格把讲师那支彩色的粉笔变成了数:取等只发生在 (差恰为 );下界的最高点恰在 ——对可调块 求导归零,解出来 ,正是 12.3 里「红色总份数 / 总次数」的数数公式。当时的直觉「按比例数数」,在这节课里露出了它的真身:把 这个可调块最大化。至于 那行——下界差了 ,松得一塌糊涂:参数离谱的程度,就写在下界与似然的缝里。
📝 动手练一练
- 三块分解与收敛链:给定分解式 ,回答四问:(a) 哪两块在 给定后是「动不了」的死数?M 步唯一能推大的是哪一块?(b) 为什么 时恰好取等号?(c) 把「每一轮似然不降」的完整链条写出来,并注明三个不等号各自的来源。(d) 上角标 代表什么——数据个数,还是更新时刻?
👉 点击查看参考答案
(a) 与被减的 是死数(数据固定、 给定后就定了);可调的是 。 (b) 取等条件是琴生的「期望取在常数上」: 时分式比值 ,与 无关——分子分母成正比,比例恰为当前似然。 (c) 。第一个 来自琴生(似然压在下界上方);第二个 来自 M 步的 argmax( 至少不差于原地取 );最后的 就是 (b) 的取等。 (d) 更新时刻( 是迭代的轮数),不是数据个数 。 是随机初值,每轮 E 步都用最新的 重算期望。
- 把数数公式重推一遍:固定 (E 步算出的后验),可调块为 。对 求导并令其为零,解出最大值点 ,并说明它与 12.3 的「红色总份数 / 总次数」是同一件事。
👉 点击查看参考答案
求导:。移项整理:,展开消项得 ,所以
代入块 2 的数字:。12.3 里它读作「红色总份数除以总次数」——每个观测按 拆成红色份数,加起来就是总份数。直觉的数数与代数的求导,给的是同一个 :M 步就是把可调块最大化。
本章小结
本节把 EM 的数学底层正式写全:先构造大 Q 函数 (E 步求期望、M 步 argmax,上角标 是更新时刻、 随机给定);再经乘除同值、认出期望、琴生不等式三步得到似然的下界;用贝叶斯展开分母、约掉发射项,把下界拆成三块——两块死数(当前似然 与被减的 )加一块唯一可调的 。收敛性的全部秘密就在这:M 步每轮只能把可调块往上推,下界抬升、又永远压在似然下面,于是 逐轮成立。发射侧也带参数的一般情形,被约掉的项并回完整的大 Q,结论不变;而在三硬币上,可调块求导归零解出的 ,正是 12.3 那条「按比例数数」公式的真身。
📋 行动清单
- 把板书推导亲手重走一遍:乘除同值 → 认出期望 → 琴生 → 贝叶斯展开 → 约掉 → 三块——讲师预告「跟着稍稍紧一点」,值得慢速重放。
- 回到 12.3 的三硬币迭代,把每一步标注成「算 (E 步)」或「argmax (M 步)」。
- 对照 12.4 的 与本节大 :确认两者只差一个与 无关的熵项、argmax 相同。
- 预习下一节:同一套 HMM 骨架怎么装下分词、词性、语音三档难度,以及它如何收尾到「HMM 的参数怎么估」。
—— 小象教研组
配套资料 · 直接下载
课件、代码、数据集等配套资料全部免费,点击即可直接下载,无需分享或解锁。
- 下载第14章笔记:隐马尔可夫模型(HMM)