No-U-Turn Sampler | Codeboy's Blog

形式陈述

NUTS 是Hamiltonian Monte Carlo的严格变体：目标仍为 $\pi(q)\propto e^{-U(q)}$ ，辅助动量仍来自 $N(0,M)$ ，轨迹仍由leapfrog 积分器生成并受联合能量 $H(q,p)$ 约束。它替代固定步数 $L$ 的部分，是在每次迭代内自动构造有限轨迹集合并从中选候选。

原始 slice 版本从当前状态 $z_0=(q_0,p_0)$ 抽取

u\sim\operatorname{Uniform}(0,e^{-H(z_0)}),

只把满足 $e^{-H(z)}\ge u$ 的数值轨迹状态列为有效候选。算法随机选择向前或向后的时间方向，以 $1,2,4,\ldots$ 步递归倍增二叉树；每次合并子树时，按各子树有效状态数成比例更新候选，使最终选择不是偏向端点或较晚生成状态。现代 multinomial 版本改按近似联合密度加权候选，但同样必须保持整棵构造对称。

在欧氏质量矩阵下，记树两端为 $(q^-,p^-)$ 与 $(q^+,p^+)$ 。基本回头判据是

(q^+-q^-)^{\mathsf T}M^{-1}p^-<0 \quad\text{或}\quad (q^+-q^-)^{\mathsf T}M^{-1}p^+<0.

它表示至少一个端点的速度已经指回另一端。实际递归还要对各子树检查判据；只检查最终两个端点可能跨过更早发生的回头。遇到回头、能量误差超过安全阈值或最大树深即停止扩展。最大树深让成本有界；频繁撞上它说明轨迹可能被人为截短，不是收敛证明。

正确性不来自“停在掉头前”。树的随机方向、对称停止与候选选择共同确保从任一候选反看都能构造兼容集合，从而保持扩展目标。任意选择最远端点会破坏这项对称性。步长常在 warmup 用 dual averaging 适配，质量矩阵也可从 warmup 学习；正式采样阶段固定这些参数，才能直接应用平稳核论证。

直觉

固定短轨迹会在平缓方向未走够，固定长轨迹又可能绕过等能面后折返，花梯度计算回到起点附近。NUTS 同时向前后探索并不断加倍，直到位移与端点速度的内积变负，说明继续走大概在重走旧路。

树中候选选择同停止同样重要。轨迹是一串相关的近等能状态；若总拿最后一点，停止规则会让某些位置因更容易触发回头而被系统偏爱。按有效集合对称选点，才把“自动决定走多远”变成合法转移核，而不是启发式优化轨迹。

例子与边界

对一维标准正态，取 $M=1$ 、 $q_0=0,p_0=1$ 、 $\epsilon=0.5$ 。连续动力学沿圆周运动。顺向 leapfrog 的前四个端点依次为

(q_1,p_1)=(0.5,0.875),

(q_2,p_2)=(0.875,0.53125),

(q_3,p_3)=(1.03125,0.0546875),

(q_4,p_4)=(0.9296875,-0.435546875).

到第四步，若左端仍为初始点，位移 $0.9296875$ 与右端速度 $-0.435546875$ 的乘积为负，表示右端已越过最远位置并折回。NUTS 会停止相应树的继续增长，却不会必然选择第四个点；它从满足 slice 与能量条件的树内状态按规定抽取候选。

回头判据不能修复坏几何。在 funnel 颈部，步长过大先产生 divergence，树可能在几何回头之前就失真；把最大树深调高只增加不可靠积分。强弯曲流形上，端点位移的欧氏内积也只是局部度量下的判据，质量矩阵失配会让一个方向过早停止、另一个方向走得过久。

多峰目标是另一边界。单条 Hamilton 轨迹若没有足够动量越过势垒，自动轨迹长度不会创造跨峰路径。表面上树深、接受率和峰内有效样本量都可能正常，模态权重仍然错误。需要分散初值、重参数化或跨温度方法检验，而不是把“无 U-turn 警告”解释为全局探索完成。

推论与应用

NUTS 去掉了固定 $L$ 这一项难调参数，但没有去掉步长、质量矩阵和目标参数化。可靠工作流先在 warmup 学习尺度，再检查 divergence、能量行为与树深饱和，最后对具体后验函数估计相关误差。不同诊断对应不同机制，不能由一个总体接受率汇总。

树倍增使单次迭代梯度数随机且最多按 $2^J$ 增长，其中 $J$ 是最大深度。比较算法时应按梯度评值或墙钟时间，而不是只按迭代数。若模型低维、尺度已知且固定轨迹长度经过结构分析，普通 HMC 可能更可预测；NUTS 的优势是避免普遍的过短或折返轨迹，不是无条件支配固定长度方案。

参考资料

Matthew D. Hoffman and Andrew Gelman, “The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo,” Journal of Machine Learning Research 15(47), 2014, pp. 1593–1623.
Radford M. Neal, “MCMC Using Hamiltonian Dynamics,” in Handbook of Markov Chain Monte Carlo, CRC Press, 2011, Ch. 5.
Michael Betancourt, “A Conceptual Introduction to Hamiltonian Monte Carlo,” arXiv:1701.02434, 2017, §4.4.

形式陈述 ​

反向链接

形式陈述