Próbkowanie ważności

Próbkowanie ważności to metoda Monte Carlo służąca do oceny właściwości określonego rozkładu , podczas gdy próbki są generowane tylko z innego rozkładu niż rozkład będący przedmiotem zainteresowania. Jego wprowadzenie do statystyki jest generalnie przypisywane pracy Teuna Kloeka i Hermana K. van Dijka z 1978 r., Ale jej prekursorów można znaleźć w fizyce statystycznej już w 1949 r. Próbkowanie ważności jest również związane 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 tej alternatywnej dystrybucji, procesu wnioskowania lub obu.

Podstawowa teoria

Niech ${\ Displaystyle X \ okrężnica \ Omega \ do \ mathbb {R}}$ będzie zmienną losową w pewnej przestrzeni prawdopodobieństwa ${\ Displaystyle (\ Omega, {\ mathcal {F} },P)}$ . Chcemy oszacować oczekiwaną wartość X pod P , oznaczoną E [ X;P ]. Jeśli mamy statystycznie niezależne próbki losowe ${\ Displaystyle x_ {1}, \ ldots, x_ {n}}$ , generowane zgodnie z P , to empiryczne oszacowanie E [ X; P ] to

$\ Displaystyle {\ widehat {\ mathbf {E}}} _ {n} [X; P] = {\ frac {1}{n}}\sum _{i=1}^{n}x_{i}\quad \mathrm {gdzie} \;x_{i}\sim P(X)}$

a precyzja tego oszacowania zależy od wariancji X :

${\ Displaystyle \ nazwa operatora {var} [{\ widehat {\ mathbf {E}}} _ {n}; P] = {\ Frac {\ nazwa operatora {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ą , że mi [ L P. ] = 1 i to P. - prawie wszędzie ${\ Displaystyle L (\ omega) \ neq 0}$ . Ze zmienną L definiujemy prawdopodobieństwo, które spełnia ${\ Displaystyle P ^ {(L)}}$

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

Zmienna X / L będzie zatem próbkowana pod P ^{( L )} w celu oszacowania E [ X;P ] jak powyżej, a oszacowanie to zostanie ulepszone ${\ Displaystyle \ nazwa operatora {var} \ lewo [{\ Frac {X} {L}}; P ^ {(L)} \ prawej] <\ nazwa operatora {var} [X; P]}$ .

Gdy X ma stały znak nad Ω, najlepszą zmienną L byłoby oczywiście ${\ Displaystyle L ^ {*} = {\ Frac {X} {\ mathbf {E} [X; P]}} \ geq 0}, więc$ X / L * jest szukaną stałą E [ X; P ] i pojedyncza próbka pod P ^{( L *)} wystarczy, aby podać jego wartość. 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 to, jakie znaczenie ma próbkowanie:

${\ Displaystyle {\ rozpocząć {wyrównane} \ forall a \ w \ mathbb {R}, \; P ^ {(L ^ {*})} ( X\in [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ównane}}}$

po prawej $_$ _ _ X ; P ]:

${\ Displaystyle E [X; P] = \ int _ {a = - \ infty} ^ {+ \ infty} a\,P(X\in [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 zostaną posortowane bezpośrednio według ich wag 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 . Gdy $X\colon \mathbb {R} \to \mathbb {R} }$$rozkładem$ równomiernym i , mi [ X $\$ odpowiada całce funkcji rzeczywistej ${$ displaystyle .

Zastosowanie do wnioskowania probabilistycznego

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

Zastosowanie do symulacji

Próbkowanie ważności jest techniką redukcji wariancji , którą można zastosować 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 częstsze pobieranie próbek, to estymator wariancję można zmniejszyć. Stąd podstawową metodologią doboru ważności jest wybór rozkładu, który „zachęca” do ważnych wartości. Takie użycie rozkładów „obciążonych” spowoduje powstanie estymatora obciążonego, jeśli zostanie zastosowany bezpośrednio w symulacji. Jednak wyniki symulacji są ważone, aby skorygować użycie rozkładu obciążonego, co gwarantuje, że nowy estymator próbkowania ważności jest nieobciążony. Waga jest określona przez iloraz wiarygodności , to znaczy pochodną Radona-Nikodyma rzeczywistego rozkładu bazowego w odniesieniu do obciążonego rozkładu symulacji.

Podstawową kwestią we wdrażaniu symulacji doboru próby ważności jest wybór rozkładu obciążonego, który sprzyja ważnym regionom zmiennych wejściowych. Wybór lub zaprojektowanie dobrze obciążonej dystrybucji to „sztuka” ważnego próbkowania. Nagrodą za dobrą dystrybucję mogą być ogromne oszczędności czasu pracy; karą za złą dystrybucję mogą być dłuższe czasy działania niż w przypadku ogólnej symulacji Monte Carlo bez próbkowania ważności.

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

${\ Displaystyle g ^ {*} = \ min _ {g} \ nazwa operatora {var} _ {g} \ lewo (X {\ Frac {f (X)} {g (X)}} \ prawo).}$

Można wykazać, że następujący rozkład minimalizuje powyższą wariancję:

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

Zauważ, że gdy ${\ displaystyle X \ geq 0}$ , ta wariancja wynosi 0.

Podejście matematyczne

$}$ symulację prawdopodobieństwa $,$ gdzie $jest$ zmienną losową o rozkładzie $t}$$Displaystyle X$$_$ i funkcja _ _ _ A $\ displaystyle K}$$displaystyle$ -niezależna od długości i identycznie rozłożona (iid) sekwencja $jest$ generowana z rozkładu i liczby $t}}$$k_ {$ zmiennych losowych, które znajdują się powyżej progu, $liczone$ . Zmienna $się$ charakteryzuje rozkładem

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

Można $_$ że ${\ Displaystyle \ operatorname {var} [k_ {t}/K] = p_ {t} (1-p_ {t})/K} , więc w$ granicy ${\ styl wyświetlania K\do \infty }$ jesteśmy w stanie uzyskać ${\ displaystyle p_ {t}}$ . Zauważ, że wariancja jest niska, jeśli ${\ Displaystyle p_ {t} \ około 1}$ . Próbkowanie $)$ dotyczy określenia i wykorzystania alternatywnej funkcji gęstości ( $określanej$ zwykle jako gęstość odchylająca, dla eksperymentu symulacyjnego. Ta gęstość pozwala na zdarzenie ${\ Displaystyle {X \ geq t \}}$ występuje częściej, więc długości sekwencji $estymatora$ się mniejsze dla danej wariancji . Alternatywnie, dla danej $.$ , użycie gęstości odchylenia daje wariancję mniejszą niż w przypadku konwencjonalnego oszacowania Monte Carlo Z definicji ${\ displaystyle p_ {t} \,}$$możemy$ wprowadzić jak

${\ Displaystyle {\ rozpocząć {wyrównane} p_ {t} & = {E} [1 (X \ geq t)] \\ [6pt] & = \ int 1 (x \ geq t) {\ frac {f (x )}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{wyrównane }}}$

Gdzie

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

jest ilorazem wiarygodności i jest określany jako funkcja ważąca. Ostatnia równość w powyższym równaniu motywuje estymator

${\ 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 próbkowania ważności $nieobciążony$ . $Oznacza$ to, że procedura szacowania polega na wygenerowaniu próbek iid z i każdej próbki, która przekracza $,$$jest$ zwiększane o $W\,}$ oceniane według wartości próbki. Wyniki są uśredniane $prób$ . Wariancja estymatora ważności doboru próby jest łatwa do wykazania

${\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {var} _ {*} {\ widehat {p}} _ {t} i = { \frac {1}{K}}\operatorname {var} _{*}[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}}}$

$,$ na znalezieniu gęstości odchylenia że wariancja estymatora próbkowania ważności jest mniejsza niż wariancja ogólnego oszacowania Monte Carlo. Dla pewnej funkcji gęstości odchylenia, która minimalizuje wariancję iw pewnych warunkach redukuje ją do zera, nazywa się to optymalną funkcją gęstości odchylenia.

Konwencjonalne metody obciążania

Chociaż istnieje wiele rodzajów metod odchylania, następujące dwie metody są najczęściej stosowane w zastosowaniach pobierania próbek o znaczeniu.

skalowanie

${\ displaystyle {X$ do regionu zdarzenia przez dodatnie skalowanie zmiennej losowej o liczbie większej niż jedność skutkuje zwiększeniem wariancji ( $\ geq t \}}$ oznacza również) funkcji gęstości. Powoduje to cięższy ogon gęstości, co prowadzi do wzrostu prawdopodobieństwa zdarzenia. Skalowanie jest prawdopodobnie jedną z najwcześniejszych znanych metod odchylania i było szeroko stosowane w praktyce. Jest prosta do wdrożenia i zwykle zapewnia konserwatywne zyski symulacji w porównaniu z innymi metodami.

$oszacowania$ wybierana jako funkcja gęstości skalowanej zmiennej losowej $,$ dla ogona. przez transformację,

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

a funkcja ważąca jest

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

$co$ gdy skalowanie przesuwa masę prawdopodobieństwa do pożądanego regionu zdarzenia, wypycha również masę do regionu komplementarnego jest niepożądane Jeśli $jest$ sumą zmiennych $losowych$ , rozprzestrzenianie się masy odbywa $przestrzeni$ wymiarowej Konsekwencją tego jest malejący wzrost znaczenia próbkowania dla zwiększenia ${\ displaystyle n \,}$ i jest nazywany 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 wysokowydajnych metod szacowania (takich jak odległości najgorszego przypadku WCD), SSS nie cierpi zbytnio z powodu problemu z wymiarowością. Również adresowanie wielu wyjść MC nie powoduje pogorszenia wydajności. Z drugiej strony, jako WCD, metoda SSS jest przeznaczona tylko dla Gaussowskich zmiennych statystycznych, aw przeciwieństwie do WCD, metoda SSS nie jest przeznaczona do dostarczania dokładnych narożników statystycznych. Inną wadą SSS jest to, że przebiegi MC z dużymi współczynnikami skali mogą być trudne, np. z powodu problemów ze zbieżnością modelu i symulatora. Ponadto w SSS mamy do czynienia z silnym kompromisem wariancji odchylenia: stosując duże współczynniki skali, uzyskujemy dość stabilne wyniki wydajności, ale im większe współczynniki skali, tym większy błąd obciążenia. Jeśli zalety SSS nie mają większego znaczenia w aplikacji będącej przedmiotem zainteresowania, to często inne metody są bardziej wydajne.

Tłumaczenie

Inna prosta i skuteczna technika odchylania wykorzystuje translację funkcji gęstości (a tym samym zmiennej losowej), aby umieścić większość jej masy prawdopodobieństwa w regionie rzadkich zdarzeń. Tłumaczenie nie cierpi z powodu efektu wymiarowości i zostało z powodzeniem wykorzystane w kilku zastosowaniach związanych z symulacją cyfrowych systemów komunikacyjnych . Często zapewnia lepsze wzmocnienia symulacji niż skalowanie. Przy odchylaniu przez translację gęstość symulacji jest określona wzorem

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

gdzie jest wielkością $przesunięcia$ i należy ją wybrać, aby zminimalizować wariancję estymatora ważności próbkowania

Skutki złożoności systemu

Podstawowy problem z próbkowaniem ważności polega na tym, że projektowanie dobrych rozkładów obciążonych staje się bardziej skomplikowane wraz ze wzrostem złożoności systemu. Systemy złożone to systemy o dużej 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żna interferencja międzysymbolowa (ISI))
• nieznana pamięć ( dekodery Viterbiego )
• możliwie nieskończona pamięć (korektory adaptacyjne)

Zasadniczo w takich sytuacjach znaczenie próbkowania pomysłów pozostaje takie samo, ale projektowanie staje się znacznie trudniejsze. Skuteczne podejście do walki z tym problemem polega zasadniczo na rozbiciu symulacji na kilka mniejszych, lepiej zdefiniowanych podproblemów. Następnie stosuje się strategie próbkowania ważności w celu ukierunkowania na każdy z prostszych podproblemów. Przykładami technik rozkładania symulacji są symulacja kondycjonowania i błędów (EES) oraz symulacja regeneracyjna.

Ocena doboru próby ważności

Aby zidentyfikować udane techniki próbkowania ważności, przydatna jest możliwość ilościowego określenia oszczędności w czasie wykonywania dzięki zastosowaniu metody próbkowania ważności. Powszechnie stosowaną miarą wydajności jest ${\ Displaystyle \ sigma _ {MC} ^ {2} / \ sigma _ {IS} ^ {2} \,}$ , i można to 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 estymatora prawdopodobnie nie będą możliwe analitycznie, gdy ich średnia jest trudna. Inne przydatne koncepcje w ilościowym określaniu 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óby (ESS) .

Funkcja kosztu wariancji

Wariancja nie jest jedyną możliwą funkcją kosztu w symulacji, a inne funkcje kosztu, takie jak średnie odchylenie bezwzględne, są wykorzystywane w różnych zastosowaniach statystycznych. Niemniej jednak wariancja jest podstawową funkcją kosztu omawianą w literaturze, prawdopodobnie ze względu na wykorzystanie wariancji w przedziałach ufności i w mierniku wydajności ${\ Displaystyle \ sigma _ {MC} ^ {2 }/\sigma _{IS}^{2}\,}$ .

$_$ fakt _ oszczędności wynikające z próbkowania ważności, ponieważ nie obejmuje dodatkowego czasu obliczeniowego wymaganego do obliczenia funkcji wagi. Dlatego niektórzy oceniają poprawę czasu pracy netto na różne sposoby. Być może poważniejszym obciążeniem związanym z próbkowaniem ważności jest czas potrzebny na opracowanie i zaprogramowanie techniki oraz analityczne wyprowadzenie pożądanej funkcji wagi.

Wielokrotne i adaptacyjne próbkowanie ważności

Gdy różne rozkłady propozycji są wspólnie używane do rysowania próbek , ${\ Displaystyle g_ {n} (x)}$ , ${\ Displaystyle n = 1, \ ldots, N,}$ można zastosować różne $)$ W warunkach adaptacyjnych dystrybucje propozycji, ${\ Displaystyle g_ {n, t} (x)}$ , ${\ Displaystyle n = 1, \ ldots, N,}$ i ${\ displaystyle t = 1, \ ldots, T,}$ są aktualizowane w każdej iteracji $.$ próbkowania o adaptacyjnym znaczeniu W związku z tym, ponieważ stosowana jest populacja proponowanych gęstości, można zastosować kilka odpowiednich kombinacji schematów doboru próby i ważenia.

Zobacz też

• Metoda Monte Carlo
• Redukcja wariancji
• Próbkowanie warstwowe
• Próbkowanie rekurencyjne warstwowe
• Algorytm VEGASA
• Filtr cząstek stałych — sekwencyjna metoda Monte Carlo, wykorzystująca próbkowanie ważności
• Boisko pomocnicze Monte Carlo
• Próbkowanie odrzucenia
• Zmienna przepływność — powszechne zastosowanie audio do próbkowania ważności

Notatki

•   Arouna, Bouhari (2004). „Adaptacyjna metoda Monte Carlo, technika redukcji wariancji”. Metody Monte Carlo i ich zastosowania . 10 (1): 1–24. doi : 10.1515/156939604323091180 . S2CID 21949573 .
• Bucklew, James Antonio (2004). Wprowadzenie do symulacji rzadkich zdarzeń . Nowy Jork: Springer-Verlag.
•   Doucet, A.; de Freitas, N.; Gordon, N. (2001). Sekwencyjne metody Monte Carlo w praktyce . Skoczek. ISBN 978-0-387-95146-1 .
•    Ferrari, M.; Bellini, S. (2001). Znaczenie Próbkowanie symulacji kodów produktów turbo . Międzynarodowa konferencja IEEE na temat komunikacji . Tom. 9. s. 2773–2777. doi : 10.1109/ICC.2001.936655 . ISBN 978-0-7803-7097-5 . S2CID 5158473 .
• Mazonka, Oleg (2016). „Łatwe jak pi: metoda próbkowania ważności” (PDF) . Dziennik referencyjny . 16 .
• Oberg, Tommy (2001). Modulacja, detekcja i kodowanie . Nowy Jork: John Wiley & Sons.
•   Prasa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Sekcja 7.9.1 Próbkowanie ważności” . Przepisy numeryczne: sztuka obliczeń naukowych (wyd. 3). Nowy Jork: Cambridge University Press. ISBN 978-0-521-88068-8 .
• Ripley, BD (1987). Symulacja stochastyczna . Wiley & Synowie.
• Smith, PJ; Szafi, M.; Gao, H. (1997). „Szybka symulacja: przegląd technik próbkowania ważności w systemach komunikacyjnych”. Dziennik IEEE dotyczący wybranych obszarów komunikacji . 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.

Linki zewnętrzne

• Sequential Monte Carlo Methods (filtrowanie cząstek) na Uniwersytecie Cambridge
• Wprowadzenie do próbkowania ważności w symulacjach rzadkich zdarzeń European Journal of Physics. dokument PDF.
• Adaptacyjne metody monte carlo do symulacji rzadkich zdarzeń: adaptacyjne metody monte carlo do symulacji rzadkich zdarzeń Winter Simulation Conference