有人可以用英语向我解释 NUTS 吗?

机器算法验证 贝叶斯 蒙特卡洛 马尔科夫过程
2022-01-28 16:51:20

我对算法的理解如下:

No U-Turn Sampler (NUTS) 是一种哈密顿蒙特卡罗方法。这意味着它不是马尔可夫链方法,因此,该算法避免了随机游走部分,这通常被认为是低效且收敛缓慢的部分。

NUTS 不进行随机游走,而是进行长度为 x 的跳跃。随着算法继续运行,每次跳跃都会翻倍。这种情况一直发生,直到轨迹到达它想要返回起点的点。

我的问题:掉头有什么特别之处?加倍轨迹如何不跳过优化点?我上面的描述正确吗?

2个回答

不掉头是如何生成提案的。HMC 生成一个假设的物理系统:想象一个具有一定动能的球在您要从中采样的后部定义的山谷和丘陵(类比分解为超过 2 个维度)的景观中滚动。每次您想要获取新的 MCMC 样本时,您都会随机选择动能并从您所在的位置开始滚动球。您以离散时间步长进行模拟,并确保您正确探索参数空间,您在一个方向上模拟步骤,在另一个方向上模拟两倍,再次转身等。在某些时候您想要停止这种情况,这是一个好方法这样做是当你做了一个掉头(即似乎已经走遍了整个地方)。

此时,从您访问过的点中挑选出建议的马尔可夫链的下一步(有一定的限制)。即,假设物理系统的整个模拟“只是”为了获得一个提案,然后该提案被接受(下一个 MCMC 样本是建议点)或被拒绝(下一个 MCMC 样本是起点)。

关于它的聪明之处在于,提案是根据后验的形状提出的,并且可以位于分布的另一端。相比之下,Metropolis-Hastings 在一个(可能是倾斜的)球内提出建议,Gibbs 抽样一次只沿一个(或至少很少)维度移动。

您认为 HMC 不是马尔可夫链方法是不正确的。根据维基百科

在数学和物理学中,混合蒙特卡罗算法,也称为哈密顿蒙特卡罗,是一种马尔可夫链蒙特卡罗方法,用于从难以直接采样的概率分布中获取随机样本序列。该序列可用于近似分布(即,生成直方图),或计算积分(例如期望值)。

为了更清楚,请阅读Betancourt 的 arXiv 论文,其中提到了 NUTS 终止标准:

...确定何时轨迹足够长,可以对当前能量水平集周围的邻域进行充分的探索。特别是,我们希望避免积分太短,在这种情况下我们不会充分利用哈密顿轨迹,以及积分太长,在这种情况下,我们将宝贵的计算资源浪费在只会产生递减收益的探索上。

附录 A.3 讨论了您提到的轨迹加倍之类的内容:

我们还可以通过在每次迭代中将轨迹的长度加倍来更快地扩展,从而产生一个采样轨迹 t∼T(t|z)=U T2L 和相应的采样状态 z′∼T(z′|t)。在这种情况下,每次迭代的新旧轨迹分量都等效于完美有序二叉树的叶子(图 37)。这使我们能够递归地构建新的轨迹组件,在递归的每一步传播一个样本......

并在 A.4 中对此进行了扩展,其中讨论了动态实现(A.3 节讨论了静态实现):

幸运的是,一旦我们选择了一个标准来确定轨迹何时长到足以令人满意地探索相应的能级集,就可以迭代第 A.3 节中讨论的有效静态方案以实现动态实现。

我认为关键是它不会进行双倍的跳跃,它使用一种技术来计算下一次跳跃,该技术将建议的跳跃长度加倍,直到满足标准。至少到目前为止我是这样理解这篇论文的。