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