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:

Semnal de alarmă în Australia. Ziarele au fost editate cu textele acoperite cu tuș negru. Protest puternic față de cenzură

IZOLAȚI ÎN ROMÂNIA? Ei sau noi? Maria Zăican - Bătrâna din pădure - VIDEO

Alegeri în Republica Moldova: Socialiștii au câștigat în cele mai multe raioane

Partidul Laburist se va alia cu alte formațiuni politice din Parlamentul britanic pentru a bloca adoptarea acordului pentru Brexit

Ministrul britanic de Externe: Guvernul lui Boris Johnson are numărul necesar de voturi pentru adoptarea acordului privind Brexit

Vrea să fie liber. Lionel Messi a refuzat o clauză care l-ar fi legat pe viață de FC Barcelona

Un nou caz de plecare inexplicabilă. Fată de 13 ani, dată dispărută. FOTO pentru recunoaștere

Heiko Maas, ministru german, numește ofensiva turcă din Siria o "invazie" ilegitimă

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

Un tânăr decedat și un altul rănit într-un accident produs pe o stradă din Târgu Mureș

Justin Trudeau, sub presiune în contextul în care circa 27 de milioane de canadieni sunt chemați la urne

Fotbal: Ronaldo Vieira (Sampdoria), victima strigătelor rasiste la meciul cu AS Roma

Președintele Klaus Iohannis, primit la Tokyo de premierul japonez

Viceprim-ministrul spaniol îi cere liderului catalan Quim Torra să renunțe la discursul secesionist

Orban dezminte informația diseminată de Dăncilă privind interferența PPE pentru deschiderea unei fabrici Volkswagen în țara vecină

Trupe americane au trecut din Siria în Irak în cadrul retragerii ordonate de Trump

Prahova: Bărbat de 45 de ani, pasager într-un taxi, decedat într-un accident rutier pe Șoseaua Vestului din Ploiești

Întâlnire Vladimir Putin și Recep Tayyip Erdogan, la Soci, pe tema intervenției militare din nordul Siriei

Nivel înalt al operațiunilor de spionaj. FT: Un grup de hackeri din Rusia a "furat" identitatea unei organizații similare din Iran

ULTIMA ORĂ Boris Johnson, acționat în judecată pentru că a recomandat UE să refuze amânarea Brexit. Premierul Marii Britanii a trimis două scrisori sâmbătă noaptea

Vrancea: Urs accidentat mortal de un autoturism pe Ojdula, după ce animalul ar fi pătruns pe partea carosabilă

Darius Vâlcov, fost consilier pe economie și eminența cenușie a programului de guvernare al PSD, și-ar fi plagiat teza de doctorat în finanțe. Rectorul ASE propune retragerea titlului

Eurostat: România a avut un deficit de 3% din PIB, în 2018

Focuri de armă, trase după o mașină în Argeș. Patru persoane au reușit să fugă de polițiști. Cazul este în derulare

Buzău: Accident rutier pe DN 2B, în zona unei treceri de cale ferată

Box: Pugilistul ucrainean Aleksandr Gvodzik, 48 de ore în spital după o comoție cerebrală suferită în ring

Pilotul Valentin Gvinda refuză să preia conducerea TAROM, după ce a făcut o analiză a situației companiei

Economistul Robert Shiller, câștigător al premiului Nobel, crede că președintele american Donald Trump a speriat recesiunea

CITATUL ZILEI

Violența din cadrul protestelor din Chile a provocat moartea a cinci persoane

Accident de autocar cu numere de Ucraina. Vehiculul cu 46 de persoane s-a răsturnat, după ce s-a izbit de un stâlp

Harghita: Jandarmii au intervenit pentru alungarea unui urs care a intrat în gospodăria unei femei din Șimonești

Fotbal: FC Liverpool, ținută în șah de Manchester United în campionatul Angliei

Vietnam: Prim-ministrul promite că nu va face nicio concesie teritorială Chinei

Galați: Un autocar cu 46 de pasageri din Ucraina s-a izbit de un stâlp de pe marginea DN 26; nu sunt înregistrate victime

COPAC solicită MS și MEN să clarifice situația rezidențiatului și să îl organizeze anul acesta, nu în 2020

Românii au cumpărat online cu 30% mai multă mobilă, în această toamnă decât în 2018 (analiză)

Bonurile fiscale în valoare de 328 lei emise pe 6 septembrie au ieșit câștigătoare la extragerea de duminică

Dăncilă merge în Parlament la grupurile reunite ale PSD. Discuții despre votul pentru noul Guvern

Mădălina Mezei, fost director general al TAROM, chemată luni la DNA

IȘMB: Elevii de clasa a VII-a nu au în continuare manuale la Matematică, Chimie și Istorie

DNA anchetează acuzațiile de abuz în serviciu aduse lui Răzvan Cuc. Mădălina Mezei, fosta șefă de la TAROM, audiată

Ofensiva turcă încalcă dreptul internațional, acuză Berlinul

Spania: Rămășițele lui Franco vor fi exhumate joi, anunță guvernul

Indonezia: Joko Widodo a depus jurământul și și-a început al doilea și ultim mandat prezidențial

Harghita: Doi morți și un rănit grav după ce un autoturism s-a izbit de un imobil

Alegeri în Republica Moldova: Ion Ceban și Andrei Năstase se vor duela în turul doi (rezultate preliminare)

Germania va împrumuta Marii Britanii Discul ceresc de la Nebra, un artefact datând din Epoca Bronzului

Protest împotriva cenzurii în Australia: Prima pagină a ziarelor, în chenar negru

Argeș: Polițiștii au făcut uz de armă în timpul urmăririi ocupanților unui autoturism care nu a oprit la semnal

Tenis: Andrei Rublev, campion la Moscova în ziua în care a împlinit 22 de ani

Alegeri în Republica Moldova: Marile municipii, împărțite între partide și independenți

Accident grav. O mașină a intrat în zidul unei case. Doi morți și persoana din locuință, rănită grav

Hunedoara: Amenajare de șantier pentru restaurarea Castelului Corvinilor

Maramureș: Șase persoane salvate în urma prelevării de organe și țesuturi de la un pacient cu anevrism cerebral

Sorina Pintea: Ministerul Sănătății și Ministerul Educației nu pot rezolva problema rezidențiatului

BREAKING Dosarul de corupție al fostului ministru Dan Șova va fi rejudecat de la zero

Prințul moștenitor al Arabiei Saudite vrea să devină acționar la un prestigios club de fotbal din Marea Britanie

Presa o laudă pe Halep, înainte de Turneul Campioanelor. "Chiar și în absența lui Cahill, a continuat să scrie istorie"

Rugby - CM 2019: Arbitrul meciului Țara Galilor - Franța, cercetat de World Rugby


Pag.1 Pag.2 Pag.3 Pag.4 Pag.5 Pag.6 Pag.7
Pag.8 Pag.9 Pag.10 Pag.11 Pag.12 Pag.13 Pag.14 Pag.15
Pag.16 Pag.17 Pag.18 Pag.19 Pag.20 Pag.21 Pag.22 Pag.23
Pag.24 Pag.25 Pag.26 Pag.27 Pag.28 Pag.29 Pag.30 Pag.31
Pag.32 Pag.33

Nr. de articole la aceasta sectiune: 1951, afisate in 33 pagini.



ieri 05:07 CITATUL ZILEI