Алгоритм Ланжевена с поправкой на мегаполис - Metropolis-adjusted Langevin algorithm

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

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

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

Более подробная информация

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

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

управляется производной по времени от стандарта Броуновское движение ${\displaystyle W}$. (Обратите внимание, что еще одна часто используемая нормализация для этого распространения -

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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\},}$

куда

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

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

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

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

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

В практических приложениях оптимальная скорость приема для этого алгоритма ${\displaystyle 0.574}$; если обнаружится, что он существенно отличается, ${\displaystyle \tau }$ следует соответствующим образом изменить.^[3]

Рекомендации

1. Ж. Бесаг (1994). «Комментарии к« Представлениям знаний в сложных системах »У. Гренандера и М.И. Миллера». Журнал Королевского статистического общества, серия B. 56: 591–592.
2. Дж. О. Робертс и Р. Л. Твиди (1996). «Экспоненциальная сходимость распределений Ланжевена и их дискретные приближения». Бернулли. 2 (4): 341–363. Дои:10.2307/3318418. JSTOR  3318418.
3. Дж. О. Робертс и Дж. С. Розенталь (1998). «Оптимальное масштабирование дискретных приближений к диффузии Ланжевена». Журнал Королевского статистического общества, серия B. 60 (1): 255–268. Дои:10.1111/1467-9868.00123.
4. М. Джиролами и Б. Колдерхед (2011). "Римановы многообразия Ланжевена и гамильтоновы методы Монте-Карло". Журнал Королевского статистического общества, серия B. 73 (2): 123–214. CiteSeerX  10.1.1.190.580. Дои:10.1111 / j.1467-9868.2010.00765.x.