Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии по
Байесовская статистика
Байесовский значок.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 , высокопроизводительное последовательное / параллельное программное обеспечение для моделирования Монте-Карло, в том числе адаптивная программа Metropolis-Hastings MCMC с отложенным отклонением, доступная в
    • Python ,
    • MATLAB ,
    • C / C ++ / Fortran в Windows , Linux и macOS .
  • Пакеты, использующие диалекты модельного языка BUGS :
    • WinBUGS / OpenBUGS / MultiBUGS
    • JAGS
    • NIMBLE
  • greta , язык байесовского статистического моделирования / пакет R, который за кулисами использует TensorFlow [23], аналогично тому, как PyMC3 использует Theano в качестве вычислительной серверной части.
  • MCSim
  • PyMC3
  • pymcmcstat
  • R (язык программирования) с пакетами adapMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan и т. Д.
  • Стэн
  • TensorFlow Probability ( библиотека вероятностного программирования, построенная на TensorFlow )
  • MCL (кластерный алгоритм для графов) [24] и HipMCL (распараллеленная версия) [25]
  • emcee (лицензированная MIT реализация на чистом Python сэмплера ансамбля Монте-Карло от Goodman & Weare с аффинно-инвариантной цепью Маркова)
  • Keanu - универсальная библиотека вероятностного программирования, построенная на Java
  • Zeus - это реализация метода Ensemble Slice Sampling на чистом Python.
  • Turing.jl , пакет универсального вероятностного программирования на Julia
  • Mamba.jl , платформа для метода MCMC в Юлии

См. Также [ править ]

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

Ссылки [ править ]

Цитаты [ править ]

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

Источники [ править ]

  • Кристоф Андрие, Нандо де Фрейтас, Арно Дусе и Майкл И. Джордан Введение в 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 ; Теукольский С.А .; Феттерлинг, штат Вашингтон; Фланнери, Б.П. (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 .