Zarrachalar filtri

Zarrachalar filtrlari yoki ketma-ket Monte-Karlo usullari - signalni qayta ishlash va Bayes statistik xulosasi kabi chiziqli boʻlmagan holat-kosmik tizimlar uchun filtrlash muammolari uchun taxminiy yechimlarni topish uchun ishlatiladigan Monte-Karlo algoritmlari toʻplami hisoblanadi. Filtrlash muammosi qisman kuzatishlar olib borilganda va sensorlarda, shuningdek dinamik tizimda tasodifiy buzilishlar mavjud boʻladigan holatlar dinamik tizimlardagi ichki holatlarni baholashdan iborat. Maqsad shovqinli va qisman kuzatuvlarni hisobga olgan holda Markov jarayoni holatining posterior taqsimotini hisoblashdir. "Zarracha filtrlari" atamasi birinchi marta 1996-yilda Per Del Moral tomonidan kiritilgan boʻlib,1960-yillarning boshidan suyuqlik mexanikasida qoʻllanadigan oʻrtacha maydon oʻzaro taʼsir qiluvchi zarrachalar usullari haqida kiritilgan. Keyinchalik "Sequential Monte Carlo" atamasi 1998-yilda Jun S. Liu va Rong Chen tomonidan kiritilgan

Zarrachalarni filtrlash shovqinli va/yoki qisman kuzatuvlarni hisobga olgan holda stokastik jarayonning posterior taqsimotini ifodalash uchun zarralar toʻplamidan (namunalar deb ham ataladi) foydalanadi. Holat-kosmos modeli chiziqli boʻlmagan boʻlishi mumkin va boshlangʻich holat va shovqin taqsimoti talab qilinadigan har qanday shaklni olishi mumkin. Zarrachalarni filtrlash texnikasi davlat-kosmik modeli yoki holat taqsimoti haqida taxminlarni talab qilmasdan kerakli taqsimotdan namunalar yaratish uchun yaxshi oʻrnatilgan metodologiyani taʼminlaydi. 

Zarrachalar filtrlari oʻzlarining bashoratlarini taxminiy (statistik) tarzda yangilaydi. Tarqatishdan olingan namunalar zarrachalar toʻplami bilan ifodalanadi; har bir zarrachaga tayinlangan ehtimollik ogʻirligi mavjud boʻlib, u zarrachaning ehtimollik zichligi funksiyasidan namuna olish ehtimolini ifodalaydi. Ogʻirlikning pasayishiga olib keladigan vazn nomutanosibligi ushbu filtrlash algoritmlarida tez-tez uchraydigan muammodir. Biroq, ogʻirliklar notekis boʻlishidan oldin, qayta namuna olish bosqichini kiritish orqali uni yumshatish mumkin. Bir nechta moslashtirilgan qayta namuna olish mezonlaridan foydalanish mumkin, shu jumladan ogʻirliklarning oʻzgarishi va bir xil taqsimotga tegishli nisbiy entropiya . 

Statistik va ehtimollik nuqtai nazaridan, zarracha filtrlari Feynman-Kac ehtimollik oʻlchovlarining oʻrtacha maydon zarracha talqini sifatida talqin qilinishi ham mumkin. Ushbu zarrachalarni integratsiyalash usullari molekulyar kimyo va elementar zarrachalar hisoblash fizikasida 1951-yilda ikki fizik Teodor E. Xarris va Herman Kan, 1955-yilda Marshall N. Rozenblyut va Arianna V. Rozenblyut, va yaqinda 1984-yilda Jek X. Xeterington tomonidan ishlab chiqilgan Hisoblash fizikasida ushbu Feynman-Kac tipidagi zarrachalarni birlashtirish usullari Kvant Monte-Karloda, aniqrogʻi Diffuziya Monte-Karlo usullarida ham qoʻllanadi. Feynman-Kac oʻzaro taʼsir qiluvchi zarrachalar usullari, shuningdek, murakkab optimallashtirish muammolarini hal qilish uchun evolyutsion hisoblashda hozirda qoʻllanadigan mutatsiya-tanlash genetik algoritmlari bilan kuchli bogʻliq boʻladi.

Zarrachalarni filtrlash metodologiyasi Yashirin Markov Modeli (HMM) va chiziqli boʻlmagan filtrlash muammolarini hal qilish uchun ishlatiladi. Chiziqli-Gauss signal-kuzatish modellari (Kalman filtri) yoki modellarning kengroq sinflari (Benes filtri)ni isbotlashdan  tashqari, Mirey Chaleyat-Maurel va Dominik Mishel 1984-yilda tasodifiy holatlarning posterior taqsimoti ketma-ketligini isbotladilar. Berilgan kuzatishlarda yaʼni optimal filtr berilgan signalda chekli rekursiya yoʻq. Ruxsat etilgan tarmoqni taxmin qilish, Markov zanjiri Monte-Karlo texnikasi, anʼanaviy chiziqlilashtirish, kengaytirilgan Kalman filtrlari yoki eng yaxshi chiziqli tizimni aniqlash (kutilayotgan xarajat-xato maʼnosida) keng koʻlamli tizimlar, beqaror jarayonlar bilan kurashishga qodir emas., yoki etarli darajada silliq boʻlmagan chiziqli.

Zarrachalar filtrlari va Feynman-Kac zarrachalar metodologiyasi signal va tasvirni qayta ishlash, Bayes xulosasi, mashinani oʻrganish, xavf tahlili va noyob hodisalardan namuna olish, muhandislik va robototexnika, sunʼiy intellekt, bioinformatika, filogenetika, hisoblash fanlari, iqtisod va matematika moliyasida ham keng qoʻllanadi., bundan tashqari molekulyar kimyo, hisoblash fizikasi, farmakokinetika va boshqa sohalarda ham.

Tarixi

Evristik algoritmlar 
Statistik va ehtimollik nuqtai nazaridan, zarracha filtrlari tarmoqlanuvchi / genetik turdagi algoritmlar va oʻrtacha maydon tipidagi oʻzaro taʼsir qiluvchi zarrachalar metodologiyalari sinfiga kiradi. Ushbu zarracha usullarini talqin qilish ilmiy intizomga bogʻliqdir. Evolyutsion hisoblashda oʻrtacha maydon genetik tipidagi zarrachalar metodologiyalari koʻpincha evristik va tabiiy qidiruv algoritmlari sifatida ishlatiladi Metaevristik). Hisoblash fizikasi va molekulyar kimyoda evristik algaritmlar Feynman-Kac yoʻlini integratsiyalash muammolarini hal qilish yoki Boltsmann-Gibbs oʻlchovlari, eng yuqori xos qiymatlari va Shredinger operatorlarining asosiy holatlarini hisoblash uchun ishlatiladi. Biologiya va genetikada ular baʼzi bir muhitda individlar yoki genlar populyatsiyasining evolyutsiyasini ham ifodalashi mumkin.

Biologiya va genetikada avstraliyalik genetik Aleks Freyzer 1957-yilda organizmlarning sunʼiy tanlanishining genetik turini simulyatsiya qilish boʻyicha bir qator maqolalarni nashr etdi. Biologlar tomonidan evolyutsiyani kompyuter simulyatsiyasi 1960-yillarning boshlarida keng tarqalgan va usullar Freyzer va Burnel (1970) va Krosbi (1973) kitoblarida tasvirlangan. Freyzerning simulyatsiyalari zamonaviy mutatsiya-tanlash genetik zarrachalar algoritmlarining barcha muhim elementlarini oʻz ichiga olgan.Matematik nuqtai nazardan, baʼzi bir qisman va shovqinli kuzatuvlar berilgan signalning tasodifiy holatlarining shartli taqsimlanishi ehtimollik potentsial funksiyalari ketma-ketligi bilan ogʻirlikdagi signalning tasodifiy traektoriyalari boʻyicha Feynman-Kac ehtimolligi bilan tavsiflanadi. Kvant Monte-Karlo va aniqrogʻi, Diffuziya Monte-Karlo usullari, shuningdek, Feynman-Kac yoʻl integrallarining oʻrtacha maydon genetik turi zarrachalar yaqinlashishi sifatida talqin qilinishi mumkin. Kvant Monte-Karlo usullarining kelib chiqishi koʻpincha Enriko Fermi va Robert Richtmyer bilan bogʻliq boʻlib, ular 1948-yilda neytron zanjiri reaksiyalarining oʻrtacha maydon zarrachalari talqinini ishlab chiqdilar, lekin birinchi evristik va genetik turdagi zarrachalar algoritmi (aka) Kvant tizimlarining asosiy holat energiyalarini (kamaytirilgan matritsali modellarda) baholash uchun qayta namunalangan yoki qayta konfiguratsiya qilingan Monte-Karlo usullari) 1984-yilda Jek X. Xeterington tomonidan amalga oshirilgan Shuningdek, Teodor E. Xarris va Herman Kanning zarrachalar fizikasi boʻyicha 1951-yilda nashr etilgan, zarracha uzatish energiyasini baholash uchun oʻrtacha maydon, lekin evristik genetik usullardan foydalangan holda oldingi muhim ishlaridan iqtibos keltirish mumkin. Molekulyar kimyoda genetik evristik oʻxshash zarrachalar metodologiyalaridan foydalanish (aka kesish va boyitish strategiyalari) 1955-yilda Marshallning asosiy ishi bilan kuzatilishi mumkin. N. Rosenbluth va Arianna. V. Rozenblut. Ilgʻor signallarni qayta ishlash va Bayes xulosasida genetik zarrachalar algoritmlaridan foydalanish yaqinroqdir. 1993-yil yanvar oyida Genshiro Kitagava "Monte-Karlo filtrini" ishlab chiqdi, ushbu maqolaning biroz oʻzgartirilgan versiyasi 1996-yilda paydo boʻldi 1993-yil aprel oyida Gordon va boshqalar oʻzlarining asosiy ishlarida Bayes statistik xulosasida genetik turdagi algoritmni qoʻllashni nashr etdilar. Mualliflar oʻzlarining algoritmlarini "bootstrap filter" deb nomladilar va boshqa filtrlash usullari bilan solishtirganda ularning yuklash algoritmi ushbu holat maydoni yoki tizim shovqini haqida hech qanday taxminni talab qilmasligini koʻrsatdi. Mustaqil ravishda, Per Del Moral va Ximilkon Karvalyo, Per Del Moral, Andre Monin va Jerar Salut tomonidan 1990-yillarning oʻrtalarida nashr etilgan zarracha filtrlari boʻyicha. Zarrachalar filtrlari 1989-1992 yillar boshida signalni qayta ishlashda P. Del Moral, JC Noyer, G. Rigal va G. Salut tomonidan LAAS-CNRSda STCAN (Service Technique des) bilan cheklangan va tasniflangan bir qator tadqiqot hisobotlarida ishlab chiqilgan. Constructions et Armes Navales), IT kompaniyasi DIGILOG va LAAS-CNRS (Tizimlar tahlili va arxitekturasi laboratoriyasi) RADAR/SONAR va GPS signallarini qayta ishlash muammolari.

Matematik asoslar 
1950-yildan 1996-yilgacha zarrachalar filtrlari va genetik algoritmlarga oid barcha nashrlar, shu jumladan hisoblash fizikasi va molekulyar kimyoda joriy qilingan Monte-Karlo usullarini kesish va qayta namunalash, ularning izchilligining yagona isbotisiz turli vaziyatlarga qoʻllanadigan tabiiy va evristik algoritmlarni taqdim etadi., shuningdek, hisob-kitoblarning notoʻgʻriligi va genealogik va ajdodlar daraxtiga asoslangan algoritmlar haqida munozara ham yoʻq. Ushbu zarracha algoritmlarining matematik asoslari va birinchi qatʼiy tahlili 1996-yilda Per Del Moral tomonidan amalga oshirilgan. Maqolada, shuningdek, zarrachaning ehtimollik funksiyalarining yaqinlashuvi va normallashtirilmagan shartli ehtimollik oʻlchovlarining xolis xususiyatlarining isboti mavjud. Ushbu maqolada keltirilgan ehtimollik funksiyalarining xolis zarracha baholovchisi bugungi kunda Bayes statistik xulosasida qoʻllanadi.

Den Crisan, Jessica Gaines va Terri Lyons, shuningdek, Den Crisan, Per Del Moral va Terri Lyons 2001-yilning oxirlarida har xil populyatsiya kattaligiga ega boʻlgan shoxlangan zarrachalar texnikasini birgalikda yaratdilar. 1990-yillar. P. Del Moral, A. Guionnet va L. Miklo 2000-yilda bu borada koʻproq yutuqlarga erishdilar. Birinchi markaziy chegara teoremalarini Per Del Moral va Elis Guionnet 1999-yilda, Per Del Moral va Loran Miklo 2000-yilda isbotladilar. Zarrachalar filtrlari uchun vaqt parametri boʻyicha birinchi yagona yaqinlashuv natijalari 1990-yillarning oxirida Per Del Moral va Elis Guionnet tomonidan bir qancha kuzatuvlar natijasida ishlab chiqilgan. Genealogik daraxtga asoslangan zarracha filtri silliqlash vositalarining birinchi qatʼiy tahlili 2001-yilda P. Del Moral va L. Miklo tomonidan amalga oshirilgan.

Filtrlash muammosi

Maqsad 
Zarrachalar filtrining maqsadi kuzatuv oʻzgaruvchilari berilgan holat oʻzgaruvchilarining orqa zichligini baholashdir. Zarrachalar filtri yashirin Markov modeli bilan foydalanish uchun moʻljallangan boʻlib, unda tizim yashirin va kuzatilishi mumkin boʻlgan oʻzgaruvchilarni oʻz ichiga oladi. Kuzatish mumkin boʻlgan oʻzgaruvchilar (kuzatish jarayoni) maʼlum funktsional shakl orqali yashirin oʻzgaruvchilar (holat-jarayon) bilan bogʻlanadi. Xuddi shunday, holat oʻzgaruvchilari evolyutsiyasini aniqlaydigan dinamik tizimning ehtimollik tavsifi maʼlum. Umumiy zarrachalar filtri kuzatuvni oʻlchash jarayonidan foydalanib, yashirin holatlarning keyingi taqsimotini baholaydi. Quyidagi kabi davlat makoniga nisbatan:

 

filtrlash muammosi yashirin holatlarning qiymatlarini ketma-ket baholash , kuzatish jarayonining qiymatlarini hisobga olgan holdagi qiymati  istalgan vaqtda k qadam.

Barcha Bayes hisob-kitoblari  orqa zichlikdan kelib chiqadi  . Zarrachalarni filtrlash metodologiyasi genetik turdagi zarrachalar algoritmi bilan bogʻliq boʻlgan empirik oʻlchov yordamida ushbu shartli ehtimolliklarning taxminiyligini taʼminlaydi. Bundan farqli oʻlaroq, Markov zanjiri Monte-Karlo yoki ahamiyatli namuna olish yondashuvi toʻliq posteriorni modellashtiradi va u quyidagicha korinishga egadir  .

Signal-kuzatish modeli 
Zarrachalar usullari koʻpincha  qiymatni taxmin qiladiva kuzatishlar  Ushbu shaklda modellashtirish mumkin:

  Markov jarayonidir  (baʼzilar uchun ) oʻtish ehtimoli zichligiga koʻra rivojlanadi  . Ushbu model ham koʻpincha sintetik tarzda yoziladi
 

 dastlabki ehtimollik zichligi bilan  .

 Kuzatishlar  baʼzi shtat maydonidagi qiymatlarni qabul qilish  (baʼzilar uchun ) va shartli ravishda mustaqildirlar  maʼlum. Boshqacha aytganda, har biri  faqat bogʻliq  . Bundan tashqari, biz shartli taqsimlashni nazarda tutamiz  berilgan  mutlaq uzluksiz va sintetik tarzda bizda mavjud
 

Ushbu xususiyatlarga ega tizimga misol:

 
 

qayerda ikkalasi  va  ehtimollik zichlik funksiyalari maʼlum boʻlgan oʻzaro mustaqil ketma-ketliklar va g va h maʼlum funksiyalardir. Ushbu ikkita tenglamani holat fazosi tenglamalari sifatida koʻrish mumkin va Kalman filtri uchun holat fazosi tenglamalariga oʻxshaydi. Yuqoridagi misoldagi g va h funksiyalar chiziqli boʻlsa va ikkalasi ham boʻlsa  va  Gauss boʻlsa, Kalman filtri aniq Bayes filtrlash taqsimotini topadi. Agar yoʻq boʻlsa, Kalman filtriga asoslangan usullar birinchi darajali yaqinlashish (EKF) yoki ikkinchi darajali yaqinlashish boʻladi.

Taxminiy Bayes hisoblash modellari 
Muayyan baʼzi masalalarda kuzatuvlarni shartli taqsimlash, signalning tasodifiy holatlarini hisobga olgan holda, zichlikka ega boʻlmasligi mumkin; ikkinchisini hisoblash imkonsiz yoki juda murakkab boʻlishi mumkin. Bunday holda, qoʻshimcha darajaga yaqinlashtirish kerak. Bitta strategiya signalni almashtirishdir yaʼni  , Markov zanjiri tomonidan  va shaklning virtual kuzatuvini joriy etish quyidagicha

 

mustaqil tasodifiy oʻzgaruvchilarning ayrim ketma-ketligi uchun  maʼlum ehtimollik zichligi funksiyalari bilan aniqlanadi. Asosiy gʻoya buni kuzatishdir yaʼni

Nochiziqli filtrlash tenglamasi 
Shartli ehtimollik uchun Bayes qoidasi :

 

qayerda

Feynman-Kac formulasi 
Biz vaqt gorizonti n va kuzatishlar ketma-ketligini tuzamiz  va har bir k = 0, ..., n uchun biz quyidagilarni oʻrnatamiz:

 

Bu belgida, traektoriyalar toʻplami boʻyicha har qanday cheklangan F funksiyasi uchun  kelib chiqishi k = 0 dan k = n vaqtgacha, bizda Feynman-Kac formulasi mavjud

Genealogik daraxtga asoslangan zarrachalarni tekislash 
Ajdodlar yoʻlini oʻtmishda izlash

 

shaxslardan  va  har bir vaqt k qadamida bizda zarrachalarning yaqinlashuvlari ham mavjud

 

Bu empirik yaqinlashuvlar zarracha integral yaqinliklariga ekvivalentdir

Ehtimollik funksiyalarining xolis zarracha baholari 
Biz ushbu formuladan foydalanamiz

 

bilan

Orqaga zarrachalar silliqlash 
Bayes qoidasidan foydalanib, biz formulaga egamiz

 

Eʼtibor bering

Ilovalar 
Zarrachalar filtrlari va Feynman-Kac zarrachalar metodologiyasi shovqinli kuzatuvlar yoki kuchli chiziqli boʻlmagan holatlarga qarshi kurashish uchun samarali vosita sifatida bir nechta kontekstlarda qoʻllanishi mumkin, masalan:

 Bayes xulosasi, mashinani oʻrganish, xavf tahlili va kamdan-kam uchraydigan hodisalar namunasi
 Bioinformatika
 Hisoblash fani
 Iqtisodiyot, moliyaviy matematika va matematik moliya : zarracha filtrlari makroiqtisodiyotdagi dinamik stokastik umumiy muvozanat modellari va optsion bahosi kabi muammolar bilan bogʻliq yuqori oʻlchamli va/yoki murakkab integrallarni hisoblash uchun zarur boʻlgan simulyatsiyalarni amalga oshirishi mumkin
 Muhandislik
 Xatolarni aniqlash va izolyatsiya qilish : kuzatuvchiga asoslangan sxemalarda zarracha filtri nosozliklarni izolyatsiya qilishga imkon beruvchi kutilgan sensorlar chiqishini bashorat qilishi mumkin
 Molekulyar kimyo va hisoblash fizikasi
 Farmakokinetika
 Filogenetika
 Robototexnika, sunʼiy intellekt : Monte-Karlo mahalliylashtirish mobil robotlarni lokalizatsiya qilishda de-fakto standartdir
 Signal va tasvirni qayta ishlash : vizual lokalizatsiya, kuzatish, xususiyatlarni aniqlash

Boshqa zarracha filtrlari 

 Yordamchi zarrachalar filtri
 Xarajatlar boʻyicha zarracha filtri
 Eksponensial tabiiy zarracha filtri
 Feynman-Kac va oʻrtacha maydon zarrachalari metodologiyalari
 Gauss zarracha filtri
 Gauss-Germit zarrachalar filtri
 Ierarxik/Malajlanadigan zarrachalar filtri
 Qoʻzgʻaluvchan zarrachalar filtri
 Zarracha Markov-Chain Monte-Karlo, qarang, masalan, pseudo-marginal Metropolis-Xastings algoritmi.
 Rao – qoralangan zarracha filtri
 Oddiy yordamchi zarrachalar filtri
 Rad etish-namuna olishga asoslangan optimal zarracha filtri
 Hidsiz zarrachalar filtri

Yana qarang 

 Kalman ansambli filtri
 Umumiy filtrlash
 Genetik algoritm
 Oʻrtacha maydonli zarrachalar usullari
 Monte-Karlo mahalliylashtirish
 Harakatlanuvchi ufqni baholash
 Rekursiv Bayes bahosi

Manbalar

Havolalar 
 
 Feynman–Kac models and interacting particle algorithms (a.k.a. Particle Filtering) Theoretical aspects and a list of application domains of particle filters
 Sequential Monte Carlo Methods (Particle Filtering) homepage on University of Cambridge
 Dieter Fox's MCL Animations
 Rob Hess' free software
 SMCTC: A Template Class for Implementing SMC algorithms in C++
 Java applet on particle filtering
 vSMC : Vectorized Sequential Monte Carlo
 Particle filter explained in the context of self driving car

Pages with unreviewed translations