Метод Леймкюлера-Мэттьюза

В математике метод Леймкулера-Мэттьюза (или метод LM в оригинальной статье ) — алгоритм поиска дискретных решений броуновской динамики

$\mathrm {d} X=-\nabla V(X)\,\mathrm {d} t+\sigma \,\mathrm {d} W,$

где $\sigma >0$ является константой, $V(X)$ является энергетической функцией и $W(t)$ является винеровским процессом . Это стохастическое дифференциальное уравнение имеет решения (обозначенные $X(t)\in \mathbb {R} ^{N}$ во время $t$) распределяется согласно $\pi (X)\propto \exp(-V(x))$ в пределе большого времени, что делает решение этой динамики актуальным в приложениях, ориентированных на выборку, таких как классическая молекулярная динамика и машинное обучение .

Учитывая шаг по времени $\Delta t>0$схема обновления Леймкулера-Мэттьюза компактно записывается как

$X_{t+\Delta t}=X_{t}-\nabla V(X_{t})\Delta t+\sigma {\frac {\sqrt {\Delta t}}{2}}\,(R_{t}+R_{t+\Delta t}),$

с начальным состоянием $X_{0}:=X(0)$, и где $X_{t}\approx X(t)$. Вектор $R_{t}$ представляет собой вектор независимых нормальных случайных чисел , перерисовываемый на каждом шаге так, чтобы ${\text{E}}[R_{t}\cdot R_{s}]=N\delta _{ts}$ (где ${\text{E}}[\bullet ]$ обозначает ожидание ). Несмотря на то, что стоимость равна схеме Эйлера-Маруямы (с точки зрения количества оценок функции $\nabla V(X)$ за обновление), учитывая некоторые предположения о $\Delta t,\,V(X)$ и $f(X)$ были показаны решения иметь свойство сверхконвергенции

${\text{E}}[|f(X_{t})-f(X(t))|]\leq C_{1}e^{-\lambda t}\Delta t+C_{2}\Delta t^{2}$

для констант $C_{k}\geq 0,\,\lambda >0$ не в зависимости от $t$. Это означает, что как $t$ становится большим, мы получаем эффективный второй порядок с $\Delta t^{2}$ ошибка в вычисленных ожиданиях. Для малого шага по времени $\Delta t$ это может дать значительные улучшения по сравнению со схемой Эйлера-Маруямы без дополнительных затрат.

Обсуждение

Распределение решений во времени $t$ для метода Эйлера-Маруямы и метода Леймкулера-Мэттьюза с использованием дискретизации $\Delta t=0.5$ и инициализация из нормального распределения. Целевое распределение (черным цветом) представляет собой сумму двух гауссовских распределений с центром в $-2$ и $+2$. В то время как схема Эйлера-Маруямы приводит к видимой ошибке дискретизации в выборочном распределении, схема Леймкулера-Мэттьюза работает значительно лучше без дополнительных затрат.

Сравнение с другими схемами

Очевидным методом сравнения является схема Эйлера-Маруямы , поскольку она имеет ту же стоимость и требует одной оценки $\nabla V(X)$ за шаг. Его обновление имеет вид

${\hat {X}}_{t+\Delta t}={\hat {X}}_{t}-\nabla V({\hat {X}}_{t})\Delta t+\sigma {\sqrt {\Delta t}}\,R_{t},$

с ошибкой (при некоторых допущениях ) как ${\text{E}}[|f({\hat {X}}_{t})-f(X(t))|]\leq C\Delta t$ с постоянным $C>0$ независимо от $t$. По сравнению с приведенным выше определением, единственное различие между схемами заключается в одношаговом усреднении шума, что упрощает реализацию.

При достаточно малом шаге по времени $\Delta t$ и достаточно большое время $t$ видно, что схема LM дает меньшую ошибку, чем схема Эйлера-Маруямы. Хотя существует множество алгоритмов, которые могут дать меньшую ошибку по сравнению со схемой Эйлера (см., например, метод Мильштейна , Рунге-Кутты или Хойна ), они почти всегда приводят к снижению эффективности, требуя большего количества вычислений в обмен на уменьшение ошибки. Однако схема Леймкулера-Мэттьюза может дать значительно меньшую ошибку при минимальном изменении стандартной схемы Эйлера. Компромисс возникает из-за (относительно) ограниченного объема стохастического дифференциального уравнения, которое оно решает: $\sigma$ должна быть скалярной константой, а функция дрейфа должна иметь вид $\nabla V(X)$. Схема LM также не является марковской , поскольку для обновлений требуется нечто большее, чем просто состояние в данный момент. $t$. Однако мы можем преобразовать эту схему в марковский процесс, расширив пространство.

Марковская форма

Мы можем переписать алгоритм в марковской форме, расширив пространство состояний вектором импульса. $P_{t}\in \mathbb {R} ^{N}$ так что общее состояние $(X_{t},P_{t})$ во время $t$. Инициализация импульса как вектора $N$ стандартные нормальные случайные числа, у нас есть

$X'_{t+\Delta t}=X_{t}-\nabla V(X_{t})\Delta t+\sigma {\frac {\sqrt {\Delta t}}{2}}\,P_{t},$

$P_{t+\Delta t}\sim {\text{Normal}}(0,I),$

$X_{t+\Delta t}=X'_{t+\Delta t}+\sigma {\frac {\sqrt {\Delta t}}{2}}\,P_{t+\Delta t},$

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

Приложения

Алгоритм имеет применение в любой области, где слабые (т.е. средние) свойства решений броуновской динамики требуются . Это применимо к любой задаче молекулярного моделирования (например, к классической молекулярной динамике ), но также может применяться к задачам статистической выборки из-за свойств решений на больших временах. В пределе $t\to \infty$, решения будут распределены в соответствии с распределением вероятностей $\pi (X)\propto \exp(-V(X))$. Таким образом, мы можем генерировать независимые выборки в соответствии с требуемым распределением, используя $V(X)=-\log(\pi (X))$ и запускаем алгоритм LM до тех пор, пока он не станет большим $t$. Такие стратегии могут быть эффективны, например, в задачах байесовского вывода .

См. также

• Метод Эйлера-Маруямы
• метод Мильштейна
• Метод Рунге-Кутты (СДУ)
• метод Хойна