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

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

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

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

Області застосування ред.

Класифікація ред.

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

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

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

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

Приклади ред.

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

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

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

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

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

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

Приклади ред.

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

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

Збіжність ред.

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

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

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

Див. також ред.

Примітки ред.

  1. Gill, 2008.
  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 978-1-4398-1917-3.  (англ.)
  4. Green, 1995.
  5. Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. с. 626. Архів оригіналу за 8 червня 2015. Процитовано 5 серпня 2015. «Monographs on Statistics & Applied Probability»  (англ.)
  6. Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. с. 575. «Series: Probability and Applications»  (англ.)
  7. Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering.. Lecture Notes in Mathematics. Т. 1729. с. 1–145. doi:10.1007/bfb0103798.  (англ.)
  8. 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. 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. (англ.)
  13. Neal, 2003.
  14. Stramer та Tweedie, 1999.

Джерела ред.

Література ред.

Посилання ред.