Алгоритм Метрополиса — Гастингса — Википедия

Алгоритм Метрополиса — Гастингса — алгоритм семплирования, использующийся, в основном, для сложных функций распределения. Он отчасти похож на алгоритм выборки с отклонением, однако здесь вспомогательная функция распределения меняется со временем. Алгоритм был впервые опубликован Николасом Метрополисом в 1953 году, и затем обобщён К. Гастингсом в 1970 году. Семплирование по Гиббсу является частным случаем алгоритма Метрополиса — Гастингса и более популярно за счёт простоты и скорости, хотя и реже применимо.

Алгоритм Метрополиса — Гастингса позволяет семплировать любую функцию распределения. Он основан на создании цепи Маркова, то есть на каждом шаге алгоритма новое выбранное значение ${\displaystyle x^{t+1}}$ зависит только от предыдущего ${\displaystyle x^{t}}$. Алгоритм использует вспомогательную функцию распределения ${\displaystyle Q(x'|x^{t})}$, зависящую от ${\displaystyle x^{t}}$, для которой генерировать выборку просто (например, нормальное распределение). На каждом шаге для этой функции генерируется случайное значение ${\displaystyle x'}$. Затем с вероятностью

${\displaystyle u={\frac {P(x')Q(x^{t}|x')}{P(x^{t})Q(x'|x^{t})}}}$

(или с вероятностью 1, если ${\displaystyle u>1}$), выбранное значение принимается как новое: ${\displaystyle x^{t+1}=x'}$, а иначе оставляется старое: ${\displaystyle x^{t+1}=x^{t}}$.

Например, если взять нормальную функцию распределения как вспомогательную функцию, то

${\displaystyle Q(x'|x^{t})\sim N(x^{t},\sigma ^{2}I).}$

Такая функция выдаёт новое значение в зависимости от значения на предыдущем шаге. Изначально алгоритм Метрополиса требовал, чтобы вспомогательная функция была симметрична: ${\displaystyle Q(x',x^{t})=Q(x^{t},x')}$, однако обобщение Гастингса снимает это ограничение.

Алгоритм[править | править код]

Пусть мы уже выбрали случайное значение ${\displaystyle x^{t}}$. Для выбора следующего значения сначала получим случайное значение ${\displaystyle x'}$ для функции ${\displaystyle Q(x'|x^{t})}$. Затем найдем произведение ${\displaystyle a=a_{1}a_{2}}$, где

${\displaystyle a_{1}={\frac {P(x')}{P(x^{t})}}}$

является отношением вероятностей между промежуточным значением и предыдущим, а

${\displaystyle a_{2}={\frac {Q(x^{t}|x')}{Q(x'|x^{t})}}}$

это отношение между вероятностями пойти из ${\displaystyle x'}$ в ${\displaystyle x^{t}}$ или обратно. Если ${\displaystyle Q}$ симметрична, то второй множитель равен 1. Случайное значение на новом шаге выбирается по правилу:

${\displaystyle {\begin{matrix}{\mbox{If }}a\geq 1:&\\&x^{t+1}=x',\end{matrix}}}$

${\displaystyle {\begin{matrix}{\mbox{and if }}a<1:&\\&x^{t+1}=\left\{{\begin{matrix}x'{\mbox{ with probability }}a\\x^{t}{\mbox{ with probability }}1-a.\end{matrix}}\right.\end{matrix}}}$

Алгоритм стартует из случайного значения ${\displaystyle x^{0}}$, и сначала прогоняется «вхолостую» некоторое количество шагов, чтобы «забыть» о начальном значении.

Лучше всего алгоритм работает тогда, когда форма вспомогательной функции близка к форме целевой функции ${\displaystyle P}$. Однако добиться этого априори зачастую невозможно. Для решения этой проблемы вспомогательную функцию настраивают в ходе подготовительной стадии работы алгоритма. Например, для нормального распределения настраивают его параметр ${\displaystyle \sigma ^{2}}$ так, чтобы доля «принятых» случайных значений (то есть тех, для которых ${\displaystyle x^{t+1}=x'}$) была близка к 60 %. Если ${\displaystyle \sigma ^{2}}$ слишком мала, то значения будут получаться слишком близкими и доля принятых будет высока. Если ${\displaystyle \sigma ^{2}}$ слишком велика, то с большой вероятностью новые значения будут выскакивать в зоны малой вероятности ${\displaystyle P}$, отчего доля принятых значений окажется низкой.

Для улучшения этой статьи желательно: Добавить иллюстрации. Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.