Срез выборки

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

Мотивация

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

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

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

Метод

Срезовая выборка в своей простейшей форме осуществляет выборку равномерно из-под кривой f ( x ) без необходимости отбрасывать какие-либо точки следующим образом:

Выберите начальное значение x _0, для которого f ( x ₀ ) > 0.
Выборка значения a y равномерно между 0 и f ( x ₀ ).
Нарисуйте горизонтальную линию через кривую в этой позиции y .
Выберите точку ( x , y ) из сегментов линии внутри кривой.
Повторите действия, начиная с шага 2, используя новое значение x .

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

Выполнение

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

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

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

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

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

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

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

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

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

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

Чтобы выбрать случайную величину X с плотностью f ( x ), мы вводим вспомогательную переменную Y и выполняем итерацию следующим образом:

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

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

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

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

→

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

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

Многомерные методы

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

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

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

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

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

Отражательная выборка срезов

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

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

Пример

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

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

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

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

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

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

slice(x) := block([y, alpha],
 y:random(exp(-x^2 / 2.0) / sqrt(2.0 * dfloat(%pi))),
 alpha:sqrt(-2.0 * ln(y * sqrt(2.0 * dfloat(%pi)))),
 x:signum(random()) * random(alpha)
);

См. также

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

Ссылки

^ Дамлен П., Уэйкфилд Дж. и Уокер С. (1999). Выборка Гиббса для байесовских несопряженных и иерархических моделей с использованием вспомогательных переменных. Журнал Королевского статистического общества, серия B (статистическая методология), 61 (2), 331-344. Чикаго.
^ Jump up to: ^а ^б Нил, Рэдфорд М. (2003). «Срезовая выборка» . Анналы статистики . 31 (3): 705–767. дои : 10.1214/aos/1056562461 . МР 1994729 . Збл 1051.65007 .
^ Бишоп, Кристофер (2006). «11.4: Выборка срезов». Распознавание образов и машинное обучение . Спрингер . ISBN 978-0387310732 .
^ Гилкс, WR; Уайлд, П. (1 января 1992 г.). «Адаптивная отбраковочная выборка для выборки Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика) . 41 (2): 337–348. дои : 10.2307/2347565 . JSTOR 2347565 .
^ Хёрманн, Вольфганг (1 июня 1995 г.). «Техника отклонения выборки из Т-вогнутых распределений». АКМ Транс. Математика. Программное обеспечение . 21 (2): 182–193. CiteSeerX 10.1.1.56.6055 . дои : 10.1145/203082.203089 . ISSN 0098-3500 . S2CID 592740 .
^ Гилкс, WR; Бест, Нью-Йорк ; Тан, KKC (1 января 1995 г.). «Выборка мегаполиса с адаптивным отклонением в рамках выборки Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика) . 44 (4): 455–472. дои : 10.2307/2986138 . JSTOR 2986138 .
^ Мейер, Рената; Кай, Бо; Перрон, Франсуа (15 марта 2008 г.). «Адаптивная отбраковка выборки Метрополиса с использованием интерполяционных полиномов Лагранжа 2-й степени». Вычислительная статистика и анализ данных . 52 (7): 3408–3423. дои : 10.1016/j.csda.2008.01.005 .
^ Обратите внимание: если мы не знали, как выбрать x так, чтобы f ( x ) > y , мы все равно можем выбрать любое случайное значение для x , вычислить f ( x ) и использовать его в качестве значения y . y только инициализирует алгоритм; по мере продвижения алгоритма он будет находить все более и более высокие значения y .

Внешние ссылки

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

[1] Дамлен П., Уэйкфилд Дж. и Уокер С. (1999). Выборка Гиббса для байесовских несопряженных и иерархических моделей с использованием вспомогательных переменных. Журнал Королевского статистического общества, серия B (статистическая методология), 61 (2), 331-344. Чикаго.

[radford03-2] Jump up to: ^а ^б Нил, Рэдфорд М. (2003). «Срезовая выборка» . Анналы статистики . 31 (3): 705–767. дои : 10.1214/aos/1056562461 . МР 1994729 . Збл 1051.65007 .

[bishop06-3] Бишоп, Кристофер (2006). «11.4: Выборка срезов». Распознавание образов и машинное обучение . Спрингер . ISBN 978-0387310732 .

[4] Гилкс, WR; Уайлд, П. (1 января 1992 г.). «Адаптивная отбраковочная выборка для выборки Гиббса». Журнал Королевского статистического общества. Серия C (Прикладная статистика) . 41 (2): 337–348. дои : 10.2307/2347565 . JSTOR 2347565 .

[5] Хёрманн, Вольфганг (1 июня 1995 г.). «Техника отклонения выборки из Т-вогнутых распределений». АКМ Транс. Математика. Программное обеспечение . 21 (2): 182–193. CiteSeerX 10.1.1.56.6055 . дои : 10.1145/203082.203089 . ISSN 0098-3500 . S2CID 592740 .

[6] Гилкс, WR; Бест, Нью-Йорк ; Тан, KKC (1 января 1995 г.). «Выборка мегаполиса с адаптивным отклонением в рамках выборки Гиббса». Журнал Королевского статистического общества. Серия 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] Обратите внимание: если мы не знали, как выбрать x так, чтобы f ( x ) > y , мы все равно можем выбрать любое случайное значение для x , вычислить f ( x ) и использовать его в качестве значения y . y только инициализирует алгоритм; по мере продвижения алгоритма он будет находить все более и более высокие значения y .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]