MCMC

MCMC (сокращение от англ. Markov Chain Monte Carlo, «марковская цепь Монте-Карло») — это класс алгоритмов, предназначенных для приближённого вычисления сложных распределений вероятностей и их характеристик (математических ожиданий, дисперсий, модальных значений) путём построения марковской цепи, стационарное распределение которой совпадает с целевым. MCMC является одним из основных методов байесовского вывода, машинного обучения, статистической физики и вычислительной математики, позволяя решать задачи, для которых прямое аналитическое решение или численное интегрирование невозможны из-за высокой размерности пространства параметров.

История

Метод Монте-Карло, названный в честь казино в Монако, был разработан в 1940-х годах в США в рамках Манхэттенского проекта (Станислав Улам, Джон фон Нейман, Энрико Ферми) для моделирования нейтронных цепных реакций. Идея заключалась в использовании случайных чисел для приближённого вычисления интегралов, возникающих в задачах ядерной физики.

Идея объединения марковских цепей с методом Монте-Карло была предложена в 1953 году в работе Николаса Метрополиса, Ариэля Розенблюта, Маршалла Розенблюта, Августы Теллер и Эдварда Теллера, которые опубликовали алгоритм, ныне известный как алгоритм Метрополиса. Первоначально он применялся в статистической физике для расчёта равновесных свойств систем частиц (например, в модели Изинга). В 1970 году Уилфред Кейт Гастингс обобщил алгоритм, что позволило использовать его для произвольных распределений, а не только для симметричных. Этот вариант получил название алгоритм Метрополиса — Гастингса.

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

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

MCMC решает задачу получения выборки из целевого распределения \( p(x) \), которое известно с точностью до нормировочной константы. Вместо прямой генерации независимых точек (что часто невозможно) строится марковская цепь, последовательность состояний \( x_1, x_2, \dots, x_n \), где каждое следующее состояние зависит только от предыдущего. После достаточно долгого «прогрева» (burn-in) цепь достигает стационарного распределения, и её состояния можно рассматривать как выборку из \( p(x) \).

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

Этот алгоритм является базовым для большинства MCMC-методов. На каждом шаге \( t \) предлагается новое состояние \( x' \) из некоторого предложного распределения \( q(x' | x_t) \). Затем вычисляется вероятность принятия \( \alpha \):

\[ \alpha = \min\left(1, \frac{p(x') q(x_t | x')}{p(x_t) q(x' | x_t)}\right) \]

С вероятностью \( \alpha \) новое состояние принимается (\( x_{t+1} = x' \)), иначе цепь остаётся на месте (\( x_{t+1} = x_t \)). Если предложное распределение симметрично (\( q(x' | x_t) = q(x_t | x') \)), формула упрощается до \( \alpha = \min(1, p(x')/p(x_t)) \), что соответствует классическому алгоритму Метрополиса.

Сэмплирование Гиббса

Частный случай MCMC, когда каждое состояние многомерно, а предложное распределение строится по одному из условных распределений. На каждом шаге случайным образом выбирается одна координата \( x_i \), и её новое значение генерируется из условного распределения \( p(x_i | x_{-i}) \), где \( x_{-i} \) — все остальные координаты. Все остальные координаты остаются неизменными. Этот метод особенно эффективен, когда условные распределения легко сэмплировать (например, для нормальных распределений или распределений из экспоненциального семейства).

Классификация методов MCMC

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

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

Применение

MCMC является основным инструментом в байесовской статистике для вычисления апостериорных распределений параметров моделей. Это позволяет оценивать неопределённость прогнозов, делать проверки гипотез и выбирать модели. В машинном обучении MCMC применяется для обучения латентных моделей (например, латентного размещения Дирихле, LDA), для сэмплирования из сложных распределений в генеративных моделях и для байесовской оптимизации гиперпараметров.

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

Проблемы и ограничения

Основные проблемы MCMC связаны со сходимостью и автокорреляцией. Цепь может долго «прогреваться» (burn-in), особенно если начальное состояние далеко от области высокой вероятности. Высокая автокорреляция между последовательными состояниями означает, что эффективный размер выборки меньше числа шагов, что требует большого числа итераций. Для диагностики сходимости используются графики цепей (trace plots), статистика Гельмана — Рубина и автокорреляционные функции.

Ещё одной проблемой является выбор предложного распределения. Слишком узкое распределение приводит к медленному исследованию пространства, слишком широкое — к частым отклонениям предложений. Адаптивные методы помогают, но могут нарушать марковское свойство, если не используются корректно. В многомерных пространствах (более 1000 измерений) MCMC может быть крайне неэффективным, и для таких задач применяются вариационные методы или специализированные алгоритмы, такие как HMC.

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

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

Источники

• Метрополис Н., Розенблют А., Розенблют М., Теллер А., Теллер Э. «Уравнения состояния для жидкостей и твердых тел с помощью быстрых вычислительных машин» (1953).
• Гастингс У. К. «Методы Монте-Карло с использованием марковских цепей и их применения» (1970).
• Гельман А., Карлин Дж. Б., Стерн Х. С., Рубин Д. Б. «Байесовский анализ данных» (3-е издание, 2013).
• Брукс С., Гельман А., Джонс Г., Мэн Л. «Справочник по методам MCMC» (2011).
• Бетанкур М. «Концептуальное введение в гамильтоново Монте-Карло» (2017).