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

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

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

Нехай ${\displaystyle X:\Omega \to \mathbb {R} }$ є випадковою величиною в деякому ймовірнісному просторі ${\displaystyle (\Omega ,{\mathcal {F}},P)}$. Ми хочемо оцінити математичне очікування X розподілу P, позначимо його, як E[X;P]. Якщо ми маємо статистично незалежні випадкові вибірки ${\displaystyle x_{1},\ldots ,x_{n}}$, породжені відповідно до P, то емпірична оцінка E [X;P] є

${\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 є складним. Це досягається шляхом попереднього підбору такої випадкової змінної ${\displaystyle L\geq 0}$, щоб E [L;P] = 1 і P-майже скрізь ${\displaystyle L(\omega )\neq 0}$. За допомогою змінної L ми визначаємо ймовірність ${\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 буде ${\displaystyle L^{*}={\frac {X}{\mathbf {E} [X;P]}}\geq 0}$, так що X/L* є шуканою константою E [X;P], і для визначення її значення достатньо однієї вибірки 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[X;P]:

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

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

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

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

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

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

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

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

Нехай ${\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).}$

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

${\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)\,}$. Незалежна однаково розподілена (i.i.d) послідовність ${\displaystyle X_{i}\,}$ довжини ${\displaystyle K}$ генерується з розподілу ${\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\,}$ є величиною зсуву і має бути обрана для мінімізації дисперсії оцінки вибірки за значимістю.

Ефекти складності системи

Фундаментальна проблема застосування вибірки за значимістю полягає в тому, що розробка хороших зміщених розподілів стає складнішою зі збільшенням складності системи. Складні системи — це системи з довгою пам'яттю, оскільки комплексна обробка кількох входів проводиться набагато легше. Ця розмірність або пам'ять може викликати проблеми трьох видів:

• довга пам'ять (сильні ^[en] (ISI))
• невідома пам'ять (декодери Вітербі)
• можливо нескінченна пам'ять (адаптивні еквалайзери)

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

Оцінка вибірки за значимістю

Щоб визначити успішні методи вибірки за значимістю, корисно мати можливість кількісно оцінити економію під час виконання за рахунок використання цього підходу. Зазвичай використовується показник продуктивності ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$, і це можна інтерпретувати як коефіцієнт прискорення, за допомогою якого оцінка вибірки за значимістю досягає такої ж точності, що й оцінка MC. Це має бути обчислено емпіричним шляхом, оскільки дисперсія оцінки навряд чи буде аналітично можлива, коли їх середнє значення нерозбірне. Іншими корисними поняттями для кількісної оцінки вибірки за значимістю є межі дисперсії та поняття асимптотичної ефективності. Одним із відповідних показників є так званий ефективний розмір вибірки (ESS).

Функція дисперсійних втрат

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

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

Багаторазова та адаптивна вибірка за значимістю

Коли різні допоміжні розподіли, ${\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}$ адаптивного алгоритму вибірки за значимістю. Отже, оскільки використовується сукупність щільностей пропозицій, можна використовувати декілька відповідних комбінацій схем вибірки та зважування.

Див. також

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

Примітки

1. Kloek, T.; van Dijk, H. K. (1978). Bayesian Estimates of Equation System Parameters: An Application of Integration by Monte Carlo. . 46 (1): 1—19. doi:10.2307/1913641.
2. Rubinstein, R. Y., & (2011). Simulation and the Monte Carlo method (Vol. 707). John Wiley & Sons.
3. Martino, Luca; Elvira, Víctor; Louzada, Francisco (2017). Effective sample size for importance sampling based on discrepancy measures. Signal Processing. 131: 386—401. arXiv:1602.03572. doi:10.1016/j.sigpro.2016.08.025.
4. Veach, Eric; Guibas, Leonidas J. (1 січня 1995). Optimally Combining Sampling Techniques for Monte Carlo Rendering. SIGGRAPH '95. New York, NY, USA: ACM. с. 419–428. doi:10.1145/218380.218498. ISBN . {{}}: Проігноровано |journal= ()
5. Owen, Art; Associate, Yi Zhou (1 березня 2000). Safe and Effective Importance Sampling. Journal of the American Statistical Association. 95 (449): 135—143. CiteSeerX 10.1.1.36.4536. doi:10.1080/01621459.2000.10473909. ISSN 0162-1459.
6. Elvira, V.; Martino, L.; Luengo, D.; Bugallo, M.F. (1 жовтня 2015). Efficient Multiple Importance Sampling Estimators. IEEE Signal Processing Letters. 22 (10): 1757—1761. arXiv:1505.05391. Bibcode:2015ISPL...22.1757E. doi:10.1109/LSP.2015.2432078. ISSN 1070-9908.
7. Elvira, Víctor; Martino, Luca; Luengo, David; Bugallo, Mónica F. (2017). Improving population Monte Carlo: Alternative weighting and resampling schemes. Signal Processing. 131: 77—91. arXiv:1607.02758. doi:10.1016/j.sigpro.2016.07.012.
8. Cappé, O.; Guillin, A.; Marin, J. M.; Robert, C. P. (1 грудня 2004). Population Monte Carlo. Journal of Computational and Graphical Statistics. 13 (4): 907—929. doi:10.1198/106186004X12803. ISSN 1061-8600.
9. Martino, L.; Elvira, V.; Luengo, D.; Corander, J. (1 травня 2017). Layered adaptive importance sampling. Statistics and Computing (англ.). 27 (3): 599—623. arXiv:1505.04732. doi:10.1007/s11222-016-9642-5. ISSN 0960-3174.
10. Cappé, Olivier; Douc, Randal; Guillin, Arnaud; Marin, Jean-Michel; Robert, Christian P. (25 квітня 2008). Adaptive importance sampling in general mixture classes. Statistics and Computing. 18 (4): 447—459. arXiv:0710.4242. doi:10.1007/s11222-008-9059-x. ISSN 0960-3174.
11. Cornuet, Jean-Marie; Marin, Jean-Michel; Mira, Antonietta; Robert, Christian P. (1 грудня 2012). Adaptive Multiple Importance Sampling. Scandinavian Journal of Statistics. 39 (4): 798—812. arXiv:0907.1254. doi:10.1111/j.1467-9469.2011.00756.x. ISSN 1467-9469.
12. Martino, L.; Elvira, V.; Luengo, D.; Corander, J. (1 серпня 2015). An Adaptive Population Importance Sampler: Learning From Uncertainty. IEEE Transactions on Signal Processing. 63 (16): 4422—4437. Bibcode:2015ITSP...63.4422M. CiteSeerX 10.1.1.464.9395. doi:10.1109/TSP.2015.2440215. ISSN 1053-587X.
13. Bugallo, Mónica F.; Martino, Luca; Corander, Jukka (1 грудня 2015). Adaptive importance sampling in signal processing. Digital Signal Processing. Special Issue in Honour of William J. (Bill) Fitzgerald. 47: 36—49. doi:10.1016/j.dsp.2015.05.014.
14. Bugallo, M. F.; Elvira, V.; Martino, L.; Luengo, D.; Miguez, J.; Djuric, P. M. (July 2017). Adaptive Importance Sampling: The past, the present, and the future. IEEE Signal Processing Magazine. 34 (4): 60—79. Bibcode:2017ISPM...34...60B. doi:10.1109/msp.2017.2699226. ISSN 1053-5888.

Посилання

• Arouna, Bouhari (2004). Adaptative Monte Carlo Method, A Variance Reduction Technique. Monte Carlo Methods and Their Applications. 10 (1): 1—24. doi:10.1515/156939604323091180.
• Bucklew, James Antonio (2004). Introduction to Rare Event Simulation. New York: Springer-Verlag.
• Doucet, A.; de Freitas, N.; Gordon, N. (2001). Sequential Monte Carlo Methods in Practice. Springer. ISBN .
• Ferrari, M.; Bellini, S. (2001). Importance Sampling simulation of turbo product codes. Т. 9. с. 2773—2777. doi:10.1109/ICC.2001.936655. ISBN . {{}}: Проігноровано |journal= ()
• Mazonka, Oleg (2016). (PDF). Journal of Reference. 16. Архів оригіналу (PDF) за 14 квітня 2021. Процитовано 23 грудня 2021.
• Oberg, Tommy (2001). Modulation, Detection, and Coding. New York: John Wiley & Sons.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). Section 7.9.1 Importance Sampling. Numerical Recipes: The Art of Scientific Computing (вид. 3rd). New York: Cambridge University Press. ISBN .
• Ripley, B. D. (1987). Stochastic Simulation. Wiley & Sons.
• Smith, P. J.; Shafi, M.; Gao, H. (1997). Quick simulation: A review of importance sampling techniques in communication systems. IEEE Journal on Selected Areas in Communications. 15 (4): 597—613. doi:10.1109/49.585771.
• Srinivasan, R. (2002). Importance sampling – Applications in communications and detection. Berlin: Springer-Verlag.

Посилання

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