Vés al contingut

Seqüencial de Montecarlo

De la Viquipèdia, l'enciclopèdia lliure
Exemple de filtre de partícules petit

Els filtres de partícules, o mètodes seqüencials de Montecarlo, són un conjunt d'algorismes de Montecarlo utilitzats per trobar solucions aproximades per a problemes de filtratge de sistemes d'espai d'estats no lineals, com ara el processament de senyals i la inferència estadística bayesiana.[1] El problema de filtratge consisteix a estimar els estats interns en sistemes dinàmics quan es fan observacions parcials i hi ha pertorbacions aleatòries tant en els sensors com en el sistema dinàmic. L'objectiu és calcular les distribucions posteriors dels estats d'un procés de Màrkov, ateses les observacions sorolloses i parcials. El terme "filtres de partícules" va ser encunyat per primera vegada l'any 1996 per Pierre Del Moral sobre els mètodes de partícules que interaccionen amb el camp mitjà utilitzats en mecànica de fluids des de principis dels anys seixanta.[2] El terme "Montcarlo seqüencial" va ser encunyat per Jun S. Liu i Rong Chen el 1998.[3]

Un exemple d'un robot que utilitza un filtre de partícules per localitzar-se en un mapa donades observacions acumulades incompletes.

El filtratge de partícules utilitza un conjunt de partícules (també anomenades mostres) per representar la distribució posterior d'un procés estocàstic donades les observacions sorolloses i/o parcials. El model d'espai d'estats pot ser no lineal i l'estat inicial i les distribucions de soroll poden prendre qualsevol forma requerida. Les tècniques de filtre de partícules proporcionen una metodologia ben establerta [4][5][6] per generar mostres a partir de la distribució requerida sense requerir supòsits sobre el model d'espai d'estats o les distribucions d'estats. Tanmateix, aquests mètodes no funcionen bé quan s'apliquen a sistemes de dimensions molt altes.

Els filtres de partícules actualitzen la seva predicció de manera aproximada (estadística). Les mostres de la distribució estan representades per un conjunt de partícules; cada partícula té un pes de probabilitat assignat que representa la probabilitat que aquesta partícula sigui mostrejada a partir de la funció de densitat de probabilitat. La disparitat de pes que condueix al col·lapse del pes és un problema comú que es troba en aquests algorismes de filtrat. No obstant això, es pot mitigar mitjançant la inclusió d'un pas de mostreig abans que els pesos siguin desiguals. Es poden utilitzar diversos criteris de remuestreig adaptatiu incloent la variància dels pesos i l'entropia relativa respecte a la distribució uniforme.[7] En l'etapa de remuestreig, les partícules amb pesos insignificants es substitueixen per partícules noves a la proximitat de les partícules amb pesos més elevats.

Des del punt de vista estadístic i probabilístic, els filtres de partícules es poden interpretar com a interpretacions de partícules de camp mitjà de mesures de probabilitat de Feynman-Kac.[8][9][10][11][12] Aquestes tècniques d'integració de partícules van ser desenvolupades en química molecular i física computacional per Theodore E. Harris i Herman Kahn el 1951, Marshall N. Rosenbluth i Arianna W. Rosenbluth el 1955,[13] i més recentment per Jack H. Hetherington el 1984.[14] En física computacional, aquests mètodes d'integració de partícules de camí de tipus Feynman-Kac també s'utilitzen en Montecarlo quàntic, i més concretament en els mètodes de Montecarlo de difusió.[15][16][17] Els mètodes de partícules d'interacció Feynman-Kac també estan fortament relacionats amb els algorismes genètics de selecció de mutacions que s'utilitzen actualment en la computació evolutiva per resoldre problemes d'optimització complexos.

La metodologia del filtre de partícules s'utilitza per resoldre problemes del del model de Màrkov ocult (HMM) i de filtratge no lineal. Amb l'excepció notable dels models d'observació de senyals lineals gaussians (filtre de Kalman) o classes més àmplies de models (filtre de Benes [18]), Mireille Chaleyat-Maurel i Dominique Michel van demostrar el 1984 que la seqüència de distribucions posteriors dels estats aleatoris de un senyal, donades les observacions (també conegut com a filtre òptim), no té recursivitat finita.[19] Altres mètodes numèrics basats en aproximacions de quadrícula fixa, tècniques de Montecarlo de cadena de Màrkov, linealització convencional, filtres de Kalman estès o la determinació del millor sistema lineal (en el sentit de cost-error esperat) són incapaços de fer front a sistemes a gran escala, processos inestables., o no linealitats insuficientment suaus.

Els filtres de partícules i les metodologies de partícules Feynman-Kac troben aplicació en processament de senyals i imatges, inferència bayesiana, aprenentatge automàtic, anàlisi de riscos i mostreig d'esdeveniments rars, enginyeria i robòtica, intel·ligència artificial, bioinformàtica,[20] filogenètica, ciència computacional, economia i finances matemàtiques., química molecular, física computacional, farmacocinètica i altres camps.

El problema del filtratge

[modifica]

L'objectiu d'un filtre de partícules és estimar la densitat posterior de les variables d'estat donades les variables d'observació. El filtre de partícules està pensat per utilitzar-lo amb un model de Màrkov ocult, en el qual el sistema inclou variables ocultes i observables. Les variables observables (procés d'observació) estan vinculades a les variables ocultes (procés d'estat) mitjançant una forma funcional coneguda. De la mateixa manera, es coneix la descripció probabilística del sistema dinàmic que defineix l'evolució de les variables d'estat.

Un filtre de partícules genèric estima la distribució posterior dels estats ocults mitjançant el procés de mesura d'observació. Pel que fa a un espai d'estats com el següent:

el problema de filtratge és estimar seqüencialment els valors dels estats ocults , donats els valors del procés d'observació en qualsevol moment pas k.

Aplicacions

[modifica]

Els filtres de partícules i les metodologies de partícules Feynman-Kac troben aplicació en diversos contextos, com a mitjà eficaç per abordar observacions sorolloses o no linealitats fortes, com ara:

Referències

[modifica]
  1. Wills, Adrian G.; Schön, Thomas B. (en anglès) Annual Review of Control, Robotics, and Autonomous Systems, 6, 1, 03-05-2023, pàg. 159–182. DOI: 10.1146/annurev-control-042920-015119. ISSN: 2573-5144 [Consulta: free].
  2. Del Moral, Pierre Markov Processes and Related Fields, 2, 4, 1996, pàg. 555–580.
  3. Liu, Jun S.; Chen, Rong Journal of the American Statistical Association, 93, 443, 01-09-1998, pàg. 1032–1044. DOI: 10.1080/01621459.1998.10473765. ISSN: 0162-1459.
  4. Del Moral, Pierre Markov Processes and Related Fields, 2, 4, 1996, pàg. 555–580.
  5. Del Moral, Pierre Annals of Applied Probability, 8, 2, 1998, pàg. 438–495. DOI: 10.1214/aoap/1028903535 [Consulta: free].
  6. Del Moral, Pierre. Feynman-Kac formulae. Genealogical and interacting particle approximations.. Springer. Series: Probability and Applications, 2004, p. 556. ISBN 978-0-387-20268-6. 
  7. Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay Bernoulli, 18, 1, 2012, pàg. 252–278. DOI: 10.3150/10-bej335 [Consulta: free].
  8. Del Moral, Pierre. Feynman-Kac formulae. Genealogical and interacting particle approximations (en anglès). Springer, 2004, p. 575 (Probability and its Applications). ISBN 9780387202686. 
  9. Del Moral, Pierre. «Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering». A: Jacques Azéma. Séminaire de Probabilités XXXIV. 1729, 2000, p. 1–145 (Lecture Notes in Mathematics). DOI 10.1007/bfb0103798. ISBN 978-3-540-67314-9. 
  10. Del Moral, Pierre; Miclo, Laurent Stochastic Processes and Their Applications, 86, 2, 2000, pàg. 193–216. DOI: 10.1016/S0304-4149(99)00094-0.
  11. Del Moral, Pierre. Mean field simulation for Monte Carlo integration (en anglès). Chapman & Hall/CRC Press, 2013, p. 626. 
  12. Moral, Piere Del; Doucet, Arnaud ESAIM: Proc., 44, 2014, pàg. 1–46. DOI: 10.1051/proc/201444001 [Consulta: lliure].
  13. Rosenbluth, Marshall, N.; Rosenbluth, Arianna, W. J. Chem. Phys., 23, 2, 1955, pàg. 356–359. Bibcode: 1955JChPh..23..356R. DOI: 10.1063/1.1741967 [Consulta: lliure].
  14. Hetherington, Jack, H. Phys. Rev. A, 30, 2713, 1984, pàg. 2713–2719. Bibcode: 1984PhRvA..30.2713H. DOI: 10.1103/PhysRevA.30.2713.
  15. Del Moral, Pierre ESAIM Probability & Statistics, 7, 2003, pàg. 171–208. DOI: 10.1051/ps:2003001 [Consulta: free].
  16. Assaraf, Roland; Caffarel, Michel; Khelif, Anatole «Còpia arxivada». Phys. Rev. E, 61, 4, 2000, pàg. 4566–4575. Arxivat de l'original el 2014-11-07. Bibcode: 2000PhRvE..61.4566A. DOI: 10.1103/physreve.61.4566. PMID: 11088257 [Consulta: 4 novembre 2023].
  17. Caffarel, Michel; Ceperley, David; Kalos, Malvin Phys. Rev. Lett., 71, 13, 1993, pàg. 2159. Bibcode: 1993PhRvL..71.2159C. DOI: 10.1103/physrevlett.71.2159. PMID: 10054598.
  18. Ocone, D. L. Stochastic Analysis and Applications, 17, 6, 01-01-1999, pàg. 1053–1074. DOI: 10.1080/07362999908809648. ISSN: 0736-2994.
  19. Maurel, Mireille Chaleyat; Michel, Dominique Stochastics, 13, 1–2, 01-01-1984, pàg. 83–102. DOI: 10.1080/17442508408833312. ISSN: 0090-9491.
  20. Hajiramezanali, Ehsan; Imani, Mahdi; Braga-Neto, Ulisses; Qian, Xiaoning; Dougherty, Edward R. BMC Genomics, 20, Suppl 6, 2019, pàg. 435. arXiv: 1902.03188. Bibcode: 2019arXiv190203188H. DOI: 10.1186/s12864-019-5720-3. PMC: 6561847. PMID: 31189480 [Consulta: free].