Выборка с отклонением

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

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

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

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

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

Алгоритм

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

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

Примеры

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

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

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

Проблемы

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

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

Ссылки

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