5.5 计算机科学与 AI：MCMC、PageRank 与随机梯度

5.5 计算机科学与 AI：MCMC、PageRank 与随机梯度

本节摘要：机器学习把随机过程理论反向使用：不再"给定模型算性质"，而是"想要某个分布，就造一条以它为平稳分布的马尔可夫链"。本节拆解三个代表：MCMC 把第 3 章的遍历定理变成采样引擎；PageRank 把平稳分布变成十亿页面的排序；随机梯度下降把泊松式的随机性变成优化算法的燃料。三者的共同哲学：拥抱随机，因为确定性的代价付不起。

传统流程是"有模型、算性质"：给定转移矩阵，求平稳分布（第 3 章）。机器学习的需求恰好倒过来："我有一个想要的目标分布 π（比如贝叶斯后验），它高维到无法解析处理，请造一条链，让它的平稳分布恰好是 π，然后跑链取样本。"这个倒转产生了马尔可夫链蒙特卡洛（MCMC）——科学计算里最重要的算法思想之一，本节的第一个主角。

MCMC：把平稳分布当原料

核心机制：Metropolis–Hastings 算法构造链的套路是"提议 + 接受"。当前位置 x，提议跳到 x'（某个容易抽样的提议分布），以概率 min(1, [π(x')q(x|x')] / [π(x)q(x'|x)]) 接受，否则原地踏步。可以验证它满足详细平衡（3.3 节的传票）：任意两点间的概率流量两两对消，于是 π 是链的平稳分布。再由遍历定理，链跑长之后样本均值收敛到目标分布下的期望——采样合法。

工程要点两条。其一，烧入期与混合：链从任意点出发，需要丢弃开头一段（烧入）才进入平稳区；若目标分布是狭长的多峰山谷，提议步长不合适会让链在一个峰里困死（3.3 节"接近围墙"的病）。诊断手段是看轨迹图与自相关时间——有效样本量 = 名义样本量除以自相关长度，报样本量不报有效样本量是 MCMC 论文的常见病。其二，现代变体：哈密顿蒙特卡洛用梯度信息把提议变成"滑行"，高维空间的混合速度提升一个量级；朗之万动力学（5.4 节那台机器的算法转世）则是它的轻量版——物理与算法在igradient 这里会师。

PageRank 在巨型图上的实现账本

第 3 章讲过 PageRank 的思想（随机游走平稳分布即重要性），这里补工程的账本。全网级图的转移矩阵根本存不下（万亿条边），幂迭代的正确姿势是矩阵-free 的稀疏加和：每轮只遍历边表，把每个页面的当前分值沿出链分发，再全局加一次阻尼项（均匀跳转的底仓）。一轮成本正比于边数，几十轮收敛（阻尼因子 0.85 保证次大特征值不超过 0.85，收敛按几何速度）。

两个实现坑值得点名。悬挂节点（无出链的页面）会让分值泄漏，必须按 3.3 节的办法视作指向全图——漏掉这个补丁，总质量不守恒，排名整体漂移。数值稳定的收敛判据：用分值向量的 L1 变化量阈值而非固定轮数，避免"看似跑完实则未稳"。顺带一提，同样的"平稳分布当排序"思路在推荐系统（随机游走重启 RWR 找相似用户）、图神经网络的传播层、知识图谱的重要性度量里反复出现——学会一次，认得一片。

随机梯度下降：噪声是燃料不是故障

训练神经网络的标配算法随机梯度下降（SGD），每步只用一小批数据估梯度。从随机过程视角看，SGD 的迭代点是一条马尔可夫链：当前参数决定下一步的分布（由随机小批的梯度噪声驱动）。这条链有趣的地方在于它的非平稳性被故意设计：学习率衰减到零时，噪声方差同步收缩，链最终"冻结"在极小点附近——若学习率保持常数，参数会围绕极小点做有热温度的布朗式游走，永不落定。这个"热温度"被证明与学习率、批大小、梯度噪声尺度成正比，由此诞生了一条实用的调参铁律：学习率与批大小按比例联动放大（线性缩放规则），大批次训练不掉点的秘诀全在这条标度律里——4.2 节的 dt 与 dW 换算在训练曲线上的投影。

更妙的是，适度噪声还有正作用：它帮优化器跳出浅的坏极小点（退火式逃逸，与物理里的热激活同构）。噪声不是数值故障，是被驯化的搜索动力——这句判断是本节三案例的共同哲学：MCMC 驯化随机性去探索分布，PageRank 驯化随机性去排序网络，SGD 驯化随机性去搜索解空间。

动手：手搓一个 Metropolis 采样器

import numpy as np

rng = np.random.default_rng(2718)

# 目标：一个双峰混合正态的后验（一维示意，方法与维度无关）
def log_pi(x):
    return np.logaddexp(-0.5*(x + 2.0)**2, -0.5*(x - 2.0)**2) - np.log(2.0)

n_total, burn = 120_000, 20_000
x, step = 0.0, 1.5            # 初始点与提议步长
samples = np.empty(n_total)
accept = 0

for k in range(n_total):
    prop = x + step * rng.normal()
    # Metropolis 准则：log 空间比较，数值更稳
    if np.log(rng.random()) < log_pi(prop) - log_pi(x):
        x = prop
        accept += 1
    samples[k] = x

chain = samples[burn:]
print(f"接受率 {accept/n_total:.2f}（经验目标 0.2 至 0.5）")
print(f"样本均值 {chain.mean():.3f}（对称双峰的理论均值 0）")
print(f"样本方差 {chain.var():.3f}（理论约 5）")

# 自相关长度与有效样本量
x_centered = chain - chain.mean()
acf = np.correlate(x_centered, x_centered, mode="full")[len(chain)-1:]
acf /= acf[0]
tau = 1 + 2*acf[1:200].sum()          # 自相关时间
print(f"自相关时间约 {tau:.1f}，有效样本量约 {len(chain)/tau:,.0f}")
# 把 step 改成 0.1 再跑：接受率冲到 0.9 以上，但 tau 暴涨——
# "步步接受却原地蹭"是 MCMC 调参最经典的病，有效样本量才是硬通货
​

解读与变式：提议步长是 MCMC 的"油门"——太小则链寸步难行（接受率高、混合极慢），太大则提议频频被拒。经验目标接受率两到五成。变式：把目标换成两个相距十倍的峰，小步长链会困在单峰（样本均值偏离零，方差腰斩）——多峰困死的典型现场，此时该上更大的步长、并行多链、或换哈密顿蒙特卡洛。

本节要点回顾

• MCMC = 反向使用链论：造一条平稳分布等于目标分布的链，靠详细平衡与遍历定理背书。
• 报数先报有效样本量：名义样本量除以自相关时间；烧入期必须丢弃。
• PageRank 的工程账本：矩阵-free 幂迭代加悬挂节点补丁；同一思路统治推荐与图学习。
• SGD 是被设计的马尔可夫链：学习率-批大小联动即噪声标度律；适度噪声帮逃逸坏极小。
• 共同哲学：确定性付不起的地方，把随机性驯化成算法部件。

四大现场全部验收完毕。下一章收尾：前沿地图与工具箱——把本册学到的机器装进你自己的工作流。