Алгоритм Метрополиса — Гастингса

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

История

Алгоритм берёт начало в 1953 году, когда группа учёных Лос-Аламосской национальной лаборатории (США) — Николас Метрополис, Ариана Розенблут, Маршалл Розенблут, Августа Теллер и Эдвард Теллер — опубликовала статью «Уравнения состояния для жидкостей и твёрдых тел с помощью быстрых вычислительных машин». В ней был предложен метод для расчёта свойств систем многих частиц в равновесной статистической механике. Этот метод, названный впоследствии алгоритмом Метрополиса, использовал симметричную функцию предложения (например, случайное смещение частицы) и условие принятия новой конфигурации на основе отношения вероятностей.

В 1970 году канадский статистик Уилфрид Гастингс обобщил алгоритм в статье «Методы Монте-Карло с использованием цепей Маркова». Он показал, что условие принятия может быть сформулировано для произвольных (не обязательно симметричных) функций предложения, что значительно расширило область применения метода. С тех пор алгоритм Метрополиса — Гастингса стал фундаментальным инструментом в вычислительной статистике и физике.

Принцип работы

Алгоритм Метрополиса — Гастингса строит цепь Маркова, стационарное распределение которой совпадает с целевым распределением \( P(x) \), известным с точностью до нормировочной константы. Это особенно важно, когда целевое распределение сложно или невозможно нормировать аналитически. Алгоритм состоит из следующих шагов:

1. Инициализация: выбирается начальное состояние \( x_0 \) цепи Маркова.
2. Генерация предложения: из текущего состояния \( x_t \) генерируется новое состояние \( x' \) с помощью функции предложения \( Q(x' | x_t) \). Функция предложения может быть, например, нормальным распределением с центром в \( x_t \).
3. Вычисление вероятности принятия: рассчитывается отношение вероятностей:

\[ \alpha = \min\left(1, \frac{P(x') \cdot Q(x_t | x')}{P(x_t) \cdot Q(x' | x_t)}\right) \] где \( P(x) \) — целевое распределение (с точностью до константы), а \( Q \) — функция предложения.

1. Принятие или отклонение: генерируется случайное число \( u \) из равномерного распределения на [0, 1]. Если \( u \leq \alpha \), то новое состояние принимается: \( x_{t+1} = x' \). Иначе цепь остаётся в текущем состоянии: \( x_{t+1} = x_t \).
2. Повторение: шаги 2–4 повторяются до получения достаточного числа выборок.

В результате после некоторого «периода прогрева» (burn-in) цепь Маркова начинает генерировать выборки, распределённые в соответствии с \( P(x) \). Важно, что последовательные выборки коррелированы, поэтому для получения независимых наблюдений часто применяют прореживание (thinning) — сохранение каждой \( k \)-й выборки.

Разновидности и модификации

Алгоритм Метрополиса (частный случай)

В оригинальной версии Метрополиса функция предложения симметрична: \( Q(x' | x_t) = Q(x_t | x') \). Тогда вероятность принятия упрощается до: \[ \alpha = \min\left(1, \frac{P(x')}{P(x_t)}\right) \] Этот вариант часто используется в физике и при моделировании молекулярных систем.

Случайное блуждание Метрополиса

Наиболее распространённая реализация, где предложение генерируется как \( x' = x_t + \epsilon \), где \( \epsilon \) — случайная величина с симметричным распределением (например, нормальным). Размер шага \( \epsilon \) является важным гиперпараметром: слишком маленький шаг приводит к медленному исследованию пространства, слишком большой — к высокой частоте отклонений.

Независимый алгоритм Метрополиса — Гастингса

Функция предложения не зависит от текущего состояния: \( Q(x' | x_t) = Q(x') \). Этот вариант эффективен, когда целевое распределение близко к распределению предложения, но может давать плохие результаты при сильном расхождении.

Адаптивный алгоритм Метрополиса — Гастингса

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

Применение

Статистическая физика

Алгоритм Метрополиса — Гастингса изначально разрабатывался для моделирования систем частиц в равновесии. Он используется для расчёта термодинамических свойств (энергия, теплоёмкость, намагниченность) в моделях Изинга, Поттса и других решёточных моделях.

Байесовская статистика

В байесовском выводе часто требуется семплировать из апостериорного распределения, которое не имеет аналитического вида. Алгоритм Метрополиса — Гастингса позволяет оценивать параметры моделей, вычислять маргинальные распределения и делать прогнозы. Он является основой для многих программных пакетов, таких как BUGS, JAGS и Stan.

Машинное обучение

Вероятностные модели, такие как латентное размещение Дирихле (LDA) и модели гауссовских смесей, часто используют MCMC-методы, включая алгоритм Метрополиса — Гастингса, для обучения и вывода.

Биоинформатика и генетика

Алгоритм применяется для реконструкции филогенетических деревьев, анализа последовательностей ДНК и моделирования популяционной динамики.

Обработка изображений и компьютерное зрение

Методы MCMC используются для сегментации изображений, восстановления сцен и моделирования текстур.

Преимущества и недостатки

Преимущества

• Универсальность: работает для широкого класса распределений, включая многомерные и сложные.
• Не требует знания нормировочной константы целевого распределения.
• Относительно простая реализация.

Недостатки

• Корреляция между последовательными выборками, что снижает эффективную ёмкость выборки.
• Медленная сходимость для многомерных распределений с сильными корреляциями между переменными.
• Чувствительность к выбору функции предложения и её параметров.
• Необходимость периода прогрева (burn-in), который может быть длительным.

Критика и альтернативы

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

Интересные факты

• Алгоритм Метрополиса — Гастингса считается одним из десяти наиболее влиятельных алгоритмов XX века в области вычислительной науки (по версии журнала Computing in Science & Engineering, 2000 год).
• В 2013 году группа исследователей из Университета Ватерлоо (Канада) показала, что алгоритм может быть реализован на квантовом компьютере с потенциальным ускорением для некоторых задач.
• Название «Метрополис — Гастингса» часто сокращается до MH, а в физической литературе до сих пор распространён термин «алгоритм Метрополиса».

Источники

• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087–1092.
• Hastings, W. K. (1970). Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, 57(1), 97–109.
• Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods. Springer.
• Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., & Rubin, D. B. (2013). Bayesian Data Analysis (3rd ed.). CRC Press.
• MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.