Алгоритм Метрополиса – Гастингса

редактировать
Предложение распределения Q предлагает следующую точку, в которой случайное блуждание может двигаться.

В статистических данных и статистической физики, то Метрополиса-Гастингс алгоритм является цепь Маркова Монте - Карло метод (MCMC) для получения последовательности случайных выборок из распределения вероятностей, из которых прямой выборки трудно. Эта последовательность может использоваться для аппроксимации распределения (например, для создания гистограммы ) или для вычисления интеграла (например, ожидаемого значения ). Метрополис – Гастингс и другие алгоритмы MCMC обычно используются для выборки из многомерных распределений, особенно когда количество измерений велико. Для одномерных распределений обычно существуют другие методы (например, выборка с адаптивным отклонением ), которые могут напрямую возвращать независимые выборки из распределения, и они свободны от проблемы автокоррелированных выборок, присущей методам MCMC.

СОДЕРЖАНИЕ

  • 1 История
  • 2 Интуиция
  • 3 Формальное происхождение
  • 4 Использование в численном интегрировании
  • 5 Пошаговая инструкция
  • 6 См. Также
  • 7 ссылки
  • 8 Примечания
  • 9 Дальнейшее чтение

История

Алгоритм был назван в честь Николаса Метрополиса, который вместе с Арианной У. Розенблут, Маршаллом Розенблутом, Августой Х. Теллер и Эдвардом Теллером написал статью « Уравнение вычислений состояния с помощью быстрых вычислительных машин» в 1953 году. В этой статье был предложен алгоритм для случая симметричных распределений предложений, и В.К. Гастингс распространил его на более общий случай в 1970 году.

Некоторые разногласия существуют относительно кредита на разработку алгоритма. Метрополис, который был знаком с вычислительными аспектами этого метода, ввел термин «Монте-Карло» в более раннюю статью со Станиславом Уламом и возглавил группу в Теоретическом отделе, которая разработала и построила компьютер MANIAC I, который использовался в экспериментах в 1952. Однако до 2003 года подробного описания развития алгоритма не существовало. Затем, незадолго до своей смерти, Маршалл Розенблют посетил конференцию 2003 года в LANL, посвященную 50-летию публикации 1953 года. На этой конференции Розенблют описал алгоритм и его развитие в презентации под названием «Генезис алгоритма Монте-Карло для статистической механики». Дальнейшее историческое разъяснение сделано Губернатисом в журнальной статье 2005 года, посвященной 50-летию конференции. Розенблют ясно дает понять, что он и его жена Арианна сделали работу, и что Метрополис не играл никакой роли в разработке, кроме предоставления компьютерного времени.

Это противоречит рассказу Эдварда Теллера, который утверждает в своих мемуарах, что пять авторов статьи 1953 года работали вместе «днями (и ночами)». Напротив, в подробном отчете Розенблюта Теллер сделал важное, но раннее предложение «воспользоваться статистической механикой и взять средние по совокупности вместо того, чтобы следовать детальной кинематике». Это, как говорит Розенблут, побудило его задуматься об обобщенном подходе Монте-Карло - теме, которую, по его словам, он часто обсуждал с Джоном фон Нейманом. Арианна Розенблут рассказала (Губернатису в 2003 году), что Августа Теллер начала работу на компьютере, но сама Арианна взяла на себя ее и написала код с нуля. В устной истории, записанной незадолго до своей смерти, Розенблют снова приписывает Теллеру постановку исходной проблемы, его решение, а Арианну - программирование компьютера. Что касается репутации, у Розенблюта нет особых причин подвергать сомнению его версию. В биографических мемуарах Розенблута Фримен Дайсон пишет:

Я много раз приходил к Розенблюту, задавал ему вопрос [...] и получал ответ через две минуты. Затем мне обычно требовалась неделя напряженной работы, чтобы в деталях понять, почему ответ Розенблута был правильным. У него была удивительная способность видеть сложные физические ситуации и находить правильный ответ с помощью физических аргументов. Энрико Ферми был единственным из известных мне физиков, равным Розенблюту в его интуитивном понимании физики.

Интуиция

Алгоритм Метрополис-Гастингс может отбирать образцы из любого распределения вероятностей с плотностью вероятности, при условии, что мы знаем функцию, пропорциональные плотности и значения могут быть вычислены. Требование, которое должно быть только пропорционально плотности, а не точно равной ей, делает алгоритм Метрополиса – Гастингса особенно полезным, поскольку вычисление необходимого коэффициента нормализации на практике часто бывает чрезвычайно трудным. п ( Икс ) {\ Displaystyle P (x)} ж ( Икс ) {\ displaystyle f (x)} п {\ displaystyle P} ж ( Икс ) {\ displaystyle f (x)} ж ( Икс ) {\ displaystyle f (x)}

Алгоритм Метрополиса – Гастингса работает, генерируя последовательность выборочных значений таким образом, что по мере создания все большего количества выборочных значений распределение значений более точно приближается к желаемому распределению. Эти значения выборки производятся итеративно, при этом распределение следующей выборки зависит только от текущего значения выборки (таким образом, последовательность выборок превращается в цепь Маркова ). В частности, на каждой итерации алгоритм выбирает кандидата для следующего значения выборки на основе текущего значения выборки. Затем с некоторой вероятностью кандидат либо принимается (в этом случае значение кандидата используется в следующей итерации), либо отклоняется (в этом случае значение кандидата отбрасывается, а текущее значение повторно используется в следующей итерации) - вероятность приемлемости определяется путем сравнения значений функции текущего и потенциального значений выборки по отношению к желаемому распределению. ж ( Икс ) {\ displaystyle f (x)}

В целях иллюстрации ниже описывается алгоритм Метрополиса, частный случай алгоритма Метрополиса – Гастингса, в котором функция предложения является симметричной.

Алгоритм Метрополиса (симметричное распределение предложений)

Позвольте быть функцией, которая пропорциональна желаемой функции плотности вероятности (также известной как целевое распределение). ж ( Икс ) {\ displaystyle f (x)} п ( Икс ) {\ Displaystyle P (x)}

  1. Инициализация: выберите произвольную точку, которая будет первым наблюдением в выборке, и выберите произвольную плотность вероятности (иногда записанную), которая предлагает кандидата для следующего значения выборки с учетом предыдущего значения выборки. В этом разделе предполагается симметричным; другими словами, он должен удовлетворять. Обычный выбор - позволить быть распределением Гаусса с центром, чтобы точки, находящиеся ближе к, с большей вероятностью были посещены в следующий раз, превращая последовательность выборок в случайное блуждание. Эта функция называется плотностью предложения или скачкообразным распределением. Икс т {\ displaystyle x_ {t}} грамм ( Икс у ) {\ Displaystyle г (х \ середина у)} Q ( Икс у ) {\ Displaystyle Q (х \ середина у)} Икс {\ displaystyle x} у {\ displaystyle y} грамм {\ displaystyle g} грамм ( Икс у ) знак равно грамм ( у Икс ) {\ Displaystyle г (х \ середина у) = г (у \ середина х)} грамм ( Икс у ) {\ Displaystyle г (х \ середина у)} у {\ displaystyle y} у {\ displaystyle y} грамм {\ displaystyle g}
  2. Для каждой итерации t:
    • Сгенерируйте кандидата для следующей выборки, выбрав из распределения. Икс {\ displaystyle x '} грамм ( Икс Икс т ) {\ Displaystyle г (х '\ середина x_ {т})}
    • Рассчитайте коэффициент принятия, который будет использоваться, чтобы решить, принять или отклонить кандидата. Поскольку f пропорционально плотности P, мы имеем это. α знак равно ж ( Икс ) / ж ( Икс т ) {\ Displaystyle \ альфа = е (х ') / е (х_ {т})} α знак равно ж ( Икс ) / ж ( Икс т ) знак равно п ( Икс ) / п ( Икс т ) {\ Displaystyle \ альфа = f (x ') / f (x_ {t}) = P (x') / P (x_ {t})}
    • Принять или отклонить:
      • Сгенерируйте однородное случайное число. ты [ 0 , 1 ] {\ Displaystyle и \ в [0,1]}
      • Если, тогда примите кандидата, установив, ты α {\ Displaystyle и \ leq \ alpha} Икс т + 1 знак равно Икс {\ displaystyle x_ {t + 1} = x '}
      • Если, то отклоните кандидата и установите вместо него. ты gt; α {\ displaystyle ugt; \ alpha} Икс т + 1 знак равно Икс т {\ Displaystyle х_ {т + 1} = х_ {т}}

Этот алгоритм действует, пытаясь случайным образом перемещаться по пространству выборки, иногда принимая ходы, а иногда оставаясь на месте. Обратите внимание, что коэффициент приемлемости показывает, насколько вероятен новый предложенный образец по сравнению с текущим образцом в соответствии с распределением, плотность которого равна. Если мы попытаемся переместиться в точку, которая более вероятна, чем существующая точка (то есть точка в области с более высокой плотностью, соответствующей точке an), мы всегда примем это движение. Однако, если мы пытаемся перейти к менее вероятной точке, мы иногда отклоняем это движение, и чем больше относительное падение вероятности, тем больше вероятность, что мы отклоним новую точку. Таким образом, мы будем стремиться оставаться в регионах с высокой плотностью (и возвращать большое количество образцов из них) и лишь изредка посещать регионы с низкой плотностью. Интуитивно понятно, почему этот алгоритм работает и возвращает выборки, которые следуют желаемому распределению с плотностью. α {\ displaystyle \ alpha} п ( Икс ) {\ Displaystyle P (x)} п ( Икс ) {\ Displaystyle P (x)} α gt; 1 ты {\ displaystyle \ alphagt; 1 \ geq u} п ( Икс ) {\ Displaystyle P (x)} п ( Икс ) {\ Displaystyle P (x)}

По сравнению с таким алгоритмом, как адаптивная выборка отбраковки, который напрямую генерирует независимые выборки из распределения, алгоритм Метрополиса – Гастингса и другие алгоритмы MCMC имеют ряд недостатков:

  • Образцы коррелированы. Даже если в долгосрочной перспективе они будут правильно следовать, набор близлежащих выборок будет коррелирован друг с другом и не будет правильно отражать распределение. Это означает, что если нам нужен набор независимых выборок, мы должны отбросить большинство выборок и брать только каждую n- ю выборку для некоторого значения n (обычно определяется путем изучения автокорреляции между соседними выборками). Автокорреляцию можно уменьшить, увеличив ширину прыжка (средний размер прыжка, который связан с дисперсией распределения прыжков), но это также увеличит вероятность отклонения предложенного прыжка. Слишком большой или слишком маленький размер скачка приведет к медленному перемешиванию цепи Маркова, то есть к высококоррелированному набору отсчетов, так что для получения разумной оценки любого желаемого свойства распределения потребуется очень большое количество отсчетов. п ( Икс ) {\ Displaystyle P (x)}
  • Хотя цепь Маркова в конечном итоге сходится к желаемому распределению, исходные выборки могут следовать совсем другому распределению, особенно если начальная точка находится в области с низкой плотностью. В результате выгорания периода, как правило, необходимо, где начальное число выборок (например, первый 1000 или около того) выбрасываются.

С другой стороны, наиболее простые методы выборки отклонения страдают от « проклятия размерности », когда вероятность отклонения возрастает экспоненциально в зависимости от количества измерений. Метрополис – Гастингс, как и другие методы MCMC, не имеют этой проблемы в такой степени и, таким образом, часто являются единственными доступными решениями, когда количество измерений распределения, подлежащего выборке, велико. В результате методы MCMC часто являются методами выбора для получения выборок из иерархических байесовских моделей и других многомерных статистических моделей, используемых в настоящее время во многих дисциплинах.

В многомерных распределениях классический алгоритм Метрополиса – Гастингса, описанный выше, включает выбор новой многомерной точки выборки. Когда количество измерений велико, найти подходящее распределение прыжков для использования может быть сложно, так как разные отдельные измерения ведут себя по-разному, а ширина прыжка (см. Выше) должна быть "правильной" для всех измерений сразу, чтобы Избегайте слишком медленного перемешивания. Альтернативный подход, который часто лучше работает в таких ситуациях, известный как выборка Гиббса, включает выбор новой выборки для каждого измерения отдельно от других, а не выбор выборки для всех измерений сразу. Таким образом, проблема выборки из потенциально многомерного пространства будет сведена к набору задач для выборки из малой размерности. Это особенно применимо, когда многомерное распределение состоит из набора отдельных случайных величин, в которых каждая переменная зависит только от небольшого числа других переменных, как это имеет место в большинстве типичных иерархических моделей. Затем отбираются отдельные переменные по одной, причем каждая переменная зависит от самых последних значений всех остальных. Для выбора этих отдельных выборок могут использоваться различные алгоритмы, в зависимости от точной формы многомерного распределения: некоторые возможности - это методы выборки с адаптивным отклонением, алгоритм выборки с адаптивным отклонением в Метрополисе, простой одномерный шаг Метрополиса – Гастингса или выборка срезов..

Формальное происхождение

Цель алгоритма Метрополиса – Гастингса - создать набор состояний в соответствии с желаемым распределением. Для этого в алгоритме используется марковский процесс, который асимптотически достигает уникального стационарного распределения, такого что. п ( Икс ) {\ Displaystyle P (x)} π ( Икс ) {\ Displaystyle \ пи (х)} π ( Икс ) знак равно п ( Икс ) {\ Displaystyle \ пи (х) = п (х)}

Марковский процесс однозначно определяется его вероятностями перехода, вероятностью перехода из любого заданного состояния в любое другое заданное состояние. Он имеет уникальное стационарное распределение при соблюдении следующих двух условий: п ( Икс Икс ) {\ Displaystyle Р (х '\ середина х)} Икс {\ displaystyle x} Икс {\ displaystyle x '} π ( Икс ) {\ Displaystyle \ пи (х)}

  1. Существование стационарного распределения: должно существовать стационарное распределение. Достаточное, но не необходимое условие детального равновесия, который требует, чтобы каждый переход является обратимым: для каждой пары состояний, вероятность того, чтобы быть в состоянии и переходит в состояние должно быть равно вероятности того, чтобы быть в состоянии и переходит в состояние,. π ( Икс ) {\ Displaystyle \ пи (х)} Икс Икс {\ displaystyle x \ to x '} Икс , Икс {\ Displaystyle х, х '} Икс {\ displaystyle x} Икс {\ displaystyle x '} Икс {\ displaystyle x '} Икс {\ displaystyle x} π ( Икс ) п ( Икс Икс ) знак равно π ( Икс ) п ( Икс Икс ) {\ displaystyle \ pi (x) P (x '\ mid x) = \ pi (x') P (x \ mid x ')}
  2. Уникальность стационарного распределения: стационарное распределение должно быть уникальным. Это гарантируется эргодичностью марковского процесса, который требует, чтобы каждое состояние (1) было апериодическим - система не возвращается в одно и то же состояние через фиксированные промежутки времени; и (2) быть положительно повторяющимся - ожидаемое количество шагов для возврата в то же состояние конечно. π ( Икс ) {\ Displaystyle \ пи (х)}

Алгоритм Метрополиса – Гастингса включает в себя разработку марковского процесса (путем построения переходных вероятностей), который удовлетворяет двум вышеуказанным условиям, таким образом, чтобы его стационарное распределение было выбрано таким. Вывод алгоритма начинается с условия детального баланса : π ( Икс ) {\ Displaystyle \ пи (х)} п ( Икс ) {\ Displaystyle P (x)}

п ( Икс Икс ) п ( Икс ) знак равно п ( Икс Икс ) п ( Икс ) , {\ Displaystyle P (x '\ mid x) P (x) = P (x \ mid x') P (x '),}

который переписывается как

п ( Икс Икс ) п ( Икс Икс ) знак равно п ( Икс ) п ( Икс ) . {\ displaystyle {\ frac {P (x '\ mid x)} {P (x \ mid x')}} = {\ frac {P (x ')} {P (x)}}.}

Подход состоит в том, чтобы разделить переход на два подэтапа; предложение и прием-отклонение. Распределение предложений - это условная вероятность предложения данного состояния, а распределение принятия - это вероятность принятия предложенного состояния. Вероятность перехода можно записать как их произведение: грамм ( Икс Икс ) {\ Displaystyle г (х '\ середина х)} Икс {\ displaystyle x '} Икс {\ displaystyle x} А ( Икс , Икс ) {\ Displaystyle А (х ', х)} Икс {\ displaystyle x '}

п ( Икс Икс ) знак равно грамм ( Икс Икс ) А ( Икс , Икс ) . {\ Displaystyle P (x '\ mid x) = g (x' \ mid x) A (x ', x).}

Подставляя это соотношение в предыдущее уравнение, мы имеем

А ( Икс , Икс ) А ( Икс , Икс ) знак равно п ( Икс ) п ( Икс ) грамм ( Икс Икс ) грамм ( Икс Икс ) . {\ displaystyle {\ frac {A (x ', x)} {A (x, x')}} = {\ frac {P (x ')} {P (x)}} {\ frac {g (x \ mid x ')} {g (x' \ mid x)}}.}

Следующим шагом в выводе является выбор коэффициента приемлемости, который удовлетворяет вышеуказанному условию. Один из распространенных вариантов - выбор Метрополиса:

А ( Икс , Икс ) знак равно мин ( 1 , п ( Икс ) п ( Икс ) грамм ( Икс Икс ) грамм ( Икс Икс ) ) . {\ displaystyle A (x ', x) = \ min \ left (1, {\ frac {P (x')} {P (x)}} {\ frac {g (x \ mid x ')} {g (x '\ mid x)}} \ right).}

Для этого коэффициента приема Метрополиса, либо или, и, в любом случае, условие удовлетворяется. А {\ displaystyle A} А ( Икс , Икс ) знак равно 1 {\ Displaystyle А (х ', х) = 1} А ( Икс , Икс ) знак равно 1 {\ Displaystyle А (х, х ') = 1}

Таким образом, алгоритм Метрополиса – Гастингса состоит в следующем:

  1. Инициализировать
    1. Выберите начальное состояние. Икс 0 {\ displaystyle x_ {0}}
    2. Установить. т знак равно 0 {\ displaystyle t = 0}
  2. Повторять
    1. Создайте случайное состояние кандидата в соответствии с. Икс {\ displaystyle x '} грамм ( Икс Икс т ) {\ Displaystyle г (х '\ середина x_ {т})}
    2. Рассчитайте вероятность принятия. А ( Икс , Икс т ) знак равно мин ( 1 , п ( Икс ) п ( Икс т ) грамм ( Икс т Икс ) грамм ( Икс Икс т ) ) {\ displaystyle A (x ', x_ {t}) = \ min \ left (1, {\ frac {P (x')} {P (x_ {t})}} {\ frac {g (x_ {t}) } \ mid x ')} {g (x' \ mid x_ {t})}} \ right)}
    3. Принять или отклонить:
      1. генерировать однородное случайное число ; ты [ 0 , 1 ] {\ Displaystyle и \ в [0,1]}
      2. если, то принять новое состояние и установить ; ты А ( Икс , Икс т ) {\ Displaystyle и \ leq А (х ', x_ {т})} Икс т + 1 знак равно Икс {\ displaystyle x_ {t + 1} = x '}
      3. если, то отклонить новое состояние и скопировать старое состояние вперед. ты gt; А ( Икс , Икс т ) {\ Displaystyle иgt; А (х ', х_ {т})} Икс т + 1 знак равно Икс т {\ Displaystyle х_ {т + 1} = х_ {т}}
    4. Приращение: установить. т знак равно т + 1 {\ Displaystyle т = т + 1}

При соблюдении указанных условий приближается эмпирическое распределение сохраненных состояний. Количество итераций (), необходимых для эффективной оценки, зависит от количества факторов, включая взаимосвязь между распределением предложений и желаемой точностью оценки. Для распределения в дискретных пространствах состояний оно должно быть порядка времени автокорреляции марковского процесса. Икс 0 , , Икс Т {\ displaystyle x_ {0}, \ ldots, x_ {T}} п ( Икс ) {\ Displaystyle P (x)} Т {\ displaystyle T} п ( Икс ) {\ Displaystyle P (x)} п ( Икс ) {\ Displaystyle P (x)}

Важно отметить, что в общей задаче неясно, какое распределение следует использовать или количество итераций, необходимых для правильной оценки; оба являются свободными параметрами метода, которые необходимо адаптировать к конкретной проблеме. грамм ( Икс Икс ) {\ Displaystyle г (х '\ середина х)}

Использование в численном интегрировании

Основная статья: интеграция Монте-Карло

Обычно алгоритм Метрополиса – Гастингса используется для вычисления интеграла. В частности, рассмотрим пространство и распределение вероятностей по,. Метрополис – Гастингс может оценить интеграл формы Ω р {\ Displaystyle \ Omega \ subset \ mathbb {R}} п ( Икс ) {\ Displaystyle P (x)} Ω {\ displaystyle \ Omega} Икс Ω {\ displaystyle x \ in \ Omega}

п ( E ) знак равно Ω А ( Икс ) п ( Икс ) d Икс , {\ Displaystyle P (E) = \ int _ {\ Omega} A (x) P (x) \, dx,}

где - интересующая (измеримая) функция. А ( Икс ) {\ Displaystyle А (х)}

Например, рассмотрим статистику и ее распределение вероятностей, которое является предельным распределением. Предположим, что цель состоит в том, чтобы оценить для на хвосте. Формально можно записать как E ( Икс ) {\ displaystyle E (x)} п ( E ) {\ Displaystyle P (E)} п ( E ) {\ Displaystyle P (E)} E {\ displaystyle E} п ( E ) {\ Displaystyle P (E)} п ( E ) {\ Displaystyle P (E)}

п ( E ) знак равно Ω п ( E Икс ) п ( Икс ) d Икс знак равно Ω δ ( E - E ( Икс ) ) п ( Икс ) d Икс знак равно E ( п ( E Икс ) ) {\ Displaystyle P (E) = \ int _ {\ Omega} P (E \ mid x) P (x) \, dx = \ int _ {\ Omega} \ delta {\ big (} EE (x) {\ большой)} P (x) \, dx = E {\ big (} P (E \ mid X) {\ big)}}

и, таким образом, оценка может быть выполнена путем оценки ожидаемого значения индикаторной функции, которое равно 1, когда и нулю в противном случае. Поскольку находится на хвосте, вероятность нарисовать состояние с хвостом пропорциональна, что по определению мала. Здесь можно использовать алгоритм Метрополиса – Гастингса для более вероятных выборок (редких) состояний и, таким образом, увеличения количества выборок, используемых для оценки по хвостам. Это может быть сделано, например, с помощью распределения выборки в пользу этих состояний (например, с). п ( E ) {\ Displaystyle P (E)} А E ( Икс ) 1 E ( Икс ) {\ Displaystyle A_ {E} (х) \ эквив \ mathbf {1} _ {E} (х)} E ( Икс ) [ E , E + Δ E ] {\ Displaystyle E (х) \ в [E, E + \ Delta E]} E {\ displaystyle E} п ( E ) {\ Displaystyle P (E)} Икс {\ displaystyle x} E ( Икс ) {\ displaystyle E (x)} п ( E ) {\ Displaystyle P (E)} п ( E ) {\ Displaystyle P (E)} п ( E ) {\ Displaystyle P (E)} π ( Икс ) {\ Displaystyle \ пи (х)} π ( Икс ) е а E {\ displaystyle \ pi (x) \ propto e ^ {aE}} а gt; 0 {\ displaystyle agt; 0}

Пошаговая инструкция

Предположим, что выбрано самое последнее значение. Следуя алгоритму Метрополиса – Гастингса, мы затем рисуем новое состояние предложения с плотностью вероятности и вычисляем значение Икс т {\ displaystyle x_ {t}} Икс {\ displaystyle x '} грамм ( Икс Икс т ) {\ Displaystyle г (х '\ середина x_ {т})}

а знак равно а 1 а 2 , {\ displaystyle a = a_ {1} a_ {2},}

куда

а 1 знак равно п ( Икс ) п ( Икс т ) {\ displaystyle a_ {1} = {\ frac {P (x ')} {P (x_ {t})}}}

- отношение вероятности (например, байесовского апостериорного) между предложенной выборкой и предыдущей выборкой, и Икс {\ displaystyle x '} Икс т {\ displaystyle x_ {t}}

а 2 знак равно грамм ( Икс т Икс ) грамм ( Икс Икс т ) {\ displaystyle a_ {2} = {\ frac {g (x_ {t} \ mid x ')} {g (x' \ mid x_ {t})}}}

- соотношение плотности предложения в двух направлениях (от к и обратно). Это равно 1, если плотность предложения симметрична. Затем новое состояние выбирается по следующим правилам. Икс т {\ displaystyle x_ {t}} Икс {\ displaystyle x '} Икс т + 1 {\ displaystyle x_ {t + 1}}

Если а 1 : {\ displaystyle a \ geq 1 {:}}
Икс т + 1 знак равно Икс , {\ displaystyle x_ {t + 1} = x ',}
еще:
Икс т + 1 знак равно { Икс с вероятностью  а , Икс т с вероятностью  1 - а . {\ displaystyle x_ {t + 1} = {\ begin {case} x 'amp; {\ text {with possible}} a, \\ x_ {t} amp; {\ text {с вероятностью}} 1-a. \ end {случаи}}}

Цепь Маркова запускается с произвольного начального значения, и алгоритм выполняется в течение многих итераций, пока это начальное состояние не будет «забыто». Эти выбрасываемые образцы известны как прожигание. Оставшийся набор принятых значений представляет собой выборку из распределения. Икс 0 {\ displaystyle x_ {0}} Икс {\ displaystyle x} п ( Икс ) {\ Displaystyle P (x)}

Алгоритм работает лучше всего, если плотность предложения соответствует форме целевого распределения, из которого прямая выборка затруднена, то есть. Если используется гауссова плотность предложения, параметр дисперсии должен быть настроен в течение периода приработки. Обычно это делается путем расчета коэффициента приемки, который представляет собой долю предложенных образцов, которая принимается в окне последних выборок. Желаемая степень принятия зависит от целевого распределения, однако теоретически было показано, что идеальная степень принятия для одномерного гауссова распределения составляет около 50%, снижаясь до примерно 23% для -мерного целевого распределения по Гауссу. п ( Икс ) {\ Displaystyle P (x)} грамм ( Икс Икс т ) п ( Икс ) {\ Displaystyle г (х '\ середина x_ {т}) \ приблизительно Р (х')} грамм {\ displaystyle g} σ 2 {\ displaystyle \ sigma ^ {2}} N {\ displaystyle N} N {\ displaystyle N}

Если он слишком мал, цепочка будет медленно перемешиваться (т. Е. Скорость приема будет высокой, но последующие образцы будут медленно перемещаться по пространству, и цепочка будет только медленно сходиться к). С другой стороны, если оно слишком велико, степень принятия будет очень низкой, потому что предложения, вероятно, попадут в регионы с гораздо более низкой плотностью вероятности, поэтому будут очень маленькими, и снова цепочка будет сходиться очень медленно. Обычно распределение предложений настраивается так, чтобы алгоритмы принимали порядка 30% всех выборок - в соответствии с теоретическими оценками, упомянутыми в предыдущем абзаце. σ 2 {\ displaystyle \ sigma ^ {2}} п ( Икс ) {\ Displaystyle P (x)} σ 2 {\ displaystyle \ sigma ^ {2}} а 1 {\ displaystyle a_ {1}}

Результат трех цепей Маркова, работающих на трехмерной функции Розенброка с использованием алгоритма Метрополиса – Гастингса. Алгоритм выбирает из областей, где апостериорная вероятность высока, и цепочки начинают смешиваться в этих областях. Было подсвечено приблизительное положение максимума. Красные точки - это те, которые остались после процесса приработки. Более ранние были отброшены.

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

использованная литература

Примечания

дальнейшее чтение

Последняя правка сделана 2024-01-02 08:55:31
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте