Отбор проб отбраковки - Rejection sampling

В численном анализе и вычислительной статистике , отказ выборка является основным методом , используемым для создания наблюдений из в распределении . Его также обычно называют методом принятия-отклонения или «алгоритмом принятия-отклонения» и представляет собой тип точного метода моделирования. Метод работает для любого распределения с плотностью . ${\ Displaystyle \ mathbb {R} ^ {m}}$

Выборка отклонения основана на наблюдении, что для выборки случайной величины в одном измерении можно выполнить равномерно случайную выборку двумерного декартова графика и сохранить выборки в области под графиком ее функции плотности. Обратите внимание, что это свойство может быть расширено до N- мерных функций.

Описание

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

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

Отбор проб отбраковки работает следующим образом:

Выберите точку на оси x из распределения предложения.
Нарисуйте вертикальную линию в этой позиции x до максимального значения y функции плотности вероятности распределения предложения.
Равномерно выполните выборку по этой линии от 0 до максимума функции плотности вероятности. Если значение выборки больше, чем значение желаемого распределения на этой вертикальной линии, отклоните значение x и вернитесь к шагу 1; иначе значение x является выборкой из желаемого распределения.

Этот алгоритм можно использовать для выборки из области под любой кривой, независимо от того, интегрируется ли функция в 1. Фактически, масштабирование функции с помощью константы не влияет на выбранные позиции по оси x. Таким образом, алгоритм может использоваться для выборки из распределения, нормирующая константа которого неизвестна, что является обычным явлением в статистике вычислений .

Теория

Метод отклонения выборки генерирует выборочные значения из целевого распределения с произвольной функцией плотности вероятности с использованием распределения предложения с плотностью вероятности . Идея состоит в том, что можно сгенерировать значение выборки, взяв вместо этого выборку из и приняв выборку с вероятностью , повторяя выборки от до тех пор, пока значение не будет принято. здесь является константой, конечная границей отношения правдоподобия , удовлетворяющий по поддержке из ; другими словами, M должен удовлетворять для всех значений . Обратите внимание, что для этого требуется, чтобы поддержка включала поддержку - другими словами, всякий раз , когда . ${\ displaystyle X}$ ${\ displaystyle f (x)}$ ${\ displaystyle Y}$ ${\ displaystyle g (x)}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Y}$ ${\ Displaystyle f (x) / (Mg (x))}$ ${\ displaystyle Y}$ ${\ displaystyle M}$ ${\ Displaystyle е (х) / г (х)}$ ${\ Displaystyle 1 <М <\ infty}$ ${\ displaystyle X}$ ${\ Displaystyle е (х) \ Leq Mg (х)}$ ${\ displaystyle x}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle g (x)> 0}$ ${\ displaystyle f (x)> 0}$

Подтверждением этого метода является принцип конверта: при моделировании пары создается однородная симуляция над подграфом . Принимая только пары, которые затем производят пары, равномерно распределенные по подграфу, и, таким образом, незначительно, симуляция из ${\ textstyle (х, v = и \ cdot Mg (x))}$ ${\ textstyle Mg (x)}$ ${\ textstyle и <е (х) / (Mg (x))}$ ${\ Displaystyle (х, v)}$ ${\ displaystyle f (x)}$ ${\ displaystyle f (x).}$

Это означает, что при достаточном количестве реплик алгоритм генерирует выборку из желаемого распределения . У этого алгоритма есть ряд расширений, например, алгоритм Метрополиса . ${\ displaystyle f (x)}$

Этот метод относится к общей области методов Монте-Карло , включая алгоритмы Монте-Карло цепи Маркова, которые также используют прокси-распределение для моделирования из целевого распределения . Он составляет основу таких алгоритмов, как алгоритм Метрополиса . ${\ displaystyle f (x)}$

Вероятность безусловной приемки - это доля предложенных образцов, которые приняты, т.е.

{\ displaystyle {\ begin {align} \ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right) & = \ operatorname {E} \ mathbf {1 } _ {\ left [U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right]} \\ [6pt] & = E \ left [\ operatorname {E} [\ mathbf {1 } _ {\ left [U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right]} | Y] \ right] & ({\ text {по свойству башни}}) \\ [ 6pt] & = \ operatorname {E} \ left [\ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} {\ biggr |} Y \ right) \ right ] \\ [6pt] & = E \ left [{\ frac {f (Y)} {Mg (Y)}} \ right] & ({\ text {потому что}} \ Pr (U \ leq u) = u , {\ text {when}} U {\ text {равномерно на}} (0,1)) \\ [6pt] & = \ int \ limits _ {y: g (y)> 0} {\ frac { f (y)} {Mg (y)}} g (y) \, dy \\ [6pt] & = {\ frac {1} {M}} \ int \ limits _ {y: g (y)> 0 } f (y) \, dy \\ [6pt] & = {\ frac {1} {M}} & ({\ text {поскольку поддержка}} Y {\ text {включает поддержку}} X) \ end {выровнено}}}

где , и значение каждого времени генерируется под функцией плотности распределения предложения .

{\ Displaystyle U \ sim \ mathrm {Unif} (0,1)}

{\ displaystyle y}

{\ Displaystyle г (\ cdot)}

{\ displaystyle Y}

Таким образом, количество выборок, необходимых для получения принятого значения, следует геометрическому распределению с вероятностью , которая имеет среднее значение . Интуитивно это ожидаемое количество необходимых итераций как мера вычислительной сложности алгоритма. ${\ displaystyle Y}$ ${\ displaystyle 1 / M}$ ${\ displaystyle M}$ ${\ displaystyle M}$

Перепишите приведенное выше уравнение,

{\ displaystyle M = {\ frac {1} {\ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right)}}}

Обратите внимание, что из-за приведенной выше формулы, где - вероятность, которая может принимать значения только в интервале . Когда выбирается ближе к единице, вероятность безусловного принятия тем выше, чем меньше изменяется это отношение, поскольку это верхняя граница отношения правдоподобия . На практике значение, близкое к 1, является предпочтительным, поскольку оно подразумевает в среднем меньшее количество отклоненных выборок и, следовательно, меньшее количество итераций алгоритма. В этом смысле предпочтение отдается как можно меньшему размеру (но при этом удовлетворительно , что предполагает, что это в целом должно в чем-то напоминать . Однако обратите внимание, что это не может быть равно 1: это будет означать, что , т. Е. Целевое распределение и распределение предложений фактически одно и то же распределение.

{\ textstyle 1 \ leq M <\ infty}

{\ textstyle \ mathbb {P} \ left (U \ leq {\ frac {f (Y)} {Mg (Y)}} \ right)}

{\ displaystyle [0,1]}

{\ displaystyle M}

{\ displaystyle M}

{\ textstyle f (x) / g (x)}

{\ displaystyle M}

{\ displaystyle M}

{\ Displaystyle е (х) \ Leq Mg (х)}

{\ displaystyle g (x)}

{\ displaystyle f (x)}

{\ displaystyle M}

{\ Displaystyle е (х) = г (х)}

Отбор проб отбраковки чаще всего используется в тех случаях, когда форма отбора проб затрудняет. Одна итерация алгоритма отклонения требует выборки из распределения предложения, извлечения из равномерного распределения и оценки выражения. Таким образом, отбор с отбраковкой более эффективен, чем какой-либо другой метод, когда M-кратная стоимость этих операций, которая является ожидаемой стоимостью получения образца с отбором с отбраковкой, ниже, чем стоимость получения образца с использованием другого метода. ${\ displaystyle f (x)}$ ${\ Displaystyle f (x) / (Mg (x))}$

Алгоритм

Алгоритм (используемый Джоном фон Нейманом и восходящий к Бюффону и его игле ) для получения выборки из распределения с плотностью с использованием выборок из распределения с плотностью выглядит следующим образом: ${\ displaystyle X}$ ${\ displaystyle f}$ ${\ displaystyle Y}$ ${\ displaystyle g}$

Получите выборку из распределения и выборку из (равномерного распределения в единичном интервале). ${\ displaystyle y}$ ${\ displaystyle Y}$ ${\ displaystyle u}$ ${\ Displaystyle \ mathrm {Unif} (0,1)}$
Проверь, стоит ли . ${\ textstyle и <f (y) / Mg (y)}$ ${\ textstyle и <f (y) / Mg (y)}$
- Если это так, примите как образец, взятый из ; ${\ displaystyle y}$ ${\ displaystyle f}$
- в противном случае отклоните значение и вернитесь к шагу выборки. ${\ displaystyle y}$

Алгоритм потребует в среднем итераций для получения выборки. ${\ displaystyle M}$

Преимущества перед выборкой с использованием наивных методов

В некоторых ситуациях выборка отклонения может быть намного более эффективной по сравнению с наивными методами. Например, задана проблема как выборка, обусловленная заданным набором , т. Е. Иногда может быть легко смоделирована с использованием наивных методов (например, путем выборки с обратным преобразованием ): ${\ textstyle X \ sim F (\ cdot)}$ ${\ displaystyle X}$ ${\ displaystyle A}$ ${\ textstyle X | X \ in A}$ ${\ textstyle X}$

Самостоятельно пробуйте и оставьте тех, кто удовлетворяет ${\ textstyle X \ sim F (\ cdot)}$ ${\ Displaystyle \ {п \ geq 1: X_ {п} \ в А \}}$
Выход: ${\ displaystyle \ {X_ {1}, X_ {2}, ..., X_ {N}: X_ {i} \ in A, i = 1, ..., N \}}$

Проблема в том, что эта выборка может быть сложной и неэффективной, если . Ожидаемое количество итераций может быть близким к бесконечности. Более того, даже когда вы применяете метод выборки отклонения, всегда сложно оптимизировать границу для отношения правдоподобия. Чаще всего большой и процент отклонения высок, алгоритм может быть очень неэффективным. Естественные экспоненциальные семьи (если она существует), также известные как экспоненциальный наклон, обеспечивает класс распределений предложения , которое может снизить сложность вычислений, значение и ускорение вычислений (см примеров: работа с природной экспоненциальными семьями). ${\ textstyle \ mathbb {P} (Х \ в А) \ приблизительно 0}$ ${\ displaystyle {\ frac {1} {\ mathbb {P} (X \ in A)}}}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle M}$

Примеры: работа с естественными экспоненциальными семействами

Учитывая случайная величина , является объектом распределения. Предположим для простоты, что функция плотности может быть явно записана как . Выберите предложение как ${\ Displaystyle Х \ сим F (\ cdot)}$ ${\ Displaystyle F (х) = \ mathbb {P} (X \ leq x)}$ ${\ displaystyle f (x)}$

{\ displaystyle {\ begin {align} F _ {\ theta} (x) & = \ mathbb {E} \ left [\ exp (\ theta X- \ psi (\ theta)) \ mathbb {I} (X \ leq x) \ right] \\ & = \ int _ {- \ infty} ^ {x} e ^ {\ theta y- \ psi (\ theta)} f (y) dy \\ g _ {\ theta} (x) & = F '_ {\ theta} (x) = e ^ {\ theta x- \ psi (\ theta)} f (x) \ end {align}}}

где и . Ясно, что из естественного экспоненциального семейства . Кроме того, отношение правдоподобия равно

{\ Displaystyle \ psi (\ theta) = \ log \ left (\ mathbb {E} \ exp (\ theta X) \ right)}

{\ Displaystyle \ Theta = \ {\ theta: \ psi (\ theta) <\ infty \}}

{\ Displaystyle \ {F _ {\ theta} (\ cdot) \} _ {\ theta \ in \ Theta}}

{\ Displaystyle Z (x) = {\ frac {f (x)} {g _ {\ theta} (x)}} = {\ frac {f (x)} {e ^ {\ theta x- \ psi (\ theta)} f (x)}} = e ^ {- \ theta x + \ psi (\ theta)}}

Обратите внимание, это означает, что это действительно функция генерации момента журнала , то есть . И легко вывести логарифмическую функцию создания моментов предложения и, следовательно, моментов предложения.

{\ Displaystyle \ пси (\ тета) <\ infty}

{\ Displaystyle \ psi (\ theta) = \ log \ mathbb {E} {\ exp (tX)} | _ {t = \ theta} = \ log M_ {X} (t) | _ {t = \ theta} }

{\ Displaystyle {\ begin {выровнено} \ psi _ {\ theta} (\ eta) & = \ log \ left (\ mathbb {E} _ {\ theta} \ exp (\ eta X) \ right) = \ psi (\ theta + \ eta) - \ psi (\ theta) <\ infty \\\ mathbb {E} _ {\ theta} (X) & = \ left. {\ frac {\ partial \ psi _ {\ theta} (\ eta)} {\ partial \ eta}} \ right | _ {\ eta = 0} \\\ mathrm {Var} _ {\ theta} (X) & = \ left. {\ frac {\ partial ^ { 2} \ psi _ {\ theta} (\ eta)} {\ partial ^ {2} \ eta}} \ right | _ {\ eta = 0} \ end {align}}}

В качестве простого примера предположим, что Under , с . Цель состоит в том, чтобы образец , . Анализ идет следующим образом.

{\ Displaystyle F (\ cdot)}

{\ Displaystyle X \ sim \ mathrm {N} (\ mu, \ sigma ^ {2})}

{\ textstyle \ psi (\ theta) = \ theta \ mu + {\ frac {\ sigma ^ {2} \ theta ^ {2}} {2}}}

{\ displaystyle X | X \ in \ left [b, \ infty \ right]}

{\ displaystyle b> \ mu}

Выберите форму распределения предложения с логарифмической функцией генерирования момента как , что в дальнейшем подразумевает, что это нормальное распределение . ${\ Displaystyle F _ {\ theta} (\ cdot)}$ ${\ textstyle \ psi _ {\ theta} (\ eta) = \ psi (\ theta + \ eta) - \ psi (\ eta) = \ eta (\ mu + \ theta \ sigma ^ {2}) + {\ гидроразрыв {\ sigma ^ {2} \ eta ^ {2}} {2}}}$ ${\ Displaystyle \ mathrm {N} (\ му + \ тета \ сигма ^ {2}, \ сигма ^ {2})}$
Определите удачный вариант для распространения предложения. В этой настройке интуитивно понятный способ выбора - установить , то есть ${\ displaystyle \ theta ^ {*}}$ ${\ displaystyle \ theta ^ {*}}$ ${\ Displaystyle \ mathbb {E} _ {\ theta} (X) = \ mu + \ theta \ sigma ^ {2} = b}$ ${\ displaystyle \ theta ^ {*} = {\ frac {b- \ mu} {\ sigma ^ {2}}}}$
Четко запишите цель, предложение и отношение правдоподобия ${\ displaystyle {\ begin {align} f_ {X | X \ geq b} (x) & = {\ frac {f (x) \ mathbb {I} (x \ geq b)} {\ mathbb {P} ( x \ geq b)}} \\ g _ {\ theta ^ {*}} (x) & = f (x) \ exp (\ theta ^ {*} x- \ psi (\ theta ^ {*})) \ \ Z (x) & = {\ frac {f_ {X | X \ geq b} (x)} {g _ {\ theta ^ {*}} (x)}} = {\ frac {\ exp (- \ theta ^ {*} x + \ psi (\ theta ^ {*})) \ mathbb {I} (x \ geq b)} {\ mathbb {P} (x \ geq b)}} \ end {выровнено}}}$
Получите оценку отношения правдоподобия , которое является убывающей функцией для , поэтому ${\ displaystyle M}$ ${\ Displaystyle г (х)}$ ${\ Displaystyle х \ в [b, \ infty]}$ ${\ Displaystyle М = Z (b) = {\ гидроразрыва {\ ехр (- \ theta ^ {*} b + \ psi (\ theta ^ {*}))} {\ mathbb {P} (X \ geq b)} } = {\ frac {\ exp \ left (- {\ frac {(b- \ mu) ^ {2}} {2 \ sigma ^ {2}}} \ right)} {\ mathbb {P} (X \ geq b)}} = {\ frac {\ exp \ left (- {\ frac {(b- \ mu) ^ {2}} {2 \ sigma ^ {2}}} \ right)} {\ mathbb {P } \ left (\ mathrm {N} (0,1) \ geq {\ frac {b- \ mu} {\ sigma}} \ right)}}}$
Критерий отбраковки выборки: для , если ${\ Displaystyle U \ sim \ mathrm {Unif} (0,1)}$ ${\ Displaystyle U \ leq {\ frac {Z (x)} {M}} = e ^ {- \ theta ^ {*} (xb)} \ mathbb {I} (x \ geq b)}$ держит, примите значение ; в противном случае продолжайте отбор новых и новых образцов до приемки. ${\ displaystyle X}$ ${\ textstyle X \ sim _ {iid} \ mathrm {N} (\ mu + \ theta ^ {*} \ sigma ^ {2}, \ sigma ^ {2})}$ ${\ textstyle U \ sim \ mathrm {Unif} (0,1)}$

Для приведенного выше примера в качестве измерения эффективности ожидаемое количество итераций метода выборки отбраковки на основе NEF имеет порядок b, то есть , в то время как в наивном методе ожидаемое количество итераций равно , что далеко более неэффективно. ${\ Displaystyle М (Ь) = О (Ь)}$ ${\ textstyle {\ frac {1} {\ mathbb {P} (X \ geq b)}} = O (b \ cdot e ^ {\ frac {(b- \ mu) ^ {2}} {2 \ sigma ^ {2}}})}$

В общем, экспоненциальный наклон, параметрический класс распределения предложения, удобно решает проблемы оптимизации, благодаря своим полезным свойствам, которые напрямую характеризуют распределение предложения. Для этого типа проблемы, чтобы смоделировать условно , среди класса простых распределений, хитрость заключается в использовании NEF, что помогает получить некоторый контроль над сложностью и значительно ускорить вычисления. Действительно, есть глубокие математические причины для использования NEF. ${\ displaystyle X}$ ${\ displaystyle X \ in A}$

Недостатки

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

Адаптивное отклонение выборки

Для многих дистрибутивов сложно найти такой дистрибутив, который включает данный дистрибутив без лишнего использования места. Расширение выборки отбраковки, которое можно использовать для преодоления этой трудности и эффективной выборки из широкого спектра распределений (при условии, что они имеют логарифмически вогнутые функции плотности, что на самом деле имеет место для большинства распространенных распределений - даже тех, плотность которых сами функции не являются вогнутыми!) называется адаптивной выборкой отбраковки (ARS) .

В этой технике, в конечном счете, представленной Гилксом в 1992 году, есть три основные идеи:

Если это помогает, вместо этого определите распределение конвертов в пространстве журнала (например, логарифмическую вероятность или логарифмическую плотность). То есть работать с, а не напрямую. ${\ Displaystyle ч \ влево (х \ вправо) = \ журнал г \ влево (х \ вправо)}$ ${\ Displaystyle ч \ влево (х \ вправо) = \ журнал г \ влево (х \ вправо)}$ ${\ Displaystyle г \ влево (х \ вправо)}$ $г \ влево (х \ вправо)$
- Часто распределения, которые имеют алгебраически беспорядочные функции плотности, имеют достаточно простые функции логарифмической плотности (то есть, когда они беспорядочные, с ними легче работать или, по крайней мере, они ближе к кусочно-линейным). ${\ Displaystyle е \ влево (х \ вправо)}$ ${\ Displaystyle \ журнал е \ влево (х \ вправо)}$
Вместо одной функции равномерной плотности конверта используйте в качестве конверта кусочно-линейную функцию плотности.
- Каждый раз, когда вам нужно отклонить образец, вы можете использовать значение, которое вы оценили, для улучшения кусочного приближения . Таким образом, это снижает вероятность того, что ваша следующая попытка будет отклонена. Асимптотически вероятность отклонения выборки должна стремиться к нулю, а на практике часто очень быстро. ${\ Displaystyle е \ влево (х \ вправо)}$ ${\ Displaystyle ч \ влево (х \ вправо)}$
- Согласно предложению, каждый раз, когда мы выбираем отклоняемую точку, мы стягиваем огибающую другим отрезком линии, который касается кривой в точке с той же координатой x, что и выбранная точка.
- Кусочно-линейная модель логарифмического распределения предложения приводит к набору кусочно- экспоненциальных распределений (то есть сегментов одного или нескольких экспоненциальных распределений, прикрепленных встык). Экспоненциальные распределения хорошо известны и понятны. Логарифм экспоненциального распределения представляет собой прямую линию, и, следовательно, этот метод по существу включает в себя включение логарифма плотности в серию отрезков прямой. Это источник ограничения логарифмической вогнутости: если распределение логарифмически вогнутое, то его логарифм вогнутый (имеет форму перевернутой буквы U), что означает, что касательный к кривой отрезок прямой всегда будет проходить над кривой.
- Если не работает в журнальном пространстве, кусочно-линейная функция плотности также может быть выбрана с помощью треугольных распределений.
Мы можем воспользоваться еще одним преимуществом требования (логарифмической) вогнутости, чтобы потенциально избежать затрат на оценку того, когда ваш образец

будет принят.

{\ Displaystyle е \ влево (х \ вправо)}

Точно так же, как мы можем построить кусочно-линейную верхнюю границу (функцию «конверта»), используя значения, которые мы должны были оценить в текущей цепочке отклонений, мы также можем построить кусочно-линейную нижнюю границу (функция «сжатия»), используя эти значения тоже. ${\ Displaystyle ч \ влево (х \ вправо)}$
Перед оценкой (потенциально дорогостоящей), чтобы увидеть, будет ли принят ваш образец, мы можем

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

{\ Displaystyle е \ влево (х \ вправо)}

{\ Displaystyle г_ {л} \ влево (х \ вправо)}

{\ Displaystyle ч_ {л} \ влево (х \ вправо)}

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

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

К сожалению, ARS можно применять только на основе выборки из логарифмически вогнутых целевых плотностей. По этой причине в литературе было предложено несколько расширений ARS для устранения логарифмически вогнутых целевых распределений. Кроме того, были разработаны различные комбинации ARS и метода Метрополиса-Гастингса, чтобы получить универсальный пробоотборник, который строит самонастраивающиеся плотности предложений (т. Е. Предложение, автоматически построенное и адаптированное к цели). Этот класс методов часто называют алгоритмами Adaptive Rejection Metropolis Sampling (ARMS) . Результирующие адаптивные методы можно всегда применять, но в этом случае сгенерированные выборки коррелируются (хотя корреляция быстро исчезает до нуля по мере увеличения количества итераций).

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

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

Роберт С.П. и Казелла Г. «Статистические методы Монте-Карло» (второе издание). Нью-Йорк: Springer-Verlag, 2004.
J. von Neumann, "Различные методы, используемые в связи со случайными числами. Методы Монте-Карло", Nat. Стандарты бюро, 12 (1951), стр. 36–38.

Languages

In other projects