Manifold Dimension Estimation via Local Graph Structure

तकनीकी सारांश: स्थानीय ग्राफ संरचना के माध्यम से मैनिफोल्ड आयाम अनुमान

समस्या विवरण
एक उच्च-आयामी एम्बिएंट स्पेस $\mathbb{R}^p$ में सन्निहित एक मैनिफोल्ड की आंतरिक विमा (intrinsic dimension) $d$ का अनुमान लगाना नॉनलीनियर डाइमेंशनलिटी रिडक्शन की एक मौलिक चुनौती है। जबकि कई मौजूदा अनुमानक (जैसे, Local PCA, DanCo, TwoNN) "फ्लैटनेस धारणा" (flatness assumption) पर निर्भर करते हैं—जो स्थानीय पड़ोस को $d$-आयामी रैखिक उप-स्थानों (linear subspaces) के रूप में अनुमानित करते हैं—यह दृष्टिकोण तब संघर्ष करता है जब मैनिफोल्ड्स महत्वपूर्ण वक्रता (curvature) प्रदर्शित करते हैं या गैर-रैखिक रूप से सन्निहित होते हैं। हाल के तरीके जैसे Curvature-Adjusted PCA (CA-PCA) वक्रता के लिए आइगेनस्ट्रक्चर (eigenstructures) को स्पष्ट रूप से ठीक करने का प्रयास करते हैं, फिर भी वे अक्सर उच्च-आयामी एम्बिएंट स्पेस में अति-अनुमान (overestimation) या कम्प्यूटेशनल अस्थिरता से ग्रस्त होते हैं। लेखक उन विधियों के अंतराल की पहचान करते हैं जो अस्थिर प्रत्यक्ष वक्रता अनुमान या आइगेनवैल्यू गैप डिटेक्शन पर निर्भर किए बिना मजबूती से स्थानीय वक्रता को मॉडल कर सकें।

कार्यप्रणाली (Methodology)
लेखक एक नया ढांचा प्रस्तावित करते हैं जो मैनिफोल्ड आयाम अनुमान को स्थानीय PCA निर्देशांकों पर एक रिग्रेशन समस्या के रूप में पुनर्गठित करता है। स्थानीय वक्रता (curvature) का प्रत्यक्ष अनुमान लगाने या वक्रता टेंसरों को स्पष्ट रूप से अनुमानित करने के बजाय, यह विधि एक बिंदु $x_k$ के स्थानीय पड़ोस को एक सुचारू फलन (smooth function) $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$ के ग्राफ के रूप में मॉडल करती है।

1. स्थानीय ग्राफ प्रतिनिधित्व (Local Graph Representation): एक बिंदु $x_k$ और उसके $K$-निकटतम पड़ोसियों के लिए, लेखक स्पर्श रेखा स्थान (tangent space) के साथ संरेखित एक स्थानीय समन्वय प्रणाली स्थापित करने के लिए PCA करते हैं। पहले $d$ निर्देशांक स्पर्श रेखा स्थान का प्रतिनिधित्व करते हैं, जबकि शेष $p-d$ निर्देशांक अभिलंब स्थान (normal space) का प्रतिनिधित्व करते हैं।
2. रिग्रेशन फॉर्मूलेशन (Regression Formulation): ढांचा यह मानता है कि अभिलंब निर्देशांकों (normal coordinates) को स्पर्श रेखा निर्देशांकों के फलन के रूप में व्यक्त किया जा सकता है। चूंकि इस फलन का प्रथम-क्रम टेलर विस्तार (first-order Taylor expansion) शून्य होता है (स्पर्श रेखा स्थान द्वारा परिभाषा के अनुसार), लेखक स्थानीय वक्रता को पकड़ने के लिए द्वितीय-क्रम (quadratic) पदों का उपयोग करते हैं।
3. कैंडिडेट डायमेंशन प्रोबिंग (Candidate Dimension Probing): एल्गोरिदम संभावित आयामों $j$ (1 से $p-1$ तक) के माध्यम से पुनरावृत्ति करता है। प्रत्येक $j$ के लिए, यह पहले $j$ PCA निर्देशांकों को इनपुट के रूप में और $(j+1)$-वें निर्देशांक को आउटपुट के रूप la लेता है, और एक क्वाड्रेटिक रिग्रेशन मॉडल फिट करता है।
4. दो अनुमानक (Two Estimators):
   • क्वाड्रेटिक एम्बेडिंग (QE): क्वाड्रेटिक मॉडल को फिट करने के लिए ऑर्डिनरी लीस्ट स्क्वायर्स (OLS) का उपयोग करता है। यह मॉडल की उपयुक्तता (goodness-of-fit) का मूल्यांकन $F$-सांख्यिकी और एडजस्टेड $R^2$ का उपयोग करके करता है। अनुमानित आयाम वह सबसे छोटा $j$ है जहाँ मॉडल का फिट सांख्यिकीय रूप से महत्वपूर्ण (p-value < 1%) हो जाता है और सभी उच्च आयामों के लिए महत्वपूर्ण बना रहता है।
   • टोटल लीस्ट स्क्वायर्स (TLS): इनपुट और आउटपुट दोनों चरों में त्रुटियों को ध्यान में रखने के लिए टोटल लीस्ट स्क्वायर्स का उपयोग करता है। $F$-सांख्यिकी के बजाय, यह क्रमिक आयामों के बीच कुल TLS त्रुटि ($\eta_j$) में सापेक्ष गिरावट का मूल्यांकन करता है। अनुमानित आयाम सापेक्ष गिरावट का शिखर (peak) है।

प्रमुख योगदान

• रिग्रेशन-आधारित ढांचा (Regression-Based Framework): यह शोध पत्र एक नया दृष्टिकोण प्रस्तुत करता है जो आयाम अनुमान को एक रिकर्सिव रिग्रेशन समस्या के रूप में देखता है। यह अस्थिर स्थानीय ज्यामितीय अनुमान (जैसे प्रत्यक्ष वक्रता गणना) को एक सांख्यिकीय रूप से एकत्रित फिटिंग प्रक्रिया से बदल देता है, जिससे सैंपलिंग की कमी और शोर (noise) के प्रति अधिक मजबूती मिलती है।
• वक्रता-जागरूक मॉडलिंग (Curvature-Aware Modeling): क्वाड्रेटिक मॉडल का उपयोग करके, यह विधि प्रत्यक्ष वक्रता अनुमान या आइगेनवैल्यू सुधार की आवश्यकता के बिना मैनिफोल्ड की वक्रता को स्पष्ट रूप से कैप्चर करती है, जिससे PCA-आधारित विधियों में सामान्य अति-अनुमान की समस्याओं को कम किया जा सकता है।
• शोर और गैर-रैखिकता के प्रति मजबूती (Robustness to Noise and Nonlinearity): यह ढांचा स्वाभाविक रूप से शोर को समायोजित करता है और जटिल, गैर-रैखिक रूप से सन्निहित मैनिफोल्ड्स पर अच्छा प्रदर्शन करने के लिए डिज़ाइन किया गया है जहाँ फ्लैटनेस धारणाएं विफल हो जाती हैं।
• व्यावहारिक कार्यान्वयन (Practical Implementation): लेखक दो ठोस अनुमानक (QE और TLS) प्रदान करते हैं, जिसमें कम्प्यूटेशनल व्यवहार्यता सुनिश्चित करने के लिए पड़ोस के आकार के आधार पर खोज स्थान ($p_{max}$) को सीमित करने वाले ह्यूरिस्टिक्स सहित विस्तृत एल्गोरिदम शामिल हैं।

प्रायोगिक परिणाम
लेखकों ने 18 सिंथेटिक मैनिफोल्ड्स (स्फीयर, विकृत स्फीयर और गॉसियन सर्फेस सहित) और 6 वास्तविक दुनिया के डेटासेट्स (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift) पर QE और TLS का मूल्यांकन किया।

• सिंथेटिक डेटा: QE और TLS ने अत्याधुनिक विधियों (Local PCA, CA-PCA, DanCo, TwoNN, MADA, आदि) की तुलना में प्रतिस्पर्धी या बेहतर प्रदर्शन किया, विशेष रूप से छोटे-सैंपल शासन (small-sample regimes) और गैर-रैखिक रूप से सन्निहित मैनिफोल्ड्स (जैसे विकृत स्फीयर) पर। उन्होंने CA-PCA और Local PCA में देखे गए अति-अनुमान को प्रभावी ढंग से कम किया जब एम्बिएंट डायमेंशन $p$, आंतरिक डायमेंशन $d$ की तुलना में काफी अधिक होता है।
• शोर के प्रति मजबूती (Noise Robustness): गॉसियन, यूनिफॉर्म और लाप्लास शोर की उपस्थिति में, प्रस्तावित विधियों ने मजबूत प्रदर्शन बनाए रखा, और उन कई फ्लैटनेस-आधारित अनुमानकों से बेहतर प्रदर्शन किया जिनकी सटीकता काफी गिर गई थी।
• वास्तविक दुनिया का डेटा: वास्तविक दुनिया के डेटासेट्स पर, अनुमानकों ने सर्वसम्मत श्रेणियों के अनुरूप परिणाम दिए (जैसे, ISOMAP $\approx 3$, MNIST $\approx 8-11$ का अनुमान लगाना)। विशेष रूप से, उन्होंने उच्च एम्बिएंट डायमेंशन वाले डेटासेट्स पर Local PCA और CA-PCA में देखे गए गंभीर अति-अनुमान से परहेज किया।
• देखे गए सीमाएँ (Limitations Observed): विधियों ने "तुच्छ" (trivial) मैनिफोल्ड्स के मामले में कम प्रदर्शन दिखाया जिनमें शून्य वक्रता होती है (जैसे हाइपरबॉल्स), जहाँ क्वाड्रेटिक मॉडल एक मिस-स्पेसिफिकेशन है। इसके अतिरिक्त, TLS अपने आयामों के बीच सापेक्ष त्रुटि गिरावट पर निर्भरता के कारण 2 से नीचे सीमित है।

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