Метод Монте-Карло на основе цепей Маркова

Метод Монте-Карло на основе цепей Маркова (MCMC) осуществляет выборку из сложного целевого распределения путем симуляции цепи Маркова, разработанной таким образом, чтобы это распределение являлось ее уникальным стационарным законом.

Definition

Метод Монте-Карло на основе цепей Маркова представляет собой семейство алгоритмов, которые оценивают математические ожидания при заданном целевом распределении вероятностей путем запуска эргодической цепи Маркова, стационарное распределение которой является целевым, и усреднения функции по пути цепи.

Scope

Эта тема охватывает разработку ядер перехода с заданным стационарным распределением, алгоритм Метрополиса-Гастингса и его правило принятия, сэмплер Гиббса для условных обновлений, диагностику сходимости и период "прогрева" (burn-in), влияние автокорреляции на дисперсию оценки, а также связь между временем перемешивания и вычислительной стоимостью выборки.

Core questions

• Как строится цепь Маркова, чтобы иметь желаемое стационарное распределение?
• Почему правило принятия Метрополиса-Гастингса приводит к правильному стационарному закону?
• Как сэмплер Гиббса использует условные распределения?
• Как долго должна работать цепь, прежде чем ее выборки станут пригодными, и как это оценивается?

Key theories

Построение Метрополиса-Гастингса

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

Эргодические средние и оценка Монте-Карло

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

Clinical relevance

Метод Монте-Карло на основе цепей Маркова является основным инструментом современной байесовской статистики, статистической физики и машинного обучения, позволяя проводить вывод для многомерных апостериорных распределений, статистических сумм и энергетических ландшафтов, которые не могут быть проинтегрированы аналитически; его надежность зависит от достаточно быстрого перемешивания базовой цепи.

History

Цепь с принятием-отклонением возникла в алгоритме Метрополиса 1953 года для статистической физики, была обобщена Гастингсом в 1970 году и переработана для статистики через сэмплер Гиббса Гемана и Гемана в 1984 году, а также влиятельные байесовские приложения Гелфанда и Смита около 1990 года, которые положили начало вычислительной байесовской революции.

Key figures

• Nicholas Metropolis
• W. Keith Hastings
• Stuart Geman
• Donald Geman

Seminal works

• robertCasella2004
• hastings1970

Frequently asked questions

Зачем использовать цепь Маркова для получения выборок?

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

Что такое "прогрев" (burn-in)?

Это начальная часть цепи, которая отбрасывается, потому что цепь еще не сошлась к своему стационарному распределению, поэтому эти ранние состояния могли бы сместить оценки.