Алгоритм Ланжевена, адаптированный к Метрополису

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

• новые состояния предлагаются с использованием ( перезатухающей ) динамики Ланжевена , которая использует оценки градиента целевой функции плотности вероятности ;
• эти предложения принимаются или отклоняются с использованием алгоритма Метрополиса-Гастингса , который использует оценки целевой плотности вероятности (но не ее градиента).

Неформально, динамика Ланжевена направляет случайное блуждание к областям с высокой вероятностью наподобие градиентного потока, в то время как механизм принятия/отклонения Метрополиса-Гастингса улучшает свойства смешивания и сходимости этого случайного блуждания. MALA была первоначально предложена Джулианом Бесагом в 1994 году. (хотя метод Смарт Монте-Карло был введен уже в 1978 г.) ) и его свойства были подробно исследованы Гаретом Робертсом совместно с Ричардом Твиди. и Джефф Розенталь . С тех пор было введено множество вариаций и усовершенствований, например, многообразный вариант Джиролами и Колдерхеда (2011). Метод эквивалентен использованию гамильтонового алгоритма Монте-Карло (гибридного Монте-Карло) только с одним дискретным шагом по времени.

Дополнительная информация

Позволять $\pi$ обозначим функцию плотности вероятности на $\mathbb {R} ^{d}$, из которого желательно получить ансамбль независимых и одинаково распределенных выборок. Мы рассматриваем перезатухающую диффузию Ланжевена-Ито.

${\dot {X}}=\nabla \log \pi (X)+{\sqrt {2}}{\dot {W}}$

управляется производной по времени стандартного броуновского движения $W$. (Обратите внимание, что другая часто используемая нормировка для этой диффузии:

${\dot {X}}={\frac {1}{2}}\nabla \log \pi (X)+{\dot {W}},$

что порождает ту же динамику.) В пределе, когда $t\to \infty$, это распределение вероятностей $\rho (t)$ из $X(t)$ приближается к стационарному распределению, также инвариантному относительно диффузии, которое мы обозначим $\rho _{\infty }$. Оказывается, на самом деле $\rho _{\infty }=\pi$.

Приблизительные выборочные траектории диффузии Ланжевена могут быть созданы многими методами дискретного времени. Одним из самых простых является метод Эйлера–Маруямы с фиксированным шагом по времени. $\tau >0$. Мы устанавливаем $X_{0}:=x_{0}$ а затем рекурсивно определить приближение $X_{k}$ к истинному решению $X(k\tau )$ к

$X_{k+1}:=X_{k}+\tau \nabla \log \pi (X_{k})+{\sqrt {2\tau }}\xi _{k},$

где каждый $\xi _{k}$ является независимым выводом из многомерного нормального распределения $\mathbb {R} ^{d}$ со средним значением 0 и ковариационной матрицей, равной $d\times d$ идентификационная матрица . Обратите внимание, что $X_{k+1}$ обычно распределяется со средним значением $X_{k}+\tau \nabla \log \pi (X_{k})$ и ковариация равна $2\tau$ раз $d\times d$ идентификационная матрица.

В отличие от метода Эйлера–Маруямы для моделирования диффузии Ланжевена, который всегда обновляет $X_{k}$ согласно правилу обновления

$X_{k+1}:=X_{k}+\tau \nabla \log \pi (X_{k})+{\sqrt {2\tau }}\xi _{k},$

MALA включает дополнительный шаг. Мы рассматриваем приведенное выше правило обновления как определение предложения. ${\tilde {X}}_{k+1}$ для нового государства,

${\tilde {X}}_{k+1}:=X_{k}+\tau \nabla \log \pi (X_{k})+{\sqrt {2\tau }}\xi _{k}.$

Данное предложение принимается или отклоняется согласно алгоритму Метрополиса-Гастингса:

$\alpha :=\min \left\{1,{\frac {\pi ({\tilde {X}}_{k+1})q(X_{k}\mid {\tilde {X}}_{k+1})}{\pi ({X}_{k})q({\tilde {X}}_{k+1}\mid X_{k})}}\right\},$

где

$q(x'\mid x)\propto \exp \left(-{\frac {1}{4\tau }}\|x'-x-\tau \nabla \log \pi (x)\|_{2}^{2}\right)$

– плотность вероятности перехода из $x$ к $x'$ (обратите внимание, что в целом $q(x'\mid x)\neq q(x\mid x')$). Позволять $u$ быть получено из непрерывного равномерного распределения на интервале $[0,1]$. Если $u\leq \alpha$, то предложение принимается и мы устанавливаем $X_{k+1}:={\tilde {X}}_{k+1}$; в противном случае предложение отклоняется, и мы устанавливаем $X_{k+1}:=X_{k}$.

Комбинированная динамика диффузии Ланжевена и алгоритма Метрополиса – Гастингса удовлетворяют детальным условиям баланса, необходимым для существования уникального инвариантного стационарного распределения. $\rho _{\infty }=\pi$. По сравнению с наивным Метрополисом-Гастингсом, MALA имеет то преимущество, что обычно предлагает перемещение в регионы с более высоким уровнем доходов. $\pi$ вероятности, которые затем с большей вероятностью будут приняты. С другой стороны, когда $\pi$ сильно анизотропен (т.е. меняется в одних направлениях гораздо быстрее, чем в других), необходимо принять $0<\tau \ll 1$ чтобы правильно уловить динамику Ланжевена; использование положительно определенной предварительной обработки матрицы $A\in \mathbb {R} ^{d\times d}$ может помочь облегчить эту проблему, создавая предложения в соответствии с

${\tilde {X}}_{k+1}:=X_{k}+\tau A\nabla \log \pi (X_{k})+{\sqrt {2\tau A}}\xi _{k},$

так что ${\tilde {X}}_{k+1}$ имеет в виду $X_{k}+\tau A\nabla \log \pi (X_{k})$ и ковариация $2\tau A$.

Можно показать, что для ограниченных классов целевых распределений оптимальная скорость принятия этого алгоритма равна $0.574$; если на практике обнаруживается, что они существенно отличаются, $\tau$ должны быть соответствующим образом изменены.