WikiDer > Метрополис с несколькими попытками

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

Фон

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

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

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

Это распределение достигает максимума в ${ Displaystyle г = { sqrt {N-1}} ,}$ который ${ Displaystyle приблизительно { 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 пи ( mathbf {х})}$ - функция правдоподобия.

Определять ${ Displaystyle вес ( 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 ш ( 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 пи ( mathbf {х})}$ как стационарное распределение.

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

Недостатки

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

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

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

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

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