00:35
Comentarii Adauga Comentariu

Metoda Monte Carlo. Tehnici de Divizare Splitting techniques: Divizarea Multiplă - Multiple Splitting



Capitolul 3 - Tehnici de Divizare - Splitting techniques: Divizarea Multiplă - Multiple Splitting

3.1 Introducere

După cum s-a explicat deja în capitolele anterioare, simularea unui eveniment rar necesită tehnici de accelerare pentru a accelera apariția evenimentelor rare în discuție, în caz contrar este posibil ca dimensiunile eșantionului să fie inacceptabil de mari pentru a obține în medie, realizări suficiente, sau chiar de a obține un singur eveniment rar.

Pe de altă parte, o accelerare prea mare poate fi contraproductivă și poate chiar duce la o explozie de variație și/sau o creștere a timpului de calcul.

Prin urmare, trebuie să existe un echilibru adecvat realizat, iar acest lucru nu este întotdeauna ușor.

Această dificultate a fost evidențiată în precedentul capitol atunci când am discutat despre tehnica de prelevare a probelor (IS), metodă a cărei idee este de a schimba legile de probabilitate care dirijează modelul pentru a face ca evenimentele de interes să apară cu o probabilitate mai mare și mai apoi, pentru a corecta părtinirea făcută prin înmulțirea estimatorului cu raportul de probabilitate adecvat.

În acest capitol, analizăm o tehnică alternativă față de cea precedentă, numită Divizare, care accelerează rata de apariție a evenimentelor rare de interes.

Aici, noi nu modificăm legile de probabilitate care conduc modelul.

În schimb, folosim o selecție pentru a favoriza traiectoriile considerate de natură să conducă la aceste evenimente rare.

Ideea principală este de a descompune căile care conduc spre evenimentele rare de interes, în subcăi mai scurte ale căror probabilități de apariție nu sunt atât de mici, și să încurajăm realizările care iau calea acestor subcăi de interes (= acestor subcăi care conduc la evenimentele de interes), oferindu-le o șansă de a se reproduce (un pic ca în evoluția selectivă) și descurajând realizările care merg în direcția greșită, ucigându-le cu o probabilitate pozitivă.

Subcăile sunt, de obicei, delimitate de nivele, la fel ca și curbele de nivel ale unei hărți.

Pornind de la un anumit nivel dat, realizările procesului (pe care de asemenea le numim traiectorii sau lanțuri sau particule) care nu ajung la nivelul următor nu vor ajunge nici la evenimentul rar, dar cele care o fac sunt împărțite (clonate) în mai multe copii atunci când acestea ajunge la nivelul următor și fiecare copie își continuă evoluția de acolo încolo.

Acest procedeu creează o deviație artificială față de evenimentul rar prin favorizarea traiectoriilor care merg în direcția cea bună.

În final, un estimator imparțial poate fi recuperat înmulțind contribuția fiecărei traiectorii cu o pondere corespunzătoare.

Procedura descrisă este cunoscută sub denumirea de Divizarea Multiplă (eng. Multiple Splitting)

Dacă presupunem, de exemplu, că simulăm un proces stochastic (de obicei un lanț Markov) și că evenimentul rar de interes apare atunci când ajungem să trecem printr-un subset de stări înainte de a reveni la starea inițială, atunci nivelurile pot fi definite de o succesiune descrescătoare (încapsulată) de seturi de stări care conțin toate seturile rare de interes.

În general, aceste niveluri sunt definite printr-o funcție de importanță al cărui scop este reprezentat de cât de aproape este o anumită stare față de acest set rar.

Mai multe strategii au fost proiectate pentru a determina nivelele, pentru a decide numărul de împărțiri la fiecare nivel, și de a trata traiectoriile care tind să meargă într-o direcție greșită față de evenimentul rar de interes.

Cantitatea de împărțire la atingerea unui nou nivel este o problemă importantă; cu prea multă divizare, populația lanțurilor va exploda, în timp ce cu o despicare prea mică, este posibil ca prea puține traiectorii să ajungă la un eveniment rar.

Există, de asemenea, posibilitatea de a elimina nivelurile, urmând o strategie care poate fie să împartă traiectoria, fie să o omoare într-un anumit pas.

Unii aplică divizarea (uneori cu o anumită probabilitate) dacă funcția de importanța ponderată este semnificativ mai mare la starea actuală (nouă) decât la starea anterioară, și aplică ruletă rusească (pentru a ucide lanțul cu o anumită probabilitate), când funcția de importanță ponderată devine mai mică.

Ruletă rusească poate fi, de asemenea văzută ca o divizarea a lanțului în copii zero.

Numărul estimat de clone după împărțirea (care este mai mică de 1 în cazul ruletei rusești) este de obicei considerat ca raportul dintre valoarea funcției de importanță la noua stare și cea de la stare veche [13, 22].

Cea mai importantă dificultate, în general, este găsirea unei funcții adecvate care să modeleze importanța.

Această funcție definește nivelurile (sau cantitatea de divizare dacă ajungem să scăpăm de niveluri), iar o alegere slabă a funcției de importanță poate duce cu ușurință la rezultate proaste.

În acest sens, rolul ei este similar cu măsura de importanță a cărei alegere este critică în IS (a se vedea capitolul precedent).

Un avantaj important al divizării în comparație cu IS este că nu trebuie să modificați legile de probabilitate care conduc sistemul.

Aceasta înseamnă (printre alte lucruri) ca programul de calculator care implementează modelul de simulare poate fi doar o cutie neagră, atâta timp cât este posibil să se facă copii (clone) din model și să mențină ponderile și să obțină valoarea actuală a importanței pentru fiecare dintre aceste exemplare.


(needitat)

Este, de asemenea, interesant de observat că pentru divizare implementări în care toate lanțurile au întotdeauna aceeași pondere la orice dată nivel, distribuția empirică a stărilor lanțurilor atunci când acestea au lovit un anumit nivel oferă o estimare imparțială a unei distribuții teoretice a intrărilor de (atunci când atinge acel nivel pentru pentru prima dată), sub probabilitățile originale.

Cu implementări de divizare în cazul în care lanțurile pot avea greutăți diferite și cu IS, acest lucru este valabil numai pentru ponderate (și redimensionate) distribuții empirice, în care fiecare observație se păstrează greutatea sa când definește distribuția. Există, de asemenea, situații în care aceasta este mai simplu și mai ușor de construit o funcție de importanță bună pentru divizare decât pentru IS, deoarece este mai sensibil la comportamentul importanței funcționează în apropierea limitelor spațiului de stare, după cum se explică în [9, 12] (a se vedea și Secțiunea 3.2.3).

O limitare a divizării în ceea ce privește IS este cerința de a se descompune spațiul de stare în subseturi (sau straturi) determinat de nivelurile unora funcția de importanță, astfel încât probabilitatea de a ajunge la nivelul următor începe din actuala nu este atât de mică.

Atunci când se poate găsi o astfel de descompunere, divizarea poate fi aplicată eficient.

Cu toate acestea, există situații în care cel mai mult căile probabile care conduc la eveniment rare au foarte puține pași (sau tranziții) și în cazul în care raritatea provine din faptul că fiecare dintre aceste pași are un nivel foarte scăzut probabilitate.

De exemplu, într-un set de fiabilitate, să presupunem că definim un eveniment rar ca fiind un eșec al sistemului și că modul cel mai probabil ca acest eșec să apară este eșecul a două componente de același tip, eveniment care se întâmplă din două tranziții din lanțul Markov, unde fiecare tranziție are o probabilitate foarte mică.

Într-o astfel de situație, divizarea nu poate fi aplicată efectiv, cel puțin nu direct.

Ar fi bine necesită un truc pentru separarea tranzițiilor rare în mai multe faze.

IS, pe de altă parte de mana, se pot descurca cu ușurință prin creșterea probabilității apariției acestor tranziții rare.

De asemenea, este important să recunoaștem că, în cazul modelelor mari (cum ar fi un sistem de așteptare cu multe variabile de stare), clonarea de stare operațiile pot provoca cu ușurință o atitudine semnificativă în timpul procesorului.

Acest capitol este organizat după cum urmează.

Secțiunea 3.2 descrie principiile generale o tehnică de divizare și o versiune principală (sau o implementare) găsită în literatură.

Secțiunea 3.3 furnizează o analiză asimptotică a metodei într-un setare simplificată care implică presupunerea că atingerea nivelului următor din curentul poate fi modelat de o variabilă aleatorie Bernoulli independentă de actuală (dat fiind că tocmai ating nivelul actual).

Acest lucru este echivalent presupunând că există o singură stare de intrare la fiecare nivel.

Atunci discutăm cât de mult ar trebui să ne împărțim și câte niveluri ar trebui să definim pentru o minimizare varietatea sau versiunea sa normalizată în funcție de muncă (varianța înmulțită cu cea așteptată timpul de calcul), într-un cadru asimptomatic.

În secțiunea 3.4 vă oferim o analiză pe baza sistemelor de particule care interacționează, în conformitate cu cadrul general [10].

Acest lucru ne permite să obținem o teoremă limită centrală într-un cadru general, într-un regim asimptotic unde numărul de traiectorii inițiale (sau de particule) crește spre infinit.

Deși rezultatele anterioare s-au concentrat asupra unui caz specific de împărțire numărul de traiectorii la fiecare nivel este fix, oferim în plus versiuni din teorema limitei centrale pentru alte implementări de divizare.

Secțiunea 3.5 se aplică versiuni diferite ale tehnicii de despicare la un exemplu simplu de tandem coada, folosită mai devreme de mai mulți autori. Acest lucru ilustrează eficacitatea sistemului precum și dificultățile și problemele critice ale găsirii unei soluții adecvate pentru funcția de importanță.

Rețineți că atât tehnicile IS cât și tehnicile de divizare cu metoda Monte Carlo au fost introduse și investigate încă din mijlocul anilor 1940 în Los Alamos [21, 22, 29].

Principalele probleme relevante, cum ar fi o analiză a împărțirii optime strategiile și definirea funcției de importanță, au fost deja identificate atunci.


(Fluierul)


Linkul direct catre Petitie

CEREM NATIONALIZAREA TUTUROR RESURSELOR NATURALE ALE ROMANIEI ! - Initiativa Legislativa care are nevoie de 500.000 de semnaturi - Semneaza si tu !

Comentarii:


Adauga Comentariu



Citiți și cele mai căutate articole de pe Fluierul:

BOMBĂ ActiveNews: "Președintele Klaus Iohannis este membru al Organizației Progresiste 'European Council of Foreign Relations' un Think-Tank fondat de GEORGE SOROS". Fluierul.ro a descoperit că ECFR e condusă de Carl Bildt MEMBRU AL GRUPULUI BILDERBERG

DEMISIA. Iohannis: "Mi s-a propus să fiu membru" în organizația condusă de un Bilderberg și finanțată de Soros. "Sunt bucuros să spun că-mi doresc acest lucru"

Putin vrea să introducă în programa școlară ora de "Patriotism". Progresiștii se vor zvârcoli ca nebunii...ca să arate "cât de greșit este sa înveți copiii sa fie patrioți".. N-o să mai poată destrăma Statele Naționale

Românii sunt ținuți ÎN MOD INTENȚIONAT cu Salarii de Mizerie pentru a fi o forță de muncă ieftină pentru MULTINAȚIONALELE STRĂINE. Salarii de MIZERIE de 300-450 de euro în toate regiunile țării.

"SOLUȚIA" LUI SOROS LA CRIZA COVID. Soros vrea ca țările UE să elibereze Titluri de Stat Perpetue pentru ca popoarele UE să plătească VEȘNIC, 5 miliarde de euro dobândă în FIECARE an. Asta l-a dus mintea de speculant pe SOROS.

Noile vaccinuri vor altera în mod permanent ADN-ul uman. Nimeni nu va mai şti exact decât producătorii lor ce anume vor modifica vaccinurile în ADN-ul fiecărei persoane.

Daniela Crudu, sex la Burlăciţa. Ce decizie au luat şefii show-ului după apariţia IMAGINILOR XXX

EXCLUSIV | Un nou sponsor pentru echipa națională. FRF a semnat cu Bancpost și va primi 2,1 milioane de euro

ISTORIA AȘA CUM NU V-O POVESTEȘTE NIMENI. Dezvăluirile lui Ștefan Andrei - Ministrul de Externe al lui Nicolae Ceaușescu - despre rețeaua de Spioni KGB GRU și NKVD ai Moscovei din partidul Comunist Român - Rețea care l-a ucis pe Nicolae Ceaușescu

Kelemen: UDMR va avea un text la moțiunea de cenzură. E o condiție dacă cineva vrea voturile noastre

Protecție ZERO: Noi alerte pentru măști periculoase. Numărul lor a crescut îngrijorător

SUA: Bărbatul care și-a dat foc miercuri în apropierea Casei Albe a murit

MAI AVEM DOUĂ PÂRGHII ALE SUVERANITĂȚII NAȚIONALE: GRANIȚELE ȘI MONEDA. SĂ NU RENUNȚĂM LA ELE. Marek Belka, guvernatorul Băncii Centrale a Poloniei: "Polonia este avantajată că nu a aderat la euro"

Avionul Egyptair prăbuşit: Analiza uneia din cutiile negre arată că s-a pronunţat cuvântul "foc"

Multinaționalele Străine ce dețin Supermarketurile refuză Legea Produselor Româneşti. Asociatia Marilor Retele Comerciale acuza ca propunerea legislativa care obliga supermarketurile sa ofere cel putin 50% produse romaneşti "submineaza comertul modern"

Cristina, adolescenta cu sâni imenşi. S-a filmat şi a pus filmuleţul pe net. "Sânii mei sunt naturali.." VIDEO

SCENE DE SEX la "Mireasă pentru fiul meu"? Ce au văzut telespectatorii, la TV, a creat isterie | VIDEO

Război comercial: China acuză SUA de ''terorism economic''

Juncker: "Nu va exista o renegociere a acordului Brexit cu succesorul Theresei May"

Purtătorul de cuvânt al Vaticanului: Vizita Papei Francisc este "pentru România, dar nu numai pentru România" (Crux)

Fotbal: Liga Națiunilor - Cristiano Ronaldo s-a alăturat selecționatei Portugaliei

De ce ești baistruc? Cuvintele dobrogenilor pe care niciun alt român nu le pricepe  - ce înseamnă "buhalcă", "ciortan"sau "ghionder"

Cornel Dinu l-a acuzat pe Crăciunescu că a trântit un meci din Liga Campionilor, fostul arbitru a reacționat prompt: "Îl dau în judecată!"

Adversar tare pentru Răzvan Lucescu în Grecia! AEK Atena a numit antrenor un fost colaborator al lui Mircea Lucescu la Șahtior

Ion Cristoiu a fost dat afară de la revista Historia pe care o fondase, de progresistul SRI-istoid Mircea M. Ioniță (cel care cântă mereu laude SRI-ului și Rețelei Progresiste) și de patronii fake-news-ul progresist numit "Adevărul"

FRANȚA. Grupul Bilderberg încearcă să-l impună pe tânărul Bilderberg Emmanuel Macron ca Președinte al Franței. Macron e deja la doar 1% în spatele lui Fillon şi dacă-l depăşeşte are şanse s-o bată pe LePen în turul II

ȘTIRILE OREI 09.00 | 30 mai 2019

Zelenski își arată colții, dar va mușca la toamnă

Dezvăluirea incredibilă a Soranei Cîrstea, după eliminarea de la Roland Garros 2019: "Am jucat cu ruptură de abdomen"

Motivul pentru care BEC va prezenta REZULTATELE finale la alegerile europarlamentare abia luni după ora 14.00, după mai mult de o săptămână de la scrutin

Gimnastică artistică: Ana-Maria Puiu, calificată în finala de la paralele, la Cupa Mondială de la Koper

Vântul puternic a doborât 22 de copaci, 3 stâlpi și un acoperiș, în Corabia, județul Olt

Bancul de miercuri. Baba de 80 de ani

Buget mediu de 2.000 de lei, alocat de către români pentru achiziția unei trotinete electrice (sondaj)

VIDEO Primire Papa Francisc. La Cotroceni se curăță covorul roșu

Vremea face RAVAGII în țară: Două persoane au fost salvate de viitură în Bihor/ Case și curți inundate în Sălaj

Ploi torențiale, vijelii și grindină în aproape toată țara / 37 de județe, sub cod galben până luni dimineață

[P] Despre alegerile din fiecare zi

MIREASĂ prinsă de CAVALERUL de ONOARE în timp ce îşi înşela SOŢUL: Cine este BĂRBATUL ăsta? VIDEO

​Consiliul General nu a aprobat nici joi încredințarea unui imobil de pe Lipscani pentru Muzeul de Istorie a Evreilor și al Holocaustului din România

De Ziua Copilului, doar un sfert dintre companiile din România vor acorda beneficii suplimentare angajaților - studiu

România, sub media UE după ponderea deceselor provocate de cancerul pulmonar

"Don’t trust Tudorel Toader". Protest în fața Universității Al.I. Cuza față de rector, ex-ministrul Justiției în Guvernul Dăncilă

Demisie la Ministerul justiției. Un secretar de stat părăsește funcție

FOTO | În urmă cu 9 ani arăta așa. Cum arată acum sportivul român care luptă pentru șansa de a deveni european în kickboxing

Rednic, sătul de cazul Răduț: "M-ați omorât cu el, i-am zis să nu fie prea târziu". Puriul, deranjat și de neconvocarea lui Sorescu: "Înseamnă că n-ai încredere în ei!"

Expoziția "Dintre mii de jucării" - de joi, la Muzeul Național de Istorie a României

Tribunalul București a respins contestația lui Cristian Borcea. Afaceristul rămâne în pușcărie

După eşuarea Referendumului, eşec dirijat de toate partidele existente la lătratul neomarxistei UE, mai rămâne o singură soluție. Coaliția Pentru Familie trebuie să se transforme neapărat într-un Partid Politic.

REACȚII AGRESIVE ÎMPOTRIVA INITIAȚIVEI PRO-FAMILIE. Nesimțirea lui Florin Iaru :"Trei Milioane de Proști". Singurul Prost așa cum puteți vedea e Florin Iaru. Trei milioane de oameni râd de prostia lui.

Cine organizează așa ceva? Film porno cu primarul Buzăului și două tinere. Ménage à trois cu Constantin Boșcodeală, surprins într-o cameră de hotel, în timpul unei partide de sex - VIDEO

STUDIU. O treime din persoanele contaminate cu virusul sunt asimptomatice. Anunțul guvernului țării cu peste 241.000 de cazuri de COVID-19

Regionalizarea se întoarce. Cioloș: "Județele ar urma să dispară". SPUNE "NU" REGIONALIZĂRII. Noile Regiuni nu sunt altceva decât "noile județe" ale Federației Progresiste numite "Uniunea Europeană". UN PRIM PAS SPRE DESTRĂMAREA ROMÂNIEI.

Cum s-a trăit în România în anii '70- '80? UNII VĂ MINT spunându-vă că s-a trăit permanent prost între anii 1965 - 1989.

Remus Borza, exclus din ALDE, a fost numit consilier onorific al premierului Dăncilă

Criticul Alex Ștefănescu, Membru Fondator și șef în Consiliul director al Alianței Noastre a făcut o prezentare elogioasă și a scris prefața unei cărți PORNO și l-a lăudat pe autorul ei: Codin Maticiuc zis și Poponeț

Anisia Gafton, ipostaze de infarct, cu chiloții la vedere. Dezmăț total | VIDEO

INCEST. Mama şi fiul, îndrăgostiţi după ce s-au cunoscut pentru prima oară. "Este dragostea vieţii mele şi nu vreau să..."

MOSTENIREA nestiuta a lui Ceausescu! America e SOCATA de ce a descoperit in Romania
ULTIMA ORA: Dusmanii tarii vor sa ascunda adevarul

Procedura de destituire a lui Trump: Casa Albă refuză să coopereze la ancheta mincinoasă a Congresului controlat de Progresiști care incearca destituirea lui Trump chiar înainte de alegerile de anul viitor


Pag.1 Pag.2 Pag.3 Pag.4

Nr. de articole la aceasta sectiune: 185, afisate in 4 pagini.



ieri 05:50 CITATUL ZILEI