Русская Википедия:Алгоритм Метрополиса — Гастингса
Алгоритм Метрополиса — Гастингса — алгоритм семплирования, использующийся, в основном, для сложных функций распределения. Он отчасти похож на алгоритм выборки с отклонением, однако здесь вспомогательная функция распределения меняется со временем. Алгоритм был впервые опубликован Николасом Метрополисом в 1953 году, и затем обобщён К. Гастингсом в 1970 году. Семплирование по Гиббсу является частным случаем алгоритма Метрополиса — Гастингса и более популярно за счёт простоты и скорости, хотя и реже применимо.
Алгоритм Метрополиса — Гастингса позволяет семплировать любую функцию распределения. Он основан на создании цепи Маркова, то есть на каждом шаге алгоритма новое выбранное значение <math>x^{t+1}</math> зависит только от предыдущего <math>x^t</math>. Алгоритм использует вспомогательную функцию распределения <math>Q(x'|x^t)</math>, зависящую от <math>x^t</math>, для которой генерировать выборку просто (например, нормальное распределение). На каждом шаге для этой функции генерируется случайное значение <math>x'</math>. Затем с вероятностью
<math>u = \frac{P(x')Q(x^{t}|x')}{P(x^{t})Q(x'|x^{t})}</math>
(или с вероятностью 1, если <math>u > 1</math>), выбранное значение принимается как новое: <math>x^{t+1} = x'</math>, а иначе оставляется старое: <math>x^{t+1} = x^{t}</math>.
Например, если взять нормальную функцию распределения как вспомогательную функцию, то
<math> Q( x'| x^t ) \sim N( x^t, \sigma^2 I). </math>
Такая функция выдаёт новое значение в зависимости от значения на предыдущем шаге. Изначально алгоритм Метрополиса требовал, чтобы вспомогательная функция была симметрична: <math>Q(x',x^t) = Q(x^t,x')</math>, однако обобщение Гастингса снимает это ограничение.
Алгоритм
Пусть мы уже выбрали случайное значение <math>x^t</math>. Для выбора следующего значения сначала получим случайное значение <math>x'</math> для функции <math>Q(x'|x^t)</math>. Затем найдем произведение <math>a = a_1a_2</math>, где
<math>a_1 = \frac{P(x')}{P(x^t)}</math>
является отношением вероятностей между промежуточным значением и предыдущим, а
<math>a_2 = \frac{Q(x^t|x')}{Q(x'|x^t)}</math>
это отношение между вероятностями пойти из <math>x'</math> в <math>x^t</math> или обратно. Если <math>Q</math> симметрична, то второй множитель равен 1. Случайное значение на новом шаге выбирается по правилу:
- <math>
\begin{matrix} \mbox{If } a \geq 1: & \\ & x^{t+1} = x', \end{matrix} </math>
- <math>
\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} </math>
Алгоритм стартует из случайного значения <math>x^0</math>, и сначала прогоняется «вхолостую» некоторое количество шагов, чтобы «забыть» о начальном значении.
Лучше всего алгоритм работает тогда, когда форма вспомогательной функции близка к форме целевой функции <math>P</math>. Однако добиться этого априори зачастую невозможно. Для решения этой проблемы вспомогательную функцию настраивают в ходе подготовительной стадии работы алгоритма. Например, для нормального распределения настраивают его параметр <math>\sigma^2</math> так, чтобы доля «принятых» случайных значений (то есть тех, для которых <math>x^{t+1} = x'</math>) была близка к 60 %. Если <math>\sigma^2</math> слишком мала, то значения будут получаться слишком близкими и доля принятых будет высока. Если <math>\sigma^2</math> слишком велика, то с большой вероятностью новые значения будут выскакивать в зоны малой вероятности <math>P</math>, отчего доля принятых значений окажется низкой.
