No-U-Turn Sampler | Codeboy's Blog

形式陈述

NUTS 是Hamiltonian Monte Carlo的严格变体：位置 $q$ 是待采样参数，目标密度写成 $\pi(q)\propto e^{-U(q)}$ ； $U$ 是负对数密度， $M$ 是正定质量矩阵。每轮先重抽辅助动量 $p\sim N(0,M)$ ，以 $H(q,p)=U(q)+\tfrac12p^{\mathsf T}M^{-1}p$ 定义总能量，再用leapfrog 积分器生成近似保持该能量的轨迹。它替代固定步数 $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.

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

这里讨论显式候选集合 $C$ 的原始 slice 版本：若最后一次倍增中新建子树在内部触发停止条件，就丢弃本次倍增新增的全部候选；若新子树完整建成，只在与旧树合并后的整体两端检测到 U-turn，则可先把这个完整子树的合格状态加入 $C$ ，再停止扩展。最终从 $C$ 均匀选一点；递归时按合格状态数加权的 reservoir 选择与此等价。这是 Algorithm 2 的候选集合规则，不把它与 Algorithm 3 外层采用 $\min\{1,n_{\mathrm{new}}/n_{\mathrm{old}}\}$ 的有偏转移或现代 multinomial 权重规则混用。

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

直觉

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

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

No-U-Turn Sampler：倍增轨迹树与端点回头判据 — NUTS 的轨迹树倍增与 U-turn 停止

例子与边界

对一维标准正态，取 $M=1$ 、 $q_0=0,p_0=1$ 、 $\epsilon=0.5$ 。此时 $U(q)=q^2/2$ ，连续动力学沿圆周运动。数值上，每步先做 $p_{1/2}=p-0.25q$ ，再做 $q_{\mathrm{new}}=q+0.5p_{1/2}$ ，最后做 $p_{\mathrm{new}}=p_{1/2}-0.25q_{\mathrm{new}}$ 。第一步因此给出 $p_{1/2}=1$ 、 $q_1=0.5$ 、 $p_1=0.875$ 。顺向重复的前四个端点依次为

(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$ 是最大深度。若递归构树时每层只保留两端状态、汇总计数或权重及一个抽样候选，可把工作状态控制为 $O((J+1)d)$ 个分量；把全部轨迹点都存下则可能需要 $O(2^Jd)$ ，质量矩阵与模型评值工作区均另计。比较算法时应按梯度评值或墙钟时间，而不是只按迭代数。若模型低维、尺度已知且固定轨迹长度经过结构分析，普通 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，§3.1 的候选集合条件 C.1–C.4 与 Algorithms 2–3。
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.

形式陈述 ​

反向链接

形式陈述