Русская Википедия:Выборка с отклонением

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

Алгоритм

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

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

Примеры

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

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

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

Проблемы

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

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

Ссылки

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