- Алгоритм Метрополиса
-
Алгоритм Метрополиса — Гастингса — алгоритм семплирования, использующийся, в основном, для сложных функций распределения. Он отчасти похож на алгоритм выборки с отклонением, однако здесь вспомогательная функция распределения меняется со временем. Алгоритм был впервые опубликован Николасом Метрополисом в 1953 году, и затем обобщён К. Гастингсом в 1970 году. Семплирование по Гиббсу является частным случаем алгоритма Метрополиса — Гастингса и более популярно за счёт простоты и скорости, хотя и реже применимо.
Алгоритм Метрополиса-Гастингса позволяет семплировать любую функцию распределения. Он основан на создании цепи Маркова, то есть на каждом шаге алгоритма новое выбранное значение
зависит только от предыдущего
. Алгоритм использует вспомогательную функцию распределения
, зависящую от
, для которой генерировать выборку просто (например, нормальное распределение). На каждом шаге для этой функции генерируется случайное значение
. Затем с вероятностью
(или с вероятностью 1, если
), выбранное значение принимается как новое:
, а иначе оставляется старое:
.
Например, если взять нормальную функцию распределения как вспомогательную функцию, то
Такая функция выдаёт новое значение в зависимости от значения на предыдущем шаге. Изначально алгоритм Метрополиса требовал, чтобы вспомогательная функция была симметрична:
, однако обобщение Гастингса снимает это ограничение.
Алгоритм
Пусть мы уже выбрали случайное значение
. Для выбора следующего значения сначала получим случайное значение
для функции
. Затем найдем произведение
, где
является отношением вероятностей между промежуточным значением и предыдущим, а
это отношение между вероятностями пойти из
в
или обратно. Если
симметрична, то второй множитель равен 1. Случайное значение на новом шаге выбирается по правилу:
Алгоритм стартует из случайного значения
, и сначала прогоняется «вхолостую» некоторое количество шагов, чтобы «забыть» о начальном значении.
Лучше всего алгоритм работает тогда, когда форма вспомогательной функции близка к форме целевой функции
. Однако добиться этого априори зачастую невозможно. Для решения этой проблемы вспомогательную функцию настраивают в ходе подготовительной стадии работы алгоритма. Например, для нормального распределения настраивают его параметр
так, чтобы доля «принятых» случайных значений (то есть тех, для которых
) была близка к 60 %. Если
слишком мала, то значения будут получаться слишком близкими и доля принятых будет высока. Если
слишком велика, то с большой вероятностью новые значения будут выскакивать в зоны малой вероятности
, отчего доля принятых значений окажется низкой.
Для улучшения этой статьи желательно?: - Добавить иллюстрации.
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Категории:- Выборочный метод
- Метод Монте-Карло
Wikimedia Foundation. 2010.