प्रसार मानचित्र

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

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

प्रसार मानचित्रों की परिभाषा

निम्नलिखित और, प्रसार मानचित्रों को चार चरणों में परिभाषित किया जा सकता है।

अनुयोजकता

प्रसार मानचित्र ऊष्मा प्रसार और यादृच्छिक चाल मार्कोव श्रृंखला के बीच संबंध का लाभ उठाते हैं। मूल अवलोकन यह है कि यदि हम आंकड़ों पर यादृच्छिक रूप से चलते हैं, तो पास के आंकड़ों-बिंदु पर चलने की संभावना दूसरे आंकड़ों-बिंदु पर चलने की तुलना में अधिक होती है। मान लीजिये $(X,{\mathcal {A}},\mu )$ एक माप स्थान हो, $X$ आँकड़ा समुच्चय है और $\mu$ $X$ पर बिंदुओं के वितरण का प्रतिनिधित्व करता है।

दो डेटा बिंदुओं, x और y के बीच अनुयोजकता k को यादृच्छिक भ्रमण के एक चरण में x से y तक चलने की संभावना के रूप में परिभाषित किया जा सकता है। सामान्यतः, यह संभावना दो बिंदुओं $k:X\times X\rightarrow \mathbb {R}$ के कर्नेल फलन के संदर्भ में निर्दिष्ट होती है। उदाहरण के लिए, लोकप्रिय गॉसियन कर्नेल निम्न है:

$k(x,y)=\exp \left(-{\frac {||x-y||^{2}}{\epsilon }}\right)$

अधिक सामान्यतः, पूर्णांकी कर्नेल फलन में निम्नलिखित गुण होते हैं

$k(x,y)=k(y,x)$ ($k$ सममित है)

$k(x,y)\geq 0\,\,\forall x,y$

($k$ सकारात्मकता संरक्षित है)।

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

दिया गया $(X,k)$, फिर हम एक प्रतिवर्ती असतत-समय मार्कोव श्रृंखला $X$ का निर्माण कर सकते हैं (एक प्रक्रिया जिसे सामान्यीकृत लेखाचित्र लाप्लासियन निर्माण के रूप में जाना जाता है):

$d(x)=\int _{X}k(x,y)d\mu (y)$

और निम्न को परिभाषित करें:

$p(x,y)={\frac {k(x,y)}{d(x)}}$

यद्यपि नया सामान्यीकृत कर्नेल सममित गुण को इनहेरिट नहीं करता है, यह सकारात्मकता-संरक्षण गुण को इनहेरिट करता है और एक संरक्षण गुण प्राप्त करता है:

$\int _{X}p(x,y)d\mu (y)=1$

प्रसार प्रक्रिया

$p(x,y)$ से हम $X$ पर एक मार्कोव श्रृंखला ($M$) के परिवर्तन आव्यूह का निर्माण कर सकते हैं। दूसरे शब्दों में, $p(x,y)$ से एक-चरण संक्रमण संभावना $x$ से $y$ का प्रतिनिधित्व करता है, और $M^{t}$ t-चरण संक्रमण आव्यूह देता है।

हम प्रसार आव्यूह $L$ को परिभाषित करते हैं (यह लेखाचित्र लाप्लासियन आव्यूह का एक संस्करण भी है)

$L_{i,j}=k(x_{i},x_{j})\,$

फिर हम नए कर्नेल को परिभाषित करते हैं

$L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,$

या समकक्ष,

$L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,$

जहां D एक विकर्ण आव्यूह है और $D_{i,i}=\sum _{j}L_{i,j}.$

हम इस नए कर्नेल पर लाप्लासियन सामान्यीकरण लेखाचित्र लागू करते हैं:

$M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,$

जहाँ $D^{(\alpha )}$ एक विकर्ण आव्यूह है और ${D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.$

$p(x_{j},t|x_{i})=M_{i,j}^{t}\,$

प्रसार ढांचे के मुख्य विचारों में से एक यह है कि श्रृंखला को समय पर आगे बढ़ाना (M की बड़ी और बड़ी घात लेना) X की ज्यामितीय संरचना को बड़े और बड़े मापक्रम पर प्रकट करता है (प्रसार प्रक्रिया)। विशेष रूप से, आंकड़ों सम्मुच्चय में एक स्तवक की धारणा को एक ऐसे क्षेत्र के रूप में निर्धारित किया जाता है जिसमें इस क्षेत्र से बचने की संभावना कम होती है (एक निश्चित समय t के भीतर)। इसलिए, t न केवल एक समय मापदण्ड के रूप में कार्य करता है, बल्कि इसमें मापक्रम मापदण्ड की दोहरी भूमिका भी होती है।

आव्यूह का आइजेनडीकम्पोज़िशन $M^{t}$ उत्पादन है

$M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,$

जहाँ $\{\lambda _{l}\}$ $M$ के आइगेनमान ​​का अनुक्रम है और $\{\phi _{l}\}$ और $\{\psi _{l}\}$ क्रमशः बायोरथोगोनल दाएं और बाएं आइगेनसदिश हैं।

ईजेनवैल्यू के वर्णक्रम क्षय के कारण, इस योग में दी गई सापेक्ष सटीकता प्राप्त करने के लिए केवल कुछ परिस्थितियाँ आवश्यक हैं।

मापदण्ड α और प्रसार संचालक

$\alpha$ को सम्मिलित करने वाले सामान्यीकरण कदम को प्रस्तुत करने का कारण प्रसार के अनंत संक्रमण पर डेटा बिंदु घनत्व के प्रभाव को अनूकुल करना है। कुछ अनुप्रयोगों में, आंकड़ों का प्रतिरूप सामान्यतः बहुविध की ज्यामिति से संबंधित नहीं होता है जिसे हम वर्णन करने में रुचि रखते हैं। इस स्तिथि में, हम $\alpha =1$ सम्मुच्चय कर सकते हैं और प्रसार संचालक लाप्लास-बेल्ट्रामी संचालक का अनुमान लगाता है। इसके बाद हम अंकों के वितरण का चिंतन किए बिना आंकड़ों सम्मुच्चय की रीमैनियन ज्यामिति को पुनर्प्राप्त करते हैं। स्टोचैस्टिक अंतर समीकरणों की एक प्रणाली के बिंदु वितरण के दीर्घकालिक व्यवहार का वर्णन करने के लिए, हम $\alpha =0.5$ का उपयोग कर सकते हैं और परिणामी मार्कोव श्रृंखला फोकर-प्लैंक समीकरण का अनुमान लगाती है। $\alpha =0$ के साथ, यह पारम्परिक लेखाचित्र लाप्लासियन सामान्यीकरण को कम करता है।

प्रसार दूरी

समय $t$ पर प्रसार दूरी दो बिंदुओं के बीच अवलोकन स्थान में दो बिंदुओं की समानता के रूप में उनके बीच अनुयोजकता के रूप में मापा जा सकता है। निम्न द्वारा दिया गया है किː

$D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}$

जहाँ $\phi _{0}(y)$ के पहले बाएँ आइगेनसदिश द्वारा दिया गया मार्कोव श्रृंखला $M$ का स्थिर वितरण है। स्पष्ट रूप से:

$\phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}$

सहज रूप से, $D_{t}(x_{i},x_{j})$ छोटा होता है यदि बड़ी संख्या में छोटे रास्ते $x_{i}$ और $x_{j}$ जुड़ते हैं। हमारी पिछली चर्चा के आधार पर प्रसार दूरी से जुड़ी कई दिलचस्प विशेषताएं हैं। $t$ मापक्रम मापदण्ड के रूप में भी कार्य करता है:

1. अंक दिए गए मापक्रम पर निकट हैं (जैसा $D_{t}(x_{i},x_{j})$ निर्दिष्ट किया गया है) यदि वे त्र में अत्यधिक जुड़े हुए हैं, इसलिए स्तवक की अवधारणा पर बल देते हैं।
2. यह दूरी शोर के लिए शक्तिशाली है, क्योंकि दो बिंदुओं के बीच की दूरी लंबाई $t$ बिंदुओं के बीच के सभी संभावित रास्तों पर निर्भर करती हैं।
3. मशीन के सीखने के दृष्टिकोण से, दूरी $x_{i}$ को जोड़ने वाले सभी साक्ष्यों को ध्यान में रखती है, जिससे हमें यह निष्कर्ष निकालने की अनुमति मिलती है कि यह दूरी बहुसंख्यता के आधार पर निष्कष कलन विधि की अभिकल्पना के लिए उपयुक्त है।

प्रसार प्रक्रिया और निम्न-आयामी अंत: स्थापन

आइगेनसदिश का उपयोग करके प्रसार दूरी की गणना की जा सकती है

$D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,$

इसलिए आइगेनसदिश को आंकड़ों के लिए निर्देशांक के एक नए सम्मुच्चय के रूप में उपयोग किया जा सकता है। प्रसार मानचित्र को इस प्रकार परिभाषित किया गया है:

$\Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))$

वर्णक्रम क्षय के कारण, यह केवल पहले k ईजेनसदिश और आइगेनवैल्यू का उपयोग करने के लिए पर्याप्त है।

इस प्रकार हम मूल आंकड़ों से एक k-विमीय स्थल में प्रसार मानचित्र प्राप्त करते हैं जो मूल स्थान में सन्निहित है।

निम्न में यह सिद्ध होता है

$D_{t}(x_{i},x_{j})^{2}=||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,$

इसलिए प्रसार निर्देशांक में यूक्लिडियन दूरी प्रसार दूरी का अनुमान लगाती है।

कलन विधि

प्रसार मानचित्र का मूल कलन विधि ढांचा इस प्रकार है:

चरण 1. समानता आव्यूह L को देखते हुए।

चरण 2. मापदण्ड के अनुसार आव्यूह $\alpha$: $L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }$ को सामान्य करें।

चरण 3. सामान्यीकृत आव्यूह $M=({D}^{(\alpha )})^{-1}L^{(\alpha )}$ तैयार करें।

चरण 4. $M^{t}$ और संबंधित आइगेनसदिश के सबसे बड़े आइगेनमान ​​​​की गणना करें।

चरण 5. अंत: स्थापन प्राप्त करने के लिए प्रसार मानचित्र $\Psi _{t}$ का उपयोग करें।

आवेदन

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

इसके अतिरिक्त, प्रसार मानचित्र ढांचे को उत्पादक रूप से जटिल संजाल तक बढ़ाया गया है,

 | last1 = De Domenico
 | first1 = Manlio
 | url = https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.168301
 | title = प्रसार ज्यामिति सामूहिक घटना में कार्यात्मक समूहों के उद्भव को उजागर करती है| journal = Physical Review Letters
 | volume = 118
 | issue = 16
 | pages  = 168301
 | year = 2017
 | doi = 10.1103/PhysRevLett.118.168301
| pmid = 28474920
| arxiv = 1704.07068
| bibcode = 2017PhRvL.118p8301D
| s2cid = 2638868
}</ref> नेटवर्क के एक कार्यात्मक संगठन का खुलासा करता है जो विशुद्ध रूप से सांस्थितिकीय या संरचनात्मक एक से भिन्न होता है।

यह भी देखें

• अरैखिक विमीयता में अवकरण
• वर्णक्रमीय गुच्छन