Многократная попытка Метрополис

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

Фон

Проблемы с Метрополис – Гастингс

В цепи Маркова Монте - Карло алгоритм Метрополиса – Гастингса (MH) можно использовать для выборки из распределения вероятностей , из которого трудно выполнить выборку напрямую. Однако алгоритм MH требует от пользователя предоставления распределения предложений, которое может быть относительно произвольным. Во многих случаях используется распределение Гаусса с центром в текущей точке вероятностного пространства вида $Q(x';x^{t})={\mathcal {N}}(x^{t};\sigma ^{2}I)\,$ . Это распределение предложений удобно для выборки и может быть лучшим выбором, если у вас мало знаний о целевом распределении. $\pi (x)\,$ . При желании можно использовать более общее многомерное нормальное распределение , $Q(x';x^{t})={\mathcal {N}}(x^{t};\mathbf {\Sigma } )$ , где $\mathbf {\Sigma }$ — это ковариационная матрица, которая, по мнению пользователя, аналогична целевому распределению.

Хотя этот метод должен сходиться к стационарному распределению в пределе бесконечного размера выборки, на практике прогресс может быть чрезвычайно медленным. Если $\sigma ^{2}\,$ слишком велико, почти все шаги алгоритма MH будут отклонены. С другой стороны, если $\sigma ^{2}\,$ слишком мал, почти все шаги будут приняты, и цепь Маркова будет похожа на случайное блуждание по вероятностному пространству. В более простом случае $Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,$ , мы видим это $N\,$ шаги всего лишь ведут нас на расстояние ${\sqrt {N}}\,$ . В этом случае цепь Маркова не сможет полностью исследовать вероятностное пространство за разумный промежуток времени. Таким образом, алгоритм MH требует разумной настройки параметра масштаба ( $\sigma ^{2}\,$ или $\mathbf {\Sigma }$ ).

Проблемы с высокой размерностью

Даже если параметр масштаба настроен правильно, по мере увеличения размерности проблемы прогресс все равно может оставаться чрезвычайно медленным. Чтобы убедиться в этом, снова рассмотрим $Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,$ . В одном измерении это соответствует распределению Гаусса со средним значением 0 и дисперсией 1. Для одного измерения это распределение имеет средний шаг, равный нулю, однако среднеквадратичный размер шага определяется выражением

\langle x^{2}\rangle =\int _{-\infty }^{\infty }x^{2}{\frac {1}{\sqrt {2\pi }}}e^{-{\frac {x^{2}}{2}}}dx=1

По мере увеличения количества измерений ожидаемый размер шага становится все больше и больше. В $N\,$ размеры, вероятность перемещения на радиальное расстояние $r\,$ связано с распределением Чи и определяется выражением

P_{n}(r)\propto r^{n-1}e^{-r^{2}/2}

Это распределение достигает максимума $r={\sqrt {N-1}}\,$ который $\approx {\sqrt {N}}\,$ для больших $N\,$ . Это означает, что размер шага будет увеличиваться примерно пропорционально квадратному корню из числа измерений. Для алгоритма MH большие шаги почти всегда попадают в области с низкой вероятностью и, следовательно, отклоняются.

Если мы теперь добавим параметр масштаба $\sigma ^{2}\,$ вернувшись, мы обнаруживаем, что для сохранения разумной степени принятия мы должны выполнить преобразование $\sigma ^{2}\rightarrow \sigma ^{2}/N$ . В этой ситуации скорость принятия теперь можно сделать разумной, но исследование вероятностного пространства становится все более медленным. Чтобы убедиться в этом, рассмотрим срез по любому измерению проблемы. Выполнив приведенное выше преобразование масштаба, ожидаемый размер шага не будет равен ни одному измерению. $\sigma \,$ но вместо этого $\sigma /{\sqrt {N}}$ . Поскольку этот размер шага намного меньше «истинного» масштаба распределения вероятностей (при условии, что $\sigma \,$ каким-то образом известно априори, что является наилучшим возможным случаем), алгоритм выполняет случайное блуждание по каждому параметру.

Многократный алгоритм Метрополиса

Предполагать $Q(\mathbf {x} ,\mathbf {y} )$ — произвольная функция предложения . Мы требуем, чтобы $Q(\mathbf {x} ,\mathbf {y} )>0$ только если $Q(\mathbf {y} ,\mathbf {x} )>0$ . Кроме того, $\pi (\mathbf {x} )$ — функция правдоподобия.

Определять $w(\mathbf {x} ,\mathbf {y} )=\pi (\mathbf {x} )Q(\mathbf {x} ,\mathbf {y} )\lambda (\mathbf {x} ,\mathbf {y} )$ где $\lambda (\mathbf {x} ,\mathbf {y} )$ является неотрицательной симметричной функцией в $\mathbf {x}$ и $\mathbf {y}$ который может выбрать пользователь.

Теперь предположим, что текущее состояние $\mathbf {x}$ . Алгоритм МТМ следующий:

1) Нарисуйте k независимых предложений по испытаниям. $\mathbf {y} _{1},\ldots ,\mathbf {y} _{k}$ от $Q(\mathbf {x} ,.)$ . Вычислить веса $w(\mathbf {y} _{j},\mathbf {x} )$ для каждого из них.

2) Выберите $\mathbf {y}$ из $\mathbf {y} _{i}$ с вероятностью, пропорциональной весам.

3) Теперь создайте эталонный набор, нарисовав $\mathbf {x} _{1},\ldots ,\mathbf {x} _{k-1}$ из распределения $Q(\mathbf {y} ,.)$ . Набор $\mathbf {x} _{k}=\mathbf {x}$ (текущая точка).

4) Принять $\mathbf {y}$ с вероятностью

r={\text{min}}\left(1,{\frac {w(\mathbf {y} _{1},\mathbf {x} )+\ldots +w(\mathbf {y} _{k},\mathbf {x} )}{w(\mathbf {x} _{1},\mathbf {y} )+\ldots +w(\mathbf {x} _{k},\mathbf {y} )}}\right)

Можно показать, что этот метод удовлетворяет свойству детального баланса и, следовательно, создает обратимую цепь Маркова с $\pi (\mathbf {x} )$ как стационарное распределение.

Если $Q(\mathbf {x} ,\mathbf {y} )$ симметрично (как и в случае многомерного нормального распределения ), то можно выбрать $\lambda (\mathbf {x} ,\mathbf {y} )={\frac {1}{Q(\mathbf {x} ,\mathbf {y} )}}$ что дает $w(\mathbf {x} ,\mathbf {y} )=\pi (\mathbf {x} )$ .

Недостатки

Многократная попытка Метрополису необходимо вычислить энергию $2k-1$ другие государства на каждом шагу.Если медленная часть процесса — вычисление энергии, то этот метод может быть медленнее.Если медленная часть процесса — это поиск соседей данной точки или генерация случайных чисел, то этот метод опять же может быть медленнее.Можно утверждать, что этот метод кажется быстрее только потому, что он требует гораздо больше вычислений за «один шаг», чем это делает Метрополис-Гастингс.

См. также

Ссылки

Лю, Дж. С., Лян, Ф. и Вонг, WH (2000). Метод множественных попыток и локальная оптимизация выборки в мегаполисе, Журнал Американской статистической ассоциации , 95 (449): 121–134 JSTOR.