Eșantionarea după semnificație

Eșantionarea importanței ( denumită în continuare OT) este una dintre metodele de reducere a varianței unei variabile aleatoare, care este utilizată pentru a îmbunătăți convergența procesului de modelare a oricărei mărimi prin metoda Monte Carlo . Ideea VZ se bazează pe faptul că unele valori ale unei variabile aleatoare în procesul de modelare au o semnificație (probabilitate) mai mare pentru funcția (parametrul) evaluată decât altele. Dacă aceste valori „mai probabile” apar mai des în timpul selecției unei variabile aleatoare, varianța funcției estimate va scădea. Prin urmare, metodologia de bază a EOI este alegerea unei distribuții care favorizează selecția valorilor „mai probabile” ale variabilei aleatoare. O astfel de distribuție „părținată” modifică funcția estimată dacă este aplicată direct în procesul de calcul. Cu toate acestea, rezultatul calculului este reponderat în funcție de această distribuție părtinitoare, iar acest lucru asigură că noua funcție OT estimată nu este părtinită. Ponderea în sine este dată de raportul de probabilitate , adică derivata Radon-Nikodym a distribuției inițiale adevărate în raport cu distribuția părtinitoare aleasă.

O sarcină fundamentală în implementarea EOI este alegerea unei distribuții părtinitoare care identifică regiuni cu valori „mai probabile” ale funcției estimate.

VZ este eficient dacă o astfel de distribuție este aleasă și construită cu succes, deoarece va reduce semnificativ timpul de calcul. Cu o distribuție părtinitoare nefericită, chiar și metoda standard Monte Carlo poate da rezultate mai bune.

Fundamente matematice

Luați în considerare modelarea probabilității unui eveniment , unde este o variabilă aleatoare cu o distribuție și o densitate de probabilitate , unde primul înseamnă derivata lui . Să fie generată o statistică de lungime K, o secvență de K evenimente independente și uniform distribuite , pe baza distribuției lui , și dorim să estimăm numărul de variabile aleatoare din K ale căror valori se află peste unele . Variabila aleatoare este caracterizată de distribuția binomială $p_{t}$ ${ X \ge t\ }$ $X$ $F$ $f(x)=F'(x)$ $X_{i}$ $F$ $k_t$ $t$ $k_t$

P(k_t = k)={K\alegeți k}p_t^k(1-p_t)^{Kk},\,\quad \quad k=0,1,\dots,K.

Eșantionarea semnificației se referă la construirea și utilizarea unei alte funcții de densitate (pentru X), denumită în mod obișnuit densitate părtinitoare, într-un experiment de calcul (simulare). Noua densitate permite ca evenimentul să apară mai des, astfel lungimea secvenței pentru o valoare dată a varianței statisticilor construite va scădea. Cu alte cuvinte, pentru o statistică K dată, utilizarea densității părtinitoare are ca rezultat o varianță mai mică decât estimarea convențională Monte Carlo. Din definiție , putem intra după cum urmează: $f_{*}$ ${ X \ge t\ }$ $p_{t}$ $f_{*}$

p_t = {E}[X\ge t]

= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx

= {E_*} [(X \ge t) W(X)]

Unde

W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}

este raportul de probabilitate și se numește funcție de greutate. Ultima egalitate duce la luarea în considerare a statisticilor

\hat p_t = \frac{1}{K}\,\sum_{i=1}^K (X_i \ge t) W(X_i),\,\quad \quad X_i \sim f_*

Aceasta este o statistică OT și nu este respinsă atunci când este utilizată . Astfel, procedura de simulare pentru VZ poate fi formulată ca pregătirea unei secvențe de evenimente independente și uniform distribuite pentru densitatea , când fiecare eveniment va avea o pondere crescută, iar evenimentele ulterioare sunt acceptate ca înainte dacă sunt mai mari decât . Rezultatul este mediat pe toate statisticile . Este ușor de arătat că varianța estimării OT va fi egală cu $p_{t}$ $f_{*}$ $f_{*}$ $W$ $t$ $K$

Var_{*}{\hat {p}}_{t}={\frac {1}{K}}Var_{*}[(X\geq t)W(X)]

= \frac{1}{K}\Big[{E_*}[(X \ge t)^2 W^2(X)] - p_t^2 \Big]

= \frac{1}{K}\Big[{E}[(X \ge t)^2 W(X)] - p_t^2 \Big]

Acum problema OT poate fi formulată ca găsirea unei astfel de densități de probabilitate încât varianța noilor statistici să fie mai mică decât cea obținută prin metoda obișnuită Monte Carlo. Dacă în problemă este posibil să se construiască o densitate de probabilitate părtinitoare pentru care varianța este 0, atunci se numește densitate de probabilitate părtinitoare optimă. $f_{*}$

Metode pentru construirea distribuțiilor părtinitoare

Deși există multe metode pentru reprezentarea grafică a densităților părtinitoare, următoarele două metode sunt cele mai comune atunci când se utilizează EOI.

Scalare

Schimbați o măsură de probabilitate într-o regiune prin scalarea unei variabile aleatoare cu un număr mai mare de unu. O astfel de scalare duce la o creștere a semnificației cozii densității probabilității și, prin urmare, dă o creștere a probabilității de apariție a evenimentelor „dorite”. După toate probabilitățile, scalarea a fost una dintre primele metode de părtinire utilizate pe scară largă în practică. Implementată cu ușurință în algoritmi reali, această metodă oferă o îmbunătățire destul de modestă a eficienței simulării în comparație cu alte metode de părtinire. ${ X \ge t\ }$ $X$

În VZ la scalare, densitatea de probabilitate pentru simulare este definită ca densitatea originală pentru variabila aleatoare scalată . Dacă este important pentru noi să estimăm coada densității de probabilitate în sus, alegeți . Noua funcție de densitate și respectiv greutate sunt $aX$ $a>1$

f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg ))

și

W(x)= a \frac{f(x)}{f(x/a)} \, .

În timp ce scalarea mută măsura de probabilitate în regiunea dorită a evenimentelor „dorite”, de asemenea, deplasează probabilitatea în regiunea . Dacă este suma variabilelor aleatoare, răspândirea probabilității are loc în spațiul --lea. În consecință, aceasta reduce eficiența IO pe măsură ce crește (efect de dimensionalitate). $X<t$ $X$ $n$ $n$ $n$

Difuzare

O altă tehnică de polarizare simplă și eficientă se bazează pe traducerea densității probabilității (și, prin urmare, a variabilei aleatoare) într-o regiune în care probabilitatea crește. Traducerile nu duc la efectul de dimensiune. Această tehnică a fost aplicată cu succes în aplicații din lumea reală, cum ar fi modelarea sistemelor de comunicații digitale . Adesea, această metodă este mai eficientă decât scalarea. Sub polarizarea translației, noua densitate de probabilitate este definită ca

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

unde este valoarea deplasării aleasă din condiția minimizării varianței statisticilor IS. $c$

Efecte de complexitate a sistemului

Problema fundamentală a OT este dificultatea de a construi o bună distribuție părtinitoare pe măsură ce sistemul studiat devine mai complex. În acest sens, sistemele cu memorie lungă se numesc sisteme complexe, deoarece pentru sistemele în care are loc procesarea complexă a unui număr mic de parametri de intrare (adică în probleme cu o dimensiune mică), problema construirii unui OT este mai simplă. De exemplu, în teoria semnalizării digitale, memoria lungă (sau dimensionalitatea mare a condițiilor inițiale) duce la trei tipuri de probleme:

memorie lungă (interacțiune puternică între caractere)
memorie de lungime nedeterminată (decodor Viterbi)
memorie de lungime posibil infinită (egalizatoare adaptive)

În principiu, ideile de bază ale OE nu se schimbă atunci când sunt aplicate acestor tipuri de probleme, dar implementarea devine mult mai complicată. O strategie de succes pentru rezolvarea problemelor de memorie lungă poate fi împărțirea întregii probleme în câteva părți mai bine definite. Apoi EOI se aplică fiecărei sub-probleme în mod independent.

Estimări numerice ale OT

Pentru a determina succesul densității IO găsite, este util să existe o estimare numerică a reducerii cantității de calcule atunci când este aplicată. Pentru o astfel de estimare, se utilizează de obicei raportul , care poate fi interpretat ca un factor de creștere a vitezei cu care statisticile OT vor obține aceeași acuratețe ca și statisticile obținute prin metoda obișnuită Monte Carlo. Valoarea raportului poate fi obținută doar empiric, deoarece variațiile statisticilor sunt aproape imposibil de derivat analitic. $\sigma _{MC}^{2}/\sigma _{IS}^{2)$

Funcția de varianță a prețului

Varianta nu este singura funcție de preț de modelat, deoarece există și alte tipuri de funcții de preț care sunt utilizate în diverse aplicații statistice, cum ar fi abaterea medie absolută. Cu toate acestea, varianța este frecvent citată în literatură, posibil datorită utilizării varianței în calcularea intervalelor de încredere și în expresia pentru măsurarea eficienței . $\sigma _{MC}^{2}/\sigma _{IS}^{2)$

O problemă cu utilizarea varianței este că raportul supraestimează reducerea efortului de calcul atunci când se utilizează EOI, deoarece acest parametru nu ia în considerare timpul suplimentar necesar pentru calcularea funcției de greutate. Prin urmare, într-o aplicație reală, îmbunătățirea rezultată din aplicarea EOI trebuie evaluată prin alte metode. Poate că o problemă mai serioasă în ceea ce privește eficiența în EOI este momentul dezvoltării și implementării tehnicii în sine și construcției analitice a funcției de greutate necesare (dacă nu este cunoscută dinainte). $\sigma _{MC}^{2}/\sigma _{IS}^{2)$

Vezi și

Metoda Monte Carlo
Eșantionare zonată
Eșantionarea recurstivă zonată
Metode Monte Carlo secvenţiale sau filtru de particule

Literatură

I. M. Sobol. Metode numerice Monte Carlo. M.: Nauka, 1973
PJSmith, M.Shafi și H. Gao, „Simulare rapidă: o revizuire a importanței tehnicilor de eșantionare în sistemele de comunicare”, IEEE J.Select.Areas Commun., vol. 15, pp. 597-613, mai 1997.
M. Ferrari, S. Bellini, „Importance Sampling Simulation of turbo product codes”, ICC2001, The IEEE International Conference on Communications, vol. 9, pp. 2773–2777, iunie 2001.
Tommy Oberg, Modulation, Detection, and Coding, John Wiley & Sons, Inc., New York, 2001.
R. Srinivasan., Eșantionarea importanței. New York: Springer, 2002.

În plus

„Eșantionarea importanței – Aplicații în comunicații și detecție”, Rajan Srinivasan, Springer-Verlag, Berlin, 2002.
„Introducere în simularea evenimentelor rare”, James Antonio Bucklew, Springer-Verlag, New York, 2004.

Link -uri

Pagina de pornire a Metodelor Monte Carlo secvențiale (filtrarea particulelor) de la Universitatea din Cambridge
Introducere în importanța eșantionării în simulările cu evenimente rare Revista Europeană de Fizică. document PDF.
Metode adaptive monte carlo pentru simulări de evenimente rare: metode adaptive monte carlo pentru simulări de evenimente rare Winter Simulation Conference
Cuba - o bibliotecă pentru integrarea numerică multidimensională