В статистических данных и статистической физики, то Метрополиса-Гастингс алгоритм является цепь Маркова Монте - Карло метод (MCMC) для получения последовательности случайных выборок из распределения вероятностей, из которых прямой выборки трудно. Эта последовательность может использоваться для аппроксимации распределения (например, для создания гистограммы ) или для вычисления интеграла (например, ожидаемого значения ). Метрополис – Гастингс и другие алгоритмы MCMC обычно используются для выборки из многомерных распределений, особенно когда количество измерений велико. Для одномерных распределений обычно существуют другие методы (например, выборка с адаптивным отклонением ), которые могут напрямую возвращать независимые выборки из распределения, и они свободны от проблемы автокоррелированных выборок, присущей методам MCMC.
Алгоритм был назван в честь Николаса Метрополиса, который вместе с Арианной У. Розенблут, Маршаллом Розенблутом, Августой Х. Теллер и Эдвардом Теллером написал статью « Уравнение вычислений состояния с помощью быстрых вычислительных машин» в 1953 году. В этой статье был предложен алгоритм для случая симметричных распределений предложений, и В.К. Гастингс распространил его на более общий случай в 1970 году.
Некоторые разногласия существуют относительно кредита на разработку алгоритма. Метрополис, который был знаком с вычислительными аспектами этого метода, ввел термин «Монте-Карло» в более раннюю статью со Станиславом Уламом и возглавил группу в Теоретическом отделе, которая разработала и построила компьютер MANIAC I, который использовался в экспериментах в 1952. Однако до 2003 года подробного описания развития алгоритма не существовало. Затем, незадолго до своей смерти, Маршалл Розенблют посетил конференцию 2003 года в LANL, посвященную 50-летию публикации 1953 года. На этой конференции Розенблют описал алгоритм и его развитие в презентации под названием «Генезис алгоритма Монте-Карло для статистической механики». Дальнейшее историческое разъяснение сделано Губернатисом в журнальной статье 2005 года, посвященной 50-летию конференции. Розенблют ясно дает понять, что он и его жена Арианна сделали работу, и что Метрополис не играл никакой роли в разработке, кроме предоставления компьютерного времени.
Это противоречит рассказу Эдварда Теллера, который утверждает в своих мемуарах, что пять авторов статьи 1953 года работали вместе «днями (и ночами)». Напротив, в подробном отчете Розенблюта Теллер сделал важное, но раннее предложение «воспользоваться статистической механикой и взять средние по совокупности вместо того, чтобы следовать детальной кинематике». Это, как говорит Розенблут, побудило его задуматься об обобщенном подходе Монте-Карло - теме, которую, по его словам, он часто обсуждал с Джоном фон Нейманом. Арианна Розенблут рассказала (Губернатису в 2003 году), что Августа Теллер начала работу на компьютере, но сама Арианна взяла на себя ее и написала код с нуля. В устной истории, записанной незадолго до своей смерти, Розенблют снова приписывает Теллеру постановку исходной проблемы, его решение, а Арианну - программирование компьютера. Что касается репутации, у Розенблюта нет особых причин подвергать сомнению его версию. В биографических мемуарах Розенблута Фримен Дайсон пишет:
Я много раз приходил к Розенблюту, задавал ему вопрос [...] и получал ответ через две минуты. Затем мне обычно требовалась неделя напряженной работы, чтобы в деталях понять, почему ответ Розенблута был правильным. У него была удивительная способность видеть сложные физические ситуации и находить правильный ответ с помощью физических аргументов. Энрико Ферми был единственным из известных мне физиков, равным Розенблюту в его интуитивном понимании физики.
Алгоритм Метрополис-Гастингс может отбирать образцы из любого распределения вероятностей с плотностью вероятности, при условии, что мы знаем функцию, пропорциональные плотности и значения могут быть вычислены. Требование, которое должно быть только пропорционально плотности, а не точно равной ей, делает алгоритм Метрополиса – Гастингса особенно полезным, поскольку вычисление необходимого коэффициента нормализации на практике часто бывает чрезвычайно трудным.
Алгоритм Метрополиса – Гастингса работает, генерируя последовательность выборочных значений таким образом, что по мере создания все большего количества выборочных значений распределение значений более точно приближается к желаемому распределению. Эти значения выборки производятся итеративно, при этом распределение следующей выборки зависит только от текущего значения выборки (таким образом, последовательность выборок превращается в цепь Маркова ). В частности, на каждой итерации алгоритм выбирает кандидата для следующего значения выборки на основе текущего значения выборки. Затем с некоторой вероятностью кандидат либо принимается (в этом случае значение кандидата используется в следующей итерации), либо отклоняется (в этом случае значение кандидата отбрасывается, а текущее значение повторно используется в следующей итерации) - вероятность приемлемости определяется путем сравнения значений функции текущего и потенциального значений выборки по отношению к желаемому распределению.
В целях иллюстрации ниже описывается алгоритм Метрополиса, частный случай алгоритма Метрополиса – Гастингса, в котором функция предложения является симметричной.
Алгоритм Метрополиса (симметричное распределение предложений)
Позвольте быть функцией, которая пропорциональна желаемой функции плотности вероятности (также известной как целевое распределение).
Этот алгоритм действует, пытаясь случайным образом перемещаться по пространству выборки, иногда принимая ходы, а иногда оставаясь на месте. Обратите внимание, что коэффициент приемлемости показывает, насколько вероятен новый предложенный образец по сравнению с текущим образцом в соответствии с распределением, плотность которого равна. Если мы попытаемся переместиться в точку, которая более вероятна, чем существующая точка (то есть точка в области с более высокой плотностью, соответствующей точке an), мы всегда примем это движение. Однако, если мы пытаемся перейти к менее вероятной точке, мы иногда отклоняем это движение, и чем больше относительное падение вероятности, тем больше вероятность, что мы отклоним новую точку. Таким образом, мы будем стремиться оставаться в регионах с высокой плотностью (и возвращать большое количество образцов из них) и лишь изредка посещать регионы с низкой плотностью. Интуитивно понятно, почему этот алгоритм работает и возвращает выборки, которые следуют желаемому распределению с плотностью.
По сравнению с таким алгоритмом, как адаптивная выборка отбраковки, который напрямую генерирует независимые выборки из распределения, алгоритм Метрополиса – Гастингса и другие алгоритмы MCMC имеют ряд недостатков:
С другой стороны, наиболее простые методы выборки отклонения страдают от « проклятия размерности », когда вероятность отклонения возрастает экспоненциально в зависимости от количества измерений. Метрополис – Гастингс, как и другие методы MCMC, не имеют этой проблемы в такой степени и, таким образом, часто являются единственными доступными решениями, когда количество измерений распределения, подлежащего выборке, велико. В результате методы MCMC часто являются методами выбора для получения выборок из иерархических байесовских моделей и других многомерных статистических моделей, используемых в настоящее время во многих дисциплинах.
В многомерных распределениях классический алгоритм Метрополиса – Гастингса, описанный выше, включает выбор новой многомерной точки выборки. Когда количество измерений велико, найти подходящее распределение прыжков для использования может быть сложно, так как разные отдельные измерения ведут себя по-разному, а ширина прыжка (см. Выше) должна быть "правильной" для всех измерений сразу, чтобы Избегайте слишком медленного перемешивания. Альтернативный подход, который часто лучше работает в таких ситуациях, известный как выборка Гиббса, включает выбор новой выборки для каждого измерения отдельно от других, а не выбор выборки для всех измерений сразу. Таким образом, проблема выборки из потенциально многомерного пространства будет сведена к набору задач для выборки из малой размерности. Это особенно применимо, когда многомерное распределение состоит из набора отдельных случайных величин, в которых каждая переменная зависит только от небольшого числа других переменных, как это имеет место в большинстве типичных иерархических моделей. Затем отбираются отдельные переменные по одной, причем каждая переменная зависит от самых последних значений всех остальных. Для выбора этих отдельных выборок могут использоваться различные алгоритмы, в зависимости от точной формы многомерного распределения: некоторые возможности - это методы выборки с адаптивным отклонением, алгоритм выборки с адаптивным отклонением в Метрополисе, простой одномерный шаг Метрополиса – Гастингса или выборка срезов..
Цель алгоритма Метрополиса – Гастингса - создать набор состояний в соответствии с желаемым распределением. Для этого в алгоритме используется марковский процесс, который асимптотически достигает уникального стационарного распределения, такого что.
Марковский процесс однозначно определяется его вероятностями перехода, вероятностью перехода из любого заданного состояния в любое другое заданное состояние. Он имеет уникальное стационарное распределение при соблюдении следующих двух условий:
Алгоритм Метрополиса – Гастингса включает в себя разработку марковского процесса (путем построения переходных вероятностей), который удовлетворяет двум вышеуказанным условиям, таким образом, чтобы его стационарное распределение было выбрано таким. Вывод алгоритма начинается с условия детального баланса :
который переписывается как
Подход состоит в том, чтобы разделить переход на два подэтапа; предложение и прием-отклонение. Распределение предложений - это условная вероятность предложения данного состояния, а распределение принятия - это вероятность принятия предложенного состояния. Вероятность перехода можно записать как их произведение:
Подставляя это соотношение в предыдущее уравнение, мы имеем
Следующим шагом в выводе является выбор коэффициента приемлемости, который удовлетворяет вышеуказанному условию. Один из распространенных вариантов - выбор Метрополиса:
Для этого коэффициента приема Метрополиса, либо или, и, в любом случае, условие удовлетворяется.
Таким образом, алгоритм Метрополиса – Гастингса состоит в следующем:
При соблюдении указанных условий приближается эмпирическое распределение сохраненных состояний. Количество итераций (), необходимых для эффективной оценки, зависит от количества факторов, включая взаимосвязь между распределением предложений и желаемой точностью оценки. Для распределения в дискретных пространствах состояний оно должно быть порядка времени автокорреляции марковского процесса.
Важно отметить, что в общей задаче неясно, какое распределение следует использовать или количество итераций, необходимых для правильной оценки; оба являются свободными параметрами метода, которые необходимо адаптировать к конкретной проблеме.
Обычно алгоритм Метрополиса – Гастингса используется для вычисления интеграла. В частности, рассмотрим пространство и распределение вероятностей по,. Метрополис – Гастингс может оценить интеграл формы
где - интересующая (измеримая) функция.
Например, рассмотрим статистику и ее распределение вероятностей, которое является предельным распределением. Предположим, что цель состоит в том, чтобы оценить для на хвосте. Формально можно записать как
и, таким образом, оценка может быть выполнена путем оценки ожидаемого значения индикаторной функции, которое равно 1, когда и нулю в противном случае. Поскольку находится на хвосте, вероятность нарисовать состояние с хвостом пропорциональна, что по определению мала. Здесь можно использовать алгоритм Метрополиса – Гастингса для более вероятных выборок (редких) состояний и, таким образом, увеличения количества выборок, используемых для оценки по хвостам. Это может быть сделано, например, с помощью распределения выборки в пользу этих состояний (например, с).
Предположим, что выбрано самое последнее значение. Следуя алгоритму Метрополиса – Гастингса, мы затем рисуем новое состояние предложения с плотностью вероятности и вычисляем значение
куда
- отношение вероятности (например, байесовского апостериорного) между предложенной выборкой и предыдущей выборкой, и
- соотношение плотности предложения в двух направлениях (от к и обратно). Это равно 1, если плотность предложения симметрична. Затем новое состояние выбирается по следующим правилам.
Цепь Маркова запускается с произвольного начального значения, и алгоритм выполняется в течение многих итераций, пока это начальное состояние не будет «забыто». Эти выбрасываемые образцы известны как прожигание. Оставшийся набор принятых значений представляет собой выборку из распределения.
Алгоритм работает лучше всего, если плотность предложения соответствует форме целевого распределения, из которого прямая выборка затруднена, то есть. Если используется гауссова плотность предложения, параметр дисперсии должен быть настроен в течение периода приработки. Обычно это делается путем расчета коэффициента приемки, который представляет собой долю предложенных образцов, которая принимается в окне последних выборок. Желаемая степень принятия зависит от целевого распределения, однако теоретически было показано, что идеальная степень принятия для одномерного гауссова распределения составляет около 50%, снижаясь до примерно 23% для -мерного целевого распределения по Гауссу.
Если он слишком мал, цепочка будет медленно перемешиваться (т. Е. Скорость приема будет высокой, но последующие образцы будут медленно перемещаться по пространству, и цепочка будет только медленно сходиться к). С другой стороны, если оно слишком велико, степень принятия будет очень низкой, потому что предложения, вероятно, попадут в регионы с гораздо более низкой плотностью вероятности, поэтому будут очень маленькими, и снова цепочка будет сходиться очень медленно. Обычно распределение предложений настраивается так, чтобы алгоритмы принимали порядка 30% всех выборок - в соответствии с теоретическими оценками, упомянутыми в предыдущем абзаце.
Результат трех цепей Маркова, работающих на трехмерной функции Розенброка с использованием алгоритма Метрополиса – Гастингса. Алгоритм выбирает из областей, где апостериорная вероятность высока, и цепочки начинают смешиваться в этих областях. Было подсвечено приблизительное положение максимума. Красные точки - это те, которые остались после процесса приработки. Более ранние были отброшены.