Выборка по важности

Выборка по важности — это метод Монте-Карло для оценки свойств конкретного распределения , при котором выборки создаются только из распределения, отличного от интересующего распределения. Его введение в статистику обычно приписывают статье Теуна Клука и Германа К. ван Дейка в 1978 году: но его предшественники можно найти в статистической физике уже в 1949 году. Выборка по важности также связана с зонтичной выборкой в ​​вычислительной физике . В зависимости от применения этот термин может относиться к процессу выборки из этого альтернативного распределения, процессу вывода или к тому и другому.

Основная теория

Позволять $X\colon \Omega \to \mathbb {R}$ быть случайной величиной в некотором вероятностном пространстве $(\Omega ,{\mathcal {F}},P)$. Мы хотим оценить ожидаемое значение X ] при P , обозначаемое E [ X;P . Если у нас есть статистически независимые случайные выборки $x_{1},\ldots ,x_{n}$, сгенерированный согласно P , то эмпирическая оценка E [ X;P ] равна

${\widehat {\mathbf {E} }}_{n}[X;P]={\frac {1}{n}}\sum _{i=1}^{n}x_{i}\quad \mathrm {where} \;x_{i}\sim P(X)$

и точность этой оценки зависит от дисперсии X :

$\operatorname {var} [{\widehat {\mathbf {E} }}_{n};P]={\frac {\operatorname {var} [X;P]}{n}}.$

Основная идея выборки по важности состоит в том, чтобы выбрать состояния из другого распределения, чтобы снизить дисперсию оценки E [ X;P ] или когда выборка из P затруднена.Это достигается путем предварительного выбора случайной величины $L\geq 0$ такой, что E [ L ; P ] = 1 и что P - почти всюду $L(\omega )\neq 0$.С помощью переменной L мы определяем вероятность $P^{(L)}$ это удовлетворяет

$\mathbf {E} [X;P]=\mathbf {E} \left[{\frac {X}{L}};P^{(L)}\right].$

Таким образом, переменная X / L будет выбрана под P ^{( Л )} чтобы оценить E [ X; P ], как указано выше, и эта оценка улучшается, когда $\operatorname {var} \left[{\frac {X}{L}};P^{(L)}\right]<\operatorname {var} [X;P]$.

Когда X имеет постоянный знак над Ω, лучшей переменной L , очевидно, будет $L^{*}={\frac {X}{\mathbf {E} [X;P]}}\geq 0$, так что X / L * — это искомая константа E [ X;P ] и единственная выборка под P ^{( Л * )} достаточно, чтобы указать его значение. К сожалению, мы не можем сделать этот выбор, потому что E [ X; P ] — это именно то значение, которое мы ищем! Однако этот теоретический лучший случай L* дает нам представление о том, что делает выборка по важности:

${\begin{aligned}\forall a\in \mathbb {R} ,\;P^{(L^{*})}(X\in [a;a+da])&=\int _{\omega \in \{X\in [a;a+da]\}}{\frac {X(\omega )}{E[X;P]}}\,dP(\omega )\\[6pt]&={\frac {1}{E[X;P]}}\;a\,P(X\in [a;a+da])\end{aligned}}$

Направо, $a\,P(X\in [a;a+da])$ — один из бесконечно малых элементов, сумма которых равна E [ X ; П ]:

$E[X;P]=\int _{a=-\infty }^{+\infty }a\,P(X\in [a;a+da])$

следовательно, хорошее изменение вероятности P ^{( Л )} выборка по важности перераспределит закон X так, что частоты ее выборок сортируются непосредственно в соответствии с их весами в E [ X ; П ]. Отсюда и название «выборка по важности».

Выборка по важности часто используется в качестве интегратора Монте-Карло .Когда $P$ является равномерным распределением и $\Omega =\mathbb {R}$, E [ X;P ] соответствует интегралу действительной функции $X\colon \mathbb {R} \to \mathbb {R}$.

Приложение к вероятностному выводу

Такие методы часто используются для оценки апостериорных плотностей или ожиданий в задачах оценки состояния и/или параметров в вероятностных моделях, которые слишком сложно обрабатывать аналитически. Примеры включают байесовские сети и вариационные автоэнкодеры , взвешенные по важности .

Приложение к моделированию

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

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

Учитывать $X$ быть образцом и ${\frac {f(X)}{g(X)}}$ быть отношением правдоподобия, где $f$ - функция плотности вероятности (массы) желаемого распределения и $g$ — это функция плотности вероятности (массы) смещенного/предложения/выборочного распределения. Тогда проблему можно охарактеризовать, выбрав выборочное распределение $g$ что минимизирует дисперсию масштабированной выборки:

$g^{*}=\min _{g}\operatorname {var} _{g}\left(X{\frac {f(X)}{g(X)}}\right).$

Можно показать, что следующее распределение минимизирует указанную выше дисперсию:

$g^{*}(X)={\frac {|X|f(X)}{\int |x|f(x)\,dx}}.$

Обратите внимание, что когда $X\geq 0$, эта дисперсия становится равной 0.

Математический подход

Рассмотрите возможность оценки вероятности путем моделирования $p_{t}\,$ события $X\geq t$, где $X$ — случайная величина с кумулятивной функцией распределения $F(x)$ и функция плотности вероятности $f(x)=F'(x)\,$, где штрих обозначает производную . А $K$-независимая по длине и одинаково распределенная (iid) последовательность $X_{i}\,$ генерируется из распределения $F$, и число $k_{t}$ случайных величин, лежащих выше порога $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.$

Можно показать, что $\operatorname {E} [k_{t}/K]=p_{t}$, и $\operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K$, поэтому в пределе $K\to \infty$ мы можем получить $p_{t}$. Обратите внимание, что дисперсия мала, если $p_{t}\approx 1$. Выборка по важности связана с определением и использованием альтернативной функции плотности. $f_{*}\,$(для $X$), обычно называемая плотностью смещения для симуляционного эксперимента. Такая плотность позволяет событию ${X\geq t\ }$ происходить чаще, поэтому длина последовательности $K$ становится меньше для заданной дисперсии оценки . Альтернативно, для данного $K$, использование плотности смещения приводит к меньшей дисперсии, чем дисперсия традиционной оценки Монте-Карло. Из определения $p_{t}\,$, мы можем представить $f_{*}\,$ как показано ниже.

${\begin{aligned}p_{t}&={E}[1(X\geq t)]\\[6pt]&=\int 1(x\geq t){\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{aligned}}$

где

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

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

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

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

${\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1(X\geq t)W(X)]\\[5pt]&={\frac {1}{K}}\left\{{E_{*}}[1(X\geq t)^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{{E}[1(X\geq t)W(X)]-p_{t}^{2}\right\}\end{aligned}}$

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

Обычные методы смещения

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

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

Смещение вероятностной массы в область событий ${X\geq 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\,$и называется эффектом размерности.Современной версией выборки по значимости путем масштабирования является, например, так называемая сигма-масштабированная выборка (SSS), при которой выполняется множественный анализ Монте-Карло (MC) с различными коэффициентами масштабирования. В отличие от многих других высокопроизводительных методов оценки (например, WCD для наихудшего случая), SSS не сильно страдает от проблемы размерности. Кроме того, обращение к нескольким выходам MC не приводит к снижению эффективности. С другой стороны, как и WCD, SSS предназначен только для гауссовых статистических переменных и, в отличие от WCD, метод SSS не предназначен для получения точных статистических углов. Еще одним недостатком SSS является то, что запуск MC с большими масштабными факторами может оказаться затруднительным, например, из-за проблем сходимости модели и симулятора. Кроме того, в SSS мы сталкиваемся с серьезным компромиссом между смещением и дисперсией: используя крупномасштабные факторы, мы получаем довольно стабильные результаты урожайности, но чем больше масштабные коэффициенты, тем больше ошибка смещения. Если преимущества SSS не имеют большого значения в интересующем приложении, то зачастую другие методы оказываются более эффективными.

Перевод

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

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

где $c\,$ — это величина сдвига, которую следует выбирать так, чтобы минимизировать дисперсию средства оценки выборки важности.

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

Фундаментальная проблема с выборкой по важности заключается в том, что проектирование хороших смещенных распределений становится более сложным по мере увеличения сложности системы. Сложные системы — это системы с длинной памятью, поскольку со сложной обработкой нескольких входных данных справиться гораздо проще. Эта размерность или память могут вызывать проблемы тремя способами:

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

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

Оценка важности выборки

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

Функция стоимости дисперсии

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

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

Множественная и адаптивная выборка по важности

При различных распределениях предложений, $g_{n}(x)$ , $n=1,\ldots ,N,$ совместно используются для отбора проб $x_{1},\ldots ,x_{N},$ могут быть использованы различные правильные весовые функции (например, см. ). В адаптивной настройке распределения предложений, $g_{n,t}(x)$ , $n=1,\ldots ,N,$ и $t=1,\ldots ,T,$ обновляются каждую итерацию $t$ алгоритма адаптивной выборки важности. Следовательно, поскольку используется популяция с плотностью предложений, можно использовать несколько подходящих комбинаций схем выборки и взвешивания.

См. также

• Метод Монте-Карло
• Уменьшение дисперсии
• Стратифицированная выборка
• Рекурсивная стратифицированная выборка
• Алгоритм Вегаса
• Фильтр частиц — последовательный метод Монте-Карло, использующий выборку по важности.
• Вспомогательное поле Монте-Карло
• Отбраковочная выборка
• Переменный битрейт — распространенное аудиоприложение с важной выборкой.

Ссылки

• Аруна, Бухари (2004). «Адаптационный метод Монте-Карло, метод уменьшения дисперсии». Методы Монте-Карло и их приложения . 10 (1): 1–24. дои : 10.1515/156939604323091180 . S2CID   21949573 .
• Баклью, Джеймс Антонио (2004). Введение в моделирование редких событий . Нью-Йорк: Springer-Verlag.
• Дусе, А.; де Фрейтас, Н.; Гордон, Н. (2001). Последовательные методы Монте-Карло на практике . Спрингер. ISBN  978-0-387-95146-1 .
• Феррари, М.; Беллини, С. (2001). «Моделирование выборки по важности кодов турбопродуктов». ICC 2001. Международная конференция IEEE по коммуникациям. Протокол конференции (Кат. № 01CH37240) . Том. 9. стр. 2773–2777. дои : 10.1109/ICC.2001.936655 . ISBN  978-0-7803-7097-5 . S2CID   5158473 .
• Мазонька, Олег (2016). «Просто как пи: метод выборки по важности» . Справочный журнал . 16 .
• Оберг, Томми (2001). Модуляция, обнаружение и кодирование . Нью-Йорк: Джон Уайли и сыновья.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 7.9.1 Выборка по значимости» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 .
• Рипли, Б.Д. (1987). Стохастическое моделирование . Уайли и сыновья.
• Смит, П.Дж.; Шафи, М.; Гао, Х. (1997). «Быстрое моделирование: обзор методов выборки по важности в системах связи». Журнал IEEE по избранным областям коммуникаций . 15 (4): 597–613. дои : 10.1109/49.585771 .
• Шринивасан, Р. (2002). Выборка по важности – Применение в области связи и обнаружения . Берлин: Springer-Verlag.

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

• Домашняя страница последовательных методов Монте-Карло (фильтрация частиц) в Кембриджском университете
• Введение в выборку по важности в моделировании редких событий. Европейский журнал физики. PDF-документ.
• Адаптивные методы Монте-Карло для моделирования редких событий Зимняя конференция по моделированию