Skip to content
Назад к результатам поиска

Марковские цепи Монте-Карло (MCMC) — алгоритмы Метрополиса-Хастингса и Гиббса

Автор метода
Metropolis et al. (1953); Gibbs sampler formalised by Geman & Geman (1984)
Год
1953 (Metropolis-Hastings); 1984 (Gibbs)
Тип
Simulation-based Bayesian inference / numerical integration

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Разработанные Метрополисом и его коллегами в 1953 году и расширенные Хастингсом в 1970 году, алгоритмы MCMC лежат в основе современной байесовской статистики. Два наиболее широко используемых варианта — это Метрополиса-Хастингса, который предлагает переходы из общего распределения предложений, и выборка Гиббса, которая поочередно извлекает каждый параметр из его полного условного распределения.

Интуиция метода

Представьте, что вы хотите узнать форму горного хребта, скрытого в тумане. Вы не можете видеть его целиком, но можете сделать шаг в случайном направлении и решить, двигаться ли дальше, основываясь на том, выше или ниже находится земля. Достаточно долго гуляя и записывая, где вы побывали, вы обнаружите, что места, которые вы посещали чаще всего, очерчивают вершины — это и есть апостериорное распределение. Алгоритмы MCMC делают то же самое в пространстве параметров высокой размерности: они строят цепочку выборок, которая постепенно блуждает в областях высокой вероятности, так что гистограмма посещенных значений аппроксимирует целевое распределение, не требуя при этом явной аналитической формы этого распределения.

История

Фундаментальный алгоритм Метрополиса был опубликован в 1953 году Метрополисом, Розенблютом, Розенблютом, Теллером и Теллером для молекулярного моделирования. Хастингс (1970) обобщил его для асимметричных распределений предложений, создав алгоритм Метрополиса-Хастингса. Джеман и Джеман (1984) ввели выборку Гиббса в контексте восстановления изображений. Алгоритм стал основным статистическим инструментом в начале 1990-х годов после того, как Гельфанд и Смит (1990) продемонстрировали его широкую применимость для байесовских вычислений, а Гельман и Рубин (1992) предоставили диагностический критерий сходимости R̂. Последующая разработка Гамильтоновского Монте-Карло Дьюаном и др. (1987) и его автоматического варианта NUTS Хоффманом и Гельманом (2014) расширила MCMC на задачи высокой размерности. Байесовский анализ данных Гельмана и др. (2013) и Справочник по Марковским цепям Монте-Карло (Брукс и др., 2011) являются стандартными исчерпывающими справочниками.

Когда применять

MCMC является подходящим инструментом, когда байесовская модель специфицирована, а апостериорное распределение не может быть вычислено аналитически — что является обычным случаем для моделей с более чем несколькими параметрами или с не сопряженными априорными распределениями. Это также стандартный подход для моделей со скрытыми переменными, иерархических моделей и любых ситуаций, где неопределенность должна быть полностью распространена через сложный конвейер. Никаких предположений о распределении данных, кроме спецификации правдоподобия, не требуется. Основным практическим требованием является достаточное количество итераций для сходимости цепи: менее примерно 1 000 выборок после разогрева обычно не дают надежной характеристики апостериорного распределения, а в условиях высокой размерности требуется гораздо больше. Когда пространство параметров имеет очень высокую размерность, Гамильтоновский Монте-Карло (HMC) или Сэмплер без поворотов (NUTS) — автоматические расширения идеи MCMC — значительно эффективнее, чем базовый Метрополис-Хастингс.

Ограничения и замечания

  • Сходимость не гарантируется за конечное время; цепь, которая, кажется, сошлась, может все еще застрять в локальной области апостериорного распределения.
  • Автокорреляция между последовательными выборками означает, что эффективный размер выборки меньше фактического количества итераций, что требует более длительных запусков, чем потребовалось бы для эквивалентной независимой выборки.
  • В пространствах параметров высокой размерности случайное блуждание Метрополиса-Хастингса плохо смешивается; для эффективного исследования требуется Гамильтоновский Монте-Карло или NUTS.
  • Спецификация модели требует от аналитика вдумчивого выбора априорных распределений, а плохо выбранные априорные распределения или некорректно специфицированные функции правдоподобия могут сместить апостериорное распределение таким образом, что это будет трудно обнаружить.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Обеспечивает точный (асимптотически) байесовский вывод для моделей, где апостериорное распределение не имеет замкнутой формы, охватывая иерархические модели, задачи с пропущенными данными и сложные функции правдоподобия.
  • Производит полную совместную выборку апостериорного распределения, поэтому любая производная величина, прогноз или решение могут быть вычислены с правильно распространенной неопределенностью.
  • Применяется к непрерывным, бинарным и счетным исходам и не налагает никаких предположений о распределении данных, кроме заданного моделистом правдоподобия.
  • Запуск нескольких параллельных цепей делает проверку сходимости систематической с помощью диагностического критерия Гельмана-Рубина R̂.

Применение

  • Подгонка иерархических байесовских моделей в психологии, образовании и медицине, где данные сгруппированы и требуется частичное объединение (partial pooling).
  • Оценка параметров эпидемиологических компартментных моделей (SIR, SEIR) по наблюдаемым данным о случаях заболевания, включая количественную оценку неопределенности.
  • Байесовское моделирование структурных уравнений и модели со скрытыми переменными в социальных науках.
  • Апостериорный вывод для моделей теории отклика элементов (IRT) в образовательном измерении.
  • Калибровка сложных моделей моделирования против наблюдаемых данных, когда функция правдоподобия доступна, но не сопряжена.
  • Моделирование финансовых рисков и оценка опционов при байесовской неопределенности параметров.

Как это работает

Как это работает

1

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

2

Выбираются начальные значения для всех параметров, а также количество цепей, длина периода разогрева (burn-in) и общее количество итераций после разогрева. Стандартной практикой является запуск нескольких независимых цепей — обычно четырех — из разных начальных точек, поскольку это позволяет оценить сходимость путем сравнения цепей, а не полагаться на одну траекторию.

3

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

4

После отбрасывания начального периода (burn-in) оценивается сходимость. Статистика Гельмана-Рубина R̂ сравнивает дисперсию внутри цепи с дисперсией между цепями по нескольким цепям; значения ниже 1.05 указывают на то, что цепи смешались и сошлись к одному и тому же распределению. Также проверяются траекторные графики (последовательность выборочных значений по итерациям) и эффективный размер выборки. Если R̂ велико или траекторные графики показывают плохое смешивание, модель, априорные распределения или настройки сэмплера должны быть пересмотрены до начала вывода.

5

Коллекция выборок после периода разогрева формирует эмпирическую аппроксимацию апостериорного распределения. Точечные оценки (среднее или медиана апостериорного распределения), доверительные интервалы и апостериорные предсказательные распределения вычисляются непосредственно из выборки. Поскольку выборки являются реализациями совместного апостериорного распределения, любая производная величина — отношения, разности, нелинейные функции параметров — может быть оценена путем применения той же функции к каждой выборке и суммирования полученного распределения.

Частые ошибки

  • Пропуск или сокращение периода разогрева означает, что начальная нестационарная часть цепи загрязняет оценки апостериорного распределения — всегда отбрасывайте достаточный период разогрева.
  • Запуск только одной цепи делает невозможным обнаружение того, сошелся ли сэмплер или застрял в одной области; всегда запускайте как минимум четыре независимые цепи.
  • Рассмотрение большого фактического количества итераций как доказательства сходимости без вычисления R̂ или проверки траекторных графиков может дать ложную уверенность — требуется R̂ < 1.05, а не просто много итераций.
  • Игнорирование автокорреляции и представление эффективного размера выборки как фактического количества завышает точность; сообщайте эффективный размер выборки наряду с фактическим количеством.
  • Применение MCMC к модели с менее чем примерно 1 000 итерациями после разогрева, как правило, не даст надежного апостериорного распределения; если вычислительный бюджет так ограничен, рассмотрите аналитические байесовские методы или сопряженную модель.

Часто задаваемые вопросы

Как узнать, сошлась ли моя цепь MCMC?

Основным диагностическим критерием является статистика Гельмана-Рубина R̂, вычисляемая путем запуска как минимум четырех независимых цепей из разных начальных точек и сравнения дисперсии внутри цепи с дисперсией между цепями. Значения R̂ ниже 1.05 для всех параметров являются общепринятым порогом. Траекторные графики должны показывать цепи, которые перекрываются и исследуют одну и ту же область; траектории в форме воронки или дрейфующие указывают на плохое смешивание. Также следует проверить эффективный размер выборки — очень маленький эффективный размер выборки по сравнению с фактическим количеством указывает на высокую автокорреляцию и необходимость большего количества итераций или лучшего сэмплера.

В чем разница между Метрополисом-Хастингсом и выборкой Гиббса?

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

Когда следует использовать Гамильтоновский Монте-Карло вместо Метрополиса-Хастингса?

Гамильтоновский Монте-Карло (HMC) и его автоматический вариант NUTS используют информацию градиента логарифма апостериорного распределения для предложения больших, информированных переходов, которые тем не менее принимаются с высокой вероятностью. Это делает их гораздо более эффективными, чем случайное блуждание Метрополиса-Хастингса в пространствах параметров высокой размерности, где случайные предложения почти всегда отклоняются. Практическое правило: если ваша модель имеет более десяти параметров или если цепи Метрополиса-Хастингса демонстрируют плохое смешивание и очень низкие эффективные размеры выборки, рекомендуется перейти на HMC или NUTS.

Сколько итераций мне нужно?

Универсального ответа нет, но обычной отправной точкой является 1 000 итераций разогрева (burn-in) плюс 2 000 итераций выборки на цепь, всего четыре цепи, что дает 8 000 выборок после разогрева. Адекватность этого зависит от автокорреляции цепи и сложности апостериорного распределения. Цепь достаточна, когда R̂ < 1.05 для всех параметров, а эффективный размер выборки достаточно велик для характеристики интересующих признаков апостериорного распределения — обычно не менее нескольких сотен эффективных выборок для средних значений и нескольких тысяч для хвостовых квантилей.

Похожие методы

Источники

  1. Gelman, A., Carlin, J.B., Stern, H.S., Dunson, D.B., Vehtari, A. & Rubin, D.B. (2013). Bayesian Data Analysis (3rd ed.). Chapman & Hall/CRC.

    Открыть ссылку DOI
    Скопировано.
  2. Brooks, S., Gelman, A., Jones, G.L. & Meng, X.-L. (Eds.) (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC.

    Открыть ссылку DOI
    Скопировано.