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:

${\begin{array}{cccccccccc}X_{0}&\to &X_{1}&\to &X_{2}&\to &X_{3}&\to &\cdots &{\text{signal}}\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{observation}}\end{array}}$

filtrlash muammosi yashirin holatlarning qiymatlarini ketma-ket baholash $X_{k}$, kuzatish jarayonining qiymatlarini hisobga olgan holdagi qiymati $Y_{0},\cdots ,Y_{k},$ istalgan vaqtda k qadam.

Barcha Bayes hisob-kitoblari $X_{k}$ orqa zichlikdan kelib chiqadi $p(x_{k}|y_{0},y_{1},...,y_{k})$ . 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 $p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})$ .

Signal-kuzatish modeli

Zarrachalar usullari koʻpincha $X_{k}$ qiymatni taxmin qiladiva kuzatishlar $Y_{k}$ Ushbu shaklda modellashtirish mumkin:

• $X_{0},X_{1},\cdots$ Markov jarayonidir $\mathbb {R} ^{d_{x}}$ (baʼzilar uchun $d_{x}\geqslant 1$) oʻtish ehtimoli zichligiga koʻra rivojlanadi $p(x_{k}|x_{k-1})$ . Ushbu model ham koʻpincha sintetik tarzda yoziladi

  $X_{k}|X_{k-1}=x_{k}\sim p(x_{k}|x_{k-1})$

dastlabki ehtimollik zichligi bilan $p(x_{0})$ .

• Kuzatishlar $Y_{0},Y_{1},\cdots$ baʼzi shtat maydonidagi qiymatlarni qabul qilish $\mathbb {R} ^{d_{y}}$ (baʼzilar uchun $d_{y}\geqslant 1$) va shartli ravishda mustaqildirlar $X_{0},X_{1},\cdots$ maʼlum. Boshqacha aytganda, har biri $Y_{k}$ faqat bogʻliq $X_{k}$ . Bundan tashqari, biz shartli taqsimlashni nazarda tutamiz $Y_{k}$ berilgan $X_{k}=x_{k}$ mutlaq uzluksiz va sintetik tarzda bizda mavjud

  $Y_{k}|X_{k}=y_{k}\sim p(y_{k}|x_{k})$

Ushbu xususiyatlarga ega tizimga misol:

$X_{k}=g(X_{k-1})+W_{k-1}$

$Y_{k}=h(X_{k})+V_{k}$

qayerda ikkalasi $W_{k}$ va $V_{k}$ 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 $W_{k}$ va $V_{k}$ 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 $X_{k}$ , Markov zanjiri tomonidan ${\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)$ va shaklning virtual kuzatuvini joriy etish quyidagicha

${\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]$

mustaqil tasodifiy oʻzgaruvchilarning ayrim ketma-ketligi uchun ${\mathcal {V}}_{k}$ maʼlum ehtimollik zichligi funksiyalari bilan aniqlanadi. Asosiy gʻoya buni kuzatishdir yaʼni

${\text{Law}}\left(X_{k}|{\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k}\right)\approx _{\epsilon \downarrow 0}{\text{Law}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}=y_{k}\right)$

Nochiziqli filtrlash tenglamasi

Shartli ehtimollik uchun Bayes qoidasi :

$p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})}{p(y_{0},\cdots ,y_{k})}}$

qayerda

${\begin{aligned}p(y_{0},\cdots ,y_{k})&=\int p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})dx_{0}\cdots dx_{k}\\p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})&=\prod _{l=0}^{k}p(y_{l}|x_{l})\\p(x_{0},\cdots ,x_{k})&=p_{0}(x_{0})\prod _{l=1}^{k}p(x_{l}|x_{l-1})\end{aligned}}$

Feynman-Kac formulasi

Biz vaqt gorizonti n va kuzatishlar ketma-ketligini tuzamiz $Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}$ va har bir k = 0, ..., n uchun biz quyidagilarni oʻrnatamiz:

$G_{k}(x_{k})=p(y_{k}|x_{k}).$

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

${\begin{aligned}\int F(x_{0},\cdots ,x_{n})p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n})dx_{0}\cdots dx_{n}&={\frac {\int F(x_{0},\cdots ,x_{n})\left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}{\int \left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}}\\&={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}\end{aligned}}$

Genealogik daraxtga asoslangan zarrachalarni tekislash

Ajdodlar yoʻlini oʻtmishda izlash

$\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right),\quad \left(\xi _{0,k}^{i},\xi _{1,k}^{i},\cdots ,\xi _{k-1,k}^{i},\xi _{k,k}^{i}\right)$

shaxslardan ${\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)$ va $\xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)$ har bir vaqt k qadamida bizda zarrachalarning yaqinlashuvlari ham mavjud

${\begin{aligned}{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\ \\{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k-1})dx_{0},\cdots ,dx_{k}\end{aligned}}$

Bu empirik yaqinlashuvlar zarracha integral yaqinliklariga ekvivalentdir

${\begin{aligned}\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\ \\\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\end{aligned}}$

Ehtimollik funksiyalarining xolis zarracha baholari

Biz ushbu formuladan foydalanamiz

$p(y_{0},\cdots ,y_{n})=\prod _{k=0}^{n}p(y_{k}|y_{0},\cdots ,y_{k-1})$

bilan

$p(y_{k}|y_{0},\cdots ,y_{k-1})=\int p(y_{k}|x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})$

Orqaga zarrachalar silliqlash

Bayes qoidasidan foydalanib, biz formulaga egamiz

$p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n-1})=p(x_{n}|y_{0},\cdots ,y_{n-1})p(x_{n-1}|x_{n},y_{0},\cdots ,y_{n-1})\cdots p(x_{1}|x_{2},y_{0},y_{1})p(x_{0}|x_{1},y_{0})$

Eʼtibor bering

${\begin{aligned}p(x_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))&\propto p(x_{k}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-1}))\\p(x_{k-1}|(y_{0},\cdots ,y_{k-1})&\propto p(y_{k-1}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-2})\end{aligned}}$

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

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