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

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

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

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

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

$\forall x\ \ f(x)<cg(x)$ , где $c>1$$c>1$ .

АлгоритмПравить

1. Взять семпл $x$$x$  по распределению $g(x)$$g(x)$ ;
2. Выбрать случайное число $u$$u$  равномерно из отрезка $[0,cg(x)]$$[0,cg(x)]$ ;
3. Вычислить $f(x)$$f(x)$ ;
   • Если $u\le <!--\; \le \; -->f(x)$$u\leq f(x)$ , то $x$$x$  добавляется к семплам;
   • Если $u>f(x)$$u>f(x)$ , то $x$$x$  отклоняется (отсюда и название метода).

Алгоритм выбирает точки $[x,u]$$[x,u]$  равномерно из области под графиком $f(x)$$f(x)$ , а это и означает что получаются семплы $f(x)$$f(x)$ .

ПримерыПравить

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

Сгенерируем точку $(x,y)$$(x, y)$  выбрав $x$$x$  и $y$$y$  как независимые произвольные числа из отрезка $[-<!--\; -\; -->1,1]$$[-1,1]$ . Если получится так, что $x^2+y^2\le <!--\; \le \; -->1$$x^{2}+y^{2}\leq 1$ , то это означает что точка лежит внутри круга, и должна быть принята. В противном случае точка отклоняется, и генерируется следующая.

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

ПроблемыПравить

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

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

СсылкиПравить

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