Это не официальный сайт wikipedia.org 01.01.2023

Марковская цепь Монте-Карло — Википедия
Википедия

Марковская цепь Монте-Карло

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

Прикладные областиПравить

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

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

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

Общее определениеПравить

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

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

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

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

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

Уменьшение корреляцииПравить

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

ПримерыПравить

Случайное блужданиеПравить

  • Алгоритм Метрополиса-Гастингса: этот метод генерирует марковскую цепь, используя заданную плотность и фильтрацию новых шагов. Фактически это общая схема, частными случаями которой являются: самый первый и простой MCMC (алгоритм Метрополиса), а также альтернативы, перечисленные ниже.
    • Семплирование по Гиббсу: для этого метода требуется, чтобы были известны все условные распределения целевого распределения. Если вывод из полностью условных распределений не является непосредственным, то используются другие сэмплеры по Гиббсу (см. напр. [6][7][8]). Семплирование по Гиббсу популярно, потому что оно не требует предварительной «настройки».
    • Методы Монте-Карло по Ланжевену (Langevin Monte Carlo) и прочие методы, опирающиеся на градиент (и, возможно, вторую производную) логарифма целевой плотности. Цель этих методов – предложить наиболее правдоподобные шаги в направлении более высокой плотности вероятности[9].
    • Псевдо-маргинальный метод Метрополиса-Гастингса: этот метод заменяет плотность целевого распределения его несмещённой оценкой. Метод применим, когда целевая плотность не задана аналитически (напр. в моделях со скрытыми переменными).
  • Выборка по слоям: в основе этого метода лежит принцип, согласно которому выборку некоторого распределения можно построить, равномерно семплируя область под графиком функции плотности этого распределения. Этот метод заменяет однородное семплирование в вертикальном направлении однородным семплированием горизонтального «слоя», определённого текущей вертикальной позицией.
  • Алгоритм многократных попыток Метрополиса (Multiple-try Metropolis): это вариация алгоритма Метрополиса-Гастингса, которая позволяет делать в каждой точке многократные попытки. Делая более крупные шаги на каждой итерации, алгоритм помогает избавиться от «проклятия размерностей»[10][11].
  • Метод обратимого прыжка (Reversible-jump) : ещё один вариант алгоритма Метрополиса-Гастингса, допускающий изменения размерности пространства[12]. Такие методы марковской цепи долгое время использовались в прикладной статистической физике, где в некоторых задачах имело место распределение, называемое «большим каноническим ансамблем» (напр. при переменном количеством молекул в замкнутом сосуде). Метод обратимого прыжка применим при использовании MCMC или семплирования по Гиббсу на непараметрических байесовских моделях, где количество смешивающихся компонент (кластеров) автоматически прогнозируется с помощью данных (напр. процесс Дирихле или «процесс китайского ресторана»).
  • Гамильтонов (гибридный) метод Монте-Карло: этот метод пытается избежать случайного блуждания введением дополнительного «вектора момента» и применением гамильтоновой динамики, где функция потенциальной энергии — это целевая плотность. Выборки момента отбрасываются после семплирования. Окончательный результат алгоритма состоит в том, что движение по пространству выборки делается крупными шагами. Таким образом, они менее коррелированы и быстрее сходятся к целевому распределению.

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

Интерактивные методологии МСМС – это класс методов частиц в среднем поле для получения выборок псевдослучайных чисел из последовательности распределений вероятности с возрастающим уровнем сложности семплирования[13].

Эти вероятностные модели включают в себя:

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

В общем случае любые сэмплеры MCMC можно превратить в интерактивные. Их, в свою очередь, можно использовать как способ параллельного запуска последовательности обычных сэмплеров. Например, интерактивные алгоритмы имитации отжига основаны на независимых перемещениях по алгоритму Метрополиса-Гастингса, которые последовательно взаимодействуют с механизмом выборочного ресемплирования. В противоположность классическим методам MCMC, здесь параметр точности интерактивных сэмплеров зависит только от их количества. Методы взаимодействующих частиц принадлежат классу моделей частиц Фейнмана-Каца[14][15], также называемому «последовательным методом Монте-Карло» или «методами фильтра частиц» в теории байесовских выводов и в области обработки сигналов[16]. Интерактивные методы МСМС можно также понимать как циклы в алгоритме генетических частиц с мутациями в виде классических МСМС мутаций.

Марковская цепь квази-Монте-Карло (MCQMC)[17][18]Править

Использование последовательностей с низким расхождением вместо случайных чисел для простого независимого семплирования Монте-Карло обладает явными преимуществами[19]. Такая замена используется в методе квази-Монте-Карло (QMC)[20]. Согласно неравенству Коксма-Хлавка, погрешность интеграции в таком методе гораздо меньше, чем при семплировании независимых одинаково распределённых случайных величин (IID). Это позволяет на порядок уменьшить и погрешность оценки и время сходимости.

Метод Array-RQMC вводит моделирование марковских цепей на основе QMC путём моделирования n   цепей одновременно. На каждом шаге эмпирическое распределение этих n   состояний даёт более точное приближение к функции распределения, чем при использовании MCMC[21]. В эмпирических экспериментах сходимость дисперсии среднего функции состояния иногда имеет скорость порядка O ( n − 2 )   или даже быстрее, вместо O ( n − 1 )   у метода Монте-Карло[22].

СходимостьПравить

Обычно построить марковскую цепь с необходимыми свойствами нетрудно. Сложнее определить, сколько шагов потребуется для сходимости к стационарному распределению с приемлемой ошибкой[23]. Хорошая цепь обладает свойством перемешивания: стационарное распределение достигается быстро для любой начальной позиции. Классический эмпирический метод достижения сходимости состоит в том, чтобы запустить несколько независимо смоделированных марковских цепей и проверить, что дисперсии вне цепи и внутри неё примерно равны[23][24].

Обычно семплирование MCMC может только приближать целевое распределение, поскольку всегда присутствует остаточный эффект начальной позиции. Более сложные алгоритмы, основанные на MCMC, такие как coupling from the past, могут получать точные выборки, что сказывается на количестве вычислений и потраченного времени.

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

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

Программное обеспечениеПравить

Программное обеспечение для работы с МСМС семплированием:

  • пакеты, которые используют диалекты языка модели BUGS
  • greta, язык байесовского статистического моделирования
  • MCSim
  • PyMC3
  • pymcmcstat
  • R (язык программирования) с пакетами adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan, и т. д.
  • Stan
  • TensorFlow Probability (библиотека вероятностного программирования, встроенная в TensorFlow)
  • MCL (кластерный алгоритм для графов и HipMCL (альтернативная версия))[26]
  • emcee (реализация аффинного инвариантного семплера ансамбля MCMC на Python)
  • Keanu Java-библиотека многоцелевого вероятностного программирования
  • Zeus реализация ансамблевого семплирования по слоям на Python
  • Turing.jl пакет для многоцелевого вероятностного программирования в Julia
  • Mamba.jl платформа для МСМС метода в Julia

ПримечанияПравить

ЦитатыПравить

  1. ↑ Kasim, M.F.; Bott, A.F.A.; Tzeferacos, P.; Lamb, D.Q.; Gregori, G.; Vinko, S.M. Retrieving fields from proton radiography without source profiles (англ.) // Physical Review E : journal. — 2019. — September (vol. 100). — doi:10.1103/PhysRevE.100.033208. — arXiv:1905.12934.
  2. ↑ Gupta, Ankur; Rawlings, James B. Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology (англ.) // AIChE Journal : journal. — 2014. — April (vol. 60, no. 4). — P. 1253—1268. — doi:10.1002/aic.14409. — PMID 27429455. — PMC 4946376.
  3. ↑ See Gill 2008.
  4. ↑ See Robert & Casella 2004.
  5. ↑ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (англ.). — Second. — CRC Press, 2014. — P. xix. — ISBN 978-1-4398-1917-3.
  6. ↑ Gilks, W. R.; Wild, P. Adaptive Rejection Sampling for Gibbs Sampling (англ.) // Journal of the Royal Statistical Society. Series C (Applied Statistics)  (англ.) (рус. : journal. — 1992. — 1 January (vol. 41, no. 2). — P. 337—348. — doi:10.2307/2347565. — JSTOR 2347565.
  7. ↑ Gilks, W. R.; Best, N. G.  (англ.) (рус.; Tan, K. K. C. Adaptive Rejection Metropolis Sampling within Gibbs Sampling (англ.) // Journal of the Royal Statistical Society. Series C (Applied Statistics)  (англ.) (рус. : journal. — 1995. — 1 January (vol. 44, no. 4). — P. 455—472. — doi:10.2307/2986138. — JSTOR 2986138.
  8. ↑ Martino, L.; Read, J.; Luengo, D. Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling (англ.) // IEEE Transactions on Signal Processing  (англ.) (рус. : journal. — 2015. — 1 June (vol. 63, no. 12). — P. 3123—3138. — ISSN 1053-587X. — doi:10.1109/TSP.2015.2420537. — Bibcode: 2015ITSP...63.3123M. — arXiv:1205.5494.
  9. ↑ See Stramer 1999.
  10. ↑ Liu, Jun S.; Liang, Faming; Wong, Wing Hung. The Multiple-Try Method and Local Optimization in Metropolis Sampling (англ.) // Journal of the American Statistical Association : journal. — 2000. — 1 March (vol. 95, no. 449). — P. 121—134. — ISSN 0162-1459. — doi:10.1080/01621459.2000.10473908.
  11. ↑ Martino, Luca; Read, Jesse. On the flexibility of the design of multiple try Metropolis schemes (англ.) // Computational Statistics  (англ.) (рус. : journal. — 2013. — 11 July (vol. 28, no. 6). — P. 2797—2823. — ISSN 0943-4062. — doi:10.1007/s00180-013-0429-2. — arXiv:1201.0646.
  12. ↑ See Green 1995.
  13. ↑ Del Moral, Pierre. Mean field simulation for Monte Carlo integration (англ.). — Chapman & Hall/CRC Press, 2013. — P. 626.. — «Monographs on Statistics & Applied Probability».
  14. ↑ Del Moral, Pierre. Feynman-Kac formulae. Genealogical and interacting particle approximations (англ.). — Springer, 2004. — P. 575.. — «Series: Probability and Applications».
  15. ↑ Del Moral, Pierre; Miclo, Laurent. Séminaire de Probabilités XXXIV / Jacques Azéma, Michel Ledoux, Michel Émery, Marc Yor. — 2000. — Т. 1729. — С. 1—145. — (Lecture Notes in Mathematics). — ISBN 978-3-540-67314-9. — doi:10.1007/bfb0103798.
  16. ↑ Del Moral, Pierre. Sequential Monte Carlo samplers - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library (англ.) // Journal of the Royal Statistical Society. Series B (Statistical Methodology)  (англ.) (рус. : journal. — 2006. — Vol. 68, no. 3. — P. 411—436. — doi:10.1111/j.1467-9868.2006.00553.x. — arXiv:cond-mat/0212648.
  17. ↑ Chen, S.; Dick, Josef; Owen, Art B. Consistency of Markov chain quasi-Monte Carlo on continuous state spaces (англ.) // Annals of Statistics  (англ.) (рус. : journal. — 2011. — Vol. 39, no. 2. — P. 673—701. — doi:10.1214/10-AOS831.
  18. ↑ Tribble, Seth D. (2007). Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences (Diss.). Stanford University. Шаблон:ProQuest.
  19. ↑ Papageorgiou, Anargyros; Traub, J. F. Beating Monte Carlo // Risk. — 1996. — Т. 9, № 6. — С. 63—65.
  20. ↑ Sobol, Ilya M. On quasi-monte carlo integrations // Mathematics and Computers in Simulation. — 1998. — Т. 47, № 2. — С. 103—112. — doi:10.1016/s0378-4754(98)00096-2.
  21. ↑ L'Ecuyer, P.; Lécot, C.; Tuffin, B. A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains (англ.) // Operations Research  (англ.) (рус. : journal. — 2008. — Vol. 56, no. 4. — P. 958—975. — doi:10.1287/opre.1080.0556.
  22. ↑ L'Ecuyer, P.; Munger, D.; Lécot, C.; Tuffin, B. Sorting Methods and Convergence Rates for Array-RQMC: Some Empirical Comparisons (англ.) // Mathematics and Computers in Simulation : journal. — 2018. — Vol. 143. — P. 191—201. — doi:10.1016/j.matcom.2016.07.010.
  23. ↑ 1 2 Gelman, A.; Rubin, D.B. Inference from iterative simulation using multiple sequences (with discussion) (англ.) // Statistical Science  (англ.) (рус. : journal. — 1992. — Vol. 7, no. 4. — P. 457—511. — doi:10.1214/ss/1177011136. — Bibcode: 1992StaSc...7..457G.
  24. ↑ Cowles, M.K.; Carlin, B.P. Markov chain Monte Carlo convergence diagnostics: a comparative review (англ.) // Journal of the American Statistical Association : journal. — 1996. — Vol. 91, no. 434. — P. 883—904. — doi:10.1080/01621459.1996.10476956.
  25. ↑ Hill, S. D.; Spall, J. C. Stationarity and Convergence of the Metropolis-Hastings Algorithm: Insights into Theoretical Aspects (англ.) // IEEE Control Systems Magazine : journal. — 2019. — Vol. 39, no. 1. — P. 56—67. — doi:10.1109/MCS.2018.2876959.
  26. ↑ Azad, A; Pavlopoulos, GA; Ouzounis, CA; Kyrpides, NC; Buluç, A. HipMCL: a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks (англ.) // Nucleic Acids Research  (англ.) (рус. : journal. — 2018. — 6 April (vol. 46, no. 6). — P. e33. — doi:10.1093/nar/gkx1313. — PMID 29315405. — PMC 5888241.

ИсточникиПравить

ЛитератураПравить

СсылкиПравить

Источник — https://ru.wikipedia.org/w/index.php?title=Марковская_цепь_Монте-Карло&oldid=117782695