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

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

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

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

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

, где .

Алгоритм

  1. Взять семпл по распределению ;
  2. Выбрать случайное число равномерно из отрезка ;
  3. Вычислить ;
    • Если , то добавляется к семплам;
    • Если , то отклоняется (отсюда и название метода).

Алгоритм выбирает точки равномерно из области под графиком , а это и означает что получаются семплы .

Примеры

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

Сгенерируем точку выбрав и как независимые произвольные числа из отрезка . Если получится так, что , то это означает что точка лежит внутри круга, и должна быть принята. В противном случае точка отклоняется, и генерируется следующая.

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

Проблемы

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

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

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.