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

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

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

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

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

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

Алгоритм

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

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

Пример

140px

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

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

Проблемы

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

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

Ссылки

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