Monte Carlo Integration

Problem rzadkich zdarzeń

Załóżmy, że chcesz oszacować prawdopodobieństwo awarii systemu – mosta przekraczającego próg naprężenia, sieci tracącej więcej niż krytyczny procent pakietów, portfelu tracącego więcej niż ekstremalną kwotę w ciągu dnia. Sposób działania Monte Carlo na drodze naiwnego próbkowania z naturalnej rozkładu i liczenia częstotliwości występowania rzadkiego zdarzenia jest niewystarczający. Jeśli prawdziwe prawdopodobieństwo wynosi p, potrzebujesz rzędu wielkości 1/p próbek, aby obserwować zdarzenie kilka razy, a względny błąd standardowy oszacowania maleje tylko w miarę 1/sqrt(N·p). Dla p około jedne na milion, wiarygodną ocenę może wymagać miliardy symulowanych prób – często po prostu nieosiągalnych.

Przesuń wzrok

Ważne jest próbkowanie reframuje problem. Zamiast pobierać próbki z prawdziwej gęstości f(x) i liczyć, że wystarczająca liczba z nich trafi w rzadką strefę, pobierasz próbki z wybranej, proponowanej gęstości g(x), która celowo umieszcza większą masę tam, gdzie zachodzi interesujące zdarzenie. Następnie korygujesz wkład każdej próbki przez współczynnik prawdopodobieństwa, aby estimator pozostał dokładnie bezstronny dla pierwotnej wielkości, nawet jeśli nigdy nie pobierałeś próbek z oryginalnego rozkładu:

E_f[h(X)] = całka h(x) f(x) dx = całka h(x) * (f(x)/g(x)) * g(x) dx = E_g[ h(X) * w(X) ] gdzie w(x) = f(x) / g(x) Estymator: (1/N) * suma_i h(x_i) * w(x_i), x_i ~ g Ponieważ g(x) została dobrana, aby uczynić zdarzenie powszechne, większość z N próbek teraz faktycznie na niego trafiła, a każdy trafiony został prawidłowo obniżony przez w(x) < 1, aby skompensować nadpróbkowanie. Estymator jest bezstronny dla dowolnej g, którego zakres obejmuje zakres f·h — jedyne wymaganie matematyczne — ale jego wariancja zależy ogromnie od tego, jak dobrze została dobrana 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

Wybór propozycji dobrze

Teoretycznie optymalna propozycja – ta, która redukuje wariancję oszacowania do zera – to g*(x) ∝ |h(x)|·f(x), co jest nieużyteczne w praktyce, ponieważ obliczanie jej stałej normalizującej wymaga już znajomości ilości, którą chcemy oszacować. W praktyce decydujemy się na rozsądne, możliwe do obliczenia przybliżenie: przesuwamy średnią rozkładu Gaussa w stronę obszaru niepowodzeń, używamy nachylenia wykładniczego na ogonie rozkładu lub wykorzystujemy wiedzę domenową o tym, gdzie rzadkie zdarzenie ma tendencję do występowania. Nawet niedoskonała, ale sensowna propozycja zazwyczaj zmniejsza wymagane przybliżenie o kilka rzędów wielkości w porównaniu z naiwnym Monte Carlo.

Jak to się zwraca

Niewłaściwie dobrany g nie jest jedynie mniej pomocny niż Monte Carlo z natychału – może być wręcz gorszy. Jeśli g umieszcza zbyt mały rozkład prawdopodobieństwa w obszarze, gdzie h(x)·f(x) jest niebagatelny, każdy próbny punkt, który tam trafi, otrzymuje ogromną wagę w(x) = f(x)/g(x), a niewielka liczba dużych wag może zdominować cały szacunek, dramatycznie inflując jego wariancję – w patologicznych przypadkach nawet do nieskończoności. Praktycznym sygnałem ostrzegawczym jest mała liczba próbek, która przyczynia się niezgodnie z proporcjami do całkowitej wagi – to diagnostyka, którą warto sprawdzić za każdym razem, gdy stosuje się ważenie oparte na znaczeniu dla czegoś, co ma znaczenie.

Gdzie jest używane

Metoda Monte Carlo opiera się na ważeniu, które leży u podstaw oszacowania rzadkich zdarzeń w inżynierii niezawodności strukturalnej, szacowaniu ryzyka ogórkowego w finansach ilościowych (wartość bez ryzyka, oczekiwane niedociągnięcie) oraz generatorów zdarzeń w fizyce cząstek i algorytmów renderingu grafiki komputerowej, gdzie rzeczywiste ścieżki światła docierające do aparatu są rzadkie wśród wszystkich możliwych ścieżek, które foton mógłby pokonać. W każdym przypadku idea jest identyczna: próbuj w miejscach, gdzie znajduje się odpowiedź, a koszty skrótu pokrywa się z wagą korekcyjną.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Monte Carlo Importance Sampling i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.