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

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

${\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}$

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

${\displaystyle p_{t}={E}[X\geq t]}$

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

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

где

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

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

${\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}(X_{i}\geq t)W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}$

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

${\displaystyle Var_{*}{\hat {p}}_{t}={\frac {1}{K}}Var_{*}[(X\geq t)W(X)]}$

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

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

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

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

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

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

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

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

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

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

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

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

• 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