Выборка срезов - Slice sampling

Выборка срезов это тип Цепь Маркова Монте-Карло алгоритм за выборка псевдослучайных чисел, т.е. для получения случайных выборок из статистического распределения. Метод основан на наблюдении, что для отбора проб случайная переменная можно получить однородную выборку из области под графиком функции плотности.^[1][2][3]

Мотивация

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

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

Чтобы попробовать Икс таким образом, чтобы сохранить распределение ж(Икс), необходимо использовать некоторый метод выборки, который учитывает различную вероятность для каждого диапазона ж(Икс).

Метод

В простейшей форме выборка срезов равномерно отбирает из-под кривой. ж(Икс) без необходимости отклонять какие-либо точки, а именно:

1. Выберите начальное значение x₀ для которого ж(Икс₀) > 0.
2. Образец у значение равномерно от 0 до ж(Икс₀).
3. Проведите горизонтальную линию поперек кривой в этом месте. у позиция.
4. Выбрать точку (Икс, у) от отрезков линии внутри кривой.
5. Повторите с шага 2, используя новый Икс ценить.

Мотивация здесь заключается в том, что один из способов получить однородную выборку точки внутри произвольной кривой - это сначала провести тонкие горизонтальные срезы одинаковой высоты по всей кривой. Затем мы можем выбрать точку на кривой, случайным образом выбрав срез, который находится на или ниже кривой в позиции x из предыдущей итерации, а затем случайным образом выбрав позицию x где-нибудь вдоль среза. Используя координату x из предыдущей итерации алгоритма, в конечном итоге мы выбираем срезы с вероятностями, пропорциональными длинам их сегментов внутри кривой. Самая трудная часть этого алгоритма - это нахождение границ горизонтального среза, который включает в себя инвертирование функции, описывающей распределение, из которого производится выборка. Это особенно проблематично для мультимодальных распределений, где срез может состоять из нескольких прерывистых частей. Часто для преодоления этого можно использовать форму отбраковки выборки, когда мы выбираем из большего среза, который, как известно, включает желаемый рассматриваемый срез, а затем отбрасываем точки за пределами желаемого среза. Этот алгоритм можно использовать для выборки. из области под любой кривой, независимо от того, интегрируется ли функция в 1. Фактически, масштабирование функции с помощью константы не влияет на выбранные позиции x. Это означает, что алгоритм можно использовать для выборки из распределения, функция плотности вероятности известен только с точностью до константы (т.е. чья нормализующая константа неизвестно), что часто встречается в вычислительная статистика.

Выполнение

Выборка срезов получила свое название от первого шага: определение ломтик путем выборки из вспомогательной переменной ${displaystyle Y}$. Эта переменная взята из ${displaystyle [0,f(x)]}$, куда ${displaystyle f(x)}$ либо функция плотности вероятности (PDF) из Икс или, по крайней мере, пропорциональна его PDF. Это определяет часть Икс куда ${displaystyle f(x)geq Y}$. Другими словами, сейчас мы смотрим на область Икс где плотность вероятности не менее ${displaystyle Y}$. Затем следующее значение Икс равномерно отбирается из этого среза. Новое значение ${displaystyle Y}$ выбирается, то Икс, и так далее. Это можно визуализировать как альтернативную выборку положения y, а затем x-положения точек в PDF, таким образом, Иксs из желаемого распределения. В ${displaystyle Y}$ ценности не имеют особых последствий или интерпретаций, кроме их полезности для процедуры.

Если доступны и PDF-файл, и его обратный, и распределение является одномодальным, то найти срез и выборку из него будет просто. Если нет, то можно использовать процедуру выхода, чтобы найти область, конечные точки которой выходят за пределы среза. Затем образец можно взять из среза, используя отбраковка. Различные процедуры для этого подробно описаны Нилом.^[2]

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

По сравнению с другими методами

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

Напомним, Метрополис чувствителен к размеру шага. Если размер шага слишком мал случайная прогулка вызывает медленную декорреляцию. Если размер шага слишком велик, это приводит к большой неэффективности из-за высокой скорости отклонения.

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

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

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

Одномерный случай

Для данного образца x значение y выбирается из [0, ж(Икс)], который определяет «срез» распределения (показан сплошной горизонтальной линией). В этом случае есть два фрагмента, разделенных областью за пределами диапазона распределения.

Чтобы выбрать случайную величину Икс с плотностью ж(Икс) введем вспомогательную переменную Y и повторяем следующим образом:

• Учитывая образец Икс мы выбрали у равномерно случайным образом из интервала [0, ж(Икс)];
• данный у мы выбрали Икс равномерно случайным образом из множества ${displaystyle f^{-1}[y,+infty )}$.
• Образец Икс получается игнорированием у значения.

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

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

• Во-первых, параметр ширины ш используется для определения области, содержащей данный 'x ценить. Каждая конечная точка этой области проверяется, чтобы увидеть, находится ли она за пределами данного среза. Если нет, то область расширяется в соответствующем направлении (ах) на ш до конца обе конечные точки лежат вне среза.
• Выборка-кандидат выбирается равномерно из этого региона. Если образец-кандидат находится внутри среза, он принимается как новый образец. Если он находится за пределами среза, точка-кандидат становится новой границей для области. Новая выборка кандидатов отбирается равномерно. Процесс повторяется до тех пор, пока образец-кандидат не окажется внутри среза. (См. Диаграмму для наглядного примера).

Нахождение образца по набору срезов (срезы здесь представлены синими линиями и соответствуют срезам сплошной линией на предыдущем графике ж(Икс)). а) Параметр ширины ш установлен. б) Область шириной ш определяется вокруг данной точки ${displaystyle x_{0}}$. в) Область расширяется на ш пока обе конечные точки не выйдут за пределы рассматриваемого среза. г) ${displaystyle x_{1}}$ выбирается равномерно по региону. д) Поскольку ${displaystyle x_{1}}$ лежит за пределами рассматриваемого среза, левая граница области настраивается на ${displaystyle x_{1}}$. е) Другой образец униформы ${displaystyle x}$ берется и принимается в качестве образца, поскольку он находится в рассматриваемом срезе.

→

Выборка среза внутри Гиббса

В Сэмплер Гиббса, необходимо эффективно извлекать из всех полностью условных распределений. Когда выборка из полной условной плотности непроста, для выборки из рассматриваемой переменной можно использовать одну итерацию выборки срезов или алгоритм Метрополиса-Гастингса в пределах Гиббса. Если полная условная плотность логарифмически вогнута, более эффективной альтернативой является применение адаптивное отклонение выборки (ARS) методы.^[4][5] Когда методы ARS не могут быть применены (так как полное условие не является логарифмически вогнутым), алгоритмы выборки с адаптивным отклонением Метрополис часто используются.^[6][7]

Многовариантные методы

Независимая обработка каждой переменной

Выборка срезов одной переменной может использоваться в многомерном случае путем повторной выборки каждой переменной, как в выборке Гиббса. Для этого необходимо, чтобы мы могли вычислить для каждого компонента ${displaystyle x_{i}}$ функция, пропорциональная ${displaystyle p(x_{i}|x_{0}...x_{n})}$.

Чтобы предотвратить случайное блуждание, можно использовать методы чрезмерной релаксации для обновления каждой переменной по очереди.^{[нужна цитата ]} Чрезмерное расслабление выбирает новое значение на противоположной стороне режима от текущего значения, в отличие от выбора нового независимого значения из распределения, как это сделано в Гиббсе.

Выборка среза гипер прямоугольника

Этот метод адаптирует одномерный алгоритм к многомерному случаю, заменяя одномерный гипер прямоугольник. ш регион, использованный в оригинале. Гиперпрямоугольник ЧАС инициализируется произвольной позицией на срезе. ЧАС затем уменьшается, поскольку точки из него отклоняются.

Выборка отражающих срезов

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

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

Пример

Рассмотрим пример с одной переменной. Предположим, что наше истинное распределение - это нормальное распределение со средним 0 и стандартным отклонением 3, ${displaystyle g(x)sim N(0,3^{2})}$. Так:${displaystyle f(x)={frac {1}{sqrt {2pi cdot 3^{2}}}} e^{-{frac {(x-0)^{2}}{2cdot 3^{2}}}}}$. Пик распределения, очевидно, находится на ${displaystyle x=0}$, в этот момент ${displaystyle f(x)approx 0.1330}$.

1. Сначала рисуем однородное случайное значение у из диапазона ж(Икс), чтобы определить наши срезы. ж(Икс) находится в диапазоне от 0 до ~ 0,1330, поэтому достаточно любого значения между этими двумя крайними значениями. Допустим, мы берем у = 0,1. Проблема заключается в том, как выбрать точки, которые имеют значения у > 0.1.
2. Затем мы устанавливаем наш параметр ширины ш которые мы будем использовать для расширения области рассмотрения. Это значение произвольно. Предполагать ш = 2.
3. Далее нам нужно начальное значение для Икс. Мы рисуем Икс из равномерного распределения в области ж(Икс) который удовлетворяет ж(Икс)> 0,1 (наш у параметр). Предполагать Икс = 2. Это работает, потому что ж(2) = ~0.1065 > 0.1.^[8]
4. Потому что Икс = 2 и ш = 2, наша текущая область интересов ограничена (1, 3).
5. Теперь каждая конечная точка этой области проверяется, чтобы увидеть, находится ли она за пределами данного среза. Наша правая граница лежит за пределами нашего среза (ж(3) = ~ 0,0807 <0,1), но левое значение не (ж(1) = ~ 0,1258> 0,1). Мы расширяем левую границу, добавляя ш к нему, пока он не выйдет за пределы среза. После этого процесса новые границы области нашего интереса будут (−3, 3).
6. Затем мы берем однородную выборку в пределах (−3, 3). Предположим, что этот образец дает x = −2,9. Хотя этот образец находится в пределах нашей области интереса, он не находится в пределах нашего среза (f (2.9) = ~ 0,08334 <0,1), поэтому мы модифицируем левую границу нашей области интереса до этой точки. Теперь возьмем однородную выборку из (−2.9, 3). Предположим, на этот раз наш образец дает x = 1, который находится в пределах нашего среза, и, таким образом, это принятый образец, выводимый с помощью сэмплирования среза. Был наш новый Икс не было в пределах нашего среза, мы будем продолжать процесс сжатия / повторной выборки до тех пор, пока Икс в пределах не найдено.

Если нас интересует пик распределения, мы можем продолжать повторять этот процесс, поскольку новая точка соответствует более высокому ж(Икс), чем исходная точка.

Другой пример

Чтобы пробовать из нормальное распределение ${displaystyle N(0,1)}$ мы сначала выбираем начальную Икс- говорят 0. После каждой пробы Икс мы выбрали у равномерно наугад от ${displaystyle (0,e^{-x^{2}/2}/{sqrt {2pi }}]}$, которая ограничивает PDF ${displaystyle N(0,1)}$. После каждого у образец мы выбираем Икс равномерно наугад от ${displaystyle [-alpha ,alpha ]}$ куда ${displaystyle alpha ={sqrt {-2ln(y{sqrt {2pi }})}}}$. Это кусок, где ${displaystyle f(x)>y}$.

Реализация в Macsyma язык:

ломтик(Икс) := блокировать([у, альфа], y:случайный(exp(-Икс^2 / 2.0) / sqrt(2.0 * dfloat(%число Пи))), альфа:sqrt(-2.0 * пер(у * sqrt(2.0 * dfloat(%число Пи)))), Икс:сигнум(случайный()) * случайный(альфа));

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

• Цепь Маркова Монте-Карло

Рекомендации

1. Дамлен П., Уэйкфилд Дж. И Уокер С. (1999). Выборка Гиббса для байесовских несопряженных и иерархических моделей с использованием вспомогательных переменных. Журнал Королевского статистического общества, серия B (статистическая методология), 61 (2), 331-344, Чикаго
2. Нил, Рэдфорд М. (2003). «Выборка срезов». Анналы статистики. 31 (3): 705–767. Дои:10.1214 / aos / 1056562461. МИСТЕР  1994729. Zbl  1051.65007.
3. Епископ, Кристофер (2006). «11.4: Выборка срезов». Распознавание образов и машинное обучение. Springer. ISBN  978-0387310732.
4. Gilks, W. R .; Уайлд, П. (1992-01-01). «Адаптивная выборка отбраковки для выборки Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 41 (2): 337–348. Дои:10.2307/2347565. JSTOR  2347565.
5. Хёрманн, Вольфганг (01.06.1995). «Метод отклонения для отбора проб из T-вогнутых распределений». ACM Trans. Математика. Softw. 21 (2): 182–193. CiteSeerX  10.1.1.56.6055. Дои:10.1145/203082.203089. ISSN  0098-3500.
6. Gilks, W. R .; Бест, Н.Г.; Тан, К. К. (1995-01-01). «Адаптивное отклонение семплирования мегаполиса в рамках семплирования Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 44 (4): 455–472. Дои:10.2307/2986138. JSTOR  2986138.
7. Мейер, Ренате; Цай, Бо; Перрон, Франсуа (15 марта 2008 г.). «Адаптивное отклонение выборки Метрополиса с использованием полиномов интерполяции Лагранжа степени 2». Вычислительная статистика и анализ данных. 52 (7): 3408–3423. Дои:10.1016 / j.csda.2008.01.005.
8. Обратите внимание: если мы не знали, как выбрать Икс такой, что ж(Икс) > у, мы все еще можем выбрать любое случайное значение для Икс, оценивать ж(Икс), и использовать это как нашу ценность у. у только инициализирует алгоритм; по мере продвижения алгоритма он будет находить все более и более высокие значения у.

внешняя ссылка

• http://www.probability.ca/jeff/java/slice.html