कण फिल्टर

This article is about mathematical algorithms. For devices to filter particles from air, see Air filter.

कण फिल्टर, या अनुक्रमिक मोंटे कार्लो विधियां, मोंटे कार्लो विधि एल्गोरिदम का सेट है जिसका उपयोग सिग्नल प्रोसेसिंग और बायेसियन अनुमान जैसे गैर-रेखीय राज्य-अंतरिक्ष प्रणालियों के लिए फ़िल्टरिंग समस्या (स्टोकेस्टिक प्रक्रियाओं) के लिए अनुमानित समाधान खोजने के लिए किया जाता है। फ़िल्टरिंग समस्या (स्टोकेस्टिक प्रक्रियाएं) में गतिशील प्रणालियों में आंतरिक स्थितियों का अनुमान लगाना शामिल है जब आंशिक अवलोकन किए जाते हैं और सेंसर के साथ-साथ गतिशील प्रणाली में यादृच्छिक गड़बड़ी मौजूद होती है। इसका उद्देश्य शोर और आंशिक टिप्पणियों को देखते हुए, मार्कोव प्रक्रिया की स्थिति की पिछली संभावना की गणना करना है। कण फिल्टर शब्द पहली बार 1996 में पियरे डेल मोरल द्वारा माध्य-क्षेत्र कण विधियों के बारे में गढ़ा गया था। 1960 के दशक की शुरुआत से द्रव यांत्रिकी में उपयोग किए जाने वाले माध्य-क्षेत्र अंतःक्रियात्मक कण तरीकों के बारे में। अनुक्रमिक मोंटे कार्लो शब्द 1998 में जून एस. लियू और रोंग चेन द्वारा गढ़ा गया था। कण फ़िल्टरिंग शोर और/या आंशिक अवलोकनों को देखते हुए स्टोकेस्टिक प्रक्रिया के पीछे के वितरण का प्रतिनिधित्व करने के लिए कणों के सेट (जिसे नमूने भी कहा जाता है) का उपयोग करता है। राज्य-अंतरिक्ष मॉडल अरेखीय हो सकता है और प्रारंभिक स्थिति और शोर वितरण आवश्यक कोई भी रूप ले सकता है। कण फ़िल्टर तकनीकें सुस्थापित पद्धति प्रदान करती हैं राज्य-अंतरिक्ष मॉडल या राज्य वितरण के बारे में धारणाओं की आवश्यकता के बिना आवश्यक वितरण से नमूने उत्पन्न करने के लिए। हालाँकि, बहुत उच्च-आयामी प्रणालियों पर लागू होने पर ये विधियाँ अच्छा प्रदर्शन नहीं करती हैं।

कण फ़िल्टर अपनी भविष्यवाणी को अनुमानित (सांख्यिकीय) तरीके से अपडेट करते हैं। वितरण से नमूने कणों के सेट द्वारा दर्शाए जाते हैं; प्रत्येक कण को ​​एक संभाव्यता भार सौंपा गया है जो संभाव्यता घनत्व फ़ंक्शन से उस कण के नमूने लिए जाने की संभावना को दर्शाता है। वजन में असमानता के कारण वजन कम होना इन फ़िल्टरिंग एल्गोरिदम में आने वाली आम समस्या है। हालाँकि, वजन के असमान होने से पहले पुनः नमूनाकरण चरण को शामिल करके इसे कम किया जा सकता है। वजन के विचरण और समान वितरण से संबंधित सापेक्ष एन्ट्रापी सहित कई अनुकूली पुन: नमूनाकरण मानदंडों का उपयोग किया जा सकता है। पुन: नमूनाकरण चरण में, नगण्य भार वाले कणों को उच्च भार वाले कणों की निकटता में नए कणों द्वारा प्रतिस्थापित किया जाता है।

सांख्यिकीय और संभाव्य दृष्टिकोण से, कण फिल्टर की व्याख्या माध्य-क्षेत्र कण विधियों के रूप में की जा सकती है|फेनमैन-केएसी सूत्र की माध्य-क्षेत्र कण व्याख्या|फेनमैन-केएसी संभाव्यता उपाय। इन कण एकीकरण तकनीकों को आणविक रसायन विज्ञान और कम्प्यूटेशनल भौतिकी में टेड हैरिस (गणितज्ञ)|थियोडोर ई. हैरिस और हरमन कहन द्वारा 1951 में, मार्शल रोसेनब्लुथ|मार्शल एन. रोसेनब्लुथ और एरियाना डब्ल्यू. रोसेनब्लुथ द्वारा 1955 में विकसित किया गया था। और हाल ही में 1984 में जैक एच. हेदरिंगटन द्वारा।कम्प्यूटेशनल भौतिकी में, इन फेनमैन-केएसी प्रकार पथ कण एकीकरण विधियों का उपयोग क्वांटम मोंटे कार्लो और विशेष रूप से प्रसार मोंटे कार्लो में भी किया जाता है। फेनमैन-केएसी इंटरैक्टिंग कण विधियां जेनेटिक एल्गोरिद्म से भी दृढ़ता से संबंधित हैं। जटिल अनुकूलन समस्याओं को हल करने के लिए वर्तमान में विकासवादी गणना में उत्परिवर्तन-चयन आनुवंशिक एल्गोरिदम का उपयोग किया जाता है।

कण फ़िल्टर पद्धति का उपयोग छिपा हुआ मार्कोव मॉडल (एचएमएम) और अरेखीय फ़िल्टर समस्याओं को हल करने के लिए किया जाता है। रैखिक-गॉसियन सिग्नल-अवलोकन मॉडल (कलमन फ़िल्टर) या मॉडल के व्यापक वर्गों (बेन्स फ़िल्टर) के उल्लेखनीय अपवाद के साथ), मिरेइल चालेयाट-मौरेल और डोमिनिक मिशेल ने 1984 में साबित किया कि अवलोकनों (ए.के.ए. इष्टतम फ़िल्टर) को देखते हुए, सिग्नल के यादृच्छिक राज्यों के पीछे के वितरण के अनुक्रम में कोई सीमित पुनरावृत्ति नहीं होती है। निश्चित ग्रिड सन्निकटन, मार्कोव श्रृंखला मोंटे कार्लो तकनीक, पारंपरिक रैखिककरण, विस्तारित कलमन फिल्टर, या सर्वोत्तम रैखिक प्रणाली का निर्धारण (अपेक्षित लागत-त्रुटि अर्थ में) के आधार पर कई अन्य संख्यात्मक विधियां बड़े पैमाने पर सिस्टम, अस्थिर प्रक्रियाओं, या अपर्याप्त रूप से चिकनी गैर-रैखिकताओं से निपटने में असमर्थ हैं।

कण फिल्टर और फेनमैन-केएसी कण पद्धतियों का उपयोग सिग्नल प्रोसेसिंग, बायेसियन अनुमान, यंत्र अधिगम , दुर्लभ घटना नमूनाकरण, अभियांत्रिकी रोबोटिक्स, कृत्रिम बुद्धिमत्ता, जैव सूचना विज्ञान, में किया जाता है। फाइलोजेनेटिक्स, कम्प्यूटेशनल विज्ञान, अर्थशास्त्र वित्तीय गणित गणितीय वित्त, आणविक रसायन विज्ञान, कम्प्यूटेशनल भौतिकी, फार्माकोकाइनेटिक्स, और अन्य क्षेत्र।

इतिहास

अनुमानी-जैसे एल्गोरिदम

सांख्यिकीय और संभाव्य दृष्टिकोण से, कण फिल्टर शाखा प्रक्रिया/आनुवंशिक एल्गोरिदम और माध्य-क्षेत्र कण विधियों | माध्य-क्षेत्र प्रकार अंतःक्रियात्मक कण पद्धतियों के वर्ग से संबंधित हैं। इन कण विधियों की व्याख्या वैज्ञानिक अनुशासन पर निर्भर करती है। विकासवादी गणना में, माध्य-क्षेत्र कण विधियाँ | माध्य-क्षेत्र आनुवंशिक प्रकार कण पद्धतियों का उपयोग अक्सर अनुमानी और प्राकृतिक खोज एल्गोरिदम (a.k.a. मेटाह्यूरिस्टिक) के रूप में किया जाता है। कम्प्यूटेशनल भौतिकी और आणविक रसायन विज्ञान में, उनका उपयोग फेनमैन-केएसी पथ एकीकरण समस्याओं को हल करने या बोल्ट्जमैन-गिब्स उपायों, शीर्ष आइगेनवैल्यू और श्रोडिंगर समीकरण | श्रोडिंगर ऑपरेटरों की जमीनी स्थिति की गणना करने के लिए किया जाता है। जीव विज्ञान और आनुवंशिकी में, वे किसी वातावरण में व्यक्तियों या जीनों की आबादी के विकास का प्रतिनिधित्व करते हैं।

माध्य-क्षेत्र प्रकार के विकासवादी एल्गोरिदम की उत्पत्ति का पता एलन ट्यूरिंग के साथ 1950 और 1954 में लगाया जा सकता है|जेनेटिक प्रकार के उत्परिवर्तन-चयन सीखने की मशीनों पर एलन ट्यूरिंग का काम और प्रिंसटन, न्यू जर्सी में उन्नत अध्ययन संस्थान में निल्स ऑल बरीज़ के लेख। सांख्यिकी में कण फिल्टर का पहला निशान 1950 के दशक के मध्य का है; 'गरीब आदमी का मोंटे कार्लो', यह हैमरस्ले और अन्य द्वारा 1954 में प्रस्तावित किया गया था, जिसमें आज उपयोग की जाने वाली आनुवंशिक प्रकार के कण फ़िल्टरिंग विधियों के संकेत शामिल थे। 1963 में, निल्स आल बैरिकेली ने व्यक्तियों की साधारण गेम खेलने की क्षमता की नकल करने के लिए आनुवंशिक प्रकार के एल्गोरिदम का अनुकरण किया। विकासवादी संगणना साहित्य में, आनुवंशिक-प्रकार के उत्परिवर्तन-चयन एल्गोरिदम 1970 के दशक की शुरुआत में जॉन हॉलैंड के मौलिक कार्य, विशेष रूप से उनकी पुस्तक के माध्यम से लोकप्रिय हो गए। 1975 में प्रकाशित.

जीवविज्ञान और आनुवंशिकी में, ऑस्ट्रेलियाई आनुवंशिकीविद् एलेक्स फ्रेज़र (वैज्ञानिक) ने भी 1957 में जीवों के कृत्रिम चयन के आनुवंशिक प्रकार के अनुकरण पर पत्रों की श्रृंखला प्रकाशित की थी। जीवविज्ञानियों द्वारा विकास का कंप्यूटर सिमुलेशन 1960 के दशक की शुरुआत में अधिक आम हो गया, और तरीकों का वर्णन फ्रेज़र और बर्नेल (1970) की पुस्तकों में किया गया। और क्रॉस्बी (1973)। फ़्रेज़र के सिमुलेशन में आधुनिक उत्परिवर्तन-चयन आनुवंशिक कण एल्गोरिदम के सभी आवश्यक तत्व शामिल थे।

गणितीय दृष्टिकोण से, कुछ आंशिक और शोर अवलोकनों को देखते हुए सिग्नल के यादृच्छिक राज्यों का सशर्त वितरण संभावित संभावित कार्यों के अनुक्रम द्वारा भारित सिग्नल के यादृच्छिक प्रक्षेपवक्र पर फेनमैन-केएसी संभावना द्वारा वर्णित किया गया है।क्वांटम मोंटे कार्लो, और अधिक विशेष रूप से डिफ्यूजन मोंटे कार्लो की व्याख्या फेनमैन-केएसी पथ इंटीग्रल्स के माध्य-क्षेत्र आनुवंशिक प्रकार के कण सन्निकटन के रूप में भी की जा सकती है। क्वांटम मोंटे कार्लो विधियों की उत्पत्ति का श्रेय अक्सर एनरिको फर्मी और रॉबर्ट रिचटमेयर को दिया जाता है, जिन्होंने 1948 में न्यूट्रॉन-श्रृंखला प्रतिक्रियाओं की माध्य-क्षेत्र कण व्याख्या विकसित की थी, लेकिन क्वांटम सिस्टम (कम मैट्रिक्स मॉडल में) की जमीनी स्थिति ऊर्जा का आकलन करने के लिए पहला अनुमानी-जैसा और आनुवंशिक प्रकार का कण एल्गोरिदम (a.k.a. रेज़ैम्पल्ड या रीकॉन्फिगरेशन मोंटे कार्लो विधियां) 1984 में जैक एच. हेथरिंगटन के कारण है।कण भौतिकी में 1951 में प्रकाशित टेड हैरिस (गणितज्ञ)|थियोडोर ई. हैरिस और हरमन काह्न के पहले मौलिक कार्यों को भी उद्धृत किया जा सकता है, जिसमें कण संचरण ऊर्जा का अनुमान लगाने के लिए माध्य-क्षेत्र लेकिन अनुमानी-जैसी आनुवंशिक विधियों का उपयोग किया गया था। आणविक रसायन विज्ञान में, आनुवंशिक अनुमान-जैसी कण पद्धतियों (उर्फ प्रूनिंग और संवर्धन रणनीतियों) का उपयोग मार्शल के मौलिक कार्य के साथ 1955 में खोजा जा सकता है। एन. रोसेनब्लुथ और एरियाना। डब्ल्यू रोसेनब्लुथ।

उन्नत सिग्नल प्रोसेसिंग और बायेसियन अनुमान में जेनेटिक एल्गोरिदम का उपयोग हाल ही में हुआ है। जनवरी 1993 में, जेनशिरो कितागावा ने मोंटे कार्लो फ़िल्टर विकसित किया, इस लेख का थोड़ा संशोधित संस्करण 1996 में सामने आया। अप्रैल 1993 में, गॉर्डन एट अल ने अपना मौलिक कार्य प्रकाशित किया बायेसियन सांख्यिकीय अनुमान में आनुवंशिक प्रकार एल्गोरिदम का अनुप्रयोग। लेखकों ने अपने एल्गोरिदम को 'बूटस्ट्रैप फ़िल्टर' नाम दिया, और प्रदर्शित किया कि अन्य फ़िल्टरिंग विधियों की तुलना में, उनके बूटस्ट्रैप एल्गोरिदम को उस स्थिति स्थान या सिस्टम के शोर के बारे में किसी भी धारणा की आवश्यकता नहीं है। स्वतंत्र रूप से, पियरे डेल मोरल द्वाराऔर हिमिल्कोन कार्वाल्हो, पियरे डेल मोरल, आंद्रे मोनिन और जेरार्ड सैलुट 1990 के दशक के मध्य में प्रकाशित कण फिल्टर पर। 1989-1992 की शुरुआत में पी. डेल मोरल, जे.सी. नोयर, जी. रिगल और जी. सालुट द्वारा एलएएएस-सीएनआरएस में सिग्नल प्रोसेसिंग में एसटीसीएएन (सर्विस टेक्नीक डेस कंस्ट्रक्शन्स एट आर्म्स नेवेल्स), आईटी कंपनी डिजीलॉग, और LAAS-CNRS (विश्लेषण के लिए प्रयोगशाला) के साथ प्रतिबंधित और वर्गीकृत अनुसंधान रिपोर्टों की श्रृंखला में कण फिल्टर भी विकसित किए गए थे। रडार/सोनार और जीपीएस सिग्नल प्रोसेसिंग समस्याओं पर सिस्टम का आर्किटेक्चर)।

गणितीय आधार

1950 से 1996 तक, कण फिल्टर और आनुवंशिक एल्गोरिदम पर सभी प्रकाशन, जिसमें कम्प्यूटेशनल भौतिकी और आणविक रसायन विज्ञान में शुरू की गई मोंटे कार्लो विधियों की छंटाई और पुन: नमूना शामिल है, उनकी स्थिरता के भी सबूत के बिना विभिन्न स्थितियों पर लागू प्राकृतिक और अनुमानी-जैसे एल्गोरिदम प्रस्तुत करते हैं, न ही अनुमानों और वंशावली और पैतृक वृक्ष-आधारित एल्गोरिदम के पूर्वाग्रह पर कोई चर्चा करते हैं।

गणितीय नींव और इन कण एल्गोरिदम का पहला कठोर विश्लेषण पियरे डेल मोरल के कारण है1996 में. लेखइसमें संभाव्यता कार्यों के कण सन्निकटन और असामान्य सशर्त संभाव्यता उपायों के निष्पक्ष गुणों का प्रमाण भी शामिल है। इस लेख में प्रस्तुत संभावना कार्यों के निष्पक्ष कण अनुमानक का उपयोग आज बायेसियन सांख्यिकीय अनुमान में किया जाता है।

डैन क्रिसन, जेसिका गेन्स, और टेरी लियोन्स, साथ ही डैन क्रिसन, पियरे डेल मोरल, और टेरी लियोन्स, 1990 के दशक के अंत में विभिन्न जनसंख्या आकारों के साथ शाखा-प्रकार की कण तकनीकें बनाई गईं। पी. डेल मोरल, ए. गियोनेट, और एल. मिक्लो 2000 में इस विषय में और अधिक प्रगति हुई। पियरे डेल मोरल और ऐलिस गियोनेट 1999 में पियरे डेल मोरल और लॉरेंट मिक्लो ने पहली केंद्रीय सीमा प्रमेय साबित कीउन्हें 2000 में साबित किया गया। कण फिल्टर के लिए समय पैरामीटर से संबंधित पहला समान अभिसरण परिणाम 1990 के दशक के अंत में पियरे डेल मोरल और ऐलिस गियोनेट द्वारा विकसित किया गया था। वंशावली वृक्ष आधारित कण फिल्टर स्मूथर्स का पहला कठोर विश्लेषण 2001 में पी. डेल मोरल और एल. मिक्लो के कारण हुआ। फेनमैन-केएसी कण पद्धतियों और संबंधित कण फ़िल्टर एल्गोरिदम पर सिद्धांत 2000 और 2004 में पुस्तकों में विकसित किया गया था।ये अमूर्त संभाव्य मॉडल आनुवंशिक प्रकार के एल्गोरिदम, कण और बूटस्ट्रैप फिल्टर को समाहित करते हैं, कलमैन फिल्टर (उर्फ राव-ब्लैकवेलाइज्ड कण फिल्टर) को इंटरैक्ट करते हैं), महत्वपूर्ण नमूनाकरण और पुन: नमूनाकरण शैली कण फ़िल्टर तकनीक, जिसमें फ़िल्टरिंग और स्मूथिंग समस्याओं को हल करने के लिए वंशावली वृक्ष-आधारित और कण पिछड़े तरीके शामिल हैं। कण फ़िल्टरिंग पद्धतियों के अन्य वर्गों में वंशावली वृक्ष-आधारित मॉडल शामिल हैं, पिछड़े मार्कोव कण मॉडल, अनुकूली माध्य-क्षेत्र कण मॉडल,द्वीप-प्रकार के कण मॉडल, और कण मार्कोव श्रृंखला मोंटे कार्लो पद्धतियाँ।

फ़िल्टरिंग समस्या

उद्देश्य

एक कण फ़िल्टर का लक्ष्य अवलोकन चर दिए गए राज्य चर के पीछे के घनत्व का अनुमान लगाना है। कण फ़िल्टर छिपे हुए मार्कोव मॉडल के साथ उपयोग के लिए है, जिसमें सिस्टम में छिपे हुए और देखने योग्य दोनों चर शामिल हैं। अवलोकन योग्य चर (अवलोकन प्रक्रिया) ज्ञात कार्यात्मक रूप के माध्यम से छिपे हुए चर (राज्य-प्रक्रिया) से जुड़े हुए हैं। इसी प्रकार, राज्य चर के विकास को परिभाषित करने वाली गतिशील प्रणाली का संभाव्य विवरण ज्ञात है।

एक सामान्य कण फ़िल्टर अवलोकन माप प्रक्रिया का उपयोग करके छिपी हुई अवस्थाओं के पीछे के वितरण का अनुमान लगाता है। राज्य-स्थान के संबंध में जैसे कि नीचे दिया गया है:

${\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}}$

फ़िल्टरिंग समस्या छुपे हुए राज्यों के मूल्यों का क्रमिक रूप से अनुमान लगाना है $X_{k}$, अवलोकन प्रक्रिया के मूल्यों को देखते हुए $Y_{0},\cdots ,Y_{k},$ किसी भी समय चरण k.

के सभी बायेसियन अनुमान $X_{k}$ पश्च संभाव्यता से अनुसरण करें $p(x_{k}|y_{0},y_{1},...,y_{k})$. कण फ़िल्टर पद्धति आनुवंशिक प्रकार के कण एल्गोरिदम से जुड़े अनुभवजन्य माप का उपयोग करके इन सशर्त संभावनाओं का अनुमान प्रदान करती है। इसके विपरीत, मार्कोव चेन मोंटे कार्लो या महत्व नमूनाकरण दृष्टिकोण पूर्ण पश्च भाग का मॉडल तैयार करेगा $p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})$.

सिग्नल-अवलोकन मॉडल

कण विधियाँ प्रायः मान ली जाती हैं $X_{k}$ और अवलोकन $Y_{k}$ इस रूप में प्रतिरूपित किया जा सकता है:

• $X_{0},X_{1},\cdots$ मार्कोव प्रक्रिया चालू है $\mathbb {R} ^{d_{x}}$ (कुछ के लिए $d_{x}\geqslant 1$) जो संक्रमण संभाव्यता घनत्व के अनुसार विकसित होता है $p(x_{k}|x_{k-1})$. इस मॉडल को अक्सर सिंथेटिक तरीके से भी लिखा जाता है

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

प्रारंभिक संभाव्यता घनत्व के साथ $p(x_{0})$.

• अवलोकन $Y_{0},Y_{1},\cdots$ कुछ राज्य स्थान में मान लें $\mathbb {R} ^{d_{y}}$ (कुछ के लिए $d_{y}\geqslant 1$) और सशर्त रूप से स्वतंत्र हैं बशर्ते कि $X_{0},X_{1},\cdots$ ज्ञात हैं। दूसरे शब्दों में, प्रत्येक $Y_{k}$ पर ही निर्भर करता है $X_{k}$. इसके अलावा, हम इसके लिए सशर्त वितरण मानते हैं $Y_{k}$ दिया गया $X_{k}=x_{k}$ बिल्कुल निरंतर हैं, और हमारे पास सिंथेटिक तरीके से हैं

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

इन गुणों वाले सिस्टम का उदाहरण है:

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

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

दोनों कहाँ $W_{k}$ और $V_{k}$ ज्ञात संभाव्यता घनत्व फ़ंक्शन के साथ परस्पर स्वतंत्र अनुक्रम हैं और g और h ज्ञात फ़ंक्शन हैं। इन दो समीकरणों को राज्य स्थान (नियंत्रण) समीकरणों के रूप में देखा जा सकता है और कलमन फ़िल्टर के लिए राज्य अंतरिक्ष समीकरणों के समान दिख सकते हैं। यदि उपरोक्त उदाहरण में फ़ंक्शन g और h रैखिक हैं, और यदि दोनों $W_{k}$ और $V_{k}$ गाऊसी हैं, कलमन फ़िल्टर सटीक बायेसियन फ़िल्टरिंग वितरण पाता है। यदि नहीं, तो कलमैन फ़िल्टर-आधारित विधियाँ प्रथम-क्रम सन्निकटन (विस्तारित कलमान फ़िल्टर) या दूसरे-क्रम सन्निकटन (सामान्य तौर पर अनसेंटेड कलमैन फ़िल्टर, लेकिन यदि संभाव्यता वितरण गॉसियन है तो तीसरे-क्रम सन्निकटन संभव है)।

इस धारणा को शिथिल किया जा सकता है कि प्रारंभिक वितरण और मार्कोव श्रृंखला के संक्रमण लेब्सेग माप के लिए निरंतर हैं। कण फिल्टर को डिजाइन करने के लिए हमें बस यह मानने की जरूरत है कि हम संक्रमणों का नमूना ले सकते हैं $X_{k-1}\to X_{k}$ मार्कोव श्रृंखला का $X_{k},$ और संभाव्यता फ़ंक्शन की गणना करने के लिए $x_{k}\mapsto p(y_{k}|x_{k})$ (उदाहरण के लिए नीचे दिए गए कण फिल्टर का आनुवंशिक चयन उत्परिवर्तन विवरण देखें)। मार्कोव संक्रमणों पर निरंतर धारणा $X_{k}$ इसका उपयोग केवल अनौपचारिक (और बल्कि अपमानजनक) तरीके से सशर्त घनत्वों के लिए बेयस नियम का उपयोग करके पश्च वितरण के बीच विभिन्न सूत्रों को प्राप्त करने के लिए किया जाता है।

अनुमानित बायेसियन गणना मॉडल

Main article: Approximate Bayesian computation

कुछ समस्याओं में, सिग्नल की यादृच्छिक स्थिति को देखते हुए अवलोकनों का सशर्त वितरण, घनत्व में विफल हो सकता है; उत्तरार्द्ध की गणना करना असंभव या बहुत जटिल हो सकता है।इस स्थिति में, सन्निकटन का अतिरिक्त स्तर आवश्यक है। रणनीति सिग्नल को बदलने की है $X_{k}$ मार्कोव श्रृंखला द्वारा ${\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)$ और प्रपत्र का आभासी अवलोकन प्रस्तुत करना

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

स्वतंत्र यादृच्छिक चर के कुछ अनुक्रम के लिए ${\mathcal {V}}_{k}$ ज्ञात संभाव्यता घनत्व कार्यों के साथ। केंद्रीय विचार उसका निरीक्षण करना है

${\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)$

मार्कोव प्रक्रिया से जुड़ा कण फ़िल्टर ${\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)$ आंशिक अवलोकन दिए गए ${\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},$ विकसित होने वाले कणों के संदर्भ में परिभाषित किया गया है $\mathbb {R} ^{d_{x}+d_{y}}$ कुछ स्पष्ट अपमानजनक संकेतन के साथ दिए गए संभावना फ़ंक्शन के साथ $p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})$. ये संभाव्य तकनीकें अनुमानित बायेसियन संगणना (एबीसी) से निकटता से संबंधित हैं। कण फिल्टर के संदर्भ में, इन एबीसी कण फ़िल्टरिंग तकनीकों को 1998 में पी. डेल मोरल, जे. जैकॉड और पी. प्रॉटर द्वारा पेश किया गया था। इन्हें आगे पी. डेल मोरल, ए. डौसेट और ए. जसरा द्वारा विकसित किया गया।

अरेखीय फ़िल्टरिंग समीकरण

बेयस नियम|सशर्त संभाव्यता के लिए बेयस नियम देता है:

$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})}}$

कहाँ

${\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}}$

कण फिल्टर भी अनुमान है, लेकिन पर्याप्त कणों के साथ वे अधिक सटीक हो सकते हैं।अरेखीय फ़िल्टरिंग समीकरण प्रत्यावर्तन द्वारा दिया गया है

${\begin{aligned}p(x_{k}|y_{0},\cdots ,y_{k-1})&{\stackrel {\text{updating}}{\longrightarrow }}p(x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{k}|x_{k})p(x_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k})p(x'_{k}|y_{0},\cdots ,y_{k-1})dx'_{k}}}\\&{\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}\end{aligned}}$

(Eq. 1)

सम्मेलन के साथ $p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})$ k = 0 के लिए। नॉनलाइनियर फ़िल्टरिंग समस्या में इन सशर्त वितरणों की क्रमिक रूप से गणना करना शामिल है।

फेनमैन-केएसी सूत्रीकरण

Main article: Feynman–Kac formula

हम समय क्षितिज n और अवलोकनों का क्रम तय करते हैं $Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}$, और प्रत्येक k = 0, ..., n के लिए हम सेट करते हैं:

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

इस अंकन में, प्रक्षेप पथ के सेट पर किसी भी बंधे हुए फ़ंक्शन F के लिए $X_{k}$ मूल k = 0 से समय k = n तक, हमारे पास फेनमैन-Kac सूत्र है

${\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}}$

फेनमैन-केएसी पथ एकीकरण मॉडल कम्प्यूटेशनल भौतिकी, जीव विज्ञान, सूचना सिद्धांत और कंप्यूटर विज्ञान सहित विभिन्न वैज्ञानिक विषयों में उत्पन्न होते हैं।उनकी व्याख्याएँ अनुप्रयोग डोमेन पर निर्भर हैं। उदाहरण के लिए, यदि हम संकेतक फ़ंक्शन चुनते हैं $G_{n}(x_{n})=1_{A}(x_{n})$ राज्य स्थान के कुछ सबसेट में से, वे मार्कोव श्रृंखला के सशर्त वितरण का प्रतिनिधित्व करते हैं, यह दिए गए ट्यूब में रहता है; अर्थात्, हमारे पास है:

$E\left(F(X_{0},\cdots ,X_{n})|X_{0}\in A,\cdots ,X_{n}\in A\right)={\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)}}$

और

$P\left(X_{0}\in A,\cdots ,X_{n}\in A\right)=E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)$

जैसे ही सामान्यीकरण स्थिरांक सख्ती से सकारात्मक होता है।

कण फिल्टर

एक आनुवंशिक प्रकार का कण एल्गोरिथ्म

प्रारंभ में, ऐसा एल्गोरिदम एन स्वतंत्र यादृच्छिक चर से शुरू होता है $\left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}$ सामान्य संभाव्यता घनत्व के साथ $p(x_{0})$. आनुवंशिक एल्गोरिथ्म चयन-उत्परिवर्तन संक्रमण

$\xi _{k}:=\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{selection}}{\longrightarrow }}{\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{mutation}}{\longrightarrow }}\xi _{k+1}:=\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}$

इष्टतम फ़िल्टर विकास के अद्यतन-भविष्यवाणी बदलावों की नकल/अनुमानित करें (Eq. 1):

• चयन-अद्यतन संक्रमण के दौरान हम एन (सशर्त) स्वतंत्र यादृच्छिक चर का नमूना लेते हैं ${\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}$ सामान्य (सशर्त) वितरण के साथ

$\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})$

कहाँ $\delta _{a}$ किसी दिए गए राज्य में डिराक माप के लिए खड़ा है।

• उत्परिवर्तन-भविष्यवाणी संक्रमण के दौरान, प्रत्येक चयनित कण से ${\widehat {\xi }}_{k}^{i}$ हम स्वतंत्र रूप से संक्रमण का नमूना लेते हैं

${\widehat {\xi }}_{k}^{i}\longrightarrow \xi _{k+1}^{i}\sim p(x_{k+1}|{\widehat {\xi }}_{k}^{i}),\qquad i=1,\cdots ,N.$

ऊपर प्रदर्शित सूत्रों में $p(y_{k}|\xi _{k}^{i})$ संभाव्यता फ़ंक्शन के लिए खड़ा है $x_{k}\mapsto p(y_{k}|x_{k})$ पर मूल्यांकन किया गया $x_{k}=\xi _{k}^{i}$, और $p(x_{k+1}|{\widehat {\xi }}_{k}^{i})$ सशर्त घनत्व के लिए खड़ा है $p(x_{k+1}|x_{k})$ पर मूल्यांकन किया गया $x_{k}={\widehat {\xi }}_{k}^{i}$.

प्रत्येक समय k पर, हमारे पास कण सन्निकटन होते हैं

${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})$

और

${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})$

आनुवंशिक एल्गोरिदम और विकासवादी कंप्यूटिंग समुदाय में, ऊपर वर्णित उत्परिवर्तन-चयन मार्कोव श्रृंखला को अक्सर आनुपातिक चयन के साथ आनुवंशिक एल्गोरिदम कहा जाता है। लेखों में यादृच्छिक जनसंख्या आकार सहित कई शाखाओं के प्रकार भी प्रस्तावित किए गए हैं।

मोंटे कार्लो विधि

कण विधियाँ, सभी नमूना-आधारित दृष्टिकोणों (जैसे, मार्कोव श्रृंखला मोंटे कार्लो) की तरह, नमूनों का सेट उत्पन्न करती हैं जो फ़िल्टरिंग घनत्व का अनुमान लगाती हैं

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

उदाहरण के लिए, हमारे पास अनुमानित पश्च वितरण से एन नमूने हो सकते हैं $X_{k}$, जहां नमूनों को सुपरस्क्रिप्ट के साथ इस प्रकार लेबल किया गया है:

${\widehat {\xi }}_{k}^{1},\cdots ,{\widehat {\xi }}_{k}^{N}.$

फिर, फ़िल्टरिंग वितरण के संबंध में अपेक्षाओं का अनुमान लगाया जाता है

$\int f(x_{k})p(x_{k}|y_{0},\cdots ,y_{k})\,dx_{k}\approx _{N\uparrow \infty }{\frac {1}{N}}\sum _{i=1}^{N}f\left({\widehat {\xi }}_{k}^{i}\right)=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})$

(Eq. 2)

साथ

${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})$

कहाँ $\delta _{a}$ किसी दिए गए राज्य में डिराक माप के लिए खड़ा है। फ़ंक्शन एफ, मोंटे कार्लो के लिए सामान्य तरीके से, कुछ सन्निकटन त्रुटि तक वितरण के सभी क्षण (गणित) आदि दे सकता है। जब सन्निकटन समीकरण (Eq. 2) हमारे द्वारा लिखे गए किसी भी परिबद्ध फलन के लिए संतुष्ट है

$p(dx_{k}|y_{0},\cdots ,y_{k}):=p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})$

कण फिल्टर की व्याख्या उत्परिवर्तन और चयन संक्रमण के साथ विकसित होने वाले आनुवंशिक प्रकार के कण एल्गोरिदम के रूप में की जा सकती है। हम पैतृक वंशावली का हिसाब रख सकते हैं

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

कणों का $i=1,\cdots ,N$. यादृच्छिक अवस्थाएँ ${\widehat {\xi }}_{l,k}^{i}$, निम्न सूचकांकों के साथ l=0,...,k, व्यक्ति के पूर्वज को दर्शाता है ${\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}$ स्तर पर l=0,...,k. इस स्थिति में, हमारे पास सन्निकटन सूत्र है

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

(Eq. 3)

अनुभवजन्य माप के साथ

${\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},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))$

यहां एफ सिग्नल के पथ स्थान पर किसी भी स्थापित फ़ंक्शन के लिए है। अधिक सिंथेटिक रूप में (Eq. 3) के बराबर है

${\begin{aligned}p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\approx _{N\uparrow \infty }{\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 }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\end{aligned}}$

कण फिल्टर की व्याख्या कई अलग-अलग तरीकों से की जा सकती है। संभाव्य दृष्टिकोण से वे माध्य-क्षेत्र कण विधियों के साथ मेल खाते हैं | गैर-रेखीय फ़िल्टरिंग समीकरण की माध्य-क्षेत्र कण व्याख्या। इष्टतम फ़िल्टर विकास के अद्यतन-भविष्यवाणी संक्रमणों की व्याख्या व्यक्तियों के शास्त्रीय आनुवंशिक प्रकार के चयन-उत्परिवर्तन संक्रमणों के रूप में भी की जा सकती है। अनुक्रमिक महत्व पुन: नमूनाकरण तकनीक बूटस्ट्रैप पुन: नमूनाकरण चरण के साथ महत्व नमूने को जोड़ते हुए फ़िल्टरिंग संक्रमण की और व्याख्या प्रदान करती है। अंतिम, लेकिन महत्वपूर्ण बात यह है कि कण फिल्टर को रीसाइक्लिंग तंत्र से सुसज्जित स्वीकृति-अस्वीकृति पद्धति के रूप में देखा जा सकता है।

माध्य-क्षेत्र कण विधियाँ|माध्य-क्षेत्र कण अनुकरण

सामान्य संभाव्य सिद्धांत

गैर-रेखीय फ़िल्टरिंग विकास को फॉर्म की संभाव्यता उपायों के सेट में गतिशील प्रणाली के रूप में व्याख्या किया जा सकता है $\eta _{n+1}=\Phi _{n+1}\left(\eta _{n}\right)$ कहाँ $\Phi _{n+1}$ संभाव्यता वितरण के सेट से स्वयं में कुछ मैपिंग के लिए खड़ा है। उदाहरण के लिए, एक-चरणीय इष्टतम भविष्यवक्ता का विकास $\eta _{n}(dx_{n})=p(x_{n}|y_{0},\cdots ,y_{n-1})dx_{n}$ संभाव्यता वितरण से शुरू होने वाले अरेखीय विकास को संतुष्ट करता है $\eta _{0}(dx_{0})=p(x_{0})dx_{0}$. इन संभाव्यता मापों का अनुमान लगाने का सबसे सरल तरीका एन स्वतंत्र यादृच्छिक चर से शुरू करना है $\left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}$ सामान्य संभाव्यता वितरण के साथ $\eta _{0}(dx_{0})=p(x_{0})dx_{0}$ . मान लीजिए कि हमने N यादृच्छिक चरों का क्रम परिभाषित किया है $\left(\xi _{n}^{i}\right)_{1\leqslant i\leqslant N}$ ऐसा है कि

${\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}(dx_{n})\approx _{N\uparrow \infty }\eta _{n}(dx_{n})$

अगले चरण में हम एन (सशर्त) स्वतंत्र यादृच्छिक चर का नमूना लेते हैं $\xi _{n+1}:=\left(\xi _{n+1}^{i}\right)_{1\leqslant i\leqslant N}$ सामान्य कानून के साथ.

$\Phi _{n+1}\left({\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}\right)\approx _{N\uparrow \infty }\Phi _{n+1}\left(\eta _{n}\right)=\eta _{n+1}$

फ़िल्टरिंग समीकरण की कण व्याख्या

हम कदम इष्टतम भविष्यवक्ताओं के विकास के संदर्भ में इस माध्य-क्षेत्र कण सिद्धांत का वर्णन करते हैं

$p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}\to p(x_{k+1}|y_{0},\cdots ,y_{k})=\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}')p(x'_{k}|y_{0},\cdots ,y_{k-1})dx'_{k}}{\int p(y_{k}|x''_{k})p(x''_{k}|y_{0},\cdots ,y_{k-1})dx''_{k}}}$

(Eq. 4)

k = 0 के लिए हम परिपाटी का उपयोग करते हैं $p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})$.

बड़ी संख्या के नियम के अनुसार, हमारे पास है

${\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{0}^{i}}(dx_{0})\approx _{N\uparrow \infty }p(x_{0})dx_{0}$

इस अर्थ में कि

$\int f(x_{0}){\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{0}^{i})\approx _{N\uparrow \infty }\int f(x_{0})p(dx_{0})dx_{0}$

किसी भी सीमित फ़ंक्शन के लिए $f$. हम आगे यह भी मानते हैं कि हमने कणों का क्रम बनाया है $\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}$ कुछ रैंक k पर ऐसा है

${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }~p(x_{k}~|~y_{0},\cdots ,y_{k-1})dx_{k}$

इस अर्थ में कि किसी भी बंधे हुए कार्य के लिए $f$ अपने पास

$\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{k}^{i})\approx _{N\uparrow \infty }\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})dx_{k}$

इस स्थिति में, $p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}$ अनुभवजन्य माप द्वारा Failed to parse (Conversion error. Server ("cli") reported: "SyntaxError: Expected [, ;!_#%$&], [a-zA-Z], or [{}|] but "व" found.in 1:17"): {\displaystyle \वाइडहैट{p}(dx_k|y_0,\cdots,y_{k-1}} में बताए गए एक-चरण इष्टतम फ़िल्टर के विकास समीकरण में (Eq. 4) हम उसे ढूंढते हैं

$p(x_{k+1}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}$

ध्यान दें कि उपरोक्त सूत्र में दाहिनी ओर भारित संभाव्यता मिश्रण है

$\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}p(x_{k+1}|\xi _{k}^{i})=:{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})$

कहाँ $p(y_{k}|\xi _{k}^{i})$ घनत्व के लिए खड़ा है $p(y_{k}|x_{k})$ पर मूल्यांकन किया गया $x_{k}=\xi _{k}^{i}$, और $p(x_{k+1}|\xi _{k}^{i})$ घनत्व के लिए खड़ा है $p(x_{k+1}|x_{k})$ पर मूल्यांकन किया गया $x_{k}=\xi _{k}^{i}$ के लिए $i=1,\cdots ,N.$ फिर, हम एन स्वतंत्र यादृच्छिक चर का नमूना लेते हैं $\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}$ सामान्य संभाव्यता घनत्व के साथ ${\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})$ ताकि

${\widehat {p}}(dx_{k+1}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k+1}^{i}}(dx_{k+1})\approx _{N\uparrow \infty }{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}\approx _{N\uparrow \infty }p(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}$

इस प्रक्रिया को दोहराते हुए, हम मार्कोव श्रृंखला को इस प्रकार डिज़ाइन करते हैं

${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1}):=p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}$

ध्यान दें कि बेयस के सूत्रों का उपयोग करके प्रत्येक समय चरण k पर इष्टतम फ़िल्टर का अनुमान लगाया जाता है

$p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }{\frac {p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k}){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}~\delta _{\xi _{k}^{i}}(dx_{k})$

शब्दावली माध्य-क्षेत्र सन्निकटन इस तथ्य से आता है कि हम प्रत्येक समय कदम पर संभाव्यता माप को प्रतिस्थापित करते हैं $p(dx_{k}|y_{0},\cdots ,y_{k-1})$ अनुभवजन्य सन्निकटन द्वारा ${\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})$. फ़िल्टरिंग समस्या का माध्य-क्षेत्र कण सन्निकटन अद्वितीय होने से बहुत दूर है। पुस्तकों में कई रणनीतियाँ विकसित की गई हैं।

कुछ अभिसरण परिणाम

कण फिल्टर के अभिसरण का विश्लेषण 1996 में शुरू किया गया थाऔर 2000 में किताब मेंऔर लेखों की श्रृंखला. हाल के घटनाक्रम किताबों में पाए जा सकते हैं,जब फ़िल्टरिंग समीकरण स्थिर होता है (इस अर्थ में कि यह किसी भी गलत प्रारंभिक स्थिति को सही करता है), कण कण का पूर्वाग्रह और विचरण अनुमान लगाता है

$I_{k}(f):=\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})\approx _{N\uparrow \infty }{\widehat {I}}_{k}(f):=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})$

गैर-स्पर्शोन्मुख समान अनुमानों द्वारा नियंत्रित होते हैं

$\sup _{k\geqslant 0}\left\vert E\left({\widehat {I}}_{k}(f)\right)-I_{k}(f)\right\vert \leqslant {\frac {c_{1}}{N}}$

$\sup _{k\geqslant 0}E\left(\left[{\widehat {I}}_{k}(f)-I_{k}(f)\right]^{2}\right)\leqslant {\frac {c_{2}}{N}}$

1 से घिरे किसी भी फलन f के लिए, और कुछ परिमित स्थिरांकों के लिए $c_{1},c_{2}.$ इसके अलावा, किसी के लिए भी $x\geqslant 0$:

$\mathbf {P} \left(\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c{\sqrt {\frac {x\log(n)}{N}}}\right)>1-e^{-x}$

कुछ परिमित स्थिरांकों के लिए $c_{1},c_{2}$ कण अनुमान के स्पर्शोन्मुख पूर्वाग्रह और विचरण से संबंधित, और कुछ परिमित स्थिरांक सी। यदि हम चरण वाले इष्टतम भविष्यवक्ता को इष्टतम फ़िल्टर सन्निकटन से प्रतिस्थापित करते हैं तो वही परिणाम संतुष्ट होते हैं।

वंशावली वृक्ष एवं निष्पक्षता गुण

वंशावली वृक्ष आधारित कण चौरसाई

समय में पूर्वज वंशावली का पता लगाना

$\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)$

व्यक्तियों का ${\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)$ और $\xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)$ हर समय चरण k पर, हमारे पास कण सन्निकटन भी होते हैं

ये अनुभवजन्य सन्निकटन कण अभिन्न सन्निकटन के समतुल्य हैं

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