Diffusion map
विसरण मानचित्र एक आयामी कमी या विशेषता निष्कर्षण एल्गोरिथ्म है जिसे कोइफमैन और लाफॉन द्वारा पेश किया गया है जो यूक्लिडियन स्पेस (अक्सर कम आयामी) में सेट किए गए डेटा के एम्बेडिंग के एक परिवार की गणना करता है जिसके निर्देशांक की गणना डेटा पर एक विसरण ऑपरेटर के आइगेनवेक्टर्स और आइगेनवैल्यूज से की जा सकती है। अंतःस्थापित स्थान में बिंदुओं के बीच यूक्लिडियन दूरी उन बिंदुओं पर केंद्रित संभाव्यता वितरण के बीच "प्रसार दूरी" के बराबर होती है। प्रमुख घटक विश्लेषण (पी. सी. ए.) जैसी रैखिक आयामी कमी विधियों से अलग, प्रसार मानचित्र गैर-रैखिक आयामी कमी विधियों के परिवार का हिस्सा हैं जो अंतर्निहित कई गुना की खोज पर ध्यान केंद्रित करते हैं जिससे डेटा का नमूना लिया गया है। विभिन्न पैमानों पर स्थानीय समानताओं को एकीकृत करके, प्रसार मानचित्र डेटा-सेट का वैश्विक विवरण देते हैं। अन्य विधियों की तुलना में, प्रसार मानचित्र एल्गोरिथ्म शोर गड़बड़ी के लिए मजबूत है और कम्प्यूटेशनल रूप से सस्ता है। प्रसार मानचित्रों की परिभाषा निम्नलिखित और प्रसार मानचित्रों को चार चरणों में परिभाषित किया जा सकता है। संपर्क प्रसार मानचित्र गर्मी प्रसार और यादृच्छिक चलने मार्कोव श्रृंखला के बीच संबंध का फायदा उठाते हैं। बुनियादी अवलोकन यह है कि यदि हम डेटा पर यादृच्छिक रूप से चलते हैं, तो पास के डेटा-पॉइंट पर चलने की संभावना दूसरे दूर जाने की तुलना में अधिक है। मान लीजिए कि एक माप स्थान है, जहां डेटा सेट है और उस पर बिंदुओं के वितरण का प्रतिनिधित्व करता है। इसके आधार पर, दो डेटा बिंदुओं के बीच संपर्क, और, को यादृच्छिक चलने के एक चरण में चलने की संभावना के रूप में परिभाषित किया जा सकता है। आमतौर पर, इस संभावना को दो बिंदुओं के कर्नेल फलन के संदर्भ में निर्दिष्ट किया जाता हैः उदाहरण के लिए, लोकप्रिय गॉसियन कर्नेलः अधिक सामान्य रूप से, कर्नेल फ़ंक्शन में निम्नलिखित गुण होते हैं (सममित है) (सकारात्मक संरक्षण है)। कर्नेल डेटा-सेट की स्थानीय ज्यामिति की पूर्व परिभाषा का गठन करता है। चूँकि दिया गया कर्नेल डेटा सेट की एक विशिष्ट विशेषता को पकड़ लेगा, इसलिए इसकी पसंद उस अनुप्रयोग द्वारा निर्देशित की जानी चाहिए जो किसी के दिमाग में है। यह प्रमुख घटक विश्लेषण जैसी विधियों के साथ एक बड़ा अंतर है, जहां सभी डेटा बिंदुओं के बीच सहसंबंध को एक बार में ध्यान में रखा जाता है। यह देखते हुए, हम फिर एक प्रतिवर्ती असतत-समय मार्कोव श्रृंखला का निर्माण कर सकते हैं (एक प्रक्रिया जिसे सामान्यीकृत ग्राफ लाप्लासियन निर्माण के रूप में जाना जाता है): और परिभाषित कर सकते हैंः हालांकि नई सामान्यीकृत कर्नेल को सममित संपत्ति विरासत में नहीं मिलती है, यह सकारात्मक-संरक्षित संपत्ति विरासत में प्राप्त करता है और एक संरक्षण संपत्ति प्राप्त करता हैः प्रसार प्रक्रिया हम एक मार्कोव श्रृंखला () के संक्रमण मैट्रिक्स का निर्माण कर सकते हैं। दूसरे शब्दों में, से एक-चरण संक्रमण संभावना का प्रतिनिधित्व करता है, और टी-चरण संक्रमण मैट्रिक्स देता है। हम प्रसार मैट्रिक्स को परिभाषित करते हैं (यह ग्राफ लाप्लासियन मैट्रिक्स का एक संस्करण भी है) हम फिर नए कर्नेल या समकक्ष को परिभाषित करते हैं, जहां डी एक विकर्ण मैट्रिक्स है और हम इस नए कर्नेल पर ग्राफ लाप्लासियन सामान्यीकरण लागू करते हैंः जहां एक विकर्ण मैट्रिक्स है और प्रसार ढांचे के मुख्य विचारों में से एक यह है कि श्रृंखला को समय पर आगे चलाना (बड़ी और बड़ी शक्तियों को लेना) बड़े और बड़े पैमाने (प्रसार प्रक्रिया) पर ज्यामितीय संरचना को प्रकट करता है। विशेष रूप से, डेटा सेट में एक समूह की धारणा को एक ऐसे क्षेत्र के रूप में निर्धारित किया जाता है जिसमें इस क्षेत्र से बचने की संभावना कम होती है (एक निश्चित समय टी के भीतर)। इसलिए, टी न केवल एक समय पैरामीटर के रूप में कार्य करता है, बल्कि इसमें स्केल पैरामीटर की दोहरी भूमिका भी है। मैट्रिक्स यील्ड्स की आइगेनडैकंपोजिशन जहां और के आइगेनवैल्यूज का अनुक्रम है और क्रमशः बायॉर्थोगोनल राइट और लेफ्ट आइगेनवेक्टर्स हैं। आइगेनवैल्यूज के स्पेक्ट्रम क्षय के कारण, इस राशि में दी गई सापेक्ष सटीकता प्राप्त करने के लिए केवल कुछ शब्दों की आवश्यकता होती है। पैरामीटर α और प्रसार प्रचालक सामान्यीकरण चरण को शामिल करने का कारण प्रसार के असीम संक्रमण पर डेटा बिंदु घनत्व के प्रभाव को ट्यून करना है। कुछ अनुप्रयोगों में, डेटा का नमूना आमतौर पर उस मैनिफोल्ड की ज्यामिति से संबंधित नहीं होता है जिसका हम वर्णन करने में रुचि रखते हैं। इस मामले में, हम सेट कर सकते हैं और प्रसार प्रचालक लाप्लास-बेल्ट्रामी प्रचालक का अनुमान लगा सकता है। फिर हम अंकों के वितरण की परवाह किए बिना डेटा सेट की रीमानियन ज्यामिति को पुनर्प्राप्त करते हैं। यादृच्छिक विभेदक समीकरणों की एक प्रणाली के बिंदु वितरण के दीर्घकालिक व्यवहार का वर्णन करने के लिए, हम उपयोग कर सकते हैं और परिणामी मार्कोव श्रृंखला फोकर-प्लैंक प्रसार का अनुमान लगाती है। के साथ, यह शास्त्रीय ग्राफ लाप्लासियन सामान्यीकरण तक कम हो जाता है। दो बिंदुओं के बीच समय पर प्रसार दूरी को उनके बीच संपर्क के साथ अवलोकन स्थान में दो बिंदुओं की समानता के रूप में मापा जा सकता है। यह मार्कोव श्रृंखला के पहले बाएं आइगेनवेक्टर द्वारा दिए गए स्थिर वितरण द्वारा दिया जाता है। स्पष्ट रूप सेः सहज रूप से, छोटा है यदि बड़ी संख्या में जुड़ने वाले छोटे मार्ग हैं और। प्रसार दूरी से जुड़ी कई दिलचस्प विशेषताएं हैं, जो हमारी पिछली चर्चा के आधार पर हैं जो एक पैमाने के पैरामीटर के रूप में भी काम करती हैंः अंक एक दिए गए पैमाने पर करीब होते हैं (जैसा कि निर्दिष्ट किया गया है) यदि वे ग्राफ में अत्यधिक जुड़े हुए हैं, इसलिए एक समूह की अवधारणा पर जोर देते हैं। यह दूरी शोर के लिए मजबूत है, क्योंकि दो बिंदुओं के बीच की दूरी बिंदुओं के बीच की लंबाई के सभी संभावित रास्तों पर निर्भर करती है। मशीन लर्निंग के दृष्टिकोण से, दूरी से जुड़े सभी साक्ष्यों को ध्यान में रखा जाता है, जिससे हम यह निष्कर्ष निकाल सकते हैं कि यह दूरी अधिकांश प्रमुखता के आधार पर अनुमान एल्गोरिदम के डिजाइन के लिए उपयुक्त है। प्रसार प्रक्रिया और निम्न-आयामी एम्बेडिंग प्रसार दूरी की गणना आइगेनवेक्टर्स का उपयोग करके की जा सकती है इसलिए आइगेनवेक्टर्स का उपयोग डेटा के लिए निर्देशांक के एक नए सेट के रूप में किया जा सकता है। प्रसार मानचित्र को इस प्रकार परिभाषित किया गया हैः स्पेक्ट्रम क्षय के कारण, यह केवल पहले के आइगेनवेक्टर्स और आइगेनवैल्यूज का उपयोग करने के लिए पर्याप्त है। इस प्रकार हम मूल डेटा से एक के-आयामी स्थान पर प्रसार मानचित्र प्राप्त करते हैं जो मूल स्थान में अंतर्निहित है। इसमें यह साबित किया गया है कि इसलिए प्रसार निर्देशांक में यूक्लिडियन दूरी प्रसार दूरी का अनुमान लगाती है। एल्गोरिदम प्रसार मानचित्र का मूल एल्गोरिदम ढांचा इस प्रकार हैः चरण 1। समानता मैट्रिक्स एल. चरण 2 को देखते हुए। मैट्रिक्स को पैरामीटरः के अनुसार सामान्य करें। चरण 3. सामान्यीकृत मैट्रिक्स बनाएँ। चरण 4. के सबसे बड़े आइगेनवैल्यूज और संबंधित आइगेनवेक्टर्स की गणना करें। चरण 5. एम्बेडिंग प्राप्त करने के लिए प्रसार मानचित्र का उपयोग करें। कागज में आवेदन नैडलर एट अल। यह दिखाया कि एक कर्नेल को कैसे डिजाइन किया जाता है जो फोकर-प्लैंक समीकरण द्वारा प्रेरित प्रसार को पुनः उत्पन्न करता है। उन्होंने यह भी समझाया कि जब डेटा एक मैनिफोल्ड का अनुमान लगाता है, तो लाप्लास-बेल्ट्रामी ऑपरेटर के एक सन्निकटन की गणना करके इस मैनिफोल्ड की ज्यामिति को पुनर्प्राप्त किया जा सकता है। यह गणना अंकों के वितरण के प्रति पूरी तरह से असंवेदनशील है और इसलिए सांख्यिकी और डेटा की ज्यामिति का पृथक्करण प्रदान करती है। चूंकि प्रसार मानचित्र डेटा-सेट का एक वैश्विक विवरण देते हैं, वे उस मैनिफोल्ड में नमूना बिंदुओं के जोड़े के बीच की दूरी को माप सकते हैं जिसमें डेटा अंतर्निहित है। प्रसार मानचित्रों पर आधारित अनुप्रयोगों में चेहरे की पहचान, वर्णक्रमीय क्लस्टरिंग, छवियों का कम आयामी प्रतिनिधित्व, छवि विभाजन, 3डी मॉडल विभाजन, वक्ता सत्यापन और पहचान, मैनिफोल्ड पर नमूनाकरण, विसंगति का पता लगाना, छवि चित्रकारी, मस्तिष्क विश्राम राज्य नेटवर्क संगठन को प्रकट करना आदि शामिल हैं। इसके अलावा, प्रसार मानचित्र ढांचे को उत्पादक रूप से जटिल नेटवर्क तक विस्तारित किया गया है, जो नेटवर्क के एक कार्यात्मक संगठन को प्रकट करता है जो विशुद्ध रूप से स्थलाकृतिक या संरचनात्मक से अलग है। गैर-रैखिक आयामी कमी स्पेक्ट्रल क्लस्टरिंग संदर्भ मशीन लर्निंग एल्गोरिदम भी देखें।