Выборка с отклонением — метод, используемый для семплирования сложных вероятностных распределений.
Постановка задачи
Для семплирования вероятностного распределения выборка с отклонением используется тогда, когда форма делает семплирование напрямую сложным.
Генерация семплов по происходит с помощью более простого вспомогательного распределения , которое мы можем просемплировать, и которое удовлетворяет следующему условию:
, где .
Алгоритм
Взять семпл по распределению ; Выбрать случайное число равномерно из отрезка ; Вычислить ; Если , то добавляется к семплам; Если , то отклоняется (отсюда и название метода).
Алгоритм выбирает точки равномерно из области под графиком , а это и означает что получаются семплы .
Примеры
Приведем простой геометрический пример. Предположим, мы хотим выбрать случайную точку внутри окружности единичного радиуса.
Сгенерируем точку выбрав и как независимые произвольные числа из отрезка . Если получится так, что , то это означает что точка лежит внутри круга, и должна быть принята. В противном случае точка отклоняется, и генерируется следующая.
В качестве еще одного примера можно рассмотреть алгоритм Зиккурат, в основе которого лежит выборка с отклонением. Этот алгоритм используется для генерирования неравномерно распределенных случайных чисел.
Проблемы Проблемы, как правило, возникают при решении задач большой размерности.
При этом будет очень большим (экспоненциальным от размерности), и почти все семплы будут отвергаться.
Ссылки Николенко С. Курс «Вероятностное обучение».
Категория:Метод Монте-Карло