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

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

Основная теория [ править ]

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

${\ displaystyle {\ widehat {\ mathbf {E}}} _ {n} [X; P] = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} x_ {i} }$

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

Применение к вероятностному выводу [ править ]

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

Приложение к моделированию [ править ]

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

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

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

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

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

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

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

Математический подход [ править ]

Рассмотрите возможность оценки с помощью моделирования вероятности события , где - случайная величина с распределением и функцией плотности вероятности , где штрих обозначает производную . -Длина независимыми и одинаково распределенными (IID) последовательность генерируется из распределения , а число случайных величин , которые лежат выше порога подсчитываются. Случайная величина характеризуется биномиальным распределением${\displaystyle p_{t}\,}$${\displaystyle X\geq t}$${\displaystyle X}$ ${\displaystyle F}$ ${\displaystyle f(x)=F'(x)\,}$${\displaystyle K}$${\displaystyle X_{i}\,}$${\displaystyle F}$${\displaystyle k_{t}}$${\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 \operatorname {E} [k_{t}/K]=p_{t}}$${\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}$${\displaystyle K\to \infty }$${\displaystyle p_{t}}$${\displaystyle p_{t}\approx 1}$${\displaystyle f_{*}\,}$${\displaystyle X}$${\displaystyle {X\geq t\ }}$${\displaystyle K}$${\displaystyle K}$${\displaystyle p_{t}\,}$${\displaystyle f_{*}\,}$

${\displaystyle {\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}}}$

где

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

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

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

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

${\displaystyle {\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}}}$

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

Обычные методы смещения [ править ]

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

Масштабирование [ править ]

Сдвиг вероятностной массы в область события путем положительного масштабирования случайной величины с числом больше единицы приводит к увеличению дисперсии (также среднего) функции плотности. Это приводит к более тяжелому хвосту плотности, что приводит к увеличению вероятности события. Масштабирование, вероятно, является одним из первых известных методов смещения, широко использовавшимся на практике. Он прост в реализации и обычно обеспечивает консервативный выигрыш от моделирования по сравнению с другими методами.${\displaystyle {X\geq t\ }}$${\displaystyle X\,}$

При выборке по важности с помощью масштабирования плотность моделирования выбирается как функция плотности масштабированной случайной величины , обычно для оценки вероятности хвоста. Путем трансформации${\displaystyle aX\,}$${\displaystyle a>1}$

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

а весовая функция

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

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

Перевод [ править ]

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

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

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

Влияние сложности системы [ править ]

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

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

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

Оценка выборки важности [ править ]

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

Функция дисперсионной стоимости [ править ]

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

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

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

Когда различные распределения предложений ,, используются совместно для построения выборок , могут использоваться различные надлежащие весовые функции (например, см. ^{[3] [4] [5] [6]} ). В адаптивной настройке распределения предложений , и обновляются каждую итерацию алгоритма выборки адаптивной важности. Следовательно, поскольку используется совокупность плотностей предложений, можно использовать несколько подходящих комбинаций схем выборки и взвешивания. ^{[7] [8] [9] [10] [11] [12] [13]}${\displaystyle g_{n}(x)}$${\displaystyle n=1,\ldots ,N,}$${\displaystyle x_{1},\ldots ,x_{N},}$${\displaystyle g_{n,t}(x)}$${\displaystyle n=1,\ldots ,N,}$${\displaystyle t=1,\ldots ,T,}$${\displaystyle t}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

• Домашняя страница последовательных методов Монте-Карло (фильтрация частиц) Кембриджского университета
• Введение в выборку важности при моделировании редких событий European Journal of Physics. PDF-документ.
• Адаптивные методы Монте-Карло для моделирования редких событий: адаптивные методы Монте-Карло для моделирования редких событий Winter Simulation Conference