WikiSort.ru - Не сортированное

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

Постановка задачи

Для семплирования вероятностного распределения ${\displaystyle f(x)}$ выборка с отклонением используется тогда, когда форма ${\displaystyle f(x)}$ делает семплирование напрямую сложным.

Генерация семплов по ${\displaystyle f(x)}$ происходит с помощью более простого вспомогательного распределения ${\displaystyle g(x)}$ , которое мы можем просемплировать, и которое удовлетворяет следующему условию:

${\displaystyle \forall x\ \ f(x)<cg(x)}$ , где ${\displaystyle c>1}$ .

Алгоритм

1. Взять семпл ${\displaystyle x}$ по распределению ${\displaystyle g(x)}$ ;
2. Выбрать случайное число ${\displaystyle u}$ равномерно из отрезка ${\displaystyle [0,cg(x)]}$ ;
3. Вычислить ${\displaystyle f(x)}$ ;
   • Если ${\displaystyle u\leq f(x)}$ , то ${\displaystyle x}$ добавляется к семплам;
   • Если ${\displaystyle u>f(x)}$ , то ${\displaystyle x}$ отклоняется (отсюда и название метода).

Алгоритм выбирает точки ${\displaystyle [x,u]}$ равномерно из области под графиком ${\displaystyle f(x)}$ , а это и означает что получаются семплы ${\displaystyle f(x)}$ .

Примеры

Приведем простой геометрический пример. Предположим, мы хотим выбрать случайную точку внутри окружности единичного радиуса.

Сгенерируем точку ${\displaystyle (x,y)}$ выбрав ${\displaystyle x}$ и ${\displaystyle y}$ как независимые произвольные числа из отрезка ${\displaystyle [-1,1]}$ . Если получится так, что ${\displaystyle x^{2}+y^{2}\leq 1}$ , то это означает что точка лежит внутри круга, и должна быть принята. В противном случае точка отклоняется, и генерируется следующая.

В качестве еще одного примера можно рассмотреть алгоритм Зиккурат, в основе которого лежит выборка с отклонением. Этот алгоритм используется для генерирования неравномерно распределенных случайных чисел.

Проблемы

Проблемы, как правило, возникают при решении задач большой размерности.

При этом ${\displaystyle c}$ будет очень большим (экспоненциальным от размерности), и почти все семплы будут отвергаться.

Ссылки

Николенко С. Курс «Вероятностное обучение».