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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

У статистиці вибірка за значимістю є загальною технікою для оцінки властивостей конкретного розподілу, при цьому вибірки створюються лише з розподілу, відмінного від того, що досліджується. Метод був вперше введений Теуном Клоеком[en] і Германом К. ван Дейком[en] у 1978 році[1] і пов'язаний з парасольковою вибіркою[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], який можна використовувати в методі Монте-Карло. Ідея вибірки за значимістю полягає в тому, що певні значення вхідних випадкових величин у симуляції мають більший вплив на оцінюваний параметр ніж інші. Якщо ці «важливі» значення підкреслюються шляхом вибірки частіше, то дисперсію оцінки можна зменшити. Отже, основна методологія вибірки за значимістю полягає у виборі розподілу, який «заохочує» важливі значення. Таке використання «зміщених» розподілів призведе до зміщеної оцінки, якщо її застосовувати безпосередньо під час моделювання. Однак результати моделювання зважуються, щоб виправити використання зміщеного розподілу, і це гарантує, що нова оцінка вибірки за значимістю є незміщеною. Вага визначається коефіцієнтом правдоподібності, тобто похідною Радона–Нікодима від справжнього основного розподілу щодо розподілу зміщеного моделювання.

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

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

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

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

Математичний підхід[ред. | ред. код]

Розглянемо оцінку ймовірності шляхом моделювання події , де є випадковою величиною з розподілом і функцією густини ймовірності . Незалежна однаково розподілена (i.i.d) послідовність довжини генерується з розподілу , та підраховується число випадкових величин, які лежать вище порога . Випадкова величина характеризується біноміальним розподілом

Це демонструє, що і , тож у межі ми можемо отримати . Зауважимо, що дисперсія є малою, якщо . Вибірка за значимістю пов'язана з визначенням і використанням альтернативної функції щільності (для ), що зазвичай називають густиною зміщення для імітаційного експерименту. Ця щільність дозволяє події зустрічатися частіше, тому довжина послідовності зменшується для даної дисперсії оцінки. Як варіант, для даного використання густини зміщення призводить до меншої дисперсії в порівнянні зі звичайною оцінкою Монте-Карло. Використовуючи визначення , ми можемо представити наступним чином:

де

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

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

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

Загальноприйняті методи зміщення[ред. | ред. код]

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

Масштабування[ред. | ред. код]

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

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

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

У той час як масштабування зміщує масу ймовірності в бажану область події, воно також штовхає масу в комплементарну область , що є небажаним. Якщо є сумою випадкові величини, розповсюдження маси відбувається в розмірний простір. Наслідком цього є зменшення значення приросту вибірки для збільшення , і називається ефектом розмірності. Сучасною версією вибірки за значимістю шляхом масштабування є, наприклад, так звана сигма-масштабована вибірка (SSS), яка виконує множинний аналіз Монте-Карло (MC) з різними коефіцієнтами масштабування. На відміну від багатьох інших методів оцінки високої продуктивності (наприклад, відстаней у гіршому випадку (WCD)), SSS не сильно страждає від проблеми розмірності. Крім того, звернення до кількох виходів MC не призводить до зниження ефективності. З іншого боку, як WCD, SSS призначений лише для гаусових статистичних змінних, і на відміну від WCD, метод SSS не призначений для надання точних статистичних кутів. Іншим недоліком SSS є те, що робота MC з великомасштабними факторами може стати складною, наприклад, через проблеми зближення моделі та симулятора. Крім того, у SSS ми стикаємося з сильним компромісом зміщення та дисперсії: використовуючи великі масштабні коефіцієнти, ми отримуємо досить стабільні вихідні результати, але чим більш масштабні коефіцієнти, тим більша похибка зміщення. Якщо переваги SSS не мають великого значення, то інші методи є більш ефективними.

Трансляція[ред. | ред. код]

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

де є величиною зсуву і має бути обрана для мінімізації дисперсії оцінки вибірки за значимістю.

Ефекти складності системи[ред. | ред. код]

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

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

Оцінка вибірки за значимістю[ред. | ред. код]

Щоб визначити успішні методи вибірки за значимістю, корисно мати можливість кількісно оцінити економію під час виконання за рахунок використання цього підходу. Зазвичай використовується показник продуктивності , і це можна інтерпретувати як коефіцієнт прискорення, за допомогою якого оцінка вибірки за значимістю досягає такої ж точності, що й оцінка MC. Це має бути обчислено емпіричним шляхом, оскільки дисперсія оцінки навряд чи буде аналітично можлива, коли їх середнє значення нерозбірне. Іншими корисними поняттями для кількісної оцінки вибірки за значимістю є межі дисперсії та поняття асимптотичної ефективності. Одним із відповідних показників є так званий ефективний розмір вибірки (ESS).[3]

Функція дисперсійних втрат[ред. | ред. код]

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

Супутнім питанням є той факт, що співвідношення переоцінює економію часу виконання через вибірку за значимістю, оскільки не включає додатковий обчислювальний час, необхідний для підрахування вагової функції. Отже, деякі люди оцінюють чисте покращення часу виконання різними способами. Можливо, більш серйозними витратами на вибірку за значимістю є час, необхідний для розробки та програмування техніки та аналітичного виведення бажаної вагової функції.

Багаторазова та адаптивна вибірка за значимістю[ред. | ред. код]

Коли різні допоміжні розподіли, , спільно використовуються для опису вибірок можна використовувати різні відповідні вагові функції (наприклад, див.[4][5][6][7]). В адаптивному налаштуванні допоміжні розподіли, , та оновлюються на кожній ітерації адаптивного алгоритму вибірки за значимістю. Отже, оскільки використовується сукупність щільностей пропозицій, можна використовувати декілька відповідних комбінацій схем вибірки та зважування.[8][9][10][11][12][13][14]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Kloek, T.; van Dijk, H. K. (1978). Bayesian Estimates of Equation System Parameters: An Application of Integration by Monte Carlo. Econometrica. 46 (1): 1—19. doi:10.2307/1913641.
  2. Rubinstein, R. Y., & Kroese, D. P. (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 978-0-89791-701-8. {{cite book}}: Проігноровано |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 978-0-387-95146-1.
  • Ferrari, M.; Bellini, S. (2001). Importance Sampling simulation of turbo product codes. Т. 9. с. 2773—2777. doi:10.1109/ICC.2001.936655. ISBN 978-0-7803-7097-5. {{cite book}}: Проігноровано |journal= (довідка)
  • Mazonka, Oleg (2016). Easy as Pi: The Importance Sampling Method (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 978-0-521-88068-8.
  • 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.

Посилання[ред. | ред. код]