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