कण फिल्टर

This article is about गणितीय एल्गोरिदम. For हवा से कणों को फ़िल्टर करने के लिए उपकरण, see एयर फिल्टर.

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

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

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

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

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

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

इतिहास

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

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

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

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

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

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

गणितीय आधार

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

फ़िल्टरिंग समस्या किसी भी समय चरण k अवलोकन प्रक्रिया $Y_{0},\cdots ,Y_{k},$ के मूल्यों को देखते हुए छुपे हुए अवस्थाओं $X_{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_{}$