Выборка по значимости

Выборка по значимости (англ. importance sampling, далее ВЗ) — один из методов уменьшения дисперсии случайной величины, который используется для улучшения сходимости процесса моделирования какой-либо величины методом Монте-Карло. Идея ВЗ основывается на том, что некоторые значения случайной величины в процессе моделирования имеют бо́льшую значимость (вероятность) для оцениваемой функции (параметра), чем другие. Если эти «более вероятные» значения будут появляться в процессе выбора случайной величины чаще, дисперсия оцениваемой функции уменьшится. Следовательно, базовая методология ВЗ заключается в выборе распределения, которое способствует выбору «более вероятных» значений случайной величины. Такое «смещенное» распределение изменяет оцениваемую функцию, если применяется прямо в процессе расчета. Однако, результат расчета пере-взвешивается согласно этому смещенному распределению, и это гарантирует, что новая оцениваемая функция ВЗ не будет смещена. Сам вес дается отношением правдоподобия, то есть производной Радона-Никодима истинного начального распределения по отношению к выбранному смещенному распределению.

Фундаментальной задачей в реализации ВЗ является выбор смещенного распределения, которое выделяет регионы с «более вероятными» значениями оцениваемой функции.

ВЗ эффективен при удачном выборе и построении такого распределения, так как оно даст существенное сокращение времени вычислений. При неудачном смещенном распределении даже стандартный метод Монте-Карло может дать лучшие результаты.

Математические основания

Рассмотрим моделирование вероятности <math>p_t</math> события <math>{ X \ge t\ }</math>, где <math>X</math> — случайная величина с распределением <math>F</math> и плотностью вероятности <math>f(x)= F'(x)</math>, где штрих означает производную. Пусть, статистика длины K — последовательность К независимых и однородно распределенных событий <math>X_i</math>, создается на основе распределения <math>F</math>, и мы хотим оценить число случайных переменных <math>k_t</math> в K, значения которых лежат выше некоторого <math>t</math>. Случайная переменная <math>k_t</math> характеризуется биномиальным распределением

<math>P(k_t = k)={K\choose k}p_t^k(1-p_t)^{K-k},\,\quad \quad k=0,1,\dots,K.</math>

Выборкой по значимости называют построение и использование другой функции плотности <math>f_*</math>(для X), обычно называемой смещенной плотностью, в вычислительном эксперименте (моделировании). Новая плотность позволяет событию <math>{ X \ge t\ }</math> появляться чаще, тем самым длина последовательности для данного значения дисперсии построенной статистики будет уменьшаться. Другими словами, для данной статистики K, использование смещенной плотности приводит к меньшей дисперсии, чем при оценке обычным Монте-Карло. Из определения <math>p_t</math>, мы можем ввести <math>f_*</math> следующим образом:

<math>p_t = {E} [X \ge t] </math>

<math>= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx </math>

<math>= {E_*} [(X \ge t) W(X)] </math>

где

<math>W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)} </math>

— отношение правдоподобия и называется весовой функцией. Последнее равенство приводит к рассмотрению статистики

<math> \hat p_t = \frac{1}{K}\,\sum_{i=1}^K (X_i \ge t) W(X_i),\,\quad \quad X_i \sim f_*</math>

Это статистика ВЗ для <math>p_t</math> и она не отклонена при использовании <math>f_*</math>. Таким образом, процедуру моделирования при ВЗ можно сформулировать как, приготовление последовательности независимых и однородно распределенных событий для плотности <math>f_*</math>, тогда когда каждое событие будет иметь увеличенный на <math>W</math> вес, и далее события также как и раньше принимаются, если они больше, чем <math>t</math>. Результат усредняется по всей статистике <math>K</math>. Легко показать, что дисперсия ВЗ оценки будет равна

<math>Var_*\hat p_t = \frac{1}{K} Var_* [(X \ge t)W(X)]</math>

<math>= \frac{1}{K}\Big[{E_*}[(X \ge t)^2 W^2(X)] - p_t^2 \Big] </math>

<math>= \frac{1}{K}\Big[{E}[(X \ge t)^2 W(X)] - p_t^2 \Big] </math>

Теперь проблему ВЗ можно сформулировать как поиск такой плотности вероятности <math>f_*</math>, что дисперсия новой статистики будет меньше по сравнению с полученной обычным методом Монте-Карло. Если в задаче возможно построить смещенную плотность вероятности, для которой дисперсия равна 0, то она называется оптимальной смещенной плотностью вероятности.

Методы построения смещенных распределений

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

Масштабирование

Сдвиг вероятностной меры в область <math>{ X \ge t\ }</math> с помощью масштабирования случайной переменной <math>X</math> числом больше единицы. Такое масштабирование приводит к увеличению значимости хвоста плотности вероятности и, тем самым, дает увеличение вероятности появления «нужных» событий. По всей вероятности, масштабирование было одним из первых смещающих методов, широко используемых на практике. Легко реализуемый в реальные алгоритмы, этот метод дает довольно скромное улучшение эффективности моделирования по сравнению с другими смещающими методами.

в ВЗ при масштабировании, плотность вероятности для моделирования определяется как первоначальная плотность для масштабированной случайной переменной <math>aX</math>. Если нам важна оценка хвоста плотности вероятности в большую сторону, выбирают <math>a>1</math>. Новая плотность и весовая функция, соответственно, равны

<math> f_*(x)=\frac{1}{a} f \bigg( \frac{x}{a} \bigg)</math>

и

<math> W(x)= a \frac{f(x)}{f(x/a)} \, .</math>

Хотя масштабирование сдвигает вероятностную меру в желаемый регион «нужных» событий, оно также сдвигает вероятность в регион <math>X<t</math>. Если <math>X</math> — сумма <math>n</math> случайных переменных, разброс вероятности происходит в <math>n</math>-ном пространстве. Как следствие, это уменьшает эффективность ВЗ при увеличении <math>n</math> (эффект размерности).

Трансляция

Другая простая и эффективная смещающая техника основана на трансляции плотности вероятности (и, следовательно, случайной переменной) в область, где вероятность увеличивается. Трансляции не приводят к эффекту размерности. Эта техника успешно применяется в реальных приложениях, например, при моделировании систем цифровой связи. Часто, этот метод эффективнее, чем масштабирование. При смещении трансляцией новая плотность вероятности определяется, как

<math> f_*(x)= f(x-c), \quad c>0</math>

где <math>c</math> — величина сдвига, выбираемая из условия минимизации дисперсии ВЗ статистики.

Эффекты сложности системы

Фундаментальной проблемой ВЗ является трудность построения хорошего смещенного распределения при усложнении изучаемой системы. В этом смысле, сложными системами называют системы с долгой памятью, так как для систем, где происходит сложная обработка малого количества входных параметров (то есть в задачах с малой размерностью), проблема построения ВЗ проще. Например, в теории цифровой передачи сигналов, долгая память (или большая размерность начальных условий) приводит к проблемам трех типов:

• длинная память (сильное межсимвольное взаимодействие)
• память неопределенной длины (декодеры Витерби)
• память возможно бесконечной длины (адаптивные эквалайзеры)

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

Численные оценки ВЗ

Для определения успешности найденной плотности ВЗ, полезно иметь численную оценку уменьшения объёма вычислений при её применении. Для такой оценки обычно применяют отношение <math>\sigma^2_{MC} / \sigma^2_{IS}</math>, которое можно интерпретировать, как фактор увеличения скорости, с которой ВЗ статистика достигнет такой же точности, как и статистика, полученная методом обычного Монте-Карло. Значение отношения можно получить только эмпирическом путём, так как дисперсии статистик практически не возможно вывести аналитически.

Ценовая функция дисперсии

Дисперсия — не единственная ценовая функция для моделирования, так как возможны другие типы ценовых функций, использующихся в различных статистических приложениях, например, среднее абсолютное отклонение. Тем не менее, в литературе обычно цитируется дисперсия, возможно, из-за использования дисперсии в вычислении доверительных интервалов и в выражении для измерения эффективности <math>\sigma^2_{MC} / \sigma^2_{IS}</math>.

Одна из проблем использования дисперсии заключается в том, что отношение <math>\sigma^2_{MC} / \sigma^2_{IS}</math> переоценивает уменьшение объёма вычислений в случае использования ВЗ, так как этот параметр не учитывает дополнительного времени, необходимого для вычисления весовой функции. Следовательно, при реальном применении улучшение в результате применения ВЗ должно оцениваться другими методами. Возможно, более серьёзной проблемой с точки зрения эффективности в ВЗ является время на разработку и реализации самой техники и аналитическое построение необходимой весовой функции (если она не известна заранее).

См. также

• Метод Монте-Карло
• Районированная выборка
• Рекурсивная районированная выборка
• Последовательные методы Монте-Карло или фильтр частиц

Литература

• И. М. Соболь. Численные методы Монте-Карло. М.: Наука, 1973 г.
• P. J.Smith, M.Shafi, and H. Gao, "Quick simulation: A review of importance sampling techniques in communication systems, " IEEE J.Select.Areas Commun., vol. 15, pp. 597–613, May 1997.
• M. Ferrari, S. Bellini, "Importance Sampling simulation of turbo product codes, " ICC2001, The IEEE International Conference on Communications, vol. 9, pp. 2773–2777, June 2001.
• Tommy Oberg, Modulation, Detection, and Coding, John Wiley & Sons, Inc., New York, 2001.
• R. Srinivasan., Importance Sampling. New York: Springer, 2002.

Дополнительно

• «Importance sampling — Applications in communications and detection», Rajan Srinivasan, Springer-Verlag, Berlin, 2002.
• «Introduction to rare event simulation», James Antonio Bucklew, Springer-Verlag, New York, 2004.

Ссылки

• [www-sigproc.eng.cam.ac.uk/smc/ Sequential Monte Carlo Methods (Particle Filtering)] homepage on University of Cambridge
• [www.iop.org/EJ/abstract/0143-0807/22/4/315 Introduction to importance sampling in rare-event simulations] European journal of Physics. PDF document.
• [portal.acm.org/citation.cfm?id=1030470 Adaptive monte carlo methods for rare event simulation: adaptive monte carlo methods for rare event simulations] Winter Simulation Conference
• [www.feynarts.de/cuba/ Cuba — a library for multidimensional numerical integration]

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

Когда граф взошел к ней, она беспокойно оборотилась на звук его мужских шагов, и лицо ее приняло прежнее холодное и даже злое выражение. Она даже не поднялась на встречу ему.
– Что с тобой, мой ангел, больна? – спросил граф. Наташа помолчала.
– Да, больна, – отвечала она.
На беспокойные расспросы графа о том, почему она такая убитая и не случилось ли чего нибудь с женихом, она уверяла его, что ничего, и просила его не беспокоиться. Марья Дмитриевна подтвердила графу уверения Наташи, что ничего не случилось. Граф, судя по мнимой болезни, по расстройству дочери, по сконфуженным лицам Сони и Марьи Дмитриевны, ясно видел, что в его отсутствие должно было что нибудь случиться: но ему так страшно было думать, что что нибудь постыдное случилось с его любимою дочерью, он так любил свое веселое спокойствие, что он избегал расспросов и всё старался уверить себя, что ничего особенного не было и только тужил о том, что по случаю ее нездоровья откладывался их отъезд в деревню.


Со дня приезда своей жены в Москву Пьер сбирался уехать куда нибудь, только чтобы не быть с ней. Вскоре после приезда Ростовых в Москву, впечатление, которое производила на него Наташа, заставило его поторопиться исполнить свое намерение. Он поехал в Тверь ко вдове Иосифа Алексеевича, которая обещала давно передать ему бумаги покойного.
Когда Пьер вернулся в Москву, ему подали письмо от Марьи Дмитриевны, которая звала его к себе по весьма важному делу, касающемуся Андрея Болконского и его невесты. Пьер избегал Наташи. Ему казалось, что он имел к ней чувство более сильное, чем то, которое должен был иметь женатый человек к невесте своего друга. И какая то судьба постоянно сводила его с нею.
«Что такое случилось? И какое им до меня дело? думал он, одеваясь, чтобы ехать к Марье Дмитриевне. Поскорее бы приехал князь Андрей и женился бы на ней!» думал Пьер дорогой к Ахросимовой.
На Тверском бульваре кто то окликнул его.
– Пьер! Давно приехал? – прокричал ему знакомый голос. Пьер поднял голову. В парных санях, на двух серых рысаках, закидывающих снегом головашки саней, промелькнул Анатоль с своим всегдашним товарищем Макариным. Анатоль сидел прямо, в классической позе военных щеголей, закутав низ лица бобровым воротником и немного пригнув голову. Лицо его было румяно и свежо, шляпа с белым плюмажем была надета на бок, открывая завитые, напомаженные и осыпанные мелким снегом волосы.
«И право, вот настоящий мудрец! подумал Пьер, ничего не видит дальше настоящей минуты удовольствия, ничто не тревожит его, и оттого всегда весел, доволен и спокоен. Что бы я дал, чтобы быть таким как он!» с завистью подумал Пьер.
В передней Ахросимовой лакей, снимая с Пьера его шубу, сказал, что Марья Дмитриевна просят к себе в спальню.
Отворив дверь в залу, Пьер увидал Наташу, сидевшую у окна с худым, бледным и злым лицом. Она оглянулась на него, нахмурилась и с выражением холодного достоинства вышла из комнаты.
– Что случилось? – спросил Пьер, входя к Марье Дмитриевне.
– Хорошие дела, – отвечала Марья Дмитриевна: – пятьдесят восемь лет прожила на свете, такого сраму не видала. – И взяв с Пьера честное слово молчать обо всем, что он узнает, Марья Дмитриевна сообщила ему, что Наташа отказала своему жениху без ведома родителей, что причиной этого отказа был Анатоль Курагин, с которым сводила ее жена Пьера, и с которым она хотела бежать в отсутствие своего отца, с тем, чтобы тайно обвенчаться.
Пьер приподняв плечи и разинув рот слушал то, что говорила ему Марья Дмитриевна, не веря своим ушам. Невесте князя Андрея, так сильно любимой, этой прежде милой Наташе Ростовой, променять Болконского на дурака Анатоля, уже женатого (Пьер знал тайну его женитьбы), и так влюбиться в него, чтобы согласиться бежать с ним! – Этого Пьер не мог понять и не мог себе представить.
Милое впечатление Наташи, которую он знал с детства, не могло соединиться в его душе с новым представлением о ее низости, глупости и жестокости. Он вспомнил о своей жене. «Все они одни и те же», сказал он сам себе, думая, что не ему одному достался печальный удел быть связанным с гадкой женщиной. Но ему всё таки до слез жалко было князя Андрея, жалко было его гордости. И чем больше он жалел своего друга, тем с большим презрением и даже отвращением думал об этой Наташе, с таким выражением холодного достоинства сейчас прошедшей мимо него по зале. Он не знал, что душа Наташи была преисполнена отчаяния, стыда, унижения, и что она не виновата была в том, что лицо ее нечаянно выражало спокойное достоинство и строгость.
– Да как обвенчаться! – проговорил Пьер на слова Марьи Дмитриевны. – Он не мог обвенчаться: он женат.
– Час от часу не легче, – проговорила Марья Дмитриевна. – Хорош мальчик! То то мерзавец! А она ждет, второй день ждет. По крайней мере ждать перестанет, надо сказать ей.
Узнав от Пьера подробности женитьбы Анатоля, излив свой гнев на него ругательными словами, Марья Дмитриевна сообщила ему то, для чего она вызвала его. Марья Дмитриевна боялась, чтобы граф или Болконский, который мог всякую минуту приехать, узнав дело, которое она намерена была скрыть от них, не вызвали на дуэль Курагина, и потому просила его приказать от ее имени его шурину уехать из Москвы и не сметь показываться ей на глаза. Пьер обещал ей исполнить ее желание, только теперь поняв опасность, которая угрожала и старому графу, и Николаю, и князю Андрею. Кратко и точно изложив ему свои требования, она выпустила его в гостиную. – Смотри же, граф ничего не знает. Ты делай, как будто ничего не знаешь, – сказала она ему. – А я пойду сказать ей, что ждать нечего! Да оставайся обедать, коли хочешь, – крикнула Марья Дмитриевна Пьеру.
Пьер встретил старого графа. Он был смущен и расстроен. В это утро Наташа сказала ему, что она отказала Болконскому.
– Беда, беда, mon cher, – говорил он Пьеру, – беда с этими девками без матери; уж я так тужу, что приехал. Я с вами откровенен буду. Слышали, отказала жениху, ни у кого не спросивши ничего. Оно, положим, я никогда этому браку очень не радовался. Положим, он хороший человек, но что ж, против воли отца счастья бы не было, и Наташа без женихов не останется. Да всё таки долго уже так продолжалось, да и как же это без отца, без матери, такой шаг! А теперь больна, и Бог знает, что! Плохо, граф, плохо с дочерьми без матери… – Пьер видел, что граф был очень расстроен, старался перевести разговор на другой предмет, но граф опять возвращался к своему горю.
Соня с встревоженным лицом вошла в гостиную.
– Наташа не совсем здорова; она в своей комнате и желала бы вас видеть. Марья Дмитриевна у нее и просит вас тоже.
– Да ведь вы очень дружны с Болконским, верно что нибудь передать хочет, – сказал граф. – Ах, Боже мой, Боже мой! Как всё хорошо было! – И взявшись за редкие виски седых волос, граф вышел из комнаты.
Марья Дмитриевна объявила Наташе о том, что Анатоль был женат. Наташа не хотела верить ей и требовала подтверждения этого от самого Пьера. Соня сообщила это Пьеру в то время, как она через коридор провожала его в комнату Наташи.
Наташа, бледная, строгая сидела подле Марьи Дмитриевны и от самой двери встретила Пьера лихорадочно блестящим, вопросительным взглядом. Она не улыбнулась, не кивнула ему головой, она только упорно смотрела на него, и взгляд ее спрашивал его только про то: друг ли он или такой же враг, как и все другие, по отношению к Анатолю. Сам по себе Пьер очевидно не существовал для нее.
– Он всё знает, – сказала Марья Дмитриевна, указывая на Пьера и обращаясь к Наташе. – Он пускай тебе скажет, правду ли я говорила.
Наташа, как подстреленный, загнанный зверь смотрит на приближающихся собак и охотников, смотрела то на того, то на другого.
– Наталья Ильинична, – начал Пьер, опустив глаза и испытывая чувство жалости к ней и отвращения к той операции, которую он должен был делать, – правда это или не правда, это для вас должно быть всё равно, потому что…
– Так это не правда, что он женат!
– Нет, это правда.
– Он женат был и давно? – спросила она, – честное слово?
Пьер дал ей честное слово.
– Он здесь еще? – спросила она быстро.
– Да, я его сейчас видел.
Она очевидно была не в силах говорить и делала руками знаки, чтобы оставили ее.


Пьер не остался обедать, а тотчас же вышел из комнаты и уехал. Он поехал отыскивать по городу Анатоля Курагина, при мысли о котором теперь вся кровь у него приливала к сердцу и он испытывал затруднение переводить дыхание. На горах, у цыган, у Comoneno – его не было. Пьер поехал в клуб.
В клубе всё шло своим обыкновенным порядком: гости, съехавшиеся обедать, сидели группами и здоровались с Пьером и говорили о городских новостях. Лакей, поздоровавшись с ним, доложил ему, зная его знакомство и привычки, что место ему оставлено в маленькой столовой, что князь Михаил Захарыч в библиотеке, а Павел Тимофеич не приезжали еще. Один из знакомых Пьера между разговором о погоде спросил у него, слышал ли он о похищении Курагиным Ростовой, про которое говорят в городе, правда ли это? Пьер, засмеявшись, сказал, что это вздор, потому что он сейчас только от Ростовых. Он спрашивал у всех про Анатоля; ему сказал один, что не приезжал еще, другой, что он будет обедать нынче. Пьеру странно было смотреть на эту спокойную, равнодушную толпу людей, не знавшую того, что делалось у него в душе. Он прошелся по зале, дождался пока все съехались, и не дождавшись Анатоля, не стал обедать и поехал домой.