Может ли кто-нибудь объяснить мне орехи на английском языке?

Мое понимание алгоритма следующее:

Пробоотборник без разворота (NUTS) - это метод Гамильтона Монте-Карло. Это означает, что это не метод цепей Маркова, и, таким образом, этот алгоритм избегает части случайного блуждания, которая часто считается неэффективной и медленно сходится.

Вместо случайного блуждания NUTS делает прыжки длиной x. Каждый прыжок удваивается, поскольку алгоритм продолжает выполняться. Это происходит до тех пор, пока траектория не достигнет точки, в которой она хочет вернуться к начальной точке.

Мои вопросы: что такого особенного в развороте? Как удвоение траектории не пропускает оптимизированную точку? Правильно ли мое приведенное выше описание?

Бит без разворота - это то, как создаются предложения. HMC генерирует гипотетическую физическую систему: представьте шар с определенной кинетической энергией, катящийся по ландшафту с долинами и холмами (аналогия разбивается на более чем 2 измерения), заданную апостериором, из которого вы хотите произвести выборку. Каждый раз, когда вы хотите взять новый образец MCMC, вы случайным образом выбираете кинетическую энергию и начинаете катиться оттуда, где вы находитесь. Вы симулируете с дискретными временными шагами, и чтобы убедиться, что вы правильно исследуете пространство параметров, вы симулируете шаги в одном направлении и вдвое больше в другом направлении, снова поворачиваетесь и т. Д. В какой-то момент вы хотите остановить это и хороший способ делать это, когда вы сделали разворот (то есть, кажется, повсюду).

В этот момент предлагаемый следующий шаг вашей цепи Маркова выбирается (с некоторыми ограничениями) из посещенных вами пунктов. То есть, что вся симуляция гипотетической физической системы была «просто», чтобы получить предложение, которое затем принимается (следующий образец MCMC является предложенным пунктом) или отклоняется (следующий образец MCMC является отправной точкой).

Самое умное в том, что предложения делаются на основе формы апостериора и могут быть на другом конце распределения. В отличие от Metropolis-Hastings, делающего предложения в пределах (возможно, искаженного) шара, выборка Гиббса перемещается только по одному (или, по крайней мере, очень немногим) измерениям за один раз.

Вы ошибаетесь, что HMC не является методом цепочки Маркова. В Википедии :

В математике и физике гибридный алгоритм Монте-Карло, также известный как гамильтониан Монте-Карло, представляет собой цепной метод Монте-Карло Маркова для получения последовательности случайных выборок из распределения вероятностей, для которого прямая выборка затруднена. Эта последовательность может использоваться для аппроксимации распределения (т. Е. Для генерации гистограммы) или для вычисления интеграла (например, ожидаемого значения).

Для большей ясности прочтите статью arXiv от Betancourt , в которой упоминаются критерии завершения NUTS:

... определить, когда траектория является достаточно длинной, чтобы обеспечить достаточное исследование окрестности вокруг текущего установленного уровня энергии. В частности, мы хотим избежать как слишком короткой интеграции, и в этом случае мы не будем в полной мере использовать гамильтоновы траектории, так и слишком долгой интеграции, и в этом случае мы тратим драгоценные вычислительные ресурсы на разведку, которая дает только убывающую отдачу.

Приложение A.3 говорит о чем-то вроде траектории удвоения, которую вы упоминаете:

Мы также можем расширяться быстрее, удваивая длину траектории на каждой итерации, получая выборочную траекторию t ∼ T (t | z) = U T2L с соответствующим дискретным состоянием z ′ ∼ T (z ′ | t). В этом случае как старые, так и новые компоненты траектории на каждой итерации эквивалентны листьям совершенных, упорядоченных бинарных деревьев (рис. 37). Это позволяет нам рекурсивно строить новые компоненты траектории, распространяя выборку на каждом этапе рекурсии ...

и расширяет это в A.4, где говорится о динамической реализации (раздел A.3 говорит о статической реализации):

К счастью, эффективные статические схемы, обсуждаемые в разделе A.3, могут быть повторены для достижения динамической реализации, как только мы выбрали критерий для определения, когда траектория выросла достаточно долго, чтобы удовлетворительно исследовать соответствующий набор уровней энергии.

Я думаю, что ключ в том, что он не делает двойные прыжки, он рассчитывает свой следующий прыжок, используя технику, которая удваивает длину предлагаемого прыжка до тех пор, пока критерий не будет удовлетворен. По крайней мере, так я понимаю статью до сих пор.