Оглавление
- 1 Алгоритм Метрополиса–Гастингса
- 1.1 История алгоритма Метрополиса–Гастингса
- 1.2 Описание алгоритма
- 1.3 Процесс работы алгоритма
- 1.4 Функции предложения
- 1.5 Недостатки алгоритмов MCMC
- 1.6 Проблема “проклятия размерности”
- 1.7 Алгоритм Метрополиса–Гастингса
- 1.8 Выборка Гиббса
- 1.9 Формальный вывод
- 1.10 Использование в численном интегрировании
- 1.11 Настройка параметров гауссовой плотности предложения
- 1.12 Влияние размера выборки на сходимость
- 1.13 Байесовский вывод с помощью MCMC
- 1.14 Дополнительные методы и рекомендации
- 1.15 Полный текст статьи:
- 2 Алгоритм Метрополиса – Гастингса
Алгоритм Метрополиса–Гастингса
-
История алгоритма Метрополиса–Гастингса
- Алгоритм назван в честь Николаса Метрополиса и У.К. Гастингса.
- В 1953 году предложен для симметричного распределения предложений.
- В 1970 году Гастингс расширил алгоритм до более общего случая.
- В 2003 году Розенблют описал алгоритм и его разработку.
-
Описание алгоритма
- Алгоритм генерирует последовательность выборок из распределения вероятностей.
- Требует знания функции, пропорциональной плотности вероятности.
- Использует функцию предложения для генерации новых кандидатов.
-
Процесс работы алгоритма
- На каждой итерации предлагается кандидат для следующего выборочного значения.
- Кандидат либо принимается, либо отклоняется в зависимости от значения функции.
- Вероятность принятия определяется сравнением значений функции.
-
Функции предложения
- Обычно используется гауссово распределение с центром в текущей выборке.
- Возможны более сложные функции, такие как функции Гамильтониана Монте-Карло.
-
Недостатки алгоритмов MCMC
- Выборки автокоррелированы, что приводит к ошибкам.
- Необходим период доводки для удаления первоначальных выборок.
-
Проблема “проклятия размерности”
- Простые методы отбора проб с отбраковкой страдают от экспоненциального роста вероятности отбраковки с увеличением количества измерений.
- Методы MCMC, такие как Metropolis–Hastings, не сталкиваются с этой проблемой и часто предпочтительны для многомерных распределений.
-
Алгоритм Метрополиса–Гастингса
- Использует марковский процесс для достижения стационарного распределения, соответствующего целевому распределению.
- Процесс определяется переходными вероятностями, удовлетворяющими условиям существования и уникальности стационарного распределения.
- Алгоритм включает выборку нового состояния на основе предложения и принятие-отклонение.
-
Выборка Гиббса
- Альтернативный подход, который лучше работает при большом количестве измерений.
- Выборка новой точки для каждого измерения отдельно, что сводит проблему к набору задач для выборки из малой размерности.
- Используются различные алгоритмы для выбора отдельных выборок, включая адаптивную выборку с отбраковкой и простой одномерный шаг Метрополиса-Гастингса.
-
Формальный вывод
- Цель алгоритма Метрополиса–Гастингса — сгенерировать набор состояний в соответствии с целевым распределением.
- Процесс включает выборку нового состояния на основе предложения и принятие-отклонение.
- Количество итераций зависит от взаимосвязи между целевым распределением и распределением предложений.
-
Использование в численном интегрировании
- Алгоритм используется для вычисления интегралов, таких как оценка вероятности события на хвосте распределения.
- Выборка редких состояний увеличивает количество выборок для оценки вероятности.
- Плотность предложения должна соответствовать форме целевого распределения для оптимальной работы алгоритма.
-
Настройка параметров гауссовой плотности предложения
- Гауссова плотность предложения g используется для настройки параметра дисперсии σ2.
- Коэффициент приемлемости рассчитывается как доля принятых образцов за последний период времени.
- Идеальный уровень приемлемости для одномерного гауссова распределения составляет около 50%, снижаясь до 23% для многомерного гауссова распределения.
-
Влияние размера выборки на сходимость
- Если σ2 слишком мал, цепочка будет перемешиваться медленно.
- Если σ2 слишком велик, уровень приемлемости будет низким, и цепочка будет сходиться медленно.
- Обычно распределение предложений настраивается так, чтобы алгоритмы принимали около 30% всех выборок.
-
Байесовский вывод с помощью MCMC
- MCMC используется для получения выборок из апостериорного распределения статистической модели.
- Вероятность принятия определяется по формуле, включающей вероятности L, P и Q.
-
Дополнительные методы и рекомендации
- Генетические алгоритмы, методы определения частиц в среднем поле, легкий транспорт мегаполиса, мегаполис с несколькими попытками, параллельный отпуск, последовательный метод Монте-Карло, имитация отжига.
- Рекомендации включают книги и статьи по моделированию цепей Маркова методом Монте-Карло и байесовской статистике.