Sampling efter betydelse

Viktighetssampling ( nedan kallat OT) är en av metoderna för att reducera variansen för en slumpvariabel, som används för att förbättra konvergensen av processen att modellera valfri kvantitet med Monte Carlo-metoden . Idén med VZ är baserad på det faktum att vissa värden för en slumpvariabel i modelleringsprocessen har en större signifikans (sannolikhet) för den utvärderade funktionen (parametern) än andra. Om dessa "mer sannolika" värden dyker upp oftare under valet av en slumpmässig variabel, kommer variansen för den uppskattade funktionen att minska. Därför är den underliggande metodiken för EOI att välja en fördelning som gynnar valet av "mer troliga" värden för den slumpmässiga variabeln. En sådan "förspänd" fördelning ändrar den uppskattade funktionen om den tillämpas direkt i beräkningsprocessen. Resultatet av beräkningen vägs dock om enligt denna partiska fördelning, och detta säkerställer att den nya uppskattade OT-funktionen inte är partisk. Vikten i sig ges av sannolikhetsförhållandet , dvs Radon-Nikodym-derivatan av den verkliga initiala fördelningen med avseende på den valda snedfördelningen.

En grundläggande uppgift i implementeringen av EOI är valet av en partisk fördelning som identifierar regioner med "mer sannolika" värden för den uppskattade funktionen.

VZ är effektiv om en sådan fördelning väljs och konstrueras framgångsrikt, eftersom det kommer att avsevärt minska beräkningstiden. Med en olycklig partisk fördelning kan även standardmetoden Monte Carlo ge bättre resultat.

Matematiska grunder

Överväg att modellera sannolikheten för en händelse , där är en slumpvariabel med en fördelning och en sannolikhetstäthet , där primtal betyder derivatan av . Låt en statistik över längden K, en sekvens av K oberoende och likformigt fördelade händelser , genereras baserat på fördelningen av , och vi vill uppskatta antalet slumpvariabler i K vars värden ligger över några . Slumpvariabeln kännetecknas av binomialfördelningen $p_{t}$ ${ X \ge t\ }$ $X$ $F$ $f(x)=F'(x)$ $X_{i}$ $F$ $k_t$ $t$ $k_t$

P(k_t = k)={K\välj k}p_t^k(1-p_t)^{Kk},\,\quad \quad k=0,1,\dots,K.

Signifikanssampling hänvisar till konstruktionen och användningen av en annan densitetsfunktion (för X), vanligen kallad biased density, i ett beräkningsexperiment (simulering). Den nya tätheten tillåter händelsen att inträffa oftare, sålunda kommer längden på sekvensen för ett givet värde på variansen för den konstruerade statistiken att minska. Med andra ord, för en given K-statistik, ger användning av partisk densitet mindre varians än konventionell Monte Carlo-uppskattning. Från definitionen kan vi skriva in enligt följande: $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)]

var

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

är sannolikhetsförhållandet och kallas viktfunktionen. Den sista jämställdheten leder till övervägande av statistik

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

Detta är en OT-statistik för och avvisas inte när den används . Således kan simuleringsproceduren för VZ formuleras som att förbereda en sekvens av oberoende och likformigt fördelade händelser för densiteten , när varje händelse kommer att ha en ökad vikt, och ytterligare händelser accepteras som tidigare om de är större än . Resultatet är ett medelvärde över all statistik . Det är lätt att visa att variansen för OT-uppskattningen kommer att vara lika med $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]

Nu kan OT-problemet formuleras som att man hittar en sådan sannolikhetstäthet att variansen i den nya statistiken blir mindre än den som erhålls med den vanliga Monte Carlo-metoden. Om det i problemet är möjligt att konstruera en partisk sannolikhetstäthet för vilken variansen är 0, så kallas det den optimala förspända sannolikhetstätheten. $f_{*}$

Metoder för att konstruera partiska distributioner

Även om det finns många metoder för att plotta partiska densiteter, är följande två metoder de vanligaste när man använder EOI.

Skalning

Flytta ett sannolikhetsmått till en region genom att skala en slumpvariabel med ett tal större än ett. Sådan skalning leder till en ökning av betydelsen av svansen av sannolikhetstätheten och ger därmed en ökning av sannolikheten för att "önskade" händelser inträffar. Med all sannolikhet var skalning en av de första biasingmetoderna som användes i stor utsträckning i praktiken. Denna metod är lätt implementerad i riktiga algoritmer och ger en ganska blygsam förbättring av simuleringseffektiviteten jämfört med andra biasmetoder. ${ X \ge t\ }$ $X$

I VZ vid skalning definieras sannolikhetstätheten för simulering som den ursprungliga densiteten för den skalade slumpvariabeln . Om det är viktigt för oss att uppskatta svansen av sannolikhetstätheten uppåt, välj . Den nya densitets- respektive viktfunktionen är $aX$ $a>1$

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

och

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

Medan skalning flyttar sannolikhetsmåttet till den önskade regionen av "önskade" händelser, flyttar den också sannolikheten till regionen . Om är summan av slumpvariabler, sker sannolikhetsspridningen i det -e utrymmet. Som en konsekvens minskar detta effektiviteten hos IO när den ökar (dimensionalitetseffekt). $X<t$ $X$ $n$ $n$ $n$

Broadcast

En annan enkel och effektiv förspänningsteknik bygger på att översätta sannolikhetstätheten (och därmed den slumpmässiga variabeln) till en region där sannolikheten ökar. Översättningar leder inte till dimensionseffekten. Denna teknik har framgångsrikt tillämpats i verkliga tillämpningar, såsom modellering av digitala kommunikationssystem . Ofta är denna metod mer effektiv än skalning. Under translationsbias definieras den nya sannolikhetstätheten som

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

var är skiftvärdet valt från villkoret att minimera variansen i IS-statistiken. $c$

Systemkomplexitetseffekter

Det grundläggande problemet med OT är svårigheten att konstruera en bra partisk fördelning när systemet som studeras blir mer komplext. I denna mening kallas system med ett långt minne för komplexa system, eftersom för system där komplex bearbetning av ett litet antal ingångsparametrar äger rum (det vill säga i problem med en liten dimension), är problemet med att konstruera en OT enklare. Till exempel, inom digital signaleringsteori leder långt minne (eller stor dimensionalitet av initiala förhållanden) till tre typer av problem:

långt minne (stark inter-karaktär interaktion)
minne av obestämd längd (Viterbi-avkodare)
minne av möjligen oändlig längd (adaptiva utjämnare)

I princip förändras inte grundidéerna för EO när de tillämpas på den här typen av problem, men implementeringen blir mycket mer komplicerad. En framgångsrik strategi för att hantera långa minnesproblem kan vara att bryta ner hela problemet i flera bättre definierade delar. Sedan tillämpas EOI på vart och ett av delproblemen oberoende av varandra.

Numeriska uppskattningar av OT

För att bestämma framgången för den hittade IO-densiteten är det användbart att ha en numerisk uppskattning av minskningen av mängden beräkningar när den tillämpas. För en sådan uppskattning används vanligtvis förhållandet , vilket kan tolkas som en faktor för att öka hastigheten med vilken OT-statistiken kommer att uppnå samma noggrannhet som statistiken som erhålls med den vanliga Monte Carlo-metoden. Värdet på förhållandet kan endast erhållas empiriskt, eftersom statistikens varianser är nästan omöjliga att härleda analytiskt. ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Prisfunktion för varians

Varians är inte den enda prisfunktionen att modellera, eftersom det finns andra typer av prisfunktioner som används i olika statistiska tillämpningar, såsom den genomsnittliga absoluta avvikelsen. Varians nämns dock ofta i litteraturen, möjligen på grund av användningen av varians i beräkningen av konfidensintervall och i uttrycket för att mäta effektivitet . ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Ett problem med att använda varians är att förhållandet överskattar minskningen av beräkningsansträngning vid användning av EOI, eftersom denna parameter inte tar hänsyn till den extra tid som krävs för att beräkna viktfunktionen. I en verklig tillämpning måste därför förbättringen till följd av tillämpningen av EOI bedömas med andra metoder. Ett kanske allvarligare problem när det gäller effektiviteten i EOI är tiden att utveckla och implementera själva tekniken och den analytiska konstruktionen av den nödvändiga viktfunktionen (om den inte är känd i förväg). ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2))$

Se även

Monte Carlo metoden
Zonbestämd provtagning
Rekursiv zonindelad provtagning
Sekventiella Monte Carlo-metoder eller partikelfilter

Litteratur

I. M. Sobol. Numeriska Monte Carlo-metoder. M.: Nauka, 1973
PJSmith, M.Shafi och H. Gao, "Snabb simulering: En översyn av vikten av samplingstekniker i kommunikationssystem," IEEE J.Select.Areas Commun., vol. 15, sid. 597-613, maj 1997.
M. Ferrari, S. Bellini, "Importance Sampling simulation of turbo product codes," ICC2001, IEEE International Conference on Communications, vol. 9, sid. 2773–2777, juni 2001.
Tommy Oberg, Modulation, Detection, and Coding, John Wiley & Sons, Inc., New York, 2001.
R. Srinivasan., Viktighetsprovtagning. New York: Springer, 2002.

Dessutom

"Sampling av betydelse - Tillämpningar inom kommunikation och detektion", Rajan Srinivasan, Springer-Verlag, Berlin, 2002.
"Introduktion till simulering av sällsynta händelser", James Antonio Bucklew, Springer-Verlag, New York, 2004.

Länkar

Sequential Monte Carlo Methods (Partikelfiltrering) hemsida på University of Cambridge
Introduktion till vikten av provtagning i sällsynta händelsesimuleringar European Journal of Physics. PDF-dokument.
Adaptiva Monte Carlo-metoder för sällsynta händelsesimuleringar: adaptiva Monte Carlo-metoder för sällsynta händelsesimuleringar Vintersimuleringskonferens
Kuba - ett bibliotek för flerdimensionell numerisk integration