Алгоритм Метрополиса – Гастингса - Metropolis–Hastings algorithm
В статистических данных и статистической физики , то Метрополиса-Гастингс алгоритм является цепь Маркова Монте - Карло метод (MCMC) для получения последовательности случайных выборок из распределения вероятностей , из которых прямой выборки трудно. Эта последовательность может использоваться для аппроксимации распределения (например, для создания гистограммы ) или для вычисления интеграла (например, ожидаемого значения). Метрополис – Гастингс и другие алгоритмы MCMC обычно используются для выборки из многомерных распределений, особенно когда количество измерений велико. Для одномерных распределений обычно существуют другие методы (например, выборка с адаптивным отклонением ), которые могут напрямую возвращать независимые выборки из распределения, и они свободны от проблемы автокоррелированных выборок, присущей методам MCMC.
История
Алгоритм был назван в честь Николаса Метрополиса , который вместе с Арианной У. Розенблут , Маршаллом Розенблутом , Августой Х. Теллер и Эдвардом Теллером написал статью « Уравнение вычислений состояния с помощью быстрых вычислительных машин» в 1953 году . В этой статье был предложен алгоритм для случая симметричных распределений предложений, и В.К. Гастингс распространил его на более общий случай в 1970 году.
Некоторые разногласия существуют относительно кредита на разработку алгоритма. Метрополис, который был знаком с вычислительными аспектами этого метода, ввел термин «Монте-Карло» в более раннюю статью со Станиславом Уламом и возглавил группу в Теоретическом отделе, которая разработала и построила компьютер MANIAC I, который использовался в экспериментах в 1952. Однако до 2003 года подробного описания развития алгоритма не существовало. Затем, незадолго до своей смерти, Маршалл Розенблют посетил конференцию 2003 года в LANL, посвященную 50-летию публикации 1953 года. На этой конференции Розенблют описал алгоритм и его развитие в презентации под названием «Генезис алгоритма Монте-Карло для статистической механики». Дальнейшее историческое разъяснение сделано Губернатисом в журнальной статье 2005 года, посвященной 50-летию конференции. Розенблют ясно дает понять, что он и его жена Арианна сделали работу, и что Метрополис не играл никакой роли в разработке, кроме предоставления компьютерного времени.
Это противоречит рассказу Эдварда Теллера, который утверждает в своих мемуарах, что пять авторов статьи 1953 года работали вместе «днями (и ночами)». Напротив, в подробном отчете Розенблюта Теллер сделал важное, но раннее предложение «воспользоваться статистической механикой и взять средние по совокупности вместо того, чтобы следовать детальной кинематике». Это, как говорит Розенблут, побудило его задуматься об обобщенном подходе Монте-Карло - теме, которую, по его словам, он часто обсуждал с Джоном фон Нейманом . Арианна Розенблут рассказала (Губернатису в 2003 году), что Августа Теллер начала работу на компьютере, но сама Арианна взяла на себя ее и написала код с нуля. В устной истории, записанной незадолго до своей смерти, Розенблют снова приписывает Теллеру постановку исходной проблемы, его решение, а Арианну - программирование компьютера. Что касается репутации, у Розенблюта нет особых причин подвергать сомнению его версию. В биографических мемуарах Розенблута Фримен Дайсон пишет:
Я много раз приходил к Розенблюту, задавал ему вопрос [...] и получал ответ через две минуты. Затем мне обычно требовалась неделя напряженной работы, чтобы в деталях понять, почему ответ Розенблута был правильным. У него была удивительная способность видеть сложные физические ситуации и находить правильный ответ с помощью физических аргументов. Энрико Ферми был единственным из известных мне физиков, равным Розенблюту в его интуитивном понимании физики.
Интуиция
Алгоритм Метрополис-Гастингс может отбирать образцы из любого распределения вероятностей с плотностью вероятности , при условии , что мы знаем функцию , пропорциональные плотности и значения могут быть вычислены. Требование, которое должно быть только пропорционально плотности, а не точно равной ей, делает алгоритм Метрополиса – Гастингса особенно полезным, поскольку вычисление необходимого коэффициента нормализации на практике часто бывает чрезвычайно трудным.
Алгоритм Метрополиса – Гастингса работает, генерируя последовательность выборочных значений таким образом, что по мере создания все большего количества выборочных значений распределение значений более точно приближается к желаемому распределению. Эти значения выборки производятся итеративно, при этом распределение следующей выборки зависит только от текущего значения выборки (таким образом, последовательность выборок превращается в цепь Маркова ). В частности, на каждой итерации алгоритм выбирает кандидата для следующего значения выборки на основе текущего значения выборки. Затем с некоторой вероятностью кандидат либо принимается (в этом случае значение кандидата используется в следующей итерации), либо отклоняется (в этом случае значение кандидата отбрасывается, а текущее значение повторно используется в следующей итерации) - вероятность приемлемости определяется путем сравнения значений функции текущего и потенциального значений выборки по отношению к желаемому распределению.
В целях иллюстрации ниже описывается алгоритм Метрополиса, частный случай алгоритма Метрополиса – Гастингса, в котором функция предложения является симметричной.
Алгоритм Метрополиса (симметричное распределение предложений)
Позвольте быть функцией, которая пропорциональна желаемой функции плотности вероятности (также известной как целевое распределение).
- Инициализация: выберите произвольную точку, которая будет первым наблюдением в выборке, и выберите произвольную плотность вероятности (иногда записанную ), которая предлагает кандидата для следующего значения выборки с учетом предыдущего значения выборки . В этом разделе предполагается симметричным; другими словами, он должен удовлетворять . Обычный выбор - позволить быть распределением Гаусса с центром , чтобы точки, находящиеся ближе к , с большей вероятностью были посещены в следующий раз, превращая последовательность выборок в случайное блуждание . Эта функция называется плотностью предложения или скачкообразным распределением .
- Для каждой итерации t :
- Сгенерируйте кандидата для следующей выборки, выбрав из распределения .
- Рассчитайте коэффициент принятия , который будет использоваться, чтобы решить, принять или отклонить кандидата. Поскольку f пропорционально плотности P , мы имеем это .
-
Принять или отклонить :
- Сгенерируйте однородное случайное число .
- Если , тогда примите кандидата, установив ,
- Если , то отклоните кандидата и установите вместо него.
Этот алгоритм действует, пытаясь случайным образом перемещаться по пространству выборки, иногда принимая ходы, а иногда оставаясь на месте. Обратите внимание, что коэффициент приемлемости показывает, насколько вероятен новый предложенный образец по сравнению с текущим образцом в соответствии с распределением, плотность которого равна . Если мы попытаемся переместиться в точку, которая более вероятна, чем существующая точка (то есть точка в области с более высокой плотностью, соответствующей точке an ), мы всегда примем это движение. Однако, если мы пытаемся перейти к менее вероятной точке, мы иногда отклоняем это движение, и чем больше относительное падение вероятности, тем больше вероятность, что мы отклоним новую точку. Таким образом, мы будем стремиться оставаться в регионах с высокой плотностью (и возвращать большое количество образцов из них) и лишь изредка посещать регионы с низкой плотностью. Интуитивно понятно, почему этот алгоритм работает и возвращает выборки, которые следуют желаемому распределению с плотностью .
По сравнению с таким алгоритмом, как адаптивная выборка отбраковки, который напрямую генерирует независимые выборки из распределения, алгоритм Метрополиса – Гастингса и другие алгоритмы MCMC имеют ряд недостатков:
- Образцы коррелированы. Даже если в долгосрочной перспективе они будут правильно следовать , набор близлежащих выборок будет коррелирован друг с другом и не будет правильно отражать распределение. Это означает, что если нам нужен набор независимых выборок, мы должны отбросить большинство выборок и брать только каждую n- ю выборку для некоторого значения n (обычно определяется путем изучения автокорреляции между соседними выборками). Автокорреляцию можно уменьшить, увеличив ширину прыжка (средний размер прыжка, который связан с дисперсией распределения прыжков), но это также увеличит вероятность отклонения предложенного прыжка. Слишком большой или слишком маленький размер скачка приведет к медленному перемешиванию цепи Маркова, то есть к высококоррелированному набору отсчетов, так что для получения разумной оценки любого желаемого свойства распределения потребуется очень большое количество отсчетов.
- Хотя цепь Маркова в конечном итоге сходится к желаемому распределению, исходные выборки могут следовать совсем другому распределению, особенно если начальная точка находится в области с низкой плотностью. В результате выгорания периода , как правило , необходимо, где начальное число выборок (например, первый 1000 или около того ) выбрасываются.
С другой стороны, наиболее простые методы выборки отклонения страдают от « проклятия размерности », когда вероятность отклонения возрастает экспоненциально в зависимости от количества измерений. Метрополис – Гастингс, как и другие методы MCMC, не имеют этой проблемы в такой степени и, таким образом, часто являются единственными доступными решениями, когда количество измерений распределения, подлежащего выборке, велико. В результате методы MCMC часто являются методами выбора для получения выборок из иерархических байесовских моделей и других многомерных статистических моделей, используемых в настоящее время во многих дисциплинах.
В многомерных распределениях классический алгоритм Метрополиса – Гастингса, описанный выше, включает выбор новой многомерной точки выборки. Когда количество измерений велико, найти подходящее распределение прыжков для использования может быть сложно, так как разные отдельные измерения ведут себя по-разному, а ширина прыжка (см. Выше) должна быть "правильной" для всех измерений сразу, чтобы Избегайте слишком медленного перемешивания. Альтернативный подход, который часто лучше работает в таких ситуациях, известный как выборка Гиббса , включает выбор новой выборки для каждого измерения отдельно от других, а не выбор выборки для всех измерений сразу. Таким образом, проблема выборки из потенциально многомерного пространства будет сведена к набору задач для выборки из малой размерности. Это особенно применимо, когда многомерное распределение состоит из набора отдельных случайных величин, в которых каждая переменная зависит только от небольшого числа других переменных, как это имеет место в большинстве типичных иерархических моделей . Затем отбираются отдельные переменные по одной, причем каждая переменная зависит от самых последних значений всех остальных. Для выбора этих отдельных выборок могут использоваться различные алгоритмы, в зависимости от точной формы многомерного распределения: некоторые возможности - это методы выборки с адаптивным отклонением, алгоритм выборки с адаптивным отклонением в Метрополисе, простой одномерный шаг Метрополиса – Гастингса или выборка срезов. .
Формальное происхождение
Цель алгоритма Метрополиса – Гастингса - создать набор состояний в соответствии с желаемым распределением . Для этого в алгоритме используется марковский процесс , который асимптотически достигает уникального стационарного распределения, такого что .
Марковский процесс однозначно определяется его вероятностями перехода , вероятностью перехода из любого заданного состояния в любое другое заданное состояние . Он имеет уникальное стационарное распределение при соблюдении следующих двух условий:
- Существование стационарного распределения : должно существовать стационарное распределение . Достаточное , но не необходимое условие детального равновесия , который требует , чтобы каждый переход является обратимым: для каждой пары состояний , вероятность того , чтобы быть в состоянии и переходит в состояние должно быть равно вероятности того , чтобы быть в состоянии и переходит в состояние , .
- Уникальность стационарного распределения : стационарное распределение должно быть уникальным. Это гарантируется эргодичностью марковского процесса, который требует, чтобы каждое состояние (1) было апериодическим - система не возвращается в одно и то же состояние через фиксированные промежутки времени; и (2) быть положительно повторяющимся - ожидаемое количество шагов для возврата в то же состояние конечно.
Алгоритм Метрополиса – Гастингса включает в себя разработку марковского процесса (путем построения переходных вероятностей), который удовлетворяет двум вышеуказанным условиям, таким образом, чтобы его стационарное распределение было выбрано таким . Вывод алгоритма начинается с условия детального баланса :
который переписывается как
Подход состоит в том, чтобы разделить переход на два подэтапа; предложение и прием-отклонение. Распределение предложений - это условная вероятность предложения данного состояния , а распределение принятия - это вероятность принятия предложенного состояния . Вероятность перехода можно записать как их произведение:
Подставляя это соотношение в предыдущее уравнение, мы имеем
Следующим шагом в выводе является выбор коэффициента приемлемости, который удовлетворяет вышеуказанному условию. Один из распространенных вариантов - выбор Метрополиса:
Для этого коэффициента приема Метрополиса , либо или , и, в любом случае, условие удовлетворяется.
Таким образом, алгоритм Метрополиса – Гастингса состоит в следующем:
- Инициализировать
- Выберите начальное состояние .
- Установить .
- Повторять
- Создайте случайное состояние кандидата в соответствии с .
- Рассчитайте вероятность принятия .
-
Принять или отклонить :
- генерировать однородное случайное число ;
- если , то принять новое состояние и установить ;
- если , то отклонить новое состояние и скопировать старое состояние вперед .
- Приращение : установить .
При соблюдении указанных условий приближается эмпирическое распределение сохраненных состояний . Количество итераций ( ), необходимых для эффективной оценки, зависит от количества факторов, включая взаимосвязь между распределением предложений и желаемой точностью оценки. Для распределения в дискретных пространствах состояний оно должно быть порядка времени автокорреляции марковского процесса.
Важно отметить, что в общей задаче неясно, какое распределение следует использовать или количество итераций, необходимых для правильной оценки; оба являются свободными параметрами метода, которые необходимо адаптировать к конкретной проблеме.
Использование в численном интегрировании
Обычно алгоритм Метрополиса – Гастингса используется для вычисления интеграла. В частности, рассмотрим пространство и распределение вероятностей по , . Метрополис – Гастингс может оценить интеграл формы
где - интересующая (измеримая) функция.
Например, рассмотрим статистику и ее распределение вероятностей , которое является предельным распределением . Предположим , что цель состоит в том, чтобы оценить для на хвосте . Формально можно записать как
и, таким образом, оценка может быть выполнена путем оценки ожидаемого значения индикаторной функции , которое равно 1, когда и нулю в противном случае. Поскольку находится на хвосте , вероятность нарисовать состояние с хвостом пропорциональна , что по определению мала. Здесь можно использовать алгоритм Метрополиса – Гастингса для более вероятных выборок (редких) состояний и, таким образом, увеличения количества выборок, используемых для оценки по хвостам. Это может быть сделано, например, с помощью распределения выборки в пользу этих состояний (например, с ).
Пошаговая инструкция
Предположим, что выбрано самое последнее значение . Следуя алгоритму Метрополиса – Гастингса, мы затем рисуем новое состояние предложения с плотностью вероятности и вычисляем значение
куда
- отношение вероятности (например, байесовского апостериорного) между предложенной выборкой и предыдущей выборкой , и
- соотношение плотности предложения в двух направлениях (от к и обратно). Это равно 1, если плотность предложения симметрична. Затем новое состояние выбирается по следующим правилам.
- Если
- еще:
Цепь Маркова запускается с произвольного начального значения , и алгоритм выполняется в течение многих итераций, пока это начальное состояние не будет «забыто». Эти выбрасываемые образцы известны как прожигание . Оставшийся набор принятых значений представляет собой выборку из распределения .
Алгоритм работает лучше всего, если плотность предложения соответствует форме целевого распределения , из которого прямая выборка затруднена, то есть . Если используется гауссова плотность предложения , параметр дисперсии должен быть настроен в течение периода приработки. Обычно это делается путем расчета коэффициента приемки , который представляет собой долю предложенных образцов, которая принимается в окне последних выборок. Желаемая степень принятия зависит от целевого распределения, однако теоретически было показано, что идеальная степень принятия для одномерного гауссова распределения составляет около 50%, снижаясь до примерно 23% для -мерного целевого распределения по Гауссу.
Если он слишком мал, цепочка будет медленно перемешиваться (т. Е. Скорость приема будет высокой, но последующие образцы будут медленно перемещаться по пространству, и цепочка будет только медленно сходиться к ). С другой стороны, если оно слишком велико, степень принятия будет очень низкой, потому что предложения, вероятно, попадут в регионы с гораздо более низкой плотностью вероятности, поэтому будут очень маленькими, и снова цепочка будет сходиться очень медленно. Обычно распределение предложений настраивается так, чтобы алгоритмы принимали порядка 30% всех выборок - в соответствии с теоретическими оценками, упомянутыми в предыдущем абзаце.
Смотрите также
- Детальный баланс
- Генетические алгоритмы
- Выборка Гиббса
- Методы частиц среднего поля
- Алгоритм Ланжевена с поправкой на мегаполис
- Легковой транспорт Метрополис
- Метрополис с несколькими попытками
- Параллельный отпуск
- Предварительно подготовленный алгоритм Crank – Nicolson
- Последовательный Монте-Карло
- Имитация отжига
использованная литература
Примечания
дальнейшее чтение
- Бернд А. Берг . Моделирование цепей Маркова методом Монте-Карло и их статистический анализ . Сингапур, World Scientific , 2004.
- Сиддхартха Чиб и Эдвард Гринберг: «Понимание алгоритма Метрополиса – Гастингса». Американский статистик , 49 (4), 327–335, 1995.
- Дэвид Д.Л. Минь и До Ле Минь. «Понимание алгоритма Гастингса». Коммуникации в статистике - моделирование и вычисления, 44: 2 332-349, 2015
- Болстад, Уильям М. (2010) Понимание вычислительной байесовской статистики , John Wiley & Sons ISBN 0-470-04609-0