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

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

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

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

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

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

$P(k_t=k)=(\genfrac{}{}{0ex}{}{K}{k})p_t^k(1-<!--\; -\; -->p_t{)}^{K-<!--\; -\; -->k},k=0,1,\dots <!--\; \dots \; -->,K.$$P(k_t = k)={K\choose k}p_t^k(1-p_t)^{K-k},\,\quad \quad k=0,1,\dots,K.$ 

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

$p_t=E[X\ge <!--\; \ge \; -->t]$$p_t = {E} [X \ge t]$ 

$=\int <!--\; \int \; -->(x\ge <!--\; \ge \; -->t)\frac{f(x)}{f_{\ast <!--\; \ast \; -->}(x)}{f}_{\ast <!--\; \ast \; -->}(x)dx$$= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx$ 

$=E_{\ast <!--\; \ast \; -->}[(X\ge <!--\; \ge \; -->t)W(X)]$$= {E_*} [(X \ge t) W(X)]$ 

где

$W(\cdot <!--\; \cdot \; -->)\equiv <!--\; \equiv \; -->\frac{f(\cdot <!--\; \cdot \; -->)}{f_{\ast <!--\; \ast \; -->}(\cdot <!--\; \cdot \; -->)}$$W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}$ 

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

${\stackrel{^<!--\; ^\; -->}{p}}_t=\frac{1}{K}\underset{i=1}{\overset{K}{\sum <!--\; \sum \; -->}}(X_i\ge <!--\; \ge \; -->t)W(X_i),X_i\sim <!--\; \sim \; -->f_{\ast <!--\; \ast \; -->}$$\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$$p_{t}$  и она не отклонена при использовании $f_{\ast <!--\; \ast \; -->}$$f_{*}$ . Таким образом, процедуру моделирования при ВЗ можно сформулировать как, приготовление последовательности независимых и однородно распределенных событий для плотности $f_{\ast <!--\; \ast \; -->}$$f_{*}$ , тогда когда каждое событие будет иметь увеличенный на $W$$W$  вес, и далее события также как и раньше принимаются, если они больше, чем $t$$t$ . Результат усредняется по всей статистике $K$$K$ . Легко показать, что дисперсия ВЗ оценки будет равна

$Va{r}_{\ast <!--\; \ast \; -->}{\stackrel{^<!--\; ^\; -->}{p}}_t=\frac{1}{K}Va{r}_{\ast <!--\; \ast \; -->}[(X\ge <!--\; \ge \; -->t)W(X)]$$Var_{*}{\hat {p}}_{t}={\frac {1}{K}}Var_{*}[(X\geq t)W(X)]$ 

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

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

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

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

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

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

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

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

$f_{\ast <!--\; \ast \; -->}(x)=\frac{1}{a}f(\frac{x}{a})$$f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}$ 

и

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

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

ТрансляцияПравить

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

$f_{\ast <!--\; \ast \; -->}(x)=f(x-<!--\; -\; -->c),c>0$$f_{*}(x)=f(x-c),\quad c>0$ 

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

Эффекты сложности системыПравить

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

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

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

Численные оценки ВЗПравить

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

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

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

Одна из проблем использования дисперсии заключается в том, что отношение ${\mathrm{\sigma <!--\; \sigma \; -->}}_{MC}^2/{\mathrm{\sigma <!--\; \sigma \; -->}}_{IS}^2$$\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