Цепь Маркова Монте-Карло

Часть серии по
Байесовская статистика
Теория
Допустимое правило принятия решения Байесовская эффективность Байесовская эпистемология Байесовская вероятность Вероятностные интерпретации Теорема Байеса Байесовский фактор Байесовский вывод Байесовская сеть Прежний Задний Вероятность Конъюгировать приор Задний прогностический Гиперпараметр Hyperprior Принцип безразличия Принцип максимальной энтропии Эмпирический метод Байеса Правило Кромвеля Теорема Бернштейна – фон Мизеса Критерий Шварца Достоверный интервал Максимальная апостериорная оценка Радикальный вероятностный подход
Техники
Байесовская линейная регрессия Байесовская оценка Приближенное байесовское вычисление Цепь Маркова Монте-Карло
Математический портал
v т е

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

• 1 Домены приложений
• 2 Общее объяснение
• 3 Снижение корреляции
• 4 Примеры
  • 4.1 Случайное блуждание
  • 4.2 Методы взаимодействующих частиц
  • 4.3. Квази-Монте-Карло цепи Маркова (MCQMC). ^[15][16]
• 5 Конвергенция
• 6 Программное обеспечение
• 7 См. Также
• 8 ссылки
  • 8.1 Цитаты
  • 8.2 Источники
• 9 Дальнейшее чтение

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

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

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

Сходимость алгоритма Метрополиса – Гастингса. Марковская цепь Монте-Карло пытается аппроксимировать синее распределение оранжевым.

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

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

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

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

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

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

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

Методы взаимодействующих частиц

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

Цепь Маркова квази-Монте-Карло (MCQMC).

Хорошо известно преимущество последовательностей с низким расхождением перед случайными числами для простой независимой выборки методом Монте-Карло. Эта процедура, известная как метод квази-Монте-Карло (QMC), дает ошибку интегрирования, которая затухает с большей скоростью, чем полученная с помощью IID-выборки по неравенству Коксма-Главки. Эмпирически это позволяет на порядок уменьшить как ошибку оценки, так и время сходимости. Метод Array-RQMC сочетает в себе рандомизированное моделирование квази-Монте-Карло и цепи Маркова путем одновременного моделирования цепей таким образом, что эмпирическое распределение состояний на любом заданном шаге является лучшим приближением истинного распределения цепочки, чем с обычным MCMC. В эмпирических экспериментах дисперсия среднего значения функции состояния иногда сходится со скоростью или даже быстрее, чем со скоростью Монте-Карло. ${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle О (п ^ {- 2})}$${\ Displaystyle О (п ^ {- 1})}$

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

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

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

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

Несколько программ предоставляют возможности отбора проб MCMC, например:

• ParaMonte, высокопроизводительное последовательное / параллельное программное обеспечение для моделирования Монте-Карло, в том числе адаптивная программа Metropolis-Hastings MCMC с задержкой отбраковки, доступная в
  • Python,
  • MATLAB,
  • C / C ++ / Fortran в Windows, Linux и macOS.
• Пакет Vandal, Vandal предлагает несколько вариантов моделирования методом Монте-Карло, таких как измерение рисков, гистограмма эмпирических правил и многие другие, доступные в
  • Python
• Пакеты, использующие диалекты модельного языка BUGS :
  • WinBUGS / OpenBUGS / MultiBUGS
  • JAGS
  • NIMBLE
• greta, язык байесовского статистического моделирования / пакет R, который за кулисами использует TensorFlow, аналогично тому, как PyMC3 использует Theano в качестве вычислительной серверной части.
• MCSim
• PyMC3
• pymcmcstat
• R (язык программирования) с пакетами adapMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan и т. Д.
• Стэн
• TensorFlow Probability ( библиотека вероятностного программирования, построенная на TensorFlow )
• MCL (кластерный алгоритм для графиков) и HipMCL (распараллеленная версия)
• emcee (лицензированная MIT реализация на чистом Python сэмплера ансамбля Monte Carlo Affine Invariant Markov от Goodman amp; Weare)
• Keanu - универсальная библиотека вероятностного программирования, построенная на Java.
• Zeus - это реализация метода Ensemble Slice Sampling на чистом Python.
• Turing.jl, пакет универсального вероятностного программирования на Julia
• Mamba.jl, платформа для метода MCMC в Юлии

• Муфта из прошлого
• Алгоритм Ланжевена с поправкой на мегаполис
• Центральная предельная теорема цепи Маркова
• Расширение данных MCMC

Цитаты

Источники

• Кристоф Андрие, Нандо де Фрейтас, Арно Дусе и Майкл И. Джордан Введение в MCMC для машинного обучения, 2003 г.
• Асмуссен, Сорен; Глинн, Питер В. (2007). Стохастическое моделирование: алгоритмы и анализ. Стохастическое моделирование и прикладная вероятность. 57. Springer.
• Атцбергер П. «Введение в методы Монте-Карло» (PDF).
• Берг, Бернд А. (2004). Моделирование цепей Маркова методом Монте-Карло и их статистический анализ. World Scientific.
• Болстад, Уильям М. (2010). Понимание вычислительной байесовской статистики. Вайли. ISBN   978-0-470-04609-8.
• Казелла, Джордж; Джордж, Эдвард I. (1992). «Объясняя сэмплер Гиббса». Американский статистик. 46 (3): 167–174. CiteSeerX   10.1.1.554.3993. DOI : 10.2307 / 2685208. JSTOR   2685208.
• Гельфанд А.Е.; Смит, AFM (1990). «Выборочные подходы к расчету предельных плотностей». Журнал Американской статистической ассоциации. 85 (410): 398–409. CiteSeerX   10.1.1.512.2330. DOI : 10.1080 / 01621459.1990.10476213.
• Гельман, Андрей ; Карлин, Джон Б.; Стерн, Хэл С.; Рубин, Дональд Б. (1995). Байесовский анализ данных (1-е изд.). Чепмен и Холл. (См. Главу 11.)
• Geman, S.; Геман, Д. (1984). «Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений». IEEE Transactions по анализу шаблонов и машинному анализу. 6 (6): 721–741. DOI : 10.1109 / TPAMI.1984.4767596. PMID   22499653.
• Гилкс, WR; Richardson, S.; Шпигельхальтер, ди-джей (1996). Цепь Маркова Монте-Карло на практике. Чепмен и Холл / CRC.
• Гилл, Джефф (2008). Байесовские методы: подход социальных и поведенческих наук (2-е изд.). Чепмен и Холл / CRC. ISBN   978-1-58488-562-7.
• Грин, П.Дж. (1995). «Вычисление методом Монте-Карло цепи Маркова с обратимым скачком и определение байесовской модели». Биометрика. 82 (4): 711–732. CiteSeerX   10.1.1.407.8942. DOI : 10.1093 / Biomet / 82.4.711.
• Нил, Рэдфорд М. (2003). «Выборка срезов». Анналы статистики. 31 (3): 705–767. DOI : 10.1214 / AOS / 1056562461. JSTOR   3448413.
• Нил, Рэдфорд М. (1993). " Вероятностный вывод с использованием методов Монте-Карло цепи Маркова ".
• Роберт, Кристиан П.; Казелла, Г. (2004). Статистические методы Монте-Карло (2-е изд.). Springer. ISBN   978-0-387-21239-5.
• Рубинштейн, Р.Ю.; Круз, Д.П. (2007). Моделирование и метод Монте-Карло (2-е изд.). Вайли. ISBN   978-0-470-17794-5.
• Смит, Р.Л. (1984). «Эффективные процедуры Монте-Карло для генерации точек, равномерно распределенных по ограниченным областям». Исследование операций. 32 (6): 1296–1308. DOI : 10.1287 / opre.32.6.1296. ЛВП : 2027,42 / 7681.
• Сполл, JC (апрель 2003 г.). «Оценка через цепь Маркова Монте-Карло». Журнал IEEE Control Systems. 23 (2): 34–45. DOI : 10.1109 / mcs.2003.1188770.
• Stramer, O.; Твиди, Р. (1999). «Модели ланжевеновского типа II: самонастраивающиеся кандидаты для алгоритмов MCMC». Методология и вычисления в прикладной теории вероятностей. 1 (3): 307–328. DOI : 10,1023 / A: 1010090512027.

• Диаконис, Перси (апрель 2009 г.). «Революция Монте-Карло с цепями Маркова» (PDF). Бык. Амер. Математика. Soc. 46 (2): 179–205. DOI : 10.1090 / s0273-0979-08-01238-х. С 0273-0979 (08) 01238-Х.
• Нажмите, WH ; Teukolsky, SA ; Феттерлинг, штат Вашингтон; Фланнери, Б.П. (2007), «Раздел 15.8. Марковская цепь Монте-Карло», Численные рецепты: Искусство научных вычислений (3-е изд.), Cambridge University Press, ISBN   978-0-521-88068-8
• Ричи, Мэтью (май 2010 г.). "Эволюция методов Монте-Карло цепей Маркова" (PDF). Американский математический ежемесячник. 117 (5): 383–413. CiteSeerX   10.1.1.295.4478. DOI : 10.4169 / 000298910x485923.