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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Выборка по значимости (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.

Смотри также[править | править исходный текст]

Внешние ссылки[править | править исходный текст]

Ссылки[править | править исходный текст]

В последние годы опубликованы 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.