Pobieranie próbek o znaczeniu - Importance sampling

W statystykach , próbkowanie znaczenie ma ogólna technika właściwości konkretnego szacowania rozkładu , podczas gdy tylko mając próbek generowanych z innej dystrybucji niż dystrybucji zainteresowania. Metoda została po raz pierwszy wprowadzona przez Teuna Kloeka i Hermana K. van Dijka w 1978 roku i jest związana z próbkowaniem parasolowym w fizyce obliczeniowej . W zależności od zastosowania termin ten może odnosić się do procesu pobierania próbek z tego alternatywnego rozkładu, procesu wnioskowania lub obu.

Podstawowa teoria

Niech będzie zmienną losową w pewnej przestrzeni prawdopodobieństwa . Chcemy oszacowania wartości oczekiwanej z X mocy P , oznaczoną E [ X P ]. Jeśli mamy statystycznie niezależne próby losowe , wygenerowane zgodnie z P , to empiryczne oszacowanie E [ X;P ] jest ${\ Displaystyle X: \ Omega \ do \ mathbb {R}}$ ${\ Displaystyle (\ Omega, {\ mathcal {F}}, P)}$${\displaystyle x_{1},\ldots,x_{n}}$

${\ Displaystyle {\ widehat {\ mathbf {e}}} _ {n} [X; P] = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} x_ {i} }$

a dokładność tego oszacowania zależy od wariancji X :

${\displaystyle \operatorname {var} [{\widehat {\mathbf {e}}}_{n};P]={\frac {\operatorname {var} [X;P]}{n}}.}$

Podstawową ideą próbkowania ważności jest próbkowanie stanów z innego rozkładu w celu obniżenia wariancji estymacji E [ X; P ] lub gdy próbkowanie z P jest trudne. Osiąga się to wybierając najpierw zmienną losową taką, że E [ L ; P ] = 1 i że P - prawie wszędzie . Za pomocą zmiennej L definiujemy prawdopodobieństwo, które spełnia ${\displaystyle L\geq 0}$ ${\ Displaystyle L (\ omega ) \ neq 0}$${\ Displaystyle P ^ {(L)}}$

${\ Displaystyle \ mathbf {E} [X; P] = \ mathbf {E} \ lewo [{\ Frac {X} {L}}; P ^ {(L)} \ prawej].}$

Zmienna X / L będzie zatem próbkowana w ramach P ^{( L ) w} celu oszacowania E [ X;P ] jak powyżej, a ta ocena ulega poprawie, gdy . ${\displaystyle \operatorname {var} \left [{\frac {X}{L}};P^{(L)}\right]<\operatorname {var} [X;P]}$

Gdy X ma znak stałej nad Ω, najlepszą zmienną L byłoby oczywiście , więc X / L * jest poszukiwaną stałą E [ X; P ] i pojedyncza próbka pod P ^{( L *)} wystarczy do podania jej wartości. Niestety nie możemy dokonać takiego wyboru, ponieważ E [ X;P ] jest dokładnie tą wartością, której szukamy! Jednak ten teoretyczny najlepszy przypadek L* daje nam wgląd w znaczenie próbkowania: ${\ Displaystyle L ^ {*} = {\ Frac {X} {\ mathbf {E} [X; P]}} \ geq 0}$

${\ Displaystyle {\ zacząć {wyrównany} \ dla wszystkich a \ w \ mathbb {R} \; P ^ {(L ^ {*})} (X \ w [a; a + da]) = \ int _ {\omega \in \{X\in [a;a+da]\}}{\frac {X(\omega )}{E[X;P]}}\,dP(\omega )\\[6pt ]&={\frac {1}{E[X;P]}}\;a\,P(X\in [a;a+da])\end{wyrównany}}}$

po prawej stronie znajduje się jeden z nieskończenie małych elementów, które sumują się do E [ X ; P ]: ${\displaystyle a\,p(X\in [a;a+da])}$

${\ Displaystyle E [X; P] = \ int _ {a = - \ infty} ^ {+ \ infty} a \, P (X \ w [a; a + da])}$

dlatego dobra zmiana prawdopodobieństwa P ^{( L )} w próbkowaniu ważności spowoduje redystrybucję prawa X tak, że częstotliwości jego próbek są sortowane bezpośrednio zgodnie z ich wagami w E [ X ; P ]. Stąd nazwa „próbkowanie ważności”.

Próbkowanie ważności jest często używane jako integrator Monte Carlo . Kiedy jest rozkładem jednostajnym i , E [ X;P ] odpowiada całce funkcji rzeczywistej . ${\displaystyle P}$${\ Displaystyle \ Omega = \ mathbb {R}}$${\ Displaystyle X: \ mathbb {R} \ do \ mathbb {R}}$

Zastosowanie do wnioskowania probabilistycznego

Takie metody są często używane do szacowania gęstości a posteriori lub oczekiwań w problemach estymacji stanu i/lub parametrów w modelach probabilistycznych, które są zbyt trudne do analizy analitycznej, na przykład w sieciach bayesowskich .

Aplikacja do symulacji

Próbkowanie ważności jest techniką redukcji wariancji , którą można stosować w metodzie Monte Carlo . Ideą próbkowania ważności jest to, że pewne wartości wejściowych zmiennych losowych w symulacji mają większy wpływ na szacowany parametr niż inne. Jeśli te „ważne” wartości są podkreślane przez próbkowanie częściej, to wariancję estymatora można zmniejszyć. Stąd podstawową metodologią w próbkowaniu istotności jest wybór rozkładu, który „zachęca” do ważnych wartości. Takie użycie „obciążonych” rozkładów spowoduje powstanie tendencyjnego estymatora, jeśli zostanie on zastosowany bezpośrednio w symulacji. Jednak wyniki symulacji są ważone w celu skorygowania użycia rozkładu obciążonego, co zapewnia, że ​​estymator próbkowania o nowym znaczeniu jest nieobciążony. Wagę podaje iloraz wiarygodności , czyli pochodna Radona–Nikodyma rzeczywistego rozkładu bazowego względem rozkładu obciążonej symulacji.

Podstawową kwestią we wdrażaniu symulacji próbkowania ważności jest wybór rozkładu obciążonego, który zachęca do ważnych obszarów zmiennych wejściowych. Wybór lub zaprojektowanie dobrej dystrybucji z obciążeniem jest „sztuką” próbkowania ważności. Nagrodą za dobrą dystrybucję mogą być ogromne oszczędności czasu pracy; karą za złą dystrybucję może być dłuższy czas działania niż w przypadku ogólnej symulacji Monte Carlo bez próbkowania ważności.

Rozważmy jako próbkę i jako iloraz wiarygodności, gdzie jest funkcją gęstości prawdopodobieństwa (masy) pożądanego rozkładu i jest funkcją gęstości prawdopodobieństwa (masy) rozkładu obciążonego/propozycji/próbki. Następnie problem można scharakteryzować wybierając taki rozkład próby, który minimalizuje wariancję przeskalowanej próbki: ${\ Displaystyle X}$${\ Displaystyle {\ Frac {f (X)} {g (X)}}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle g}$

${\ Displaystyle g ^ {*} = \ min _ {g} \ operatorname {var} _ {g} \ lewo (X {\ Frac {f (X)} {g (X)}} \ prawej).}$

Można wykazać, że poniższy rozkład minimalizuje powyższą wariancję:

${\ Displaystyle g ^ {*} (X) = {\ Frac {| X | f (X)} {\ int | x | f (x) \ dx}}.}$

Zauważ, że kiedy , ta wariancja staje się 0. ${\ Displaystyle X \ geq 0}$

Podejście matematyczne

Rozważ oszacowanie przez symulację prawdopodobieństwa zdarzenia , gdzie jest zmienną losową z rozkładem i funkcją gęstości prawdopodobieństwa , gdzie liczba pierwsza oznacza pochodną . -Długość niezależne i jednakowo rozmieszczone (IID) sekwencji są generowane z rozkładu , a liczba zmiennych losowych, które znajdują się powyżej progu są zliczane. Zmienna losowa charakteryzuje się rozkładem dwumianowym${\displaystyle p_{t}\,}$${\displaystyle X\geq t}$${\ Displaystyle X}$ ${\ Displaystyle F}$ ${\displaystyle f(x)=f'(x)\,}$${\ Displaystyle K}$${\displaystyle X_{i}\,}$${\ Displaystyle F}$${\displaystyle k_{t}}$${\displaystyle t}$${\displaystyle k_{t}}$

${\ Displaystyle P (k_ {t} = k) = {K \ wybierz k} p_ {t} ^ {k} (1-p_ {t}) ^ {Kk} \, \ quad \ quad k = 0, 1,\kropki ,K.}$

Można to wykazać , a więc w limicie, jaki jesteśmy w stanie uzyskać . Zauważ, że wariancja jest niska, jeśli . Ważność próbkowania dotyczy określenia i wykorzystania w eksperymencie symulacyjnym alternatywnej funkcji gęstości (for ), zwykle nazywanej gęstością odchylenia. Ta gęstość umożliwia częstsze występowanie zdarzenia , więc długość sekwencji zmniejsza się dla danej wariancji estymatora . Alternatywnie, dla danego , użycie gęstości polaryzacji daje wariancję mniejszą niż w przypadku konwencjonalnego oszacowania Monte Carlo. Z definicji możemy wprowadzić jak poniżej. ${\ Displaystyle \ Operatorname {E} [k_ {t} / K] = p_ {t}}$${\ Displaystyle \ operatorname {var} [k_ {t} / K] = p_ {t} (1-p_ {t}) / K}$${\ Displaystyle K \ do \ infty}$${\displaystyle p_{t}}$${\displaystyle p_{t}\ok 1}$${\displaystyle f_{*}\,}$${\ Displaystyle X}$${\displaystyle {X\geq t\}}$${\ Displaystyle K}$${\ Displaystyle K}$${\displaystyle p_{t}\,}$${\displaystyle f_{*}\,}$

${\ Displaystyle {\ zacząć {wyrównany} p_ {t} i = {E} [1 (X \ geq t)] \ \ [6 pkt] i = \ int 1 (x \ geq t) {\ Frac {f (x )}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{aligned }}}$

gdzie

${\ Displaystyle W (\ cdot ) \ równoważnik {\ Frac {f (\ cdot )} {f_ {*} (\ cdot)}}}$

jest współczynnikiem prawdopodobieństwa i jest określany jako funkcja wagowa. Ostatnia równość w powyższym równaniu motywuje estymatora

${\ Displaystyle {\ kapelusz {p}} _ {t} = {\ Frac {1} {K}} \ \ suma _ {i = 1} ^ {K} 1 (X_ {i} \ geq t) W (X_{i}),\,\quad \quad X_{i}\sim f_{*}}$

Jest to estymator ważności próbkowania i jest bezstronny. Oznacza to, że procedura oszacowania polega na wygenerowaniu próbek iid z i dla każdej próbki, która przekracza , oszacowanie jest zwiększane o wagę oszacowaną przy wartości próbki. Wyniki są uśredniane z prób. Łatwo wykazać, że wariancja estymatora ważności próbkowania jest ${\displaystyle p_{t}\,}$${\displaystyle f_{*}\,}$${\displaystyle t\,}$${\displaystyle W\,}$${\displaystyle K\,}$

${\ Displaystyle {\ zacząć {wyrównany} \ nazwa operatora {zmienna} _ {*} {\ widehat {p}} _ {t} i = {\ Frac {1} {K}} \ nazwa operatora {zmienna} _ {*} [1(X\geq t)W(X)]\\[5pt]&={\frac {1}{K}}\left\{{E_{*}}[1(X\geq t)^{ 2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{{E}[1 (X\geq t)W(X)]-p_{t}^{2}\right\}\end{aligned}}}$

Teraz problem próbkowania ważności skupia się na znalezieniu gęstości odchylenia, takiej, że wariancja estymatora próbkowania ważności jest mniejsza niż wariancja ogólnego oszacowania Monte Carlo. Dla pewnej funkcji gęstości polaryzacji, która minimalizuje wariancję, aw pewnych warunkach redukuje ją do zera, nazywa się ją optymalną funkcją gęstości polaryzacji. ${\displaystyle f_{*}\,}$

Konwencjonalne metody polaryzacji

Chociaż istnieje wiele rodzajów metod tendencyjności, w zastosowaniach próbkowania ważności najczęściej stosuje się następujące dwie metody.

skalowanie

Przesunięcie masy prawdopodobieństwa w obszar zdarzenia przez dodatnie skalowanie zmiennej losowej o liczbie większej od jedności skutkuje zwiększeniem wariancji (również średniej) funkcji gęstości. Skutkuje to cięższym ogonem gęstości, co prowadzi do wzrostu prawdopodobieństwa zdarzenia. Skalowanie jest prawdopodobnie jedną z najwcześniejszych znanych metod tendencyjności i jest szeroko stosowane w praktyce. Jest prosty w implementacji i zwykle zapewnia konserwatywne korzyści z symulacji w porównaniu z innymi metodami. ${\displaystyle {X\geq t\}}$${\displaystyle X\,}$

W przypadku próbkowania ważności przez skalowanie, gęstość symulacji jest wybierana jako funkcja gęstości skalowanej zmiennej losowej , gdzie zwykle do estymacji prawdopodobieństwa ogona. Przez transformację ${\displaystyle aX\,}$${\displaystyle a>1}$

${\ Displaystyle f_ {*} (x) = {\ Frac {1} {a}} f {\ bigg (}{\ Frac {x} {a}} {\ bigg)} \,}$

a funkcja ważenia to

${\ Displaystyle W (x) = a {\ Frac {f (x)} {f (x/a)}} \,}$

Podczas gdy skalowanie przesuwa masę prawdopodobieństwa do pożądanego obszaru zdarzenia, wypycha również masę do obszaru komplementarnego, co jest niepożądane. Jeżeli jest sumą zmiennych losowych, to rozprzestrzenianie się masy odbywa się w przestrzeni wymiarowej. Konsekwencją tego jest malejące znaczenie przyrostu próbkowania przy zwiększaniu i nazywa się to efektem wymiarowości. Nowoczesną wersją próbkowania ważności przez skalowanie jest np. tak zwane próbkowanie w skali sigma (SSS), które polega na przeprowadzaniu wielokrotnej analizy Monte Carlo (MC) z różnymi współczynnikami skalowania. W przeciwieństwie do wielu innych metod szacowania o wysokiej wydajności (takich jak najgorsze odległości WCD) SSS nie cierpi zbytnio z powodu problemu wymiarowości. Również adresowanie wielu wyjść MC nie powoduje pogorszenia wydajności. Z drugiej strony, podobnie jak WCD, SSS jest przeznaczony tylko dla zmiennych statystycznych Gaussa, aw przeciwieństwie do WCD, metoda SSS nie jest przeznaczona do zapewniania dokładnych narożników statystycznych. Inną wadą SSS jest to, że przebiegi MC z dużymi współczynnikami skali mogą stać się trudne, np. z powodu problemów ze zbieżnością modelu i symulatora. Ponadto w SSS mamy do czynienia z silnym kompromisem między odchyleniami a wariancją: stosując czynniki o dużej skali, uzyskujemy dość stabilne wyniki wydajności, ale im większe współczynniki skali, tym większy błąd odchylenia. Jeśli zalety SSS nie mają większego znaczenia w zastosowaniu zainteresowania, często inne metody są bardziej efektywne. ${\displaystyle X<t\,}$${\displaystyle X\,}$${\displaystyle n\,}$${\displaystyle n\,}$${\displaystyle n\,}$

Tłumaczenie

Inna prosta i skuteczna technika polaryzacji wykorzystuje translację funkcji gęstości (a tym samym zmiennej losowej), aby umieścić większość jej masy prawdopodobieństwa w obszarze rzadkich zdarzeń. Tłumaczenie nie wykazuje efektu wymiarowości i jest z powodzeniem wykorzystywane w kilku zastosowaniach związanych z symulacją cyfrowych systemów komunikacyjnych . Często zapewnia lepsze korzyści z symulacji niż skalowanie. W przypadku odchylenia przez translację gęstość symulacji jest dana wzorem

${\ Displaystyle f_ {*} (x) = f (xc), \ quad c> 0 \,}$

gdzie jest wielkością przesunięcia i należy go wybrać, aby zminimalizować wariancję estymatora ważności próbkowania. ${\displaystyle c\,}$

Skutki złożoności systemu

Podstawowym problemem związanym z próbkowaniem ważności jest to, że projektowanie dobrych rozkładów z obciążeniem staje się bardziej skomplikowane wraz ze wzrostem złożoności systemu. Złożone systemy to systemy z dużą ilością pamięci, ponieważ złożone przetwarzanie kilku danych wejściowych jest znacznie łatwiejsze w obsłudze. Ta wymiarowość lub pamięć może powodować problemy na trzy sposoby:

• długa pamięć (poważne zakłócenia międzysymbolowe (ISI))
• nieznana pamięć ( dekodery Viterbi )
• ewentualnie nieskończona pamięć (korektory adaptacyjne)

Zasadniczo idee dotyczące pobierania próbek pozostają takie same w takich sytuacjach, ale projekt staje się znacznie trudniejszy. Skuteczne podejście do rozwiązania tego problemu polega zasadniczo na rozbiciu symulacji na kilka mniejszych, bardziej precyzyjnie określonych podproblemów. Następnie stosuje się strategie próbkowania ważności w celu rozwiązania każdego z prostszych podproblemów. Przykładami technik umożliwiających rozbicie symulacji są symulacja warunkowania i zdarzeń błędów (EES) oraz symulacja regeneracyjna.

Ocena ważności próbkowania

W celu zidentyfikowania skutecznych technik próbkowania według ważności, przydatna jest możliwość ilościowego określenia oszczędności czasu wykonywania dzięki zastosowaniu podejścia próbkowania według ważności. Powszechnie stosowaną miarą wydajności jest , i można ją interpretować jako współczynnik przyspieszenia, dzięki któremu estymator próbkowania ważności osiąga taką samą precyzję jak estymator MC. Należy to obliczyć empirycznie, ponieważ wariancje estymatorów prawdopodobnie nie będą możliwe analitycznie, gdy ich średnia jest niewykonalna. Inne przydatne pojęcia w kwantyfikacji estymatora próbkowania ważności to granice wariancji i pojęcie wydajności asymptotycznej. Jedną z powiązanych miar jest tak zwana efektywna wielkość próbki (ESS) . ${\ Displaystyle \ Sigma _ {MC} ^ {2} / \ Sigma _ {IS} ^ {2} \,}$

Funkcja kosztu wariancji

Wariancja nie jest jedyną możliwą funkcją kosztu dla symulacji, a inne funkcje kosztów, takie jak średnie odchylenie bezwzględne, są używane w różnych zastosowaniach statystycznych. Niemniej jednak wariancja jest główną funkcją kosztu omawianą w literaturze, prawdopodobnie ze względu na zastosowanie wariancji w przedziałach ufności oraz w miarach wydajności . ${\ Displaystyle \ Sigma _ {MC} ^ {2} / \ Sigma _ {IS} ^ {2} \,}$

Powiązanym problemem jest fakt, że współczynnik przeszacowuje oszczędności czasu pracy wynikające z próbkowania ważności, ponieważ nie uwzględnia dodatkowego czasu obliczeniowego wymaganego do obliczenia funkcji wagi. Dlatego niektórzy ludzie oceniają poprawę czasu pracy netto na różne sposoby. Być może poważniejszym obciążeniem ogólnym dla próbkowania ważności jest czas poświęcony na opracowanie i zaprogramowanie techniki oraz analityczne określenie pożądanej funkcji wagi. ${\ Displaystyle \ Sigma _ {MC} ^ {2} / \ Sigma _ {IS} ^ {2} \,}$

Wielokrotne i adaptacyjne próbkowanie ważności

Gdy różne rozkłady propozycji, , są wspólnie wykorzystywane do rysowania próbek, można zastosować różne właściwe funkcje wagowe (np. patrz ). W adaptacyjnego ustawieniu rozkłady propozycja , i są aktualizowane każdej iteracji algorytmu próbkowania znaczenie adaptacyjne. W związku z tym, ponieważ wykorzystywana jest populacja gęstości propozycji, można zastosować kilka odpowiednich kombinacji schematów próbkowania i ważenia. ${\ Displaystyle g_ {n} (x)}$${\displaystyle n=1,\ldots,n,}$${\displaystyle x_{1},\ldots,x_{N}}$${\ Displaystyle g_ {n, t} (x)}$${\displaystyle n=1,\ldots,n,}$${\displaystyle t=1,\ldots,t,}$${\displaystyle t}$

Zobacz też

• Metoda Monte Carlo
• Redukcja wariancji
• Próbkowanie warstwowe
• Rekurencyjne próbkowanie warstwowe
• Algorytm VEGAS
• Filtr cząstek — sekwencyjna metoda Monte Carlo, która wykorzystuje próbkowanie ważności
• Pole pomocnicze Monte Carlo
• Próbkowanie odrzucenia
• Zmienna szybkość transmisji — powszechna aplikacja audio o znaczeniu próbkowania

Uwagi

Bibliografia

• Arouna, Bouhari (2004). „Adaptacyjna metoda Monte Carlo, technika redukcji wariancji”. Metody Monte Carlo i ich zastosowania . 10 (1): 1–24. doi : 10.1515/1556939604323091180 .
• Bucklew, James Antonio (2004). Wprowadzenie do symulacji zdarzeń rzadkich . Nowy Jork: Springer-Verlag.
• Doucet, A.; de Freitas, N.; Gordon, N. (2001). Sekwencyjne metody Monte Carlo w praktyce . Skoczek. Numer ISBN 978-0-387-95146-1.
• Ferrari, M.; Bellini, S. (2001). Znaczenie Symulacja próbkowania kodów produktów turbo . Międzynarodowa Konferencja nt . Komunikacji IEEE . 9 . s. 2773–2777. doi : 10.1109/ICC.2001.936655 . Numer ISBN 978-0-7803-7097-5.
• Mazonka, Oleg (2016). „Łatwy jak Pi: metoda próbkowania ważności” (PDF) . Dziennik referencyjny . 16 .
• Oberg, Tommy (2001). Modulacja, detekcja i kodowanie . Nowy Jork: John Wiley i synowie.
• Prasa, WH; Teukolski SA; Vetterling, WT; Flannery, BP (2007). "Rozdział 7.9.1 Ważność próbkowania" . Przepisy numeryczne: The Art of Scientific Computing (3rd ed.). Nowy Jork: Cambridge University Press. Numer ISBN 978-0-521-88068-8.
• Ripley, BD (1987). Symulacja stochastyczna . Wiley i Synowie.
• Smith, PJ; Shafi, M.; Gao, H. (1997). „Szybka symulacja: przegląd technik pobierania próbek znaczenie w systemach komunikacyjnych”. IEEE Journal on Selected Areas in Communications . 15 (4): 597–613. doi : 10.1109/49.585771 .
• Srinivasan, R. (2002). Próbkowanie ważności – Zastosowania w komunikacji i wykrywaniu . Berlin: Springer-Verlag.

Zewnętrzne linki

• Strona główna sekwencyjnych metod Monte Carlo (filtrowanie cząstek) na Uniwersytecie w Cambridge
• Wprowadzenie do próbkowania ważności w symulacjach zdarzeń rzadkich European Journal of Physics. Dokument PDF.
• Adaptacyjne metody Monte Carlo do symulacji rzadkich zdarzeń: adaptacyjne metody Monte Carlo do symulacji rzadkich zdarzeń Zimowa konferencja symulacyjna