Przejdź do treści
Wróć do wyników wyszukiwania

Techniki redukcji wariancji w symulacjach Monte Carlo

Autor metody
Hammersley & Morton (antithetic variates, 1956); Lavenberg & Welch (control variates, 1981); importance sampling roots in Kahn & Marshall (1953)
Rok
1950s–1980s (technique family)
Typ
Simulation variance-reduction technique family

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Techniki redukcji wariancji to rodzina metod poprawiających efektywność symulacji Monte Carlo poprzez osiągnięcie tej samej dokładności estymacji przy mniejszej liczbie losowań.

Rozwijane stopniowo od lat 50. XX wieku — z przypisywanymi Hammersleyowi i Mortonowi zmiennymi antytetycznymi, sformalizowanymi przez Lavenberga i Welcha zmiennymi kontrolnymi oraz próbkowaniem ważonym (importance sampling) zakorzenionym w pracach Kahna i Marshalla — rodzina ta obejmuje zmienne antytetyczne (AV), zmienne kontrolne (CV), próbkowanie ważone (IS) oraz stratyfikację, z których każda wykorzystuje inną właściwość strukturalną wielkości docelowej w celu obniżenia wariancji estymatora bez wprowadzania obciążenia.

Intuicja stojąca za metodą

Standardowa metoda Monte Carlo działa poprzez uśrednianie dużej liczby niezależnych losowań. Jej słabością jest to, że czysto losowe losowania mogą być redundantne — wiele losowań trafia w obszary, które wnoszą niewiele informacji, a błędy dodatnie i ujemne nie znoszą się efektywnie. Techniki redukcji wariancji naprawiają to, inżynierując losowość. Zmienne antytetyczne parują każde losowanie z jego lustrzanym odbiciem, tak aby błędy miały tendencję do znoszenia się; zmienne kontrolne korygują estymatę za pomocą skorelowanej wielkości, której prawdziwa średnia jest znana; próbkowanie ważone koncentruje losowania tam, gdzie są one najbardziej istotne; a stratyfikacja zapewnia równomierne pokrycie przestrzeni wejściowej przez próbkowanie. Korzyścią jest ta sama dokładność przy znacznie mniejszej liczbie ewaluacji funkcji.

Historia

Podstawy redukcji wariancji dla symulacji Monte Carlo zostały położone w latach 50. XX wieku. Kahn i Marshall (1953) wprowadzili próbkowanie ważone w kontekście transportu cząstek jądrowych. Hammersley i Morton (1956) sformalizowali zmienne antytetyczne jako sposób na wykorzystanie symetrii w losowych danych wejściowych. Zmienne kontrolne zostały usystematyzowane przez Lavenberga i Welcha w latach 80. XX wieku do zastosowań w symulacjach stochastycznych. Monografia Paula Glassermana z 2003 roku ujednoliciła teorię i praktykę tych technik dla inżynierii finansowej, a podręcznik Sheldona Rossa na temat symulacji uczynił je od tego czasu standardową częścią edukacji podyplomowej w zakresie symulacji. Dziś techniki te są kluczowe w finansach obliczeniowych, inżynierii niezawodności i każdej dziedzinie, gdzie uruchomienia symulacji są kosztowne.

Kiedy stosować

Stosuj techniki redukcji wariancji, gdy standardowa metoda Monte Carlo zapewnia akceptowalną dokładność tylko przy niepraktycznie dużej liczbie uruchomień. AV pasuje do gładkich, monotonicznych funkcji podcałkowych; CV pasuje do problemów, w których dostępna jest skorelowana wielkość pomocnicza o znanej średniej; IS pasuje do estymacji rzadkich zdarzeń lub całkowania po grubych ogonach; stratyfikacja pasuje do przestrzeni wejściowych o niskiej wymiarowości. Wszystkie techniki wymagają co najmniej kilkuset — idealnie kilku tysięcy — iteracji, zanim korzyść z redukcji wariancji stanie się widoczna. Są one odpowiednie dla ciągłych zmiennych losowych i dla każdej dziedziny zastosowań, gdzie koszt symulacji jest wiążącym ograniczeniem.

Ograniczenia i uwagi

  • Każda technika wymaga znajomości struktury problemu: AV potrzebuje monotonicznej funkcji podcałkowej, CV potrzebuje analitycznie znanej średniej pomocniczej, IS potrzebuje dobrze zaprojektowanego rozkładu proponującego.
  • Źle dobrany rozkład proponujący dla próbkowania ważonego może zwiększyć wariancję zamiast ją zmniejszyć.
  • Łączenie wielu technik zwiększa złożoność implementacji i może prowadzić do nieoczekiwanych interakcji.
  • Korzyść z redukcji wariancji jest znikoma przy bardzo małej liczbie iteracji (poniżej ~1000 uruchomień).

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Znacząco zmniejsza liczbę uruchomień symulacji potrzebnych do osiągnięcia docelowej dokładności, obniżając koszty obliczeniowe.
  • Techniki można łączyć (np. AV z CV) dla skumulowanej redukcji wariancji.
  • Nie wprowadza się obciążenia: wszystkie standardowe techniki generują estymatory nieobciążone.
  • Szeroko stosowane w różnych dziedzinach — finansach, inżynierii, opiece zdrowotnej, badaniach operacyjnych — wszędzie tam, gdzie stosuje się całkowanie Monte Carlo.

Zastosowania

  • Wycena opcji w finansach obliczeniowych, gdzie próbkowanie ważone koncentruje losowania na ścieżkach "in-the-money".
  • Analiza niezawodności i ryzyka, gdzie prawdopodobieństwa rzadkich awarii są estymowane przy znacznie mniejszej liczbie uruchomień symulacji za pomocą IS.
  • Analiza wydajności systemów kolejkowych i usługowych za pomocą AV i CV w celu skrócenia czasu uruchomienia.
  • Symulacja efektywności kosztowej w opiece zdrowotnej, gdzie CV wykorzystuje znane analityczne przybliżenie modelu kosztów.
  • Projektowanie inżynierskie w warunkach niepewności, gdzie próbkowanie stratyfikowane zapewnia pokrycie przestrzeni parametrów wejściowych.

Jak to działa

Jak to działa

1

Zacznij od wyrażenia interesującej wielkości jako wartości oczekiwanej — na przykład średniej funkcji zastosowanej do losowych danych wejściowych. Takie ujęcie jasno określa, z jakiego rozkładu prawdopodobieństwa pochodzą próbki i jak wygląda surowy estymator Monte Carlo przed zastosowaniem jakiejkolwiek redukcji wariancji.

2

Wybierz technikę, która odpowiada strukturze problemu. Zmienne antytetyczne działają, gdy funkcja podcałkowa jest monotoniczna względem danych wejściowych, więc sparowanie każdego losowania jednostajnego u z jego dopełnieniem 1 − u gwarantuje ujemną korelację i znoszenie się błędów. Zmienne kontrolne działają, gdy istnieje skorelowana wielkość o znanej analitycznie wartości oczekiwanej; estymator jest korygowany o różnicę między symulowaną średnią zmiennej kontrolnej a jej znaną średnią. Próbkowanie ważone działa, gdy trzeba zwiększyć prawdopodobieństwo rzadkich lub wysoko ważonych zdarzeń; rozkład proponujący (proposal distribution) z grubszymi ogonami zastępuje rozkład oryginalny, a każda próbka jest ponownie ważona ilorazem wiarygodności. Stratyfikacja dzieli przestrzeń wejściową na warstwy (strata) i alokuje losowania proporcjonalnie, zapewniając, że żaden region nie jest nadmiernie lub niedostatecznie próbkowany. Techniki można łączyć — na przykład CV i AV razem — dla dodatkowych oszczędności.

3

Pobierz próbki zgodnie z wybraną techniką. Dla AV generuj sparowane losowania (u, 1 − u); dla IS losuj z rozkładu proponującego i rejestruj wagi ważności; dla stratyfikacji losuj w obrębie każdej warstwy. Liczba iteracji powinna wynosić co najmniej tysiące, aby korzyści z redukcji wariancji były mierzalne.

4

Agreguj próbki w estymatę punktową i estymatę wariancji. Dla AV estymatorem jest średnia sparowanych wartości funkcji. Dla CV surowa średnia jest korygowana przez optymalny współczynnik pomnożony przez odchylenie średniej próbki zmiennej kontrolnej od jej znanej wartości oczekiwanej. Dla IS każda ewaluacja funkcji jest mnożona przez jej wagę ważności przed uśrednieniem.

5

Porównaj wariancję estymatora zredukowanego wariancyjnie z wariancją prostego estymatora Monte Carlo dla tej samej liczby losowań. Stosunek tych dwóch wariancji — współczynnik redukcji wariancji — kwantyfikuje zysk. Jeśli współczynnik jest bliski 1, technika nie wykorzystuje struktury problemu i może być potrzebne inne podejście lub więcej iteracji.

Częste pułapki

  • Użycie zmiennych antytetycznych, gdy funkcja podcałkowa nie jest monotoniczna względem danych wejściowych: założenie o ujemnej korelacji załamuje się, a metoda może faktycznie zwiększyć wariancję.
  • Użycie rozkładu proponującego w próbkowaniu ważonym, który ma lżejsze ogony niż rozkład docelowy: rzadkie zdarzenia są niedostatecznie próbkowane, a wariancja estymatora może eksplodować.
  • Estymowanie współczynnika CV z tej samej próbki użytej do estymatora bez uwzględnienia indukowanego obciążenia przy małych rozmiarach próby.
  • Przeprowadzanie zbyt małej liczby iteracji (poniżej ~1000): współczynnik redukcji wariancji nie może być wiarygodnie zmierzony, a korzyść w porównaniu z prostą metodą Monte Carlo jest niewidoczna.
  • Łączenie AV i CV bez weryfikacji, czy kombinacja utrzymuje ujemną korelację: wspólny estymator może nie osiągnąć oczekiwanych oszczędności.

Najczęściej zadawane pytania

Którą technikę powinienem wybrać — AV, CV, IS czy stratyfikację?

Wybierz na podstawie struktury problemu. Jeśli funkcja podcałkowa jest monotoniczna względem danych wejściowych, AV jest proste i skuteczne. Jeśli masz powiązaną wielkość, której wartość oczekiwaną możesz obliczyć analitycznie, CV jest zazwyczaj najpotężniejszą opcją. Jeśli musisz oszacować prawdopodobieństwo rzadkiego zdarzenia lub scałkować po grubych ogonach, IS jest właściwym narzędziem. Stratyfikacja działa dobrze w niskich do umiarkowanych wymiarach, gdy chcesz równomiernego pokrycia przestrzeni wejściowej. Techniki można również łączyć dla dodatkowych korzyści.

Ile uruchomień symulacji potrzebuję?

Korzyść z redukcji wariancji staje się mierzalna dopiero po wykonaniu co najmniej kilkuset uruchomień; kilka tysięcy to bardziej wiarygodny próg. Przy bardzo małej liczbie iteracji współczynnik redukcji wariancji nie może być stabilnie oszacowany, a prosty estymator Monte Carlo może faktycznie działać porównywalnie. Praktyczna zasada to nie używać tych technik z mniej niż 1000 iteracji.

Czy techniki redukcji wariancji mogą wprowadzać obciążenie?

Nie — wszystkie cztery standardowe techniki (AV, CV, IS, stratyfikacja) generują nieobciążone estymatory, jeśli są poprawnie zaimplementowane. Estymator CV wymaga dokładnego oszacowania optymalnego współczynnika; oszacowanie go z małej próbki pilotażowej i ponowne wykorzystanie tej samej próbki do głównego oszacowania może wprowadzić niewielkie obciążenie dla małych rozmiarów próby, dlatego najlepszą praktyką jest użycie oddzielnej próbki pilotażowej lub asymptotycznie poprawnej formuły współczynnika.

Co się stanie, jeśli mój rozkład proponujący w próbkowaniu ważonym zostanie źle dobrany?

Rozkład proponujący, który ma zbyt lekkie ogony w stosunku do rozkładu docelowego, może spowodować katastrofalny wzrost wariancji, czyniąc IS gorszym niż prosta metoda Monte Carlo. Zawsze weryfikuj, czy rozkład proponujący ma grubsze ogony niż rozkład docelowy w odpowiednim regionie, i sprawdzaj wariancję wag ważności jako diagnostykę — ekstremalnie duże wartości wag sygnalizują słaby rozkład proponujący.

Pokrewne metody

Źródła

  1. Ross, S.M. (2012). Simulation (5th ed.). Academic Press.

    ISBN: 978-0124158252
    Skopiowano.
  2. Glasserman, P. (2003). Monte Carlo Methods in Financial Engineering. Springer.

    Otwórz odnośnik DOI
    Skopiowano.