Почему гамильтонова динамика лучше, чем предложение случайного блуждания в MCMC в некоторых случаях?

Гамильтонова динамика всегда превосходит случайное блуждание в алгоритме Метрополиса в некоторых случаях. Может ли кто-нибудь объяснить причину простыми словами без особой математики?

Прежде всего, позвольте мне заявить, что я не верю, что показатель приемлемости для HMC (гамильтониана Монте-Карло) всегда выше, чем для алгоритма Метрополиса. Как отмечает @JuhoKokkala, скорость приема Metropolis является настраиваемой, а высокая скорость принятия не означает, что ваш алгоритм хорошо справляется с изучением апостериорного распределения. Если вы просто используете чрезвычайно узкое распределение предложений (например, с очень маленькой ), вы получите чрезвычайно высокий уровень принятия, но только потому, что вы в основном всегда находитесь в одном и том же месте, не изучая полное последующее распределение.$T(q|q')=\mathcal{N}(q',\sigma I)$$\sigma$

Я думаю, что вы действительно спрашиваете (и если я прав, тогда, пожалуйста, измените ваш вопрос соответственно), почему гамильтониан Монте-Карло имеет (в некоторых случаях) лучшую производительность, чем Metropolis. Под «лучшей производительностью» я подразумеваю, что для многих приложений, если вы сравниваете цепочку, сгенерированную HMC, с цепочкой равной длины (с тем же числом выборок ), сгенерированной алгоритмом Метрополиса, цепочка HMC достигает устойчивого состояния раньше, чем Цепочка метрополии находит меньшее значение для отрицательного логарифмического правдоподобия (или аналогичное значение, но с меньшим количеством итераций), эффективный размер выборки меньше, автокорреляция выборок затухает быстрее с задержкой и т. Д.$N$

Я попытаюсь дать представление о том, почему это происходит, не вдаваясь в математические детали. Итак, прежде всего напомним, что алгоритмы MCMC в целом полезны для вычисления многомерных интегралов (ожиданий) функции (или нескольких функций) относительно целевой плотности , особенно когда у нас нет способ прямого отбора проб из целевой плотности:$f$$\pi(q)$

$\mathbb{E}_{\pi}{[f]}=\int_{\mathcal{Q}} f(q)\pi(q)\text{d}q_1\dots\text{d}q_d$

где - вектор параметров от которых зависят и , а - пространство параметров. Теперь в больших измерениях объем пространства параметров, который вносит наибольший вклад в приведенный выше интеграл, не является окрестностью моды (т. Е. Это не узкий объем вокруг оценки MLE для ), потому что здесь большой, но объем очень маленький.$q$$d$$f$$\pi$$\mathcal{Q}$$\pi(q)$$q$$\pi(q)$

Например, предположим, что вы хотите вычислить среднее расстояние точки от начала координат , когда ее координаты являются независимыми гауссовыми переменными с нулевым средним и единичной дисперсией. Тогда вышеуказанный интеграл становится:$q$$\mathbb{R}^d$

$\mathbb{E}_{\pi}{[X]}=\int_{\mathcal{Q}} ||q||(2\pi)^{-d/2}\exp{(-||q||^2/2)}\text{d}q_1\dots\text{d}q_d$

Теперь целевая плотность , очевидно, имеет максимум в 0. Однако, изменяя сферическим координатам и введя, вы можете видеть, что подынтегральное выражение становится пропорциональным . Эта функция имеет максимум на некотором расстоянии от начала координат. Область внутри которая вносит наибольший вклад в значение интеграла, называется типичным набором , и для этого интеграла типичный набор представляет собой сферическую оболочку радиуса . г = | | q | | г д - 1 ехр ( - г 2 / 2 ) d R Q R & alpha ; $\pi(q)=(2\pi)^{-d/2}\exp{(-||q||^2/2)}$$r=||q||$$r^{d-1}\exp{(-r^2/2)} \text{d}r$$\mathcal{Q}$$R\propto\sqrt{d}$

Теперь можно показать, что в идеальных условиях цепь Маркова, генерируемая MCMC, сначала сходится к точке в типичном наборе, затем начинает исследовать весь набор и, наконец, продолжает исследовать детали этого набора. При этом оценка ожиданий MCMC становится все более и более точной, с отклонениями и отклонениями, которые уменьшаются с увеличением количества шагов.

Однако, когда геометрия типичного набора является сложной (например, если он имеет изгиб в двух измерениях), тогда стандартный алгоритм Метрополиса с случайным блужданием сталкивается с большими трудностями при исследовании «патологических» деталей набора. Он имеет тенденцию случайным образом «прыгать» вокруг этих регионов, не исследуя их. На практике это означает, что оценочное значение для интеграла имеет тенденцию колебаться вокруг правильного значения, и прерывание цепочки за конечное число шагов приведет к плохо смещенной оценке.

Гамильтониан Монте-Карло пытается преодолеть эту проблему, используя информацию, содержащуюся в целевом распределении (в ее градиенте), чтобы информировать предложение о новой точке выборки, вместо того, чтобы просто использовать распределение предложения, не связанное с целевым. Поэтому мы говорим, что HMC использует производные от целевого распределения для более эффективного исследования пространства параметров. Тем не менее, градиент целевого распределения, сам по себе, не достаточно , чтобы сообщить об этом шаге предложения. Как в примере среднего расстояния случайной точки от начала координат$\mathbb{R}^d$градиент распределения цели сам по себе направляет нас к моде распределения, но область вокруг моды не обязательно является областью, которая вносит наибольший вклад в приведенный выше интеграл, т. е. не является типичным набором.

Чтобы получить правильное направление, в HMC мы вводим вспомогательный набор переменных, называемый переменными импульса . Физический аналог может помочь здесь. Спутник, вращающийся вокруг планеты, будет оставаться на стабильной орбите только в том случае, если его импульс имеет «правильное» значение, в противном случае он либо улетит в открытое пространство, либо будет притянут к планете гравитационным притяжением (здесь играет роль градиента плотности цели, который «тянет» к моде). Таким же образом, параметры импульса играют роль сохранения новых выборок внутри типичного набора, вместо того, чтобы они дрейфовали к хвостам или моде.

Это небольшое резюме очень интересной статьи Майкла Бетанкура об объяснении гамильтониана Монте-Карло без излишней математики. Вы можете найти статью, которая более подробно описана здесь .

ИМО, в статье не освещается достаточно подробно, когда и почему HMC может работать хуже, чем Метрополис со случайной прогулкой. Это случается не часто (по моему ограниченному опыту), но это может случиться. В конце концов, вы вводите градиенты, которые помогают вам найти свой путь в многомерном пространстве параметров, но также удваивает размерность задачи. Теоретически может случиться так, что замедление из-за увеличения размерности преодолеет ускорение, вызванное использованием градиентов. Также (и это рассматривается в статье), если типичный набор имеет области высокой кривизны, HMC может «перескочить», т. Е. Он может начать выборку бесполезных точек очень далеко в хвостах, которые ничего не вносят в ожидание. Однако, это вызывает нестабильность симплектического интегратора, который используется на практике для численной реализации HMC. Таким образом, такая проблема легко диагностируется.

Как отметил @JuhoKokkala в комментариях, высокая скорость принятия не обязательно дает хорошую производительность. Уровень принятия Metropolis Hastings может быть увеличен за счет сокращения распространения предложений. Но это приведет к тому, что будут предприняты меньшие шаги, что потребует больше времени для изучения целевого распределения. На практике существует компромисс между размером шага и скоростью принятия, и для достижения хорошей производительности необходим надлежащий баланс.

Гамильтониан Монте-Карло имеет тенденцию превосходить Metropolis Hastings, потому что он может достигать более отдаленных точек с более высокой вероятностью принятия. Итак, вопрос: почему HMC имеет более высокую вероятность принятия, чем MH для более отдаленных точек ?

MH испытывает трудности с достижением отдаленных точек, потому что его предложения делаются без использования информации о целевом распределении. Распределение предложений обычно изотропно (например, симметрично по Гауссу). Таким образом, в каждой точке алгоритм пытается переместить произвольное расстояние в случайном направлении. Если расстояние мало по сравнению с тем, как быстро изменяется распределение цели в этом направлении, есть большая вероятность того, что плотность в текущей и новой точках будет одинаковой, что даст по крайней мере разумный шанс принятия. На больших расстояниях распределение целей могло немного измениться относительно текущей точки. Таким образом, шанс случайного нахождения точки с аналогичной или (мы надеемся) более высокой плотностью может быть плохим, особенно по мере увеличения размерности. Например, если текущая точка лежит на узком гребне,

В отличие от этого, HMC использует структуру целевого распределения. В качестве механизма предложения можно использовать физическую аналогию, как описано в Neal (2012). Представьте шайбу, скользящую по холмистой поверхности без трения. Местоположение шайбы представляет текущую точку, а высота поверхности представляет собой отрицательное логарифм распределения цели. Чтобы получить новую предложенную точку, шайбе дается импульс со случайным направлением и величиной, и ее динамика затем моделируется при скольжении по поверхности. Шайба будет ускоряться в наклонных направлениях и замедляться в наклонных направлениях (возможно, даже останавливаясь и снова скатываясь вниз). Траектории, движущиеся вбок вдоль стены долины, будут изгибаться вниз. Таким образом, сам ландшафт влияет на траекторию и тянет ее к областям с более высокой вероятностью. Импульс может позволить шайбе перебираться через небольшие холмы, а также преодолевать небольшие бассейны. Расположение шайбы через некоторое количество временных шагов дает новую предложенную точку, которая принимается или отклоняется с использованием стандартного правила метрополии. Использование целевого распределения (и его градиента) - это то, что позволяет HMC достигать отдаленных точек с высокими показателями приемлемости.

Вот хороший обзор:

Нил (2012) . MCMC с использованием гамильтоновой динамики.

В качестве свободного ответа (что, кажется, то, что вы ищете) гамильтоновы методы учитывают производную логарифмической вероятности, в то время как стандартный алгоритм МН - нет.