Метод Монте-Карло для марковских цепей (MCMC): алгоритм Метрополиса-Гастингса

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

Самым знаменитым и универсальным инструментом в семействе MCMC является алгоритм Метрополиса-Гастингса (Metropolis-Hastings Algorithm). Разработанный физиками Николасом Метрополисом в 1953 году (в рамках Манхэттенского проекта) и обобщенный В. К. Гастингсом в 1970 году, этот алгоритм невероятно элегантен. Алгоритм стартует из любой произвольной точки пространства. На каждом шаге он генерирует точку-кандидата с помощью простой функции предложения (например, случайного гауссова сдвига от текущей позиции). Затем алгоритм вычисляет коэффициент принятия (Acceptance Ratio) — отношение значения целевой функции в новой точке-кандидате к значению функции в текущей точке, скорректированное на асимметрию функции предложения.

Если точка-кандидат находится в области с более высокой плотностью вероятности (коэффициент принятия больше единицы), алгоритм гарантированно и с радостью переходит в эту новую точку. Однако, в отличие от простых жадных методов оптимизации, если кандидат находится в менее вероятной области (коэффициент меньше единицы), алгоритм не отвергает его сразу! Он принимает этот ухудшающий шаг с вероятностью, строго равной вычисленному коэффициенту. Этот стохастический допуск ухудшения (напоминающий алгоритм имитации отжига) является критически важным. Он не позволяет алгоритму MCMC навсегда застрять на вершине одного единственного локального пика, заставляя его периодически спускаться в долины и исследовать весь многомодальный ландшафт функции.

Главной вычислительной проблемой алгоритмов MCMC является так называемое время прогрева (Burn-in Period). Поскольку алгоритм стартует из случайной точки, первые тысячи шагов блуждания совершенно не отражают истинное стационарное распределение. Поэтому аналитики обязаны безжалостно отбрасывать начальную часть сгенерированной цепи, собирая статистику только после того, как алгоритм математически сойдется к целевому распределению (оценка сходимости производится по критериям Гельмана-Рубина). Сегодня вариации MCMC (такие как Gibbs Sampling и Hamiltonian Monte Carlo) являются абсолютным золотым стандартом для обучения глубоких нейронных сетей, калибровки моделей ценообразования опционов и анализа сейсмических данных, доказывая, что случайное блуждание с правильными математическими ограничениями способно решить любую многомерную интегральную головоломку.