У статистиці вибірка за значимістю є загальною технікою для оцінки властивостей конкретного розподілу, при цьому вибірки створюються лише з розподілу, відмінного від того, що досліджується. Метод був вперше введений [en] і [en] у 1978 році і пов'язаний з [en] в обчислювальній фізиці. Залежно від застосування, термін може стосуватися процесу вибірки з цього альтернативного розподілу, процесу висновку або обох.
Основна теорія
Нехай є випадковою величиною в деякому ймовірнісному просторі
. Ми хочемо оцінити математичне очікування X розподілу P, позначимо його, як E[X;P]. Якщо ми маємо статистично незалежні випадкові вибірки
, породжені відповідно до P, то емпірична оцінка E [X;P] є
і точність цієї оцінки буде залежати від дисперсії X:
Основною ідею вибірки за значимістю є вибір станів з іншого розподілу задля зменшення дисперсії оцінки E[X;P], або коли взяття проб з P є складним. Це досягається шляхом попереднього підбору такої випадкової змінної , щоб E [L;P] = 1 і P-майже скрізь
. За допомогою змінної L ми визначаємо ймовірність
що задовольняє наступному рівнянню:
Таким чином, змінна X/L буде підбиратися під P(L) для оцінки E[X;P], як зазначено вище, і ця оцінка покращується, коли .
Коли X має постійний знак над Ω, очевидно, що найкращою змінною L буде , так що X/L* є шуканою константою E [X;P], і для визначення її значення достатньо однієї вибірки P(L*). На жаль, так робити неможна, тому що E[X;P] — це саме те значення, яке ми шукаємо! Однак цей теоретичний найкращий випадок L* дає нам уявлення про вибірку за значимістю:
направо, є одним із нескінченно малих елементів, які підсумовують до E[X;P]:
отже, хороша зміна ймовірності P(L) у вибірці за значимістю перерозподілить закон X так, що частоти його вибірок будуть відсортовані безпосередньо відповідно до їх ваги в E[X;P]. Звідси назва «вибірка за значимістю».
Вибірка за значимістю часто використовується як [en]. Коли — рівномірний розподіл і
, E[X;P] відповідає інтегралу від дійсної функції
.
Застосування до ймовірнісного висновку
Такі методи часто використовуються для оцінки апостеріорних густин або очікувань у завданнях оцінки стану та/або параметрів у імовірнісних моделях, які занадто важко обробляти аналітично, наприклад, у байєсівських мережах.
Застосування до моделювання
Вибірка за значимістю — це метод [en], який можна використовувати в методі Монте-Карло. Ідея вибірки за значимістю полягає в тому, що певні значення вхідних випадкових величин у симуляції мають більший вплив на оцінюваний параметр ніж інші. Якщо ці «важливі» значення підкреслюються шляхом вибірки частіше, то дисперсію оцінки можна зменшити. Отже, основна методологія вибірки за значимістю полягає у виборі розподілу, який «заохочує» важливі значення. Таке використання «зміщених» розподілів призведе до зміщеної оцінки, якщо її застосовувати безпосередньо під час моделювання. Однак результати моделювання зважуються, щоб виправити використання зміщеного розподілу, і це гарантує, що нова оцінка вибірки за значимістю є незміщеною. Вага визначається коефіцієнтом правдоподібності, тобто похідною Радона–Нікодима від справжнього основного розподілу щодо розподілу зміщеного моделювання.
Фундаментальною проблемою в реалізації моделювання вибірки за значимістю є вибір зміщеного розподілу, який стимулює важливі області вхідних змінних. Вибір або проектування хорошого зміщеного розподілу — це «мистецтво» вибірки за значимістю. Нагородою за вибір підходящого розподілу може бути величезна економія часу виконання; покаранням за вибір поганого розподілу може бути більш тривалий час виконання, ніж для загального моделювання Монте-Карло без застосування вибірки за значимістю.
Нехай є вибіркою і
є коефіцієнтом ймовірності, де
— функція густини ймовірності (маси) шуканого розподілу і
є функцією густини ймовірності (маси) зміщеного розподілу. Тоді задачу можна охарактеризувати, обравши розподіл вибірки
, що мінімізує дисперсію масштабованої вибірки:
Можна показати, що такий розподіл мінімізує вищезгадану дисперсію:
Зверніть увагу, що коли , ця дисперсія стає 0.
Математичний підхід
Розглянемо оцінку ймовірності шляхом моделювання події
, де
є випадковою величиною з розподілом
і функцією густини ймовірності
. Незалежна однаково розподілена (i.i.d) послідовність
довжини
генерується з розподілу
, та підраховується число
випадкових величин, які лежать вище порога
. Випадкова величина
характеризується біноміальним розподілом
Це демонструє, що і
, тож у межі
ми можемо отримати
. Зауважимо, що дисперсія є малою, якщо
. Вибірка за значимістю пов'язана з визначенням і використанням альтернативної функції щільності
(для
), що зазвичай називають густиною зміщення для імітаційного експерименту. Ця щільність дозволяє події
зустрічатися частіше, тому довжина послідовності
зменшується для даної дисперсії оцінки. Як варіант, для даного
використання густини зміщення призводить до меншої дисперсії в порівнянні зі звичайною оцінкою Монте-Карло. Використовуючи визначення
, ми можемо представити
наступним чином:
де
є коефіцієнтом правдоподібності і називається ваговою функцією. Остання рівність у наведеному вище рівнянні мотивує оцінювача
Це рівняння є незміщеною оцінкою вибірки за значимістю . Тобто процедура оцінки полягає у створенні i.i.d вибірок з
і для кожної вибірки, що перевищує
, оцінка збільшується на вагу
, оцінену за значенням вибірки. Результати усереднюються за
випробуваннями. Легко показати, що дисперсія оцінки вибірки за значимістю є
Тепер проблема застосування вибірки за значимістю зосереджується на пошуку густини зміщення таким чином, щоб дисперсія оцінки вибірки за значимістю була меншою за дисперсію загальної оцінки Монте-Карло. Деяка функція густини зміщення, що мінімізує дисперсію, а за певних умов зводить її до нуля, називаюється оптимальною функцією густини зміщення.
Загальноприйняті методи зміщення
Хоча існує багато видів методів зміщення, наступні два методи є найбільш широко використовуваними при застосуванні вибірки за значимістю.
Масштабування
Перенесення маси ймовірності в область події шляхом додатнього масштабування випадкової величини
з числом, більшим за одиницю, призводить до збільшення дисперсії (також середнього) функції густини. Як наслідок, збільшується хвіст щільності, результатом чого є збільшення ймовірності події. Масштабування, ймовірно, є одним з найперших відомих методів зміщення, який широко використовується на практиці. Він простий у реалізації і зазвичай забезпечує консервативні переваги моделювання порівняно з іншими методами.
У вибірці за значимістю шляхом масштабування щільність моделювання вибирається як функція густини масштабованої випадкової величини , де зазвичай
для оцінки ймовірності хвоста шляхом перетворення,
і вагова функція є
У той час як масштабування зміщує масу ймовірності в бажану область події, воно також штовхає масу в комплементарну область , що є небажаним. Якщо
є сумою
випадкові величини, розповсюдження маси відбувається в
розмірний простір. Наслідком цього є зменшення значення приросту вибірки для збільшення
, і називається ефектом розмірності. Сучасною версією вибірки за значимістю шляхом масштабування є, наприклад, так звана сигма-масштабована вибірка (SSS), яка виконує множинний аналіз Монте-Карло (MC) з різними коефіцієнтами масштабування. На відміну від багатьох інших методів оцінки високої продуктивності (наприклад, відстаней у гіршому випадку (WCD)), SSS не сильно страждає від проблеми розмірності. Крім того, звернення до кількох виходів MC не призводить до зниження ефективності. З іншого боку, як WCD, SSS призначений лише для гаусових статистичних змінних, і на відміну від WCD, метод SSS не призначений для надання точних статистичних кутів. Іншим недоліком SSS є те, що робота MC з великомасштабними факторами може стати складною, наприклад, через проблеми зближення моделі та симулятора. Крім того, у SSS ми стикаємося з сильним компромісом зміщення та дисперсії: використовуючи великі масштабні коефіцієнти, ми отримуємо досить стабільні вихідні результати, але чим більш масштабні коефіцієнти, тим більша похибка зміщення. Якщо переваги SSS не мають великого значення, то інші методи є більш ефективними.
Трансляція
Інший простий і ефективний метод зміщення використовує трансляцію функції густини (і, отже, випадкової величини), щоб помістити більшу частину її ймовірної маси в область рідкісних подій. Трансляція не страждає від ефекту розмірності і успішно використовується в кількох програмах, пов'язаних із моделюванням цифрових комунікаційних систем. Вона часто забезпечує кращий приріст симуляції, ніж масштабування. При зміщенні за допомогою трансляції густина моделювання визначається як
де є величиною зсуву і має бути обрана для мінімізації дисперсії оцінки вибірки за значимістю.
Ефекти складності системи
Фундаментальна проблема застосування вибірки за значимістю полягає в тому, що розробка хороших зміщених розподілів стає складнішою зі збільшенням складності системи. Складні системи — це системи з довгою пам'яттю, оскільки комплексна обробка кількох входів проводиться набагато легше. Ця розмірність або пам'ять може викликати проблеми трьох видів:
- довга пам'ять (сильні [en] (ISI))
- невідома пам'ять (декодери Вітербі)
- можливо нескінченна пам'ять (адаптивні еквалайзери)
В принципі, ідеї вибірки за значимістю залишається незмінною в цих ситуаціях, але дизайн стає набагато складнішим. Успішний підхід до боротьби з цією проблемою, по суті, полягає в розбитті моделювання на кілька менших, більш чітко визначених підпроблем. Потім стратегії вибірки за значимістю використовуються для націлювання на кожну з простіших підпроблем. Прикладами методів розбиття моделювання є моделювання кондиціонування та помилки-події (EES) та регенеративного моделювання.
Оцінка вибірки за значимістю
Щоб визначити успішні методи вибірки за значимістю, корисно мати можливість кількісно оцінити економію під час виконання за рахунок використання цього підходу. Зазвичай використовується показник продуктивності , і це можна інтерпретувати як коефіцієнт прискорення, за допомогою якого оцінка вибірки за значимістю досягає такої ж точності, що й оцінка MC. Це має бути обчислено емпіричним шляхом, оскільки дисперсія оцінки навряд чи буде аналітично можлива, коли їх середнє значення нерозбірне. Іншими корисними поняттями для кількісної оцінки вибірки за значимістю є межі дисперсії та поняття асимптотичної ефективності. Одним із відповідних показників є так званий ефективний розмір вибірки (ESS).
Функція дисперсійних втрат
Дисперсія не є єдиною можливою функцією втрат для моделювання, а інші функції втрат, такі як середнє абсолютне відхилення, використовуються в різних статистичних програмах. Тим не менш, дисперсія є основною функцією втрат, яка розглядається в літературі, ймовірно, через використання дисперсії в довірчих інтервалах і в показнику ефективності .
Супутнім питанням є той факт, що співвідношення переоцінює економію часу виконання через вибірку за значимістю, оскільки не включає додатковий обчислювальний час, необхідний для підрахування вагової функції. Отже, деякі люди оцінюють чисте покращення часу виконання різними способами. Можливо, більш серйозними витратами на вибірку за значимістю є час, необхідний для розробки та програмування техніки та аналітичного виведення бажаної вагової функції.
Багаторазова та адаптивна вибірка за значимістю
Коли різні допоміжні розподіли, ,
спільно використовуються для опису вибірок
можна використовувати різні відповідні вагові функції (наприклад, див.). В адаптивному налаштуванні допоміжні розподіли,
,
та
оновлюються на кожній ітерації
адаптивного алгоритму вибірки за значимістю. Отже, оскільки використовується сукупність щільностей пропозицій, можна використовувати декілька відповідних комбінацій схем вибірки та зважування.
Див. також
- Метод Монте-Карло
- [en]
- Стратифікована вибірка
- [en]
- [en]
- [en]— послідовний метод Монте-Карло, який використовує вибірку за значимістю
- [en]
- [en]
- Змінний бітрейт — звичайне аудіододаток для вибірки важливості
Примітки
- 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.
- Rubinstein, R. Y., & (2011). Simulation and the Monte Carlo method (Vol. 707). John Wiley & Sons.
- 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.
- 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=
() - 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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-документ.
- Адаптивні методи Монте-Карло для моделювання рідкісних подій: адаптивні методи Монте-Карло для моделювання рідкісних подій Зимова конференція з моделювання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U statistici vibirka za znachimistyu ye zagalnoyu tehnikoyu dlya ocinki vlastivostej konkretnogo rozpodilu pri comu vibirki stvoryuyutsya lishe z rozpodilu vidminnogo vid togo sho doslidzhuyetsya Metod buv vpershe vvedenij en i en u 1978 roci i pov yazanij z en v obchislyuvalnij fizici Zalezhno vid zastosuvannya termin mozhe stosuvatisya procesu vibirki z cogo alternativnogo rozpodilu procesu visnovku abo oboh Osnovna teoriyaNehaj X W R displaystyle X Omega to mathbb R ye vipadkovoyu velichinoyu v deyakomu jmovirnisnomu prostori W F P displaystyle Omega mathcal F P Mi hochemo ociniti matematichne ochikuvannya X rozpodilu P poznachimo jogo yak E X P Yaksho mi mayemo statistichno nezalezhni vipadkovi vibirki x1 xn displaystyle x 1 ldots x n porodzheni vidpovidno do P to empirichna ocinka E X P ye E n X P 1n i 1nxi displaystyle widehat mathbf E n X P frac 1 n sum i 1 n x i i tochnist ciyeyi ocinki bude zalezhati vid dispersiyi X var E n P var X P n displaystyle operatorname var widehat mathbf E n P frac operatorname var X P n Osnovnoyu ideyu vibirki za znachimistyu ye vibir staniv z inshogo rozpodilu zadlya zmenshennya dispersiyi ocinki E X P abo koli vzyattya prob z P ye skladnim Ce dosyagayetsya shlyahom poperednogo pidboru takoyi vipadkovoyi zminnoyi L 0 displaystyle L geq 0 shob E L P 1 i P majzhe skriz L w 0 displaystyle L omega neq 0 Za dopomogoyu zminnoyi L mi viznachayemo jmovirnist P L displaystyle P L sho zadovolnyaye nastupnomu rivnyannyu E X P E XL P L displaystyle mathbf E X P mathbf E left frac X L P L right Takim chinom zminna X L bude pidbiratisya pid P L dlya ocinki E X P yak zaznacheno vishe i cya ocinka pokrashuyetsya koli var XL P L lt var X P displaystyle operatorname var left frac X L P L right lt operatorname var X P Koli X maye postijnij znak nad W ochevidno sho najkrashoyu zminnoyu L bude L XE X P 0 displaystyle L frac X mathbf E X P geq 0 tak sho X L ye shukanoyu konstantoyu E X P i dlya viznachennya yiyi znachennya dostatno odniyeyi vibirki P L Na zhal tak robiti nemozhna tomu sho E X P ce same te znachennya yake mi shukayemo Odnak cej teoretichnij najkrashij vipadok L daye nam uyavlennya pro vibirku za znachimistyu a R P L X a a da w X a a da X w E X P dP w 1E X P aP X a a da displaystyle begin aligned forall a in mathbb R P L X in a a da amp int omega in X in a a da frac X omega E X P dP omega 6pt amp frac 1 E X P a P X in a a da end aligned napravo aP X a a da displaystyle a P X in a a da ye odnim iz neskinchenno malih elementiv yaki pidsumovuyut do E X P E X P a aP X a a da displaystyle E X P int a infty infty a P X in a a da otzhe horosha zmina jmovirnosti P L u vibirci za znachimistyu pererozpodilit zakon X tak sho chastoti jogo vibirok budut vidsortovani bezposeredno vidpovidno do yih vagi v E X P Zvidsi nazva vibirka za znachimistyu Vibirka za znachimistyu chasto vikoristovuyetsya yak en Koli P displaystyle P rivnomirnij rozpodil i W R displaystyle Omega mathbb R E X P vidpovidaye integralu vid dijsnoyi funkciyi X R R displaystyle X mathbb R to mathbb R Zastosuvannya do jmovirnisnogo visnovkuTaki metodi chasto vikoristovuyutsya dlya ocinki aposteriornih gustin abo ochikuvan u zavdannyah ocinki stanu ta abo parametriv u imovirnisnih modelyah yaki zanadto vazhko obroblyati analitichno napriklad u bajyesivskih merezhah Zastosuvannya do modelyuvannyaVibirka za znachimistyu ce metod en yakij mozhna vikoristovuvati v metodi Monte Karlo Ideya vibirki za znachimistyu polyagaye v tomu sho pevni znachennya vhidnih vipadkovih velichin u simulyaciyi mayut bilshij vpliv na ocinyuvanij parametr nizh inshi Yaksho ci vazhlivi znachennya pidkreslyuyutsya shlyahom vibirki chastishe to dispersiyu ocinki mozhna zmenshiti Otzhe osnovna metodologiya vibirki za znachimistyu polyagaye u vibori rozpodilu yakij zaohochuye vazhlivi znachennya Take vikoristannya zmishenih rozpodiliv prizvede do zmishenoyi ocinki yaksho yiyi zastosovuvati bezposeredno pid chas modelyuvannya Odnak rezultati modelyuvannya zvazhuyutsya shob vipraviti vikoristannya zmishenogo rozpodilu i ce garantuye sho nova ocinka vibirki za znachimistyu ye nezmishenoyu Vaga viznachayetsya koeficiyentom pravdopodibnosti tobto pohidnoyu Radona Nikodima vid spravzhnogo osnovnogo rozpodilu shodo rozpodilu zmishenogo modelyuvannya Fundamentalnoyu problemoyu v realizaciyi modelyuvannya vibirki za znachimistyu ye vibir zmishenogo rozpodilu yakij stimulyuye vazhlivi oblasti vhidnih zminnih Vibir abo proektuvannya horoshogo zmishenogo rozpodilu ce mistectvo vibirki za znachimistyu Nagorodoyu za vibir pidhodyashogo rozpodilu mozhe buti velichezna ekonomiya chasu vikonannya pokarannyam za vibir poganogo rozpodilu mozhe buti bilsh trivalij chas vikonannya nizh dlya zagalnogo modelyuvannya Monte Karlo bez zastosuvannya vibirki za znachimistyu Nehaj X displaystyle X ye vibirkoyu i f X g X displaystyle frac f X g X ye koeficiyentom jmovirnosti de f displaystyle f funkciya gustini jmovirnosti masi shukanogo rozpodilu i g displaystyle g ye funkciyeyu gustini jmovirnosti masi zmishenogo rozpodilu Todi zadachu mozhna oharakterizuvati obravshi rozpodil vibirki g displaystyle g sho minimizuye dispersiyu masshtabovanoyi vibirki g mingvarg Xf X g X displaystyle g min g operatorname var g left X frac f X g X right Mozhna pokazati sho takij rozpodil minimizuye vishezgadanu dispersiyu g X X f X x f x dx displaystyle g X frac X f X int x f x dx Zvernit uvagu sho koli X 0 displaystyle X geq 0 cya dispersiya staye 0 Matematichnij pidhid Rozglyanemo ocinku jmovirnosti shlyahom modelyuvannya pt displaystyle p t podiyi X t displaystyle X geq t de X displaystyle X ye vipadkovoyu velichinoyu z rozpodilom F displaystyle F i funkciyeyu gustini jmovirnosti f x F x displaystyle f x F x Nezalezhna odnakovo rozpodilena i i d poslidovnist Xi displaystyle X i dovzhini K displaystyle K generuyetsya z rozpodilu F displaystyle F ta pidrahovuyetsya chislo kt displaystyle k t vipadkovih velichin yaki lezhat vishe poroga t displaystyle t Vipadkova velichina kt displaystyle k t harakterizuyetsya binomialnim rozpodilom P kt k Kk ptk 1 pt K k k 0 1 K displaystyle P k t k K choose k p t k 1 p t K k quad quad k 0 1 dots K Ce demonstruye sho E kt K pt displaystyle operatorname E k t K p t i var kt K pt 1 pt K displaystyle operatorname var k t K p t 1 p t K tozh u mezhi K displaystyle K to infty mi mozhemo otrimati pt displaystyle p t Zauvazhimo sho dispersiya ye maloyu yaksho pt 1 displaystyle p t approx 1 Vibirka za znachimistyu pov yazana z viznachennyam i vikoristannyam alternativnoyi funkciyi shilnosti f displaystyle f dlya X displaystyle X sho zazvichaj nazivayut gustinoyu zmishennya dlya imitacijnogo eksperimentu Cya shilnist dozvolyaye podiyi X t displaystyle X geq t zustrichatisya chastishe tomu dovzhina poslidovnosti K displaystyle K zmenshuyetsya dlya danoyi dispersiyi ocinki Yak variant dlya danogo K displaystyle K vikoristannya gustini zmishennya prizvodit do menshoyi dispersiyi v porivnyanni zi zvichajnoyu ocinkoyu Monte Karlo Vikoristovuyuchi viznachennya pt displaystyle p t mi mozhemo predstaviti f displaystyle f nastupnim chinom pt E 1 X t 1 x t f x f x f x dx E 1 X t W X displaystyle begin aligned p t amp E 1 X geq t 6pt amp int 1 x geq t frac f x f x f x dx 6pt amp E 1 X geq t W X end aligned de W f f displaystyle W cdot equiv frac f cdot f cdot ye koeficiyentom pravdopodibnosti i nazivayetsya vagovoyu funkciyeyu Ostannya rivnist u navedenomu vishe rivnyanni motivuye ocinyuvacha p t 1K i 1K1 Xi t W Xi Xi f 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 Ce rivnyannya ye nezmishenoyu ocinkoyu vibirki za znachimistyu pt displaystyle p t Tobto procedura ocinki polyagaye u stvorenni i i d vibirok z f displaystyle f i dlya kozhnoyi vibirki sho perevishuye t displaystyle t ocinka zbilshuyetsya na vagu W displaystyle W ocinenu za znachennyam vibirki Rezultati userednyuyutsya za K displaystyle K viprobuvannyami Legko pokazati sho dispersiya ocinki vibirki za znachimistyu ye var p t 1Kvar 1 X t W X 1K E 1 X t 2W2 X pt2 1K E 1 X t W X pt2 displaystyle begin aligned operatorname var widehat p t amp frac 1 K operatorname var 1 X geq t W X 5pt amp frac 1 K left E 1 X geq t 2 W 2 X p t 2 right 5pt amp frac 1 K left E 1 X geq t W X p t 2 right end aligned Teper problema zastosuvannya vibirki za znachimistyu zoseredzhuyetsya na poshuku gustini zmishennya f displaystyle f takim chinom shob dispersiya ocinki vibirki za znachimistyu bula menshoyu za dispersiyu zagalnoyi ocinki Monte Karlo Deyaka funkciya gustini zmishennya sho minimizuye dispersiyu a za pevnih umov zvodit yiyi do nulya nazivayuyetsya optimalnoyu funkciyeyu gustini zmishennya Zagalnoprijnyati metodi zmishennya Hocha isnuye bagato vidiv metodiv zmishennya nastupni dva metodi ye najbilsh shiroko vikoristovuvanimi pri zastosuvanni vibirki za znachimistyu Masshtabuvannya Perenesennya masi jmovirnosti v oblast podiyi X t displaystyle X geq t shlyahom dodatnogo masshtabuvannya vipadkovoyi velichini X displaystyle X z chislom bilshim za odinicyu prizvodit do zbilshennya dispersiyi takozh serednogo funkciyi gustini Yak naslidok zbilshuyetsya hvist shilnosti rezultatom chogo ye zbilshennya jmovirnosti podiyi Masshtabuvannya jmovirno ye odnim z najpershih vidomih metodiv zmishennya yakij shiroko vikoristovuyetsya na praktici Vin prostij u realizaciyi i zazvichaj zabezpechuye konservativni perevagi modelyuvannya porivnyano z inshimi metodami U vibirci za znachimistyu shlyahom masshtabuvannya shilnist modelyuvannya vibirayetsya yak funkciya gustini masshtabovanoyi vipadkovoyi velichini aX displaystyle aX de zazvichaj a gt 1 displaystyle a gt 1 dlya ocinki jmovirnosti hvosta shlyahom peretvorennya f x 1af xa displaystyle f x frac 1 a f bigg frac x a bigg i vagova funkciya ye W x af x f x a displaystyle W x a frac f x f x a U toj chas yak masshtabuvannya zmishuye masu jmovirnosti v bazhanu oblast podiyi vono takozh shtovhaye masu v komplementarnu oblast X lt t displaystyle X lt t sho ye nebazhanim Yaksho X displaystyle X ye sumoyu n displaystyle n vipadkovi velichini rozpovsyudzhennya masi vidbuvayetsya v n displaystyle n rozmirnij prostir Naslidkom cogo ye zmenshennya znachennya prirostu vibirki dlya zbilshennya n displaystyle n i nazivayetsya efektom rozmirnosti Suchasnoyu versiyeyu vibirki za znachimistyu shlyahom masshtabuvannya ye napriklad tak zvana sigma masshtabovana vibirka SSS yaka vikonuye mnozhinnij analiz Monte Karlo MC z riznimi koeficiyentami masshtabuvannya Na vidminu vid bagatoh inshih metodiv ocinki visokoyi produktivnosti napriklad vidstanej u girshomu vipadku WCD SSS ne silno strazhdaye vid problemi rozmirnosti Krim togo zvernennya do kilkoh vihodiv MC ne prizvodit do znizhennya efektivnosti Z inshogo boku yak WCD SSS priznachenij lishe dlya gausovih statistichnih zminnih i na vidminu vid WCD metod SSS ne priznachenij dlya nadannya tochnih statistichnih kutiv Inshim nedolikom SSS ye te sho robota MC z velikomasshtabnimi faktorami mozhe stati skladnoyu napriklad cherez problemi zblizhennya modeli ta simulyatora Krim togo u SSS mi stikayemosya z silnim kompromisom zmishennya ta dispersiyi vikoristovuyuchi veliki masshtabni koeficiyenti mi otrimuyemo dosit stabilni vihidni rezultati ale chim bilsh masshtabni koeficiyenti tim bilsha pohibka zmishennya Yaksho perevagi SSS ne mayut velikogo znachennya to inshi metodi ye bilsh efektivnimi Translyaciya Inshij prostij i efektivnij metod zmishennya vikoristovuye translyaciyu funkciyi gustini i otzhe vipadkovoyi velichini shob pomistiti bilshu chastinu yiyi jmovirnoyi masi v oblast ridkisnih podij Translyaciya ne strazhdaye vid efektu rozmirnosti i uspishno vikoristovuyetsya v kilkoh programah pov yazanih iz modelyuvannyam cifrovih komunikacijnih sistem Vona chasto zabezpechuye krashij pririst simulyaciyi nizh masshtabuvannya Pri zmishenni za dopomogoyu translyaciyi gustina modelyuvannya viznachayetsya yak f x f x c c gt 0 displaystyle f x f x c quad c gt 0 de c displaystyle c ye velichinoyu zsuvu i maye buti obrana dlya minimizaciyi dispersiyi ocinki vibirki za znachimistyu Efekti skladnosti sistemi Fundamentalna problema zastosuvannya vibirki za znachimistyu polyagaye v tomu sho rozrobka horoshih zmishenih rozpodiliv staye skladnishoyu zi zbilshennyam skladnosti sistemi Skladni sistemi ce sistemi z dovgoyu pam yattyu oskilki kompleksna obrobka kilkoh vhodiv provoditsya nabagato legshe Cya rozmirnist abo pam yat mozhe viklikati problemi troh vidiv dovga pam yat silni en ISI nevidoma pam yat dekoderi Viterbi mozhlivo neskinchenna pam yat adaptivni ekvalajzeri V principi ideyi vibirki za znachimistyu zalishayetsya nezminnoyu v cih situaciyah ale dizajn staye nabagato skladnishim Uspishnij pidhid do borotbi z ciyeyu problemoyu po suti polyagaye v rozbitti modelyuvannya na kilka menshih bilsh chitko viznachenih pidproblem Potim strategiyi vibirki za znachimistyu vikoristovuyutsya dlya nacilyuvannya na kozhnu z prostishih pidproblem Prikladami metodiv rozbittya modelyuvannya ye modelyuvannya kondicionuvannya ta pomilki podiyi EES ta regenerativnogo modelyuvannya Ocinka vibirki za znachimistyu Shob viznachiti uspishni metodi vibirki za znachimistyu korisno mati mozhlivist kilkisno ociniti ekonomiyu pid chas vikonannya za rahunok vikoristannya cogo pidhodu Zazvichaj vikoristovuyetsya pokaznik produktivnosti sMC2 sIS2 displaystyle sigma MC 2 sigma IS 2 i ce mozhna interpretuvati yak koeficiyent priskorennya za dopomogoyu yakogo ocinka vibirki za znachimistyu dosyagaye takoyi zh tochnosti sho j ocinka MC Ce maye buti obchisleno empirichnim shlyahom oskilki dispersiya ocinki navryad chi bude analitichno mozhliva koli yih serednye znachennya nerozbirne Inshimi korisnimi ponyattyami dlya kilkisnoyi ocinki vibirki za znachimistyu ye mezhi dispersiyi ta ponyattya asimptotichnoyi efektivnosti Odnim iz vidpovidnih pokaznikiv ye tak zvanij efektivnij rozmir vibirki ESS Funkciya dispersijnih vtrat Dispersiya ne ye yedinoyu mozhlivoyu funkciyeyu vtrat dlya modelyuvannya a inshi funkciyi vtrat taki yak serednye absolyutne vidhilennya vikoristovuyutsya v riznih statistichnih programah Tim ne mensh dispersiya ye osnovnoyu funkciyeyu vtrat yaka rozglyadayetsya v literaturi jmovirno cherez vikoristannya dispersiyi v dovirchih intervalah i v pokazniku efektivnosti sMC2 sIS2 displaystyle sigma MC 2 sigma IS 2 Suputnim pitannyam ye toj fakt sho spivvidnoshennya sMC2 sIS2 displaystyle sigma MC 2 sigma IS 2 pereocinyuye ekonomiyu chasu vikonannya cherez vibirku za znachimistyu oskilki ne vklyuchaye dodatkovij obchislyuvalnij chas neobhidnij dlya pidrahuvannya vagovoyi funkciyi Otzhe deyaki lyudi ocinyuyut chiste pokrashennya chasu vikonannya riznimi sposobami Mozhlivo bilsh serjoznimi vitratami na vibirku za znachimistyu ye chas neobhidnij dlya rozrobki ta programuvannya tehniki ta analitichnogo vivedennya bazhanoyi vagovoyi funkciyi Bagatorazova ta adaptivna vibirka za znachimistyu Koli rizni dopomizhni rozpodili gn x displaystyle g n x n 1 N displaystyle n 1 ldots N spilno vikoristovuyutsya dlya opisu vibirok x1 xN displaystyle x 1 ldots x N mozhna vikoristovuvati rizni vidpovidni vagovi funkciyi napriklad div V adaptivnomu nalashtuvanni dopomizhni rozpodili gn t x displaystyle g n t x n 1 N displaystyle n 1 ldots N ta t 1 T displaystyle t 1 ldots T onovlyuyutsya na kozhnij iteraciyi t displaystyle t adaptivnogo algoritmu vibirki za znachimistyu Otzhe oskilki vikoristovuyetsya sukupnist shilnostej propozicij mozhna vikoristovuvati dekilka vidpovidnih kombinacij shem vibirki ta zvazhuvannya Div takozhMetod Monte Karlo en Stratifikovana vibirka en en en poslidovnij metod Monte Karlo yakij vikoristovuye vibirku za znachimistyu en en Zminnij bitrejt zvichajne audiododatok dlya vibirki vazhlivostiPrimitkiKloek 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 Rubinstein R Y amp 2011 Simulation and the Monte Carlo method Vol 707 John Wiley amp Sons Martino Luca Elvira Victor 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 Veach Eric Guibas Leonidas J 1 sichnya 1995 Optimally Combining Sampling Techniques for Monte Carlo Rendering SIGGRAPH 95 New York NY USA ACM s 419 428 doi 10 1145 218380 218498 ISBN 978 0 89791 701 8 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Proignorovano journal dovidka Owen Art Associate Yi Zhou 1 bereznya 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 Elvira V Martino L Luengo D Bugallo M F 1 zhovtnya 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 Elvira Victor Martino Luca Luengo David Bugallo Monica 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 Cappe O Guillin A Marin J M Robert C P 1 grudnya 2004 Population Monte Carlo Journal of Computational and Graphical Statistics 13 4 907 929 doi 10 1198 106186004X12803 ISSN 1061 8600 Martino L Elvira V Luengo D Corander J 1 travnya 2017 Layered adaptive importance sampling Statistics and Computing angl 27 3 599 623 arXiv 1505 04732 doi 10 1007 s11222 016 9642 5 ISSN 0960 3174 Cappe Olivier Douc Randal Guillin Arnaud Marin Jean Michel Robert Christian P 25 kvitnya 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 Cornuet Jean Marie Marin Jean Michel Mira Antonietta Robert Christian P 1 grudnya 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 Martino L Elvira V Luengo D Corander J 1 serpnya 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 Bugallo Monica F Martino Luca Corander Jukka 1 grudnya 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 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 PosilannyaArouna 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 978 0 387 95146 1 Ferrari M Bellini S 2001 Importance Sampling simulation of turbo product codes T 9 s 2773 2777 doi 10 1109 ICC 2001 936655 ISBN 978 0 7803 7097 5 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Proignorovano journal dovidka Mazonka Oleg 2016 PDF Journal of Reference 16 Arhiv originalu PDF za 14 kvitnya 2021 Procitovano 23 grudnya 2021 Oberg Tommy 2001 Modulation Detection and Coding New York John Wiley amp Sons Press WH Teukolsky SA Vetterling WT Flannery BP 2007 Section 7 9 1 Importance Sampling Numerical Recipes The Art of Scientific Computing vid 3rd New York Cambridge University Press ISBN 978 0 521 88068 8 Ripley B D 1987 Stochastic Simulation Wiley amp 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 PosilannyaDomashnya storinka poslidovnih metodiv Monte Karlo filtraciya chastinok 14 listopada 2013 u Wayback Machine u Kembridzhskomu universiteti Vstup do vazhlivosti vibirki v modelyuvanni ridkisnih podij European journal of Physics PDF dokument Adaptivni metodi Monte Karlo dlya modelyuvannya ridkisnih podij adaptivni metodi Monte Karlo dlya modelyuvannya ridkisnih podij Zimova konferenciya z modelyuvannya