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

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

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

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

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

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

, где .

Алгоритм[править | править вики-текст]

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

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

Пример[править | править вики-текст]

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

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

Проблемы[править | править вики-текст]

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

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

Ссылки[править | править вики-текст]

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