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

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

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

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

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

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

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

$p_t = {E} [X \ge t]$

$= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx$

$= {E_*} [(X \ge t) W(X)]$

где

$W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}$

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

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

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

$var_*\hat p_t = \frac{1}{K} var_* [(X \ge t)W(X)]$

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

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

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

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

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

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

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

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

$f_*(x)=\frac{1}{a} f \bigg( \frac{x}{a} \bigg)\,$

и

$W(x)= a \frac{f(x)}{f(x/a)} \, .$

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

Трансляция

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

$f_*(x)= f(x-c), \quad c>0 \,$

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

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

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

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

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

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

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

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

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

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

Ссылки

• И. М. Соболь. Численные методы Монте-Карло. М.: Наука, 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.

Смотри также

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

Внешние ссылки

• Sequential Monte Carlo Methods (Particle Filtering) homepage on University of Cambridge

• Introduction to importance sampling in rare-event simulations European journal of Physics. PDF document.

• Adaptive monte carlo methods for rare event simulation: adaptive monte carlo methods for rare event simulations Winter Simulation Conference

• Cuba — a library for multidimensional numerical integration

Ссылки

В последние годы опубликованы 2 монографии по теории и методам применения ВЗ, в которых заинтересованный читатель сможет найти больше информации о ВЗ:

1) «Importance sampling — Applications in communications and detection», Rajan Srinivasan, Springer-Verlag, Berlin, 2002.

2) «Introduction to rare event simulation», James Antonio Bucklew, Springer-Verlag, New York, 2004.