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

Для семплирования вероятностного распределения ${\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}$ будет очень большим (экспоненциальным от размерности), и почти все семплы будут отвергаться.

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