Монте-Карло важливе семплювання

Проблема рідкісних подій

Припустимо, ви хочете оцінити ймовірність того, що система відмовляється – міст перевищує межу напруження, мережа втрачає більше ніж критичну частку пакетів, портфель втрачає більше ніж екстремальну суму за день. Наївний Монте-Карло робить зразки з природного розподілу та підраховує, скільки разів відбувається рідкісна подія. Якщо істинна ймовірність дорівнює p, потрібно приблизно 1/p зразків, щоб спостерігати подію лише кілька разів, і відножня стандартне похиблення оцінки зменшується лише як 1/sqrt(N·p), де N – кількість зразків. Якщо p становить приблизно одну на мільйон, для отримання надійної оцінки може знадобитися мільярди симуляційних випробувань – часто просто неможливо.

Зміна місця, де ви оглядаєтесь

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

E_f[h(X)] = інтеграл h(x) f(x) dx = інтеграл h(x) * (f(x)/g(x)) * g(x) dx = E_g[ h(X) * w(X) ] де w(x) = f(x) / g(x) Оцінювач: (1/N) * сума_i h(x_i) * w(x_i), x_i ~ g Оскільки g(x) було обрано, щоб зробити подію поширеною, більшість з ваших N зразків тепер фактично потрапляють в неї, і кожен удар правильно зменшується за вагою w(x) < 1 для компенсації надмірної вибірки. Оцінювач є незбавленим для будь-якої g, яка покриває підтримку f·h — єдичний математичний вимог — але його дисперсія значною мірою залежить від того, наскільки добре g обрано.

E_f[h(X)] = integral h(x) f(x) dx
          = integral h(x) * (f(x)/g(x)) * g(x) dx
          = E_g[ h(X) * w(X) ]         where w(x) = f(x) / g(x)

Estimator:  (1/N) * sum_i  h(x_i) * w(x_i),   x_i ~ g

Вибір відповідної пропозиції

Теоретично оптимальна пропозиція — яка зменшує дисперсію оцінки до нуля — це g*(x) ∝ |h(x)|·f(x), що непрактичне, оскільки обчислення її нормального константи вимагає вже знати величину, яку намагаєтесь оцінити. На практиці ви обираєте розумний, обчислюваний наближення: зміщуйте середнє значення Гауссової функції до області відмов, використовуйте експоненційне нахилення на хвості розподілу або використовуйте знання про предметну область щодо того, де схиляється рідкісна подія. Навіть неточна, але розумна пропозиція зазвичай зменшує необхідний обсяг вибірок у кілька порядків величини порівняно з наївним методом Монте-Карло.

Як це може піти не так

Якщо обрано погане g, воно не просто менш корисне, ніж звичайний Monte Carlo – воно може бути навіть гіршим. Якщо g не розподіляє достатньо ймовірності в області, де h(x)·f(x) є значною, будь-який згенерований звідти зразок отримує величезну вагу w(x) = f(x)/g(x), і невелика кількість таких великих ваг може домінувати у всьому оцінюванні, що призводить до різкого збільшення дисперсії – у патологічних випадках навіть до нескінченності. Практичний показник – невелика кількість зразків, які суттєво впливають на загальну вагу – це діагноз, який варто перевіряти кожного разу, коли використовується важливе відбиття для чогось важливого.

Де застосовується

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

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Monte Carlo Importance Sampling і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.