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

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

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

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

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

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

Алгоритм

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

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

Пример

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

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

Проблемы

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

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

Ссылки

Николенко С. [logic.pdmi.ras.ru/~sergey/oldsite/index.php?page=mlbayes Курс «Вероятностное обучение»].

Отрывок, характеризующий Выборка с отклонением

Наташа сделалась влюблена с самой той минуты, как она вошла на бал. Она не была влюблена ни в кого в особенности, но влюблена была во всех. В того, на кого она смотрела в ту минуту, как она смотрела, в того она и была влюблена.
– Ах, как хорошо! – всё говорила она, подбегая к Соне.
Николай с Денисовым ходили по залам, ласково и покровительственно оглядывая танцующих.
– Как она мила, к'асавица будет, – сказал Денисов.
– Кто?
– Г'афиня Наташа, – отвечал Денисов.
– И как она танцует, какая г'ация! – помолчав немного, опять сказал он.
– Да про кого ты говоришь?
– Про сест'у п'о твою, – сердито крикнул Денисов.
Ростов усмехнулся.
– Mon cher comte; vous etes l'un de mes meilleurs ecoliers, il faut que vous dansiez, – сказал маленький Иогель, подходя к Николаю. – Voyez combien de jolies demoiselles. [Любезный граф, вы один из лучших моих учеников. Вам надо танцовать. Посмотрите, сколько хорошеньких девушек!] – Он с тою же просьбой обратился и к Денисову, тоже своему бывшему ученику.
– Non, mon cher, je fe'ai tapisse'ie, [Нет, мой милый, я посижу у стенки,] – сказал Денисов. – Разве вы не помните, как дурно я пользовался вашими уроками?
– О нет! – поспешно утешая его, сказал Иогель. – Вы только невнимательны были, а вы имели способности, да, вы имели способности.
Заиграли вновь вводившуюся мазурку; Николай не мог отказать Иогелю и пригласил Соню. Денисов подсел к старушкам и облокотившись на саблю, притопывая такт, что то весело рассказывал и смешил старых дам, поглядывая на танцующую молодежь. Иогель в первой паре танцовал с Наташей, своей гордостью и лучшей ученицей. Мягко, нежно перебирая своими ножками в башмачках, Иогель первым полетел по зале с робевшей, но старательно выделывающей па Наташей. Денисов не спускал с нее глаз и пристукивал саблей такт, с таким видом, который ясно говорил, что он сам не танцует только от того, что не хочет, а не от того, что не может. В середине фигуры он подозвал к себе проходившего мимо Ростова.