Гамильтониан Монте-Карло

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

Гамильтониан Монте-Карло соответствует экземпляру алгоритма Метрополиса-Гастингса , в котором эволюция гамильтоновой динамики моделируется с использованием обратимого во времени и сохраняющего объем числового интегратора (обычно интегратора чехарды ), чтобы предложить переход к новой точке в пространстве состояний. По сравнению с использованием гауссовского распределения предложений случайного блуждания в алгоритме Метрополиса – Гастингса, гамильтониан Монте-Карло уменьшает корреляцию между последовательными выборочными состояниями, предлагая переходы к удаленным состояниям, которые поддерживают высокую вероятность принятия из-за приблизительных энергосберегающих свойств моделируемого гамильтониана. динамический при использовании симплектического интегратора . Уменьшенная корреляция означает, что требуется меньше выборок цепи Маркова для аппроксимации интегралов относительно целевого распределения вероятностей для заданной ошибки Монте-Карло .

Первоначально алгоритм был предложен Саймоном Дуэйном, Энтони Кеннеди, Брайаном Пендлтоном и Дунканом Роуэтом в 1987 году для расчетов в решеточной квантовой хромодинамике . ^[1] В 1996 году Рэдфорд М. Нил показал, как этот метод можно использовать для более широкого класса статистических задач, в частности для искусственных нейронных сетей . ^[2] Однако бремя необходимости обеспечения градиентов байесовской сети задержало более широкое внедрение алгоритма в статистике и других количественных дисциплинах, пока в середине 2010-х годов разработчики Стэна не реализовали HMC в сочетании с автоматическим дифференцированием . ^[3]

Алгоритм

Предположим, что целевое распределение для выборки равно $f(\mathbf {x} )$ для $\mathbf {x} \in \mathbb {R} ^{d}$ ( $d\geq 1$ ) и цепочка образцов $\mathbf {X} _{0},\mathbf {X} _{1},\mathbf {X} _{2},\ldots$ требуется.

Гамильтона Уравнения :

{\frac {{\text{d}}x_{i}}{{\text{d}}t}}={\frac {\partial H}{\partial p_{i}}}\quad {\text{and}}\quad {\dfrac {{\text{d}}p_{i}}{{\text{d}}t}}=-{\dfrac {\partial H}{\partial x_{i}}}

где $x_{i}$ и $p_{i}$ являются $i$ -я компонента вектора положения и импульса соответственно и $H$ является гамильтонианом. Позволять $M$ если массовая матрица симметрична и положительно определена, то гамильтониан равен

H(\mathbf {x} ,\mathbf {p} )=U(\mathbf {x} )+{\dfrac {1}{2}}\mathbf {p} ^{\text{T}}M^{-1}\mathbf {p}

где $U(\mathbf {x} )$ это потенциальная энергия . Потенциальная энергия цели определяется как

U(\mathbf {x} )=-\ln f(\mathbf {x} )

что происходит от фактора Больцмана . Заметим, что гамильтониан $H$ в этой формулировке безразмерен, поскольку экспоненциальный вес вероятности $\exp \left(-H\right)$ должен быть четко определен. Например, в моделировании при конечной температуре $T$ фактор $k_{\text{B}}T$ (с постоянной Больцмана $k_{\text{B}}$ ) непосредственно поглощается $U$ и $M$ .

Алгоритму требуется положительное целое число для количества шагов чехарды. $L$ и положительное число для размера шага $\Delta t$ . Предположим, что цепь находится в $\mathbf {X} _{n}=\mathbf {x} _{n}$ . Позволять $\mathbf {x} _{n}(0)=\mathbf {x} _{n}$ . Во-первых, случайный гауссов импульс $\mathbf {p} _{n}(0)$ взято из ${\text{N}}\left(\mathbf {0} ,M\right)$ . Далее частица будет двигаться в условиях гамильтоновой динамики за время $L\Delta t$ , это делается путем численного решения уравнений Гамильтона с использованием алгоритма чехарды . Векторы положения и импульса по времени $\Delta t$ с использованием алгоритма чехарды: ^[4]

\mathbf {p} _{n}\left(t+{\dfrac {\Delta t}{2}}\right)=\mathbf {p} _{n}(t)-{\dfrac {\Delta t}{2}}\nabla \left.U(\mathbf {x} )\right|_{\mathbf {x} =\mathbf {x} _{n}(t)}

\mathbf {x} _{n}(t+\Delta t)=\mathbf {x} _{n}(t)+\Delta t\mathbf {p} _{n}\left(t+{\dfrac {\Delta t}{2}}\right)

\mathbf {p} _{n}(t+\Delta t)=\mathbf {p} _{n}\left(t+{\dfrac {\Delta t}{2}}\right)-{\dfrac {\Delta t}{2}}\nabla \left.U(\mathbf {x} )\right|_{\mathbf {x} =\mathbf {x} _{n}(t+\Delta t)}

Эти уравнения следует применять к $\mathbf {x} _{n}(0)$ и $\mathbf {p} _{n}(0)$ $L$ раз, чтобы получить $\mathbf {x} _{n}(L\Delta t)$ и $\mathbf {p} _{n}(L\Delta t)$ .

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

Один из способов продвинуть систему к термодинамически равновесному распределению — изменить состояние частиц с помощью алгоритма Метрополиса–Гастингса . Итак, сначала применяется шаг чехарды, затем шаг Метрополиса-Гастингса.

Переход от $\mathbf {X} _{n}=\mathbf {x} _{n}$ к $\mathbf {X} _{n+1}$ является

\mathbf {X} _{n+1}|\mathbf {X} _{n}=\mathbf {x} _{n}={\begin{cases}\mathbf {x} _{n}(L\Delta t)&{\text{with probability }}\alpha \left(\mathbf {x} _{n}(0),\mathbf {x} _{n}(L\Delta t)\right)\\\mathbf {x} _{n}(0)&{\text{otherwise}}\end{cases}}

где

\alpha \left(\mathbf {x} _{n}(0),\mathbf {x} _{n}(L\Delta t)\right)={\text{min}}\left(1,{\dfrac {\exp \left[-H(\mathbf {x} _{n}(L\Delta t),\mathbf {p} _{n}(L\Delta t))\right]}{\exp \left[-H(\mathbf {x} _{n}(0),\mathbf {p} _{n}(0))\right]}}\right).

Полное обновление состоит из первой случайной выборки импульсов. $\mathbf {p}$ (независимо от предыдущих итераций), затем интегрирование уравнений движения (например, с помощью чехарды) и, наконец, получение новой конфигурации на этапе принятия/отклонения Метрополиса-Гастингса. Этот механизм обновления повторяется для получения $\mathbf {X} _{n+1},\mathbf {X} _{n+2},\mathbf {X} _{n+3},\ldots$ .

Нет разворотного пробоотборника

Пробоотборник без разворота (NUTS) ^[5] является расширением путем управления $L$ автоматически. Тюнинг $L$ является критическим. Например, в одномерном ${\text{N}}(0,1/{\sqrt {k}})$ случае, потенциал $U(x)=kx^{2}/2$ что соответствует потенциалу простого гармонического осциллятора . Для $L$ слишком большой, частица будет колебаться и, таким образом, тратить время вычислений. Для $L$ слишком мала, частица будет вести себя как случайное блуждание.

Проще говоря, NUTS случайным образом запускает гамильтонову динамику как вперед, так и назад во времени, пока не будет выполнено условие разворота. Когда это происходит, для выборки MCMC выбирается случайная точка пути, и процесс повторяется с этой новой точки.

В деталях строится двоичное дерево , позволяющее отслеживать путь шагов чехарды. Для изготовления образца MCMC проводится итерационная процедура. Переменная среза $U_{n}\sim {\text{Uniform}}(0,\exp(-H[\mathbf {x} _{n}(0),\mathbf {p} _{n}(0)]))$ отбирается. Позволять $\mathbf {x} _{n}^{+}$ и $\mathbf {p} _{n}^{+}$ быть положением и импульсом идущей вперед частицы соответственно. Сходным образом, $\mathbf {x} _{n}^{-}$ и $\mathbf {p} _{n}^{-}$ для обратной частицы. На каждой итерации двоичное дерево случайным образом равномерно выбирает, чтобы переместить переднюю частицу вперед во времени или обратную частицу назад во времени. Также для каждой итерации количество шагов чехарды увеличивается в 2 раза. Например, в первой итерации частица, идущая вперед, перемещается вперед во времени, используя 1 шаг чехарды. На следующей итерации обратная частица движется назад во времени, используя 2 чехарды.

Итерационная процедура продолжается до тех пор, пока не будет выполнено условие разворота, т.е.

(\mathbf {x} _{n}^{+}-\mathbf {x} _{n}^{-})\cdot \mathbf {p} _{n}^{-}<0\quad {\text{or}}\quad .(\mathbf {x} _{n}^{+}-\mathbf {x} _{n}^{-})\cdot \mathbf {p} _{n}^{+}<0

или когда гамильтониан становится неточным

\exp \left[-H(\mathbf {x} _{n}^{+},\mathbf {p} _{n}^{+})+\delta \right]<U_{n}

или

\exp \left[-H(\mathbf {x} _{n}^{-},\mathbf {p} _{n}^{-})+\delta \right]<U_{n}

где, например, $\delta =1000$ .

Как только условие разворота выполнено, следующий образец MCMC, $\mathbf {x} _{n+1}$ , получается путем равномерной выборки пути чехарды, прослеженного двоичным деревом $\{\mathbf {x} _{n}^{-},\ldots ,\mathbf {x} _{n}(-\Delta t),\mathbf {x} _{n}(0),\mathbf {x} _{n}(\Delta t),\ldots ,\mathbf {x} _{n}^{+}\}$ который удовлетворяет

U_{n}<\exp \left[-H(\mathbf {x_{n+1}} ,\mathbf {p_{n+1})} \right]

Обычно это удовлетворяется, если остальные параметры HMC разумны.

См. также

Динамический метод Монте-Карло
Программное обеспечение для молекулярного моделирования Монте-Карло
Stan — вероятностный язык программирования, реализующий HMC.
PyMC — язык вероятностного программирования, реализующий HMC.
Алгоритм Ланжевена, адаптированный к Метрополису

Ссылки

^ Дуэйн, Саймон; Кеннеди, Энтони Д.; Пендлтон, Брайан Дж.; Роуэт, Дункан (1987). «Гибрид Монте-Карло». Буквы по физике Б. 195 (2): 216–222. Бибкод : 1987PhLB..195..216D . дои : 10.1016/0370-2693(87)91197-X .
^ Нил, Рэдфорд М. (1996). «Реализация Монте-Карло». Байесовское обучение для нейронных сетей . Конспект лекций по статистике. Том. 118. Спрингер. стр. 55–98. дои : 10.1007/978-1-4612-0745-0_3 . ISBN 0-387-94724-8 .
^ Гельман, Эндрю; Ли, Дэниел; Го, Цзицян (2015). «Стэн: вероятностный язык программирования для байесовского вывода и оптимизации». Журнал образовательной и поведенческой статистики . 40 (5): 530–543. дои : 10.3102/1076998615606113 . S2CID 18351694 .
^ Бетанкур, Майкл (15 июля 2018 г.). «Концептуальное введение в гамильтониан Монте-Карло». arXiv : 1701.02434 [ stat.ME ].
^ Хоффман, Мэтью Д.; Гельман, Эндрю (2014). «Пробоотборник без разворота: адаптивная настройка длины пути в гамильтоновом методе Монте-Карло» . Журнал исследований машинного обучения . 15 (1): 1593–1623 . Проверено 28 марта 2024 г.

Дальнейшее чтение

Бетанкур, Майкл; Джиролами, Марк (2015). «Гамильтониан Монте-Карло для иерархических моделей». В Упадхьяе — Сатьяншу Кумар; и др. (ред.). Современные тенденции в области применения байесовской методологии . ЦРК Пресс. стр. 79–101. ISBN 978-1-4822-3511-1 .
Бетанкур, Майкл (2018). «Концептуальное введение в гамильтониан Монте-Карло». arXiv : 1701.02434 [ stat.ME ].
Барбу, Адриан; Чжу, Сон-Чун (2020). «Гамильтониан и Ланжевен Монте-Карло». Методы Монте-Карло . Сингапур: Спрингер. стр. 281–326. ISBN 978-981-13-2970-8 .
Нил, Рэдфорд М. (2011). «MCMC с использованием гамильтоновой динамики» (PDF) . У Стива Брукса; Эндрю Гельман; Галин Л. Джонс; Сяо-Ли Мэн (ред.). Справочник цепей Маркова Монте-Карло . Чепмен и Холл/CRC. ISBN 9781420079418 .

Внешние ссылки

Бетанкур, Майкл. «Эффективный байесовский вывод с гамильтоновым методом Монте-Карло» . MLSS Исландия 2014 — через YouTube .
МакЭлрит, Ричард. «Марковская цепь Монте-Карло» . Статистическое переосмысление 2022 — через YouTube .
Гамильтониан Монте-Карло с нуля
Оптимизация и методы Монте-Карло

[1] Дуэйн, Саймон; Кеннеди, Энтони Д.; Пендлтон, Брайан Дж.; Роуэт, Дункан (1987). «Гибрид Монте-Карло». Буквы по физике Б. 195 (2): 216–222. Бибкод : 1987PhLB..195..216D . дои : 10.1016/0370-2693(87)91197-X .

[2] Нил, Рэдфорд М. (1996). «Реализация Монте-Карло». Байесовское обучение для нейронных сетей . Конспект лекций по статистике. Том. 118. Спрингер. стр. 55–98. дои : 10.1007/978-1-4612-0745-0_3 . ISBN 0-387-94724-8 .

[3] Гельман, Эндрю; Ли, Дэниел; Го, Цзицян (2015). «Стэн: вероятностный язык программирования для байесовского вывода и оптимизации». Журнал образовательной и поведенческой статистики . 40 (5): 530–543. дои : 10.3102/1076998615606113 . S2CID 18351694 .

[4] Бетанкур, Майкл (15 июля 2018 г.). «Концептуальное введение в гамильтониан Монте-Карло». arXiv : 1701.02434 [ stat.ME ].

[5] Хоффман, Мэтью Д.; Гельман, Эндрю (2014). «Пробоотборник без разворота: адаптивная настройка длины пути в гамильтоновом методе Монте-Карло» . Журнал исследований машинного обучения . 15 (1): 1593–1623 . Проверено 28 марта 2024 г.

[1]

[2]

[3]

[4]

[5]