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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Постановка задачи[править | править исходный текст]

Для семплирования вероятностного распределения 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).

Пример[править | править исходный текст]

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

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

Проблемы[править | править исходный текст]

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

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

Ссылки[править | править исходный текст]

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