Метрополис с несколькими попытками - Multiple-try Metropolis

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

Фон

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь предположим, что текущее состояние ${\displaystyle \mathbf {x} }$. Алгоритм MTM выглядит следующим образом:

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

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

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

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

${\displaystyle 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)}$

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

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

Недостатки

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

Смотрите также

• Цепь Маркова Монте-Карло
• Алгоритм Метрополиса – Гастингса
• Детальный баланс

Рекомендации

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