Марковская цепь Монте-Карло
В статистике методы Монте-Карло с марковскими цепями (англ. 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]. Интерактивные методы МСМС можно также понимать как циклы в алгоритме генетических частиц с мутациями в виде классических МСМС мутаций.
Использование последовательностей с низким расхождением вместо случайных чисел для простого независимого семплирования Монте-Карло обладает явными преимуществами[19]. Такая замена используется в методе квази-Монте-Карло (QMC)[20]. Согласно неравенству Коксма-Хлавка, погрешность интеграции в таком методе гораздо меньше, чем при семплировании независимых одинаково распределённых случайных величин (IID). Это позволяет на порядок уменьшить и погрешность оценки и время сходимости.
Метод Array-RQMC вводит моделирование марковских цепей на основе QMC путём моделирования цепей одновременно. На каждом шаге эмпирическое распределение этих состояний даёт более точное приближение к функции распределения, чем при использовании MCMC[21]. В эмпирических экспериментах сходимость дисперсии среднего функции состояния иногда имеет скорость порядка или даже быстрее, вместо у метода Монте-Карло[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
Примечания
Цитаты
- ↑ 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.
- ↑ 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.
- ↑ See Gill 2008.
- ↑ See Robert & Casella 2004.
- ↑ 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.
- ↑ 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. — .
- ↑ 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. — .
- ↑ 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. — . — arXiv:1205.5494.
- ↑ See Stramer 1999.
- ↑ 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.
- ↑ 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.
- ↑ See Green 1995.
- ↑ Del Moral, Pierre. Mean field simulation for Monte Carlo integration (англ.). — Chapman & Hall/CRC Press, 2013. — P. 626. Архивировано 8 июня 2015 года.. — «Monographs on Statistics & Applied Probability».
- ↑ Del Moral, Pierre. Feynman-Kac formulae. Genealogical and interacting particle approximations (англ.). — Springer, 2004. — P. 575.. — «Series: Probability and Applications».
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Tribble, Seth D. (2007). Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences (Diss.). Stanford University. ProQuest 304808879.
- ↑ Papageorgiou, Anargyros; Traub, J. F. Beating Monte Carlo // Risk. — 1996. — Т. 9, № 6. — С. 63—65.
- ↑ 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.
- ↑ 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. Архивировано 3 августа 2020 года.
- ↑ 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.
- ↑ 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. — . Архивировано 30 октября 2020 года.
- ↑ 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.
- ↑ 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.
- ↑ 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.
Источники
- Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan An Introduction to MCMC for Machine Learning, 2003
- Asmussen, Søren; Glynn, Peter W. Stochastic Simulation: Algorithms and Analysis (англ.). — Springer, 2007. — Vol. 57. — (Stochastic Modelling and Applied Probability).
- Atzberger, P. An Introduction to Monte-Carlo Methods . Дата обращения: 4 мая 2020. Архивировано из оригинала 20 февраля 2009 года.
- Berg, Bernd A. Markov Chain Monte Carlo Simulations and Their Statistical Analysis (англ.). — World Scientific, 2004.
- Bolstad, William M. Understanding Computational Bayesian Statistics (англ.). — Wiley, 2010. — ISBN 978-0-470-04609-8.
- Casella, George; George, Edward I. Explaining the Gibbs sampler // The American Statistician[англ.]. — 1992. — Т. 46, № 3. — С. 167—174. — doi:10.2307/2685208. — .
- Gelfand, A.E.; Smith, A.F.M. Sampling-Based Approaches to Calculating Marginal Densities (англ.) // Journal of the American Statistical Association : journal. — 1990. — Vol. 85, no. 410. — P. 398—409. — doi:10.1080/01621459.1990.10476213.
- Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. Bayesian Data Analysis. — 1st. — Chapman & Hall, 1995. (See Chapter 11.)
- Geman, S.; Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images (англ.) // IEEE Transactions on Pattern Analysis and Machine Intelligence[англ.] : journal. — 1984. — Vol. 6, no. 6. — P. 721—741. — doi:10.1109/TPAMI.1984.4767596.
- Gilks, W.R.; Richardson, S.; Spiegelhalter, D.J. Markov Chain Monte Carlo in Practice. — Chapman & Hall/CRC, 1996.
- Gill, Jeff. Bayesian methods: a social and behavioral sciences approach (англ.). — 2nd. — Chapman & Hall/CRC, 2008. — ISBN 978-1-58488-562-7.
- Green, P.J. Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination (англ.) // Biometrika : journal. — 1995. — Vol. 82, no. 4. — P. 711—732. — doi:10.1093/biomet/82.4.711.
- Neal, Radford M. Slice Sampling // Annals of Statistics[англ.]. — 2003. — Т. 31, № 3. — С. 705—767. — doi:10.1214/aos/1056562461. — .
- Neal, Radford M. Probabilistic Inference Using Markov Chain Monte Carlo Methods (1993).
- Robert, Christian P.; Casella, G. Monte Carlo Statistical Methods. — 2nd. — Springer, 2004. — ISBN 978-0-387-21239-5.
- Rubinstein, R.Y.; Kroese, D.P.[англ.]. Simulation and the Monte Carlo Method. — 2nd. — Wiley, 2007. — ISBN 978-0-470-17794-5.
- Smith, R.L. Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions (англ.) // Operations Research[англ.] : journal. — 1984. — Vol. 32, no. 6. — P. 1296—1308. — doi:10.1287/opre.32.6.1296.
- Spall, J.C. Estimation via Markov Chain Monte Carlo // IEEE Control Systems Magazine[англ.]. — 2003. — Апрель (т. 23, № 2). — С. 34—45. — doi:10.1109/mcs.2003.1188770.
- Stramer, O.; Tweedie, R. Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms (англ.) // Methodology and Computing in Applied Probability : journal. — 1999. — Vol. 1, no. 3. — P. 307—328. — doi:10.1023/A:1010090512027.
Литература
- Diaconis, Persi. The Markov chain Monte Carlo revolution (англ.) // Bulletin of the American Mathematical Society. — 2009. — April (vol. 46, no. 2). — P. 179—205. — doi:10.1090/s0273-0979-08-01238-x.
- Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. (2007), "Section 15.8. Markov Chain Monte Carlo", Numerical Recipes: The Art of Scientific Computing (3rd ed.), Cambridge University Press, ISBN 978-0-521-88068-8
- Richey, Matthew. The Evolution of Markov Chain Monte Carlo Methods (англ.) // The American Mathematical Monthly. — 2010. — May (vol. 117, no. 5). — P. 383—413. — doi:10.4169/000298910x485923.
Ссылки
- MCMC sampling and other methods in a basic overview, by Alexander Mantzaris (original link — now broken).
- PyMC — Python module implementing Bayesian statistical models and fitting algorithms, including Markov chain Monte Carlo.
- IA2RMS is a Matlab code of the «Independent Doubly Adaptive Rejection Metropolis Sampling» method, Martino, Read & Luengo (2015) , for drawing from the full-conditional densities within a Gibbs sampler.