Методи Монте-Карло марковських ланцюгів

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

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

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

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

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

Приклади

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

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

Збіжність

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

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

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

Див. також

• Баєсове висновування
• Баєсова мережа
• Спаровування з минулого
• Вибірка за Ґіббсом
• Метод квазі-Монте-Карло
• Гібридний алгоритм Монте-Карло
• Алгоритм Метрополіса — Гастінгса
• Багатоспробовий метод Метрополіса
• Частинковий фільтр
• Реверсивно-стрибковий
• Вибірка за рівнями

Джерела

• 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). (англ.)
• Berg, Bernd A. (2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis. World Scientific. (англ.)
• Bolstad, William M. (2010). Understanding Computational Bayesian Statistics. Wiley. ISBN 0-470-04609-0. (англ.)
• Casella, George; George, Edward I. (1992). Explaining the Gibbs sampler. The American Statistician. 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. Journal of the American Statistical Association. 85: 398—409. doi:10.1080/01621459.1990.10476213. (англ.)
• Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. (1995). Bayesian Data Analysis (вид. 1st). Chapman & Hall. (See Chapter 11.) (англ.)
• Geman, S.; Geman, D. (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence. 6: 721—741. (англ.)
• Gilks, W.R.; Richardson, S.; Spiegelhalter, D.J. (1996). Markov Chain Monte Carlo in Practice. Chapman & Hall/CRC. (англ.)
• Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach (вид. 2nd). Chapman & Hall/CRC. ISBN 1-58488-562-9. (англ.)
• Green, P.J. (1995). Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika. 82 (4): 711—732. doi:10.1093/biomet/82.4.711. (англ.)
• Neal, Radford M. (2003). Slice Sampling. Annals of Statistics. 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 0-387-21239-6. (англ.)
• Rubinstein, R.Y.; Kroese, D.P. (2007). Simulation and the Monte Carlo Method (вид. 2nd). Wiley. ISBN 978-0-470-17794-5. (англ.)
• Smith, R.L. (1984). Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions. Operations Research. 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. (англ.)

Література

• Diaconis, Persi (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. (англ.)
• 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), Cambridge University Press, ISBN 978-0-521-88068-8 (англ.)
• 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, що реалізує моделі та алгоритми підгонки баєсової статистики, включно з методом Монте-Карло марковських ланцюгів. (англ.)