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 formula_2, kuzatish jarayonining qiymatlarini hisobga olgan holdagi qiymati formula_3 istalgan vaqtda "k" qadam. Barcha Bayes hisob-kitoblari formula_2 orqa zichlikdan kelib chiqadi formula_5 . 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 formula_6 . Signal-kuzatish modeli. Zarrachalar usullari koʻpincha formula_2 qiymatni taxmin qiladiva kuzatishlar formula_8 Ushbu shaklda modellashtirish mumkin: Ushbu xususiyatlarga ega tizimga misol: qayerda ikkalasi formula_26 va formula_27 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 formula_26 va formula_27 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 formula_2 , Markov zanjiri tomonidan formula_31 va shaklning virtual kuzatuvini joriy etish quyidagicha mustaqil tasodifiy oʻzgaruvchilarning ayrim ketma-ketligi uchun formula_33 maʼlum ehtimollik zichligi funksiyalari bilan aniqlanadi. Asosiy gʻoya buni kuzatishdir yaʼni Nochiziqli filtrlash tenglamasi. Shartli ehtimollik uchun Bayes qoidasi : qayerda &\stackrel{\text{prediction}}{\longrightarrow}p (x_{k+1}|y_0,\cdots, y_k)=\int p (x_{k+1}|x_k) p (x_k|y_0,\cdots, y_k) dx_k Feynman-Kac formulasi. Biz vaqt gorizonti n va kuzatishlar ketma-ketligini tuzamiz formula_37 va har bir "k" = 0, ..., "n" uchun biz quyidagilarni oʻrnatamiz: Bu belgida, traektoriyalar toʻplami boʻyicha har qanday cheklangan "F" funksiyasi uchun formula_2 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 formula_42 va formula_43 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: