У статистиці ме тоди Мо нте Ка рло ма рковських ланцюгі в МКМЛ англ Markov Chain Monte Carlo MCMC це клас алгоритмів для

У статистиці, ме́тоди Мо́нте-Ка́рло ма́рковських ланцюгі́в (МКМЛ, англ. Markov Chain Monte Carlo, MCMC) — це клас алгоритмів для вибірки з розподілу ймовірностей на базі побудови такого ланцюга Маркова, що має бажаний розподіл як свій (рівноважний розподіл). Тоді стан цього ланцюга після якогось числа кроків використовується як вибірка з бажаного розподілу. Якість вибірки покращується як функція від кількості кроків.

Збіжність алгоритму Метрополіса–Гастінгса. МКМЛ намагається апроксимувати синій розподіл помаранчевим.

Ме́тоди Мо́нте-Ка́рло випадко́вого блука́ння складають великий підклас методів МКМЛ.

Області застосування

Методи МКМЛ здебільшого застосовуються для обчислення чисельних наближень багатовимірних інтегралів, наприклад, у баєсовій статистиці, обчислювальній фізиці, обчислювальній біології та обчислювальній лінгвістиці.
У баєсовій статистиці нещодавні розробки методів МКМЛ стали ключовим кроком в уможливленні обчислення великих ієрархічних моделей, що вимагають інтеграції над сотнями або навіть тисячами невідомих параметрів.
Їх також застосовують для генерування вибірок, що поступово покривають зону рідкісного збою у ^[en].

Класифікація

Методи Монте-Карло випадкового блукання

Див. також: Випадкове блукання

Багатовимірні інтеграли

Коли методи МКМЛ застосовуються для наближення багатовимірних інтегралів, то всюди випадково рухається ансамбль ходаків. У кожній точці, де ступає ходак, до інтегралу зараховується значення підінтегрального в цій точці. Потім ходак може зробити якусь кількість пробних кроків цією зоною, шукаючи місця з прийнятно високим внеском до інтегралу, щоби рухатися туди далі.

Методи Монте-Карло випадкового блукання є різновидом випадкового моделювання, або методу Монте-Карло. Проте, тоді як випадкові вибірки, що використовуються у звичайному ^[en], є статистично незалежними, ті, що використовуються у методах МКМЛ, є корельованими. Ланцюг Маркова будується таким чином, щоби мати підінтегральне як свій (рівноважний розподіл).

Приклади

Приклади методів Монте-Карло випадкового блукання включають наступні:

Алгоритм Метрополіса — Гастінгса: Цей метод породжує випадкове блукання із застосуванням густини пропозиції та методу відкидання деяких із запропонованих рухів.
^[en]: Цей метод вимагає, щоби було точно вказано вибірки з усіх умовних розподілів цільового розподілу. Він є популярним зокрема тому, що не вимагає жодного «регулювання».
^[en]: Цей метод залежить від того принципу, що можна робити вибірку з розподілу шляхом рівномірної вибірки з області під графіком функції його густини. Він чергує рівномірну вибірку у вертикальному напрямку з рівномірною вибіркою з горизонтального «рівня», визначеного поточною вертикальною позицією.
^[en]: Цей метод є варіацією алгоритму Метрополіса — Гастінгса, що дозволяє багаторазові спроби у кожній точці. Дозволяючи робити більші кроки на кожній ітерації, він допомагає розв'язувати прокляття розмірності.
^[en]: Цей метод є варіацією алгоритму Метрополіса — Гастінгса, що дозволяє пропозиції, які змінюють розмірність простору. Методи МКМЛ, що змінюють розмірність, тривалий час застосовуватися у статистичній фізиці, де для деяких задач використовується розподіл, що є великим канонічним ансамблем (наприклад, коли кількість молекул у коробці є змінною). Але реверсивно-стрибковий варіант є корисним при виконанні МКМЛ або вибірки за Ґіббсом над ^[en] баєсовими моделями, такими як пов'язані з ^[en] чи ^[en], де кількість змішуваних складових/кластерів/тощо автоматично виводиться з даних.

Інші методи МКМЛ

Взаємодійні методології МКМЛ є класом ^[en] для отримання випадкових виборок із послідовності розподілів ймовірності зі зростаючим рівнем складності вибірки. Ці ймовірнісні моделі включають моделі простору шляху зі збільшуваним часовим горизонтом, апостеріорними розподілами відносно послідовності часткових спостережень, збільшуваними наборами рівнів обмежень для умовних розподілів, зменшуваними графіками температури, пов'язаними з деякими розподілами Больцмана — Ґіббса, та багато інших. У принципі, будь-який відбірник МКМЛ може бути перетворено на взаємодійний відбірник МКМЛ. Ці взаємодійні відбірники МКМЛ може бути інтерпретовано як спосіб паралельного виконання відбірників МКМЛ. Наприклад, взаємодійні імітаційні алгоритми ренатурації базуються на незалежних кроках Метрополіса — Гастінгса, що послідовно взаємодіють з механізмом типу вибору/повторного взяття вибірки. На відміну від традиційних методів МКМЛ, параметр точності цього класу взаємодійних відбірників МКМЛ стосується лише кількості відбірників МКМЛ, що взаємодіють. Ці передові частинкові методології належать до класу частинкових моделей Фейнмана-Каца, що у спільнотах баєсового висновування та обробки сигналів називаються також ^[en], або ^[en]. Взаємодійні методи МКМЛ також може бути інтерпретовано як генетичні частинкові алгоритми мутації-відбору з мутаціями МКМЛ.

(КМКМЛ, англ. Markov Chain quasi-Monte Carlo, MCQMC). Перевага використання послідовностей з низькою розбіжністю замість випадкових чисел для простої незалежної вибірки Монте-Карло добре відома. Ця процедура, відома як метод квазі-Монте-Карло (КМК, англ. Quasi-Monte Carlo method, QMC), відповідно до ^[en] дає інтеграційну помилку, що спадає значно швидше, ніж отримувана за допомогою вибірки НОР. Емпірично це дозволяє зменшувати як помилку оцінки, так і тривалість збіжності, на порядок величини.^[]

Зменшення кореляції

Вдосконаленіші методи використовують різні шляхи зменшення кореляції між сусідніми елементами вибірки. Ці алгоритми можуть бути складнішими для втілення, проте вони зазвичай демонструють швидшу збіжність (тобто, досягнення точного результату за меншу кількість кроків).

Приклади

Приклади методів МКМЛ не випадкового блукання включають наступне:

^[en] (ГМК, англ. Hybrid Monte Carlo, HMC): Намагається уникнути поведінки випадкового блукання за допомогою введення додаткового вектора імпульсу та реалізації гамільтонової динаміки, так, що функція потенціальної енергії є цільовою густиною. Імпульсні елементи вибірки відкидаються після вибірки. Кінцевим результатом гібридного алгоритму Монте-Карло є те, що пропозиції рухаються простором вибірки більшими кроками; вони відтак є менш корельованими, та швидше згортаються до цільового розподілу.
Деякі варіації вибірки за рівнями також уникають випадкового блукання.
МКМЛ Ланжевена, та інші методи, що покладаються на градієнт (та, можливо, другу похідну) логарифму апостеріорного, уникають випадкового блукання, роблячи пропозиції, що правдоподібніше знаходяться в напрямку вищої густини ймовірності.

Збіжність

Побудувати ланцюг Маркова із потрібними властивостями зазвичай нескладно. Складнішою задачею є визначити, скільки кроків потрібно для згортки до стаціонарного розподілу із прийнятною помилкою. Добрий ланцюг матиме ^[en]: стаціонарний розподіл досягається швидко при старті з довільного положення.

Типова вибірка МКМЛ може лише наближувати цільовий розподіл, оскільки завжди залишається якийсь залишковий вплив початкового положення. Вдосконаленіші алгоритми на базі МКМЛ, такі як ^[en], можуть видавати точні вибірки ціною додаткових обчислень та необмеженого (хоча й очікувано скінченного) часу виконання.

Багато методів Монте-Карло випадкового блукання рухаються навколо рівноважного розподілу відносно малими кроками, без тенденції до того, щоби кроки просувалися в одному напрямку. Ці методи є легкими для втілення та аналізу, але, на жаль, дослідження ходаком усього простору може забирати багато часу. Ходак часто повертатиметься, і повторно досліджуватиме вже досліджену місцевість.

Див. також

Примітки

Gill, 2008.
Robert та Casella, 2004.
Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (вид. Second Edition). CRC Press. с. xix. ISBN . (англ.)
Green, 1995.
Del Moral, Pierre (2013). . Chapman & Hall/CRC Press. с. 626. Архів оригіналу за 8 червня 2015. Процитовано 5 серпня 2015. Monographs on Statistics & Applied Probability (англ.)
Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. с. 575. Series: Probability and Applications (англ.)
Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering (PDF). Т. 1729. с. 1—145. doi:10.1007/bfb0103798. {{}}: Проігноровано |journal= () (англ.)
. onlinelibrary.wiley.com. Архів оригіналу за 6 вересня 2015. Процитовано 11 червня 2015. (англ.)
Chen, S., Josef Dick, and Art B. Owen. «Consistency of Markov chain quasi-Monte Carlo on continuous state spaces.» The Annals of Statistics 39.2 (2011): 673—701. (англ.)
Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007. (англ.)
Papageorgiou, Anargyros, and J. F. Traub. «Beating Monte Carlo.» Risk 9.6 (1996): 63-65. (англ.)
Sobol, Ilya M. «On quasi-monte carlo integrations.» Mathematics and Computers in Simulation 47.2 (1998): 103—112. (англ.)
Neal, 2003.
Stramer та Tweedie, 1999.

Джерела

Christophe Andrieu, Nando De Freitas and Arnaud Doucet, An Introduction to MCMC for Machine Learning, 2003 (англ.)
Asmussen, Søren; Glynn, Peter W. (2007). Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability. Т. 57. Springer. (англ.)
Atzberger, P. An Introduction to Monte-Carlo Methods (PDF). (англ.)
(2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis. World Scientific. (англ.)
Bolstad, William M. (2010). Understanding Computational Bayesian Statistics. Wiley. ISBN . (англ.)
Casella, George; George, Edward I. (1992). Explaining the Gibbs sampler. ^[en]. 46: 167—174. doi:10.2307/2685208. (Basic summary and many references.) (англ.)
Gelfand, A.E.; Smith, A.F.M. (1990). Sampling-Based Approaches to Calculating Marginal Densities. ^[en]. 85: 398—409. doi:10.1080/01621459.1990.10476213. (англ.)
; Carlin, John B.; Stern, Hal S.; (1995). Bayesian Data Analysis (вид. 1st). . (See Chapter 11.) (англ.)
Geman, S.; (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. ^[en]. 6: 721—741. (англ.)
Gilks, W.R.; Richardson, S.; (1996). Markov Chain Monte Carlo in Practice. /CRC. (англ.)
Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach (вид. 2nd). /CRC. ISBN . (англ.)
Green, P.J. (1995). Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination. ^[en]. 82 (4): 711—732. doi:10.1093/biomet/82.4.711. (англ.)
Neal, Radford M. (2003). Slice Sampling. ^[en]. 31 (3): 705—767. doi:10.1214/aos/1056562461. JSTOR 3448413. (англ.)
Neal, Radford M. (1993). Probabilistic Inference Using Markov Chain Monte Carlo Methods. (англ.)
Robert, Christian P.; Casella, G. (2004). Monte Carlo Statistical Methods (вид. 2nd). Springer. ISBN . (англ.)
Rubinstein, R.Y.; Kroese, D.P. (2007). Simulation and the Monte Carlo Method (вид. 2nd). . ISBN . (англ.)
Smith, R.L. (1984). Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions. ^[en]. 32: 1296—1308. doi:10.1287/opre.32.6.1296. (англ.)
Spall, J.C. (April 2003). Estimation via Markov Chain Monte Carlo. IEEE Control Systems Magazine. 23 (2): 34—45. doi:10.1109/mcs.2003.1188770. (англ.)
Stramer, O.; Tweedie, R. (1999). Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms. Methodology and Computing in Applied Probability. 1 (3): 307—328. doi:10.1023/A:1010090512027. (англ.)

Література

(April 2009). The Markov chain Monte Carlo revolution (PDF). Bull. Amer. Math. Soc. 46 (2): 179—205. doi:10.1090/s0273-0979-08-01238-x. S 0273-0979(08)01238-X. (англ.)
; ; Vetterling, W.T.; Flannery, B.P. (2007), Section 15.8. Markov Chain Monte Carlo, Numerical Recipes: The Art of Scientific Computing (вид. 3rd), Cambridge University Press, ISBN (англ.)
Richey, Matthew (May 2010). The Evolution of Markov Chain Monte Carlo Methods (PDF). The American Mathematical Monthly. 117 (5): 383—413. doi:10.4169/000298910x485923. (англ.)

Посилання

, Alexander Mantzaris (первинне посилання — тепер недійсне) (англ.)
Інтерактивні методології Метрополіса–Гастінгса
Візуальна демонстрація методів вибірки МКМЛ (аплет Java), Laird Breyer (англ.)
Іграшковий приклад вибірки МКМЛ для Matlab, Zhiyuan Weng
MCL — марковський алгоритм кластеризації для графів, Stijn van Dongen (англ.)
PyMC — модуль Python, що реалізує моделі та алгоритми підгонки баєсової статистики, включно з методом Монте-Карло марковських ланцюгів. (англ.)

[FOOTNOTEGill2008-1] Gill, 2008.

[FOOTNOTERobertCasella2004-2] Robert та Casella, 2004.

[3] Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (вид. Second Edition). CRC Press. с. xix. ISBN . (англ.)

[FOOTNOTEGreen1995-4] Green, 1995.

[dp13-5] Del Moral, Pierre (2013). . Chapman & Hall/CRC Press. с. 626. Архів оригіналу за 8 червня 2015. Процитовано 5 серпня 2015. Monographs on Statistics & Applied Probability (англ.)

[dp04-6] Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. с. 575. Series: Probability and Applications (англ.)

[dmm002-7] Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering (PDF). Т. 1729. с. 1—145. doi:10.1007/bfb0103798. {{}}: Проігноровано |journal= () (англ.)

[:3-8] . onlinelibrary.wiley.com. Архів оригіналу за 6 вересня 2015. Процитовано 11 червня 2015. (англ.)

[9] Chen, S., Josef Dick, and Art B. Owen. «Consistency of Markov chain quasi-Monte Carlo on continuous state spaces.» The Annals of Statistics 39.2 (2011): 673—701. (англ.)

[10] Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007. (англ.)

[11] Papageorgiou, Anargyros, and J. F. Traub. «Beating Monte Carlo.» Risk 9.6 (1996): 63-65. (англ.)

[12] Sobol, Ilya M. «On quasi-monte carlo integrations.» Mathematics and Computers in Simulation 47.2 (1998): 103—112. (англ.)

[FOOTNOTENeal2003-13] Neal, 2003.

[FOOTNOTEStramerTweedie1999-14] Stramer та Tweedie, 1999.