Вибірка за значимістю

У статистиці вибірка за значимістю є загальною технікою для оцінки властивостей конкретного розподілу, при цьому вибірки створюються лише з розподілу, відмінного від того, що досліджується. Метод був вперше введений Шаблон:Не перекладено і Шаблон:Не перекладено у 1978 році і пов'язаний з Шаблон:Не перекладено в обчислювальній фізиці. Залежно від застосування, термін може стосуватися процесу вибірки з цього альтернативного розподілу, процесу висновку або обох.

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

Нехай $X:\mathrm{\Omega }\to ℝ$ є випадковою величиною в деякому ймовірнісному просторі $(\mathrm{\Omega },ℱ,P)$. Ми хочемо оцінити математичне очікування X розподілу P, позначимо його, як E[X;P]. Якщо ми маємо статистично незалежні випадкові вибірки $x_1,\dots ,x_n$, породжені відповідно до P, то емпірична оцінка E [X;P] є

${\widehat{𝐄}}_n[X;P]=\frac{1}{n}\sum _{i=1}^n{x}_i$

і точність цієї оцінки буде залежати від дисперсії X:

$\mathrm{var}[{\widehat{𝐄}}_n;P]=\frac{\mathrm{var}[X;P]}{n}.$

Основною ідею вибірки за значимістю є вибір станів з іншого розподілу задля зменшення дисперсії оцінки E[X;P], або коли взяття проб з P є складним. Це досягається шляхом попереднього підбору такої випадкової змінної $L\ge 0$, щоб E [L;P] = 1 і P-майже скрізь $L(\omega )\ne 0$. За допомогою змінної L ми визначаємо ймовірність $P^{(L)}$ що задовольняє наступному рівнянню:

$𝐄[X;P]=𝐄[\frac{X}{L};P^{(L)}].$

Таким чином, змінна X/L буде підбиратися під P^(L) для оцінки E[X;P], як зазначено вище, і ця оцінка покращується, коли $\mathrm{var}[\frac{X}{L};P^{(L)}]<\mathrm{var}[X;P]$.

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

$\begin{array}{cc}\mathrm{\forall }a\in ℝ,P^{(L^{*})}(X\in [a;a+da])& =\underset{\omega \in \{X\in [a;a+da]\}}{\int }\frac{X(\omega )}{E[X;P]}dP(\omega )\\ & =\frac{1}{E[X;P]}aP(X\in [a;a+da])\end{array}$

направо, $aP(X\in [a;a+da])$ є одним із нескінченно малих елементів, які підсумовують до E[X;P]:

$E[X;P]=\underset{a=-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\int }}aP(X\in [a;a+da])$

отже, хороша зміна ймовірності P^(L) у вибірці за значимістю перерозподілить закон X так, що частоти його вибірок будуть відсортовані безпосередньо відповідно до їх ваги в E[X;P]. Звідси назва «вибірка за значимістю».

Вибірка за значимістю часто використовується як Шаблон:Не перекладено. Коли $P$ — рівномірний розподіл і $\mathrm{\Omega }=ℝ$, E[X;P] відповідає інтегралу від дійсної функції $X:ℝ\to ℝ$.

Застосування до ймовірнісного висновку

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

Застосування до моделювання

Вибірка за значимістю — це метод Шаблон:Не перекладено, який можна використовувати в методі Монте-Карло. Ідея вибірки за значимістю полягає в тому, що певні значення вхідних випадкових величин у симуляції мають більший вплив на оцінюваний параметр ніж інші. Якщо ці «важливі» значення підкреслюються шляхом вибірки частіше, то дисперсію оцінки можна зменшити. Отже, основна методологія вибірки за значимістю полягає у виборі розподілу, який «заохочує» важливі значення. Таке використання «зміщених» розподілів призведе до зміщеної оцінки, якщо її застосовувати безпосередньо під час моделювання. Однак результати моделювання зважуються, щоб виправити використання зміщеного розподілу, і це гарантує, що нова оцінка вибірки за значимістю є незміщеною. Вага визначається коефіцієнтом правдоподібності, тобто похідною Радона–Нікодима від справжнього основного розподілу щодо розподілу зміщеного моделювання.

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

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

$g^{*}=\underset{g}{\min }{\mathrm{var}}_g\left(X\frac{f(X)}{g(X)}\right).$

Можна показати, що такий розподіл мінімізує вищезгадану дисперсію:

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

Зверніть увагу, що коли $X\ge 0$, ця дисперсія стає 0.

Математичний підхід

Розглянемо оцінку ймовірності шляхом моделювання $p_t$ події $X\ge t$, де $X$ є випадковою величиною з розподілом $F$ і функцією густини ймовірності $f(x)=F^{\prime }(x)$. Незалежна однаково розподілена (i.i.d) послідовність $X_i$ довжини $K$ генерується з розподілу $F$, та підраховується число $k_t$ випадкових величин, які лежать вище порога $t$. Випадкова величина $k_t$ характеризується біноміальним розподілом

$P(k_t=k)=(\genfrac{}{}{0ex}{}{K}{k})p_t^k(1-p_t{)}^{K-k},k=0,1,\dots ,K.$

Це демонструє, що $\mathrm{E}[k_t/K]=p_t$ і $\mathrm{var}[k_t/K]=p_t(1-p_t)/K$, тож у межі $K\to \mathrm{\infty }$ ми можемо отримати $p_t$. Зауважимо, що дисперсія є малою, якщо $p_t\approx 1$. Вибірка за значимістю пов'язана з визначенням і використанням альтернативної функції щільності $f_{*}$ (для $X$), що зазвичай називають густиною зміщення для імітаційного експерименту. Ця щільність дозволяє події $X\ge t$ зустрічатися частіше, тому довжина послідовності $K$ зменшується для даної дисперсії оцінки. Як варіант, для даного $K$використання густини зміщення призводить до меншої дисперсії в порівнянні зі звичайною оцінкою Монте-Карло. Використовуючи визначення $p_t$, ми можемо представити $f_{*}$ наступним чином:

$\begin{array}{cc}{p}_t& =E[1(X\ge t)]\\ & =\int 1(x\ge t)\frac{f(x)}{f_{*}(x)}{f}_{*}(x)dx\\ & =E_{*}[1(X\ge t)W(X)]\end{array}$

де

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

є коефіцієнтом правдоподібності і називається ваговою функцією. Остання рівність у наведеному вище рівнянні мотивує оцінювача

${\hat{p}}_t=\frac{1}{K}\sum _{i=1}^{K}1(X_i\ge t)W(X_i),X_i\sim f_{*}$

Це рівняння є незміщеною оцінкою вибірки за значимістю $p_t$. Тобто процедура оцінки полягає у створенні i.i.d вибірок з $f_{*}$ і для кожної вибірки, що перевищує $t$, оцінка збільшується на вагу $W$, оцінену за значенням вибірки. Результати усереднюються за $K$ випробуваннями. Легко показати, що дисперсія оцінки вибірки за значимістю є

$\begin{array}{cc}{\mathrm{var}}_{*}{\hat{p}}_t& =\frac{1}{K}{\mathrm{var}}_{*}[1(X\ge t)W(X)]\\ & =\frac{1}{K}\{E_{*}[1(X\ge t{)}^2{W}^2(X)]-p_t^2\}\\ & =\frac{1}{K}\{E[1(X\ge t)W(X)]-p_t^2\}\end{array}$

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

Загальноприйняті методи зміщення

Хоча існує багато видів методів зміщення, наступні два методи є найбільш широко використовуваними при застосуванні вибірки за значимістю.

Масштабування

Перенесення маси ймовірності в область події $X\ge t$ шляхом додатнього масштабування випадкової величини $X$ з числом, більшим за одиницю, призводить до збільшення дисперсії (також середнього) функції густини. Як наслідок, збільшується хвіст щільності, результатом чого є збільшення ймовірності події. Масштабування, ймовірно, є одним з найперших відомих методів зміщення, який широко використовується на практиці. Він простий у реалізації і зазвичай забезпечує консервативні переваги моделювання порівняно з іншими методами.

У вибірці за значимістю шляхом масштабування щільність моделювання вибирається як функція густини масштабованої випадкової величини $aX$, де зазвичай $a>1$ для оцінки ймовірності хвоста шляхом перетворення,

$f_{*}(x)=\frac{1}{a}f\left(\frac{x}{a}\right)$

і вагова функція є

$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),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,\dots ,N,$ спільно використовуються для опису вибірок $x_1,\dots ,x_N,$ можна використовувати різні відповідні вагові функції (наприклад, див.). В адаптивному налаштуванні допоміжні розподіли, $g_{n,t}(x)$, $n=1,\dots ,N,$ та $t=1,\dots ,T,$ оновлюються на кожній ітерації $t$ адаптивного алгоритму вибірки за значимістю. Отже, оскільки використовується сукупність щільностей пропозицій, можна використовувати декілька відповідних комбінацій схем вибірки та зважування.

Див. також

• Метод Монте-Карло
• Шаблон:Не перекладено
• Стратифікована вибірка
• Шаблон:Не перекладено
• Шаблон:Не перекладено
• Шаблон:Не перекладено— послідовний метод Монте-Карло, який використовує вибірку за значимістю
• Шаблон:Не перекладено
• Шаблон:Не перекладено
• Змінний бітрейт — звичайне аудіододаток для вибірки важливості

Посилання

• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite book

Посилання

• Домашня сторінка послідовних методів Монте-Карло (фільтрація частинок) Шаблон:Webarchive у Кембриджському університеті
• Вступ до важливості вибірки в моделюванні рідкісних подій European journal of Physics. PDF-документ.
• Адаптивні методи Монте-Карло для моделювання рідкісних подій: адаптивні методи Монте-Карло для моделювання рідкісних подій Зимова конференція з моделювання