Цепь Маркова Монте-Карло - Markov chain Monte Carlo

Часть серии по
Байесовская статистика
Байесовский значок.svg
Теория
Методы
  • Приложения Nuvola edu Mathematics blue-p.svg Математический портал

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

Домены приложений

Методы MCMC в основном используются для расчета численные приближения из многомерные интегралы, например в Байесовская статистика, вычислительная физика,[1] вычислительная биология[2] и компьютерная лингвистика.[3][4]

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Преимущество последовательности с низким расхождением вместо случайных чисел для простой независимой выборки Монте-Карло хорошо известен.[16] Эта процедура, известная как Квази-Монте-Карло метод (QMC),[17] дает ошибку интегрирования, которая спадает с большей скоростью, чем полученная с помощью IID-выборки, за счет Неравенство Коксмы-Главки. Эмпирически это позволяет на порядок уменьшить как ошибку оценки, так и время сходимости.[нужна цитата ] Метод Array-RQMC сочетает в себе рандомизированное моделирование квази-Монте-Карло и цепи Маркова путем моделирования цепочки одновременно таким образом, чтобы эмпирическое распределение состояний на любом заданном шаге является лучшим приближением к истинному распределению цепи, чем с обычным MCMC.[18] В эмпирических экспериментах дисперсия среднего значения функции состояния иногда сходится со скоростью или даже быстрее, вместо Ставка Монте-Карло.[19]

Конвергенция

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

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

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

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

Программного обеспечения

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

  • ParaMonte, высокопроизводительное последовательное / параллельное программное обеспечение для моделирования Монте-Карло, в том числе адаптивная программа MCMC для метрополиса-Гастингса с отложенным отклонением, доступная в
  • Пакеты, использующие диалекты ОШИБКИ язык модели:
  • Грета, язык байесовского статистического моделирования / пакет R, который негласно использует TensorFlow,[23] аналогично тому, как PyMC3 использует Theano в качестве вычислительной серверной части
  • MCSim
  • PyMC3
  • pymcmcstat
  • R (язык программирования) с пакетами adapMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan и т. д.
  • Стэн
  • Вероятность TensorFlow (вероятностное программирование библиотека построена на TensorFlow )
  • MCL (кластерный алгоритм для графиков)[24] и HipMCL (распараллеленная версия)[25]
  • ведущий (MIT лицензировала реализацию на чистом Python сэмплера ансамбля Monte Carlo Affine Invariant Markov от Goodman & Weare)
  • Киану универсальная библиотека вероятностного программирования, построенная на Java
  • Зевс - это реализация метода ансамблевого среза на чистом Python.
  • Turing.jl, пакет универсального вероятностного программирования на Julia
  • Mamba.jl, платформа для метода MCMC в Юлии

Смотрите также

Рекомендации

Цитаты

  1. ^ Kasim, M.F .; Bott, A.F.A .; Tzeferacos, P .; Lamb, D.Q .; Грегори, G .; Винько, С. (Сентябрь 2019 г.). «Получение полей из протонной радиографии без профилей источников». Физический обзор E. 100. arXiv:1905.12934. Дои:10.1103 / PhysRevE.100.033208.
  2. ^ Гупта, Анкур; Роулингс, Джеймс Б. (апрель 2014 г.). «Сравнение методов оценки параметров в стохастических химических кинетических моделях: примеры в системной биологии». Журнал Айше. 60 (4): 1253–1268. Дои:10.1002 / aic.14409. ЧВК  4946376. PMID  27429455.
  3. ^ См. Gill 2008.
  4. ^ См. Роберт и Каселла 2004.
  5. ^ Банерджи, Судипто; Карлин, Брэдли П.; Гельфанд, Алан П. (12.09.2014). Иерархическое моделирование и анализ пространственных данных (Второе изд.). CRC Press. п. xix. ISBN  978-1-4398-1917-3.
  6. ^ Gilks, W. R .; Уайлд, П. (1992-01-01). «Адаптивная выборка отбраковки для выборки Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 41 (2): 337–348. Дои:10.2307/2347565. JSTOR  2347565.
  7. ^ Gilks, W. R .; Бест, Н.Г.; Тан, К. К. (1995-01-01). «Адаптивное отклонение семплирования мегаполиса в рамках семплирования Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 44 (4): 455–472. Дои:10.2307/2986138. JSTOR  2986138.
  8. ^ См. Stramer 1999.
  9. ^ См. Green 1995.
  10. ^ Дель Мораль, Пьер (2013). Моделирование среднего поля для интеграции Монте-Карло. Чепмен и Холл / CRC Press. п. 626.
  11. ^ Дель Мораль, Пьер (2004). Формулы Фейнмана-Каца. Генеалогические и взаимодействующие приближения частиц. Springer. п. 575.
  12. ^ Дель Мораль, Пьер; Микло, Лоран (2000). "Аппроксимация систем ветвящихся и взаимодействующих частиц формул Фейнмана-Каца с приложениями к нелинейной фильтрации". В Жаке Аземе; Мишель Леду; Мишель Эмери; Марк Йор (ред.). Séminaire de Probabilités XXXIV (PDF). Конспект лекций по математике. 1729. С. 1–145. Дои:10.1007 / bfb0103798. ISBN  978-3-540-67314-9.
  13. ^ Дель Мораль, Пьер (2006). «Последовательные пробоотборники Монте-Карло». Журнал Королевского статистического общества. Серия B (статистическая методология). 68 (3): 411–436. arXiv:cond-mat / 0212648. Дои:10.1111 / j.1467-9868.2006.00553.x.
  14. ^ Chen, S .; Дик, Йозеф; Оуэн, Арт Б. (2011). «Согласованность квази-Монте-Карло цепи Маркова на непрерывных пространствах состояний». Анналы статистики. 39 (2): 673–701. Дои:10.1214 / 10-AOS831.
  15. ^ Триббл, Сет Д. (2007). Алгоритмы Монте-Карло цепи Маркова с использованием полностью равномерно распределенных управляющих последовательностей (Дисс.). Стэндфордский Университет. ProQuest  304808879.
  16. ^ Папагеоргиу, Анаргирос; Трауб, Дж. Ф. (1996). «Победить Монте-Карло». Риск. 9 (6): 63–65.
  17. ^ Соболь, Илья М (1998). «Об интеграциях квазимонте-Карло». Математика и компьютеры в моделировании. 47 (2): 103–112. Дои:10.1016 / s0378-4754 (98) 00096-2.
  18. ^ L'Ecuyer, P .; Lécot, C .; Таффин, Б. (2008). "Рандомизированный метод моделирования квази-Монте-Карло для цепей Маркова" (PDF). Исследование операций. 56 (4): 958–975. Дои:10.1287 / opre.1080.0556.
  19. ^ L'Ecuyer, P .; Munger, D .; Lécot, C .; Таффин, Б. (2018). «Методы сортировки и скорость сходимости для Array-RQMC: некоторые эмпирические сравнения». Математика и компьютеры в моделировании. 143: 191–201. Дои:10.1016 / j.matcom.2016.07.010.
  20. ^ а б Гельман, А .; Рубин, Д. (1992). «Вывод из итеративного моделирования с использованием нескольких последовательностей (с обсуждением)» (PDF). Статистическая наука. 7 (4): 457–511. Bibcode:1992StaSc ... 7..457G. Дои:10.1214 / сс / 1177011136.
  21. ^ Cowles, M.K .; Карлин, Б. (1996). «Диагностика сходимости цепи Маркова Монте-Карло: сравнительный обзор». Журнал Американской статистической ассоциации. 91 (434): 883–904. CiteSeerX  10.1.1.53.3445. Дои:10.1080/01621459.1996.10476956.
  22. ^ Hill, S.D .; Сполл, Дж. К. (2019). «Стационарность и конвергенция алгоритма Метрополиса-Гастингса: взгляд на теоретические аспекты». Журнал IEEE Control Systems. 39 (1): 56–67. Дои:10.1109 / MCS.2018.2876959.
  23. ^ «Зависимости и вдохновение от программного обеспечения greta». greta-stats.org/. Получено 2020-04-13.
  24. ^ Энрайт, AJ; Ван Донген, S; Узунис, Калифорния (1 апреля 2002 г.). «Эффективный алгоритм для крупномасштабного обнаружения семейств белков». Исследования нуклеиновых кислот. 30 (7): 1575–84. Дои:10.1093 / nar / 30.7.1575. ЧВК  101833. PMID  11917018.
  25. ^ Азад, А; Павлопулос, Джорджия; Узунис, Калифорния; Кирпидес, Северная Каролина; Buluç, A (6 апреля 2018 г.). «HipMCL: высокопроизводительная параллельная реализация алгоритма марковской кластеризации для крупномасштабных сетей». Исследования нуклеиновых кислот. 46 (6): e33. Дои:10.1093 / нар / gkx1313. ЧВК  5888241. PMID  29315405.

Источники

дальнейшее чтение