Введение

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

Приложения

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

Общие пояснения

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

Снижение корреляции

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

Случайная прогулка

Алгоритм Метрополиса–Хестингса: Этот метод генерирует цепь Маркова, используя плотность предложений для новых шагов и метод отклонения некоторых предложенных ходов. Фактически, это общая структура, включающая в себя в качестве частных случаев самый первый и более простой MCMC (алгоритм Метрополиса) и множество более поздних альтернатив, перечисленных ниже. Выборка Гиббса: Когда целевое распределение многомерно, алгоритм выборки Гиббса обновляет каждую координату из её полного условного распределения, учитывая другие координаты. Выборку Гиббса можно рассматривать как частный случай алгоритма Метрополиса–Хестингса с коэффициентом принятия, равномерно равным 1. Когда извлечение проб из полных условных распределений не является простым, используются другие методы выборки в рамках Гиббса (например, см.). Выборка Гиббса популярна отчасти потому, что не требует никакой "настройки". Структура алгоритма выборки Гиббса сильно напоминает структуру вариационного вывода координатным восхождением, поскольку оба алгоритма используют полные условные распределения в процедуре обновления. Алгоритм Ланжевена, скорректированный методом Метрополиса, и другие методы, которые опираются на градиент (и, возможно, вторую производную) логарифмической целевой плотности для предложения шагов, которые с большей вероятностью будут направлены в сторону более высокой плотности вероятности. Гамильтоновский (или гибридный) Монте-Карло (HMC): стремится избежать поведения случайного блуждания путем введения вспомогательного вектора импульса и реализации гамильтоновой динамики, так что функция потенциальной энергии является целевой плотностью. Образцы импульса отбрасываются после выборки. Результатом гибридного Монте-Карло является то, что предложения перемещаются по пространству выборки более крупными шагами; следовательно, они менее коррелированы и быстрее сходятся к целевому распределению. Псевдомаргинальный Метрополис–Хестингс: Этот метод заменяет вычисление плотности целевого распределения несмещенной оценкой и полезен, когда целевая плотность недоступна аналитически, например, в моделях со скрытыми переменными. Выборка по срезам: Этот метод основан на принципе, что можно брать выборки из распределения, равномерно выбирая образцы из области под графиком его функции плотности. Он чередует равномерную выборку в вертикальном направлении с равномерной выборкой из горизонтального "среза", определяемого текущим вертикальным положением. Многократный Metropolis: Этот метод является вариантом алгоритма Метрополиса–Хестингса, который позволяет выполнять несколько попыток в каждой точке. Обеспечивая возможность делать более крупные шаги на каждой итерации, он помогает решить проблему размерности. Обратимый скачок: Этот метод является вариантом алгоритма Метрополиса–Хестингса, который позволяет предложениям изменять размерность пространства. Методы Монте-Карло Маркова, изменяющие размерность, давно используются в приложениях статистической физики, где для некоторых задач используется распределение, являющееся большим каноническим ансамблем (например, когда количество молекул в коробке переменно). Но вариант обратимого скачка полезен при выполнении Монте-Карло Маркова или выборки Гиббса над непараметрическими байесовскими моделями, такими как модели, включающие процесс Дирихле или китайский ресторанный процесс, где количество смешивающих компонентов/кластеров/и т.д. автоматически выводится из данных.

Методы взаимодействия частиц

Методологии взаимодействующих МКМК – это класс методов частиц среднего поля, предназначенных для получения случайных выборок из последовательности распределений вероятностей с возрастающей сложностью выборки. Эти вероятностные модели включают модели пространства траекторий с увеличивающимся горизонтом планирования, апостериорные распределения относительно последовательности частичных наблюдений, возрастающие множества уровней ограничений для условных распределений, убывающие графики температуры, связанные с некоторыми распределениями Больцмана — Гиббса, и многие другие. В принципе, любой алгоритм Маркова — цепи Монте-Карло может быть преобразован во взаимодействующий алгоритм Маркова — цепи Монте-Карло. Эти взаимодействующие алгоритмы Маркова — цепи Монте-Карло можно интерпретировать как способ параллельного выполнения последовательности алгоритмов Маркова — цепи Монте-Карло. Например, взаимодействующие алгоритмы имитации отжига основаны на независимых шагах Metropolis — Hastings, последовательно взаимодействующих посредством механизма перевыборки. В отличие от традиционных методов Маркова — цепи Монте-Карло, параметр точности этого класса взаимодействующих алгоритмов Маркова — цепи Монте-Карло зависит только от числа взаимодействующих алгоритмов Маркова — цепи Монте-Карло. Эти продвинутые методы частиц относятся к классу моделей частиц Фейнмана — Каца, также известных как последовательный Монте-Карло или методы фильтрации частиц в сообществах байесовского вывода и обработки сигналов. Взаимодействующие методы Маркова — цепи Монте-Карло также можно интерпретировать как генетический алгоритм частиц мутации-селекции с мутациями Маркова — цепи Монте-Карло.

Квази-Монте-Карло

Квази-Монте-Карло метод является аналогом обычного метода Монте-Карло, использующим последовательности с низкой расходимостью вместо случайных чисел. Он обеспечивает ошибку интегрирования, убывающую быстрее, чем при истинной случайной выборке, что количественно описывается неравенством Коксмы — Хлавки. Эмпирически он позволяет уменьшить как ошибку оценки, так и время сходимости на порядок величины. Методы квази-Монте-Карло на основе цепей Маркова, такие как метод Array-RQMC, сочетают в себе рандомизированное квази-Монте-Карло и моделирование цепей Маркова, моделируя цепи одновременно таким образом, чтобы лучше аппроксимировать истинное распределение цепи, чем при использовании обычной MCMC. В эмпирических экспериментах дисперсия среднего значения функции состояния иногда сходится со скоростью или даже быстрее, вместо стандартной скорости Монте-Карло.

Сближение

Обычно несложно построить цепь Маркова с желаемыми свойствами. Более сложной задачей является определение количества шагов, необходимых для сходимости к стационарному распределению с допустимой точностью. Хорошая цепь будет обладать быстрым перемешиванием: стационарное распределение достигается быстро, независимо от начальной точки. Стандартный эмпирический метод оценки сходимости заключается в запуске нескольких независимых смоделированных цепей Маркова и проверке того, что отношение межцепочечной дисперсии к внутрицепочечной дисперсии для всех оцениваемых параметров близко к 1. Как правило, выборка методом Монте-Карло на цепях Маркова может лишь приближать целевое распределение, поскольку всегда сохраняется некоторое остаточное влияние начальной позиции. Более сложные алгоритмы, основанные на цепях Маркова Монте-Карло, такие как метод "соединения из прошлого", могут генерировать точные выборки, но требуют дополнительных вычислений и неограниченного (хотя и конечного в среднем) времени работы. Многие методы Монте-Карло на основе случайного блуждания перемещаются вокруг равновесного распределения относительно небольшими шагами, без тенденции к направленному движению. Эти методы легко реализовать и анализировать, но, к сожалению, блуждающему элементу может потребоваться много времени, чтобы исследовать все пространство. Блуждающий элемент часто возвращается назад и заново покрывает уже пройденные участки. Более подробное рассмотрение сходимости представлено в центральной предельной теореме для цепей Маркова. См. для обсуждения теории, связанной со сходимостью и стационарностью алгоритма Метрополиса-Хестингса.