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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это оценщик выборки важности ${\displaystyle p_{t}\,}$ и беспристрастен. То есть процедура оценки заключается в создании i.i.d. образцы из ${\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) и регенеративное моделирование.

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

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

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

Смотрите также

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

Примечания

1. Рубинштейн, Р. Ю., & Крезе, Д. П. (2011). Моделирование и метод Монте-Карло (Том 707). Джон Вили и сыновья.

Рекомендации

• Аруна, Бухари (2004). «Адаптивный метод Монте-Карло, метод уменьшения дисперсии». Методы Монте-Карло и их приложения. 10 (1): 1–24. Дои:10.1515/156939604323091180.
• Баклью, Джеймс Антонио (2004). Введение в моделирование редких событий. Нью-Йорк: Springer-Verlag.
• Doucet, A .; de Freitas, N .; Гордон, Н. (2001). Последовательные методы Монте-Карло на практике. Springer. ISBN  978-0-387-95146-1.
• Феррари, М .; Беллини, С. (2001). Моделирование выборки по важности кодов турбо-продуктов. Международная конференция IEEE по коммуникациям. 9. С. 2773–2777. Дои: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.
• Smith, P.J .; Шафи, М .; Гао, Х. (1997). «Быстрое моделирование: обзор методов выборки важности в системах связи». Журнал IEEE по избранным областям коммуникаций. 15 (4): 597–613. Дои:10.1109/49.585771.
• Сринивасан, Р. (2002). Выборка по важности - Приложения в коммуникациях и обнаружении. Берлин: Springer-Verlag.

внешняя ссылка

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