📊 statistics

Nearest-Neighbor Radii under Dependent Sampling

यह शोध पत्र स्थापित करता है कि स्ट्रॉन्ग मिक्सिंग डिपेंडेंट सैंपलिंग के तहत नियरेस्ट-नेबर रेडाई अपनी सूचनात्मक ज्यामितीय विशेषताओं को बनाए रखती हैं, जो वितरण-मुक्त लगभग निश्चित अभिसरण (distribution-free almost sure convergence) और तीक्ष्ण गैर-अनंत मोमेंट बाउंड्स प्रदर्शित करती हैं जो एम्बिएंट डायमेंशन के बजाय स्थानीय इंट्रिन्सिक डायमेंशन पर निर्भर करते हैं।

मूल लेखक: Yuanyuan Gao, Yilong Hou, Zhexiao Lin

प्रकाशित 2026-05-15

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Yuanyuan Gao, Yilong Hou, Zhexiao Lin

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक भीड़ भरे कमरे में खड़े हैं, और अपने करीबी दोस्तों को खोजने की कोशिश कर रहे हैं। एक पूरी तरह से यादृच्छिक (random) भीड़ में (जहाँ हर कोई स्वतंत्र रूप से बिखरा हुआ है), आप आसानी से यह अनुमान लगा सकते हैं कि आपको अपने 5वें सबसे करीबी दोस्त तक पहुँचने के लिए कितनी दूर तक हाथ बढ़ाना होगा। यदि आपके दोस्त बहुत कम हैं, तो आप दूर तक हाथ बढ़ाएंगे। यदि वे बहुत पास-पास हैं, तो आप बस थोड़ा सा हाथ बढ़ाएंगे। यह दूरी जिसे गणितज्ञ "निकटतम-पड़ोसी त्रिज्या" (nearest-neighbor radius) कहते हैं।

दशकों से, मशीन लर्निंग एल्गोरिदम इसी सरल विचार पर निर्भर रहे हैं: "अनुमान लगाने के लिए अपने आस-पास के लोगों को देखो।" लेकिन इसमें एक पेंच है। इन एल्गोरिदम के पीछे का अधिकांश गणित यह मानता है कि भीड़ यादृच्छिक (random) है। हालाँकि, वास्तविक दुनिया में, डेटा अक्सर अनुक्रमों (sequences) के रूप में आता है जहाँ लोग आपस में जुड़े होते हैं। डोमिनोज़ की एक गिरती हुई रेखा, शेयर बाजार का टिकर, या मौसम की रिपोर्ट के बारे में सोचें: अभी क्या हो रहा है, वह इस बात से बहुत प्रभावित होता है कि एक क्षण पहले क्या हुआ था। इसे "आश्रित नमूनाकरण" (dependent sampling) कहा जाता है।

यह शोध पत्र मुख्य प्रश्न यह पूछता है: क्या इस "जुड़ाव" से यह बदल जाता है कि हमें अपने दोस्तों को खोजने के लिए कितनी दूर तक हाथ बढ़ाना पड़ता है?

मुख्य खोज: "रस्सी" बनाम "भीड़"

लेखक, युआनयुआन गाओ, यिलोंग हौ और झेक्सियाओ लिन ने यह परीक्षण करने का प्रयास किया कि क्या "खेल के नियम" तब बदल जाते हैं जब डेटा आश्रित (dependent) होता है।

1. "कमजोर बंधन" की उपमा (The "Weak Tether" Analogy)
कल्पना कीजिए कि कमरे में मौजूद लोग बहुत लंबी, खिंचने वाली रस्सियों से एक साथ बंधे हुए हैं। यदि रस्सियाँ छोटी और कसी हुई हैं (मजबूत निर्भरता), तो समूह एक ही पिंड (blob) की तरह चलता है। यदि रस्सियाँ लंबी और ढीली हैं (कमजोर निर्भरता), तो समूह अभी भी एक साथ चलता है, लेकिन व्यक्ति एक-दूसरे से अलग हो सकते हैं।

यह शोध पत्र सिद्ध करता है कि जब तक "रस्सियाँ" बहुत अधिक कसी हुई नहीं हैं (एक स्थिति जिसे वे ज्यामितीय मिश्रण/geometric mixing कहते हैं, जिसका अर्थ है कि एक व्यक्ति का दूसरे पर प्रभाव समय के साथ तेजी से कम हो जाता है), तब तक आपको अपने पड़ोसियों को देखने के लिए जितनी बड़ी त्रिज्या की आवश्यकता होती है, वह बिल्कुल उतनी ही रहती है जितनी कि तब होती जब हर कोई यादृच्छिक रूप से खड़ा होता।

2. "स्थानीय मानचित्र" बनाम "बड़ा मानचित्र" (The "Local Map" vs. The "Big Map")
आमतौर पर, हम सोचते हैं कि कमरा कितना भीड़भाड़ वाला है, यह कुल आयामों (dimensions) पर आधारित होता है (जैसे एक 3D कमरा बनाम एक 100D कमरा)। लेकिन लेखक दिखाते हैं कि वास्तव में डेटा का स्थानीय आकार (local shape) मायने रखता है।

उपमा: कल्पना कीजिए कि एक 3D कमरे में तैरते हुए कागज की एक सपाट शीट है। भले ही कमरा 3D है, लेकिन कागज केवल 2D है। यदि आप कागज पर खड़े हैं, तो आप अपने पड़ोसियों के लिए 2D दूरी की परवाह करते हैं, न कि हवा के माध्यम से 3D दूरी की।
शोध पत्र दिखाता है कि आश्रित डेटा के साथ भी, आपको जिस "पहुँच" (reach) की आवश्यकता होती है, वह इस स्थानीय 2D आकार (intrinsic dimension) द्वारा निर्धारित होती है, न कि विशाल 3D कमरे (ambient dimension) द्वारा।

उन्होंने क्या पाया (खेल के "नियम")

यह शोध पत्र स्थापित करता है कि यह कैसे काम करता है (तीन मुख्य "नियम"):

नियम 1: सीमा (Limit) समान है।
यदि आप कमरे में अधिक लोग जोड़ते जाते हैं, तो आपके k-वें सबसे करीबी दोस्त की दूरी अंततः एक विशिष्ट मान पर स्थिर हो जाएगी। यह शोध पत्र सिद्ध करता है कि भले ही "रस्सियाँ" (निर्भरता) मौजूद हों, यह अंतिम दूरी वैसी ही है जैसी तब होती जब रस्सियाँ मौजूद नहीं होतीं। "गंतव्य" नहीं बदला है।
नियम 2: गति धीमी है, लेकिन पथ वही है।
हालाँकि अंतिम दूरी समान है, लेकिन वहाँ पहुँचने में थोड़ा अधिक समय लगता है या अधिक डेटा की आवश्यकता होती है जब लोग जुड़े होते हैं।
- उपमा: यदि आप एक पुस्तकालय में एक विशिष्ट पुस्तक खोजने की कोशिश कर रहे हैं जहाँ पुस्तकें यादृच्छिक रूप से रखी गई हैं, तो आप उसे जल्दी ढूंढ लेते हैं। यदि पुस्तकें ढेरों में रखी हैं (आश्रित), तो आपको उसी पुस्तक को खोजने के लिए थोड़ा और गहराई तक खुदाई करनी पड़ सकती है या कुछ और ढेर चेक करने पड़ सकते हैं।
- गणित दिखाता है कि इस निर्भरता की "लागत" केवल एक छोटा सा दंड (एक लॉगरिदमिक कारक) है। यह मौलिक सूत्र को नहीं बदलता कि दूरी कैसे स्केल करती है।
नियम 3: यह वास्तविक डेटा पर काम करता है।
लेखकों ने केवल गणित नहीं किया; उन्होंने प्रयोग भी किए।
- सिंथेटिक परीक्षण: उन्होंने अलग-अलग स्तर के "जुड़ाव" के साथ नकली टाइम-सीरीज डेटा (जैसे शेयर की कीमतें) बनाया। उन्होंने पाया कि निकटतम पड़ोसियों की "पहुँच" अभी भी यादृच्छिक डेटा के समान ही नियमों का पालन करती है।
- वास्तविक दुनिया के परीक्षण: उन्होंने इसे वास्तविक टाइम-सीरीज डेटा (मौसम, बिजली का उपयोग, यातायात) पर परखा। उन्होंने एक साधारण "अपने पड़ोसियों को देखो" पद्धति की तुलना जटिल, आधुनिक AI मॉडलों से की। उन्होंने पाया कि सरल पड़ोसी विधि अभी भी आश्चर्यजनक रूप से अच्छी तरह से काम करती है, जो यह सिद्ध करता है कि इन वास्तविक, जुड़े हुए डेटासेट्स की ज्यामिति अभी भी अनुमानित है।

निचोड़ (The Bottom Line)

इस शोध पत्र का मुख्य संदेश आश्चर्यजनक रूप से सरल और आश्वस्त करने वाला है: निर्भरता (Dependence), निकटतम पड़ोसियों की ज्यामिति को नहीं तोड़ती है।

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

यह मशीन लर्निंग इंजीनियरों को जटिल, वास्तविक दुनिया के अनुक्रमिक डेटा पर इन क्लासिक, सरल और प्रभावी "निकटतम पड़ोसी" उपकरणों का उपयोग करने के लिए हरी झंडी देता है, बिना इस बात की चिंता किए कि डेटा का "जुड़ाव" मौलिक रूप से गणित को तोड़ देगा।

तकनीकी सारांश: आश्रित सैंपलिंग के तहत निकटतम-पड़ोसी त्रिज्या (Nearest-Neighbor Radii)

समस्या विवरण

निकटतम-पड़ोसी (NN) विधियाँ शास्त्रीय और आधुनिक दोनों मशीन लर्निंग के लिए आधारभूत हैं, जो $k$ -NN वर्गीकरण और रिग्रेशन से लेकर मैनिफोल्ड लर्निंग और सूचना पुनर्प्राप्ति (information retrieval) जैसे कार्यों को सुदृढ़ करती हैं। इन विधियों का प्रदर्शन उनके द्वारा निर्मित स्थानीय पड़ोस के ज्यामितिक गुणों पर अत्यधिक निर्भर करता है। विशेष रूप से, एक क्वेरी बिंदु $x$ से उसके $k$ -वें निकटतम पड़ोसी की दूरी, जिसे $R_{n,k}(x)$ द्वारा दर्शाया जाता है, स्थानीय पड़ोस के पैमाने (scale) को निर्धारित करती है और बायस-वैरिएंस ट्रेडऑफ (bias-variance tradeoff) को नियंत्रित करती है।

जबकि स्वतंत्र और समान रूप से वितरित (i.i.d.) सैंपलिंग के तहत $R_{n,k}(x)$ का व्यवहार अच्छी तरह से समझा गया है—जहाँ कैनोनिकल स्केल $(k/n)^{1/s}$ होता है (यहाँ $s$ स्थानीय आंतरिक आयाम है)—कई वास्तविक दुनिया की लर्निंग समस्याओं में आश्रित डेटा (जैसे, टाइम सीरीज़, सुदृढीकरण लर्निंग ट्रेजेक्टरीज, स्पैटियोटेम्पोरल सेंसिंग) शामिल होते हैं। ऐसी सेटिंग्स में, अवलोकन अक्सर दृढ़ता से आश्रित होते हैं, भले ही उनकी मार्जिनल डिस्ट्रीब्यूशन स्थिर हो। यह शोध पत्र जिस केंद्रीय प्रश्न का समाधान करता है वह है: आश्रयता (dependence) निकटतम-पड़ोसी पड़ोस की ज्यामिति को कैसे प्रभावित करती है? विशेष रूप से, क्या आश्रयता निकटतम-पड़ोसी त्रिज्या के स्केलिंग को मौलिक रूप से बदल देती है, या कैनोनिकल ज्यामितिक स्केल सुदृढ़ रहता है?

कार्यप्रणाली और सेटअप

लेखक $\mathbb{R}^d$ -मान वाले यादृच्छिक चरों (random variables) के एक त्रिकोणीय सरणी $[X_{n,i} : 1 \le i \le n, n \ge 1]$ का विश्लेषण करते हैं जो एक सामान्य प्रायिकता स्थान (probability space) पर परिभाषित हैं।

मार्जिनल डिस्ट्रीबशन: सभी अवलोकन एक सामान्य मार्जिनल लॉ $\mu$ साझा करते हैं।
आश्रयता संरचना (Dependence Structure): शोध पत्र प्रत्येक पंक्ति में स्ट्रॉन्ग मिक्सिंग ( $\alpha$ -mixing) आश्रयता को मानता है। मिक्सिंग गुणांक $\alpha_m$ , $m$ इंडेक्सों द्वारा अलग किए गए अनुक्रम के खंडों के बीच आश्रयता के क्षय (decay) को परिमाणित करते हैं।
अध्ययन की वस्तु: त्रिज्या $R_{n,k}(x) = \|X_{n}^{(k)}(x) - x\|$ , जहाँ $X_{n}^{(k)}(x)$ $n$ अवलोकनों के बीच $x$ का $k$ -वाँ निकटतम पड़ोसी है।

विश्लेषण मिक्सिंग के दो शासन (regimes) के बीच अंतर करता है:

पॉलीनोमियल मिक्सिंग (Polynomial Mixing): $\alpha_m \lesssim m^{-\gamma}$ किसी $\gamma > 1$ के लिए।
जियोमेट्रिक (एक्सपोनेंशियल) मिक्सिंग (Geometric Mixing): $\alpha_m \le e^{-\gamma m}$ किसी $\gamma > 0$ के लिए।

सैद्धांतिक परिणाम एक स्थानीय घातांक (local exponent) $s > 0$ का उपयोग करके तैयार किए गए हैं, न कि एम्बिएंट डायमेंशन $d$ का। यह घातांक $x$ के पास स्थानीय द्रव्यमान संचय (local mass accumulation) को लक्षणित करता है (अर्थात, $\mu(B(x,r)) \asymp r^s$ ), जिससे सिद्धांत को कम-आयामी मैनिफोल्ड्स के पास केंद्रित डेटा पर लागू करना संभव होता है।

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

1. डिस्ट्रीब्यूशन-फ्री लगभग निश्चित अभिसरण (Almost Sure Convergence)

पॉलीनोमियल $\alpha$ -मिक्सिंग के तहत, लेखक एक डिस्ट्रीब्यूशन-फ्री लगभग निश्चित अभिसरण प्रमेय स्थापित करते हैं।

परिणाम: यदि $k/n \to 0$ , तो $R_{n,k}(x) \xrightarrow{a.s.} r_x$ , जहाँ $r_x$ , $\mu$ के सपोर्ट से $x$ की दूरी है।
निहितार्थ: यदि $x$ , $\mu$ के सपोर्ट में है, तो त्रिज्या लगभग निश्चित रूप से 0 की ओर अभिसरित होती है। यह परिणाम घनत्व (density) या स्मूथनेस धारणाओं की आवश्यकता के बिना आश्रित त्रिकोणीय सरणियों के लिए शास्त्रीय i.i.d. निरंतरता (consistency) को विस्तारित करता है, यह प्रदर्शित करते हुए कि कमजोर आश्रयता सीमित ज्यामितिक व्यवहार को नहीं बदलती है।

2. जियोमेट्रिक मिक्सिंग के तहत गैर-एसिम्प्टोटिक मोमेंट बाउंड्स

जियोमेट्रिक $\alpha$ -मिक्सिंग की मजबूत धारणा और स्थानीय द्रव्यमान स्थितियों (Assumptions 2 and 3) के तहत, शोध पत्र सटीक गैर-एसिम्प्टोटिक बाउंड्स प्राप्त करता है।

टेल बाउंड्स (Tail Bounds): लेखक एक टेल बाउंड सिद्ध करते हैं जो दिखाता है कि $R_{n,k}(x)$ , कैनोनical स्केल $(k/n)^{1/s}$ के आसपास केंद्रित होता है। अभिसरण घातांक (concentration exponent) में एक अतिरिक्त $\log n$ कारक शामिल है, जो आश्रित अवलोकनों को स्वतंत्र ब्लॉकों में डिकपल करने के लिए चुकाई गई "कीमत" है (जो मिक्सिंग सीक्वेंस विश्लेषण में एक मानक तकनीक है)।
मोमेंट अपर बाउंड: $k \gtrsim \log n$ के शासन के लिए, शोध पत्र सटीक मोमेंट अपर बांड स्थापित करता है:
$\mathbb{E}[R_{n,k}(x)^p] \lesssim \left(\frac{k}{n}\right)^{p/s}$
मोमेंट लोअर बाउंड: एक मिलान स्थानीय ऊपरी-द्रव्यमान स्थिति के तहत, एक मिलान लोअर बाउंड प्राप्त किया गया है:
$\mathbb{E}[R_{n,k}(x)^p] \gtrsim \left(\frac{k}{n}\right)^{p/s}$
सटीक ऑर्डर लक्षण वर्णन: इन्हें जोड़ते हुए, शोध पत्र सिद्ध करता है कि जियोमेट्रिक मिक्सिंग के तहत, मोमेंट्स का सटीक क्रम है:
$\mathbb{E}[R_{n,k}(x)^p] \asymp \left(\frac{k}{n}\right)^{p/s}$

3. स्थानीय घातांक (Local Exponent) की व्याख्या

इस सिद्धांत की एक महत्वपूर्ण विशेषता एम्बिएंट डायमेंशन $d$ के बजाय स्थानीय घातांक $s$ पर इसकी निर्भरता है। यह आधुनिक उच्च-आयामी लर्निंग परिदृश्यों के साथ संरेखित है जहाँ डेटा अक्सर कम-आयामी मैनिफोल्ड्स के पास स्थित होता है। परिणाम पुष्टि करते हैं कि NN त्रिज्या का स्केलिंग, आश्रयता की उपस्थिति में भी, वितरण के पास के आंतरिक आयाम (intrinsic dimension) द्वारा निर्धारित होता है, न कि एम्बिएंट स्पेस द्वारा।

प्रयोगात्मक सत्यापन

शोध पत्र अपने सैद्धांतिक निष्कर्षों को सिंथेटिक और वास्तविक दुनिया के प्रयोगों के माध्यम से समर्थन देता है:

मोमेंट कन्वर्जेंस रेट: लीनियर गौसियन स्टेट-स्पेस मॉडल, हिडन मार्कोव मॉडल (HMM), और स्टेशनरी गौसियन प्रोसेस (RBF कर्नेल) पर प्रयोग पुष्टि करते हैं कि $\log(\text{moment})$ बनाम $\log(k/n)$ संबंध का अनुमानित ढलान (slope) सैद्धांतिक $p/s$ दर के अनुरूप है। कमजोर आश्रयता i.i.d. बेसलाइन के करीब रहती है, जबकि मध्यम/मजबूत आश्रयता सैद्धांतिक एकाग्रता दंड (concentration penalty) के अनुरूप विचलन पेश करती है।
एन्ट्रॉपी एस्टीमेशन: कोज़ाचेनको-लियोनेंको (Kozachenko–Leonenko) एन्ट्रॉपी एस्टिमेटर्स का उपयोग करते हुए, अध्ययन दिखाता है कि जब डेटा का आंतरिक आयाम $s$ होता है लेकिन उसे उच्च आयाम $d$ में देखा जाता है, तो एस्टिमेटर आंतरिक प्रक्रिया की एन्ट्रॉपी की ओर अभिसरित होता है। यह टेम्पोरल डिपेंडेंस के तहत भी तब तक मान्य रहता है जब तक कि स्थानीय ज्यामिति संरक्षित रहती है (जैसे, PCA के माध्यम से)।
वास्तविक दुनिया के बेंचमार्क: लेखक टाइम सीरीज़ फोरकास्टिंग और क्लासिफिकेशन कार्यों (Informer, Monash, और UCR डेटासेट्स सहित Time Series Pile से) पर Raw-kNN और PCA-kNN का मूल्यांकन करते हैं। परिणाम संकेत देते हैं कि निकटतम-पड़ोसी विधियाँ वास्तविक आश्रित डेटा पर भी सूचनात्मक बनी रहती हैं। PCA-kNN, Raw-kNN के तुलनीय प्रदर्शन करता है, जो सुझाव देता है कि आयामी न्यूनीकरण (dimension reduction) आश्रयता के तहत भी पड़ोस-आधारित भविष्यवाणी के लिए आवश्यक स्थानीय संरचना को संरक्षित कर सकता है।

महत्व और दावे

शोध पत्र एक सरल लेकिन महत्वपूर्ण संदेश का दावा करता है: कमजोर आश्रयता के तहत, निकटतम-प menyer ज्यामिति अपने कैनोनिकल स्केल के स्तर पर स्वतंत्र मामले के समान ही रहती है।

सैद्धांतिक प्रभाव: यह कार्य आश्रित सैंपलिंग के तहत लर्निंग विधियों के लिए एक ज्यामितीय नियंत्रण सिद्धांत प्रदान करता है। यह आश्रयता के प्रभाव को अलग करता है, यह दिखाते हुए कि जबकि आश्रयता एकाग्रता स्थिरांकों (concentration constants) को बदल देती है और एक लॉगरिदमिक दंड पेश करती है, यह मौलिक घातांक $(k/n)^{1/s}$ को नहीं बदलती है।
व्यावहारिक निहितार्थ: यह निष्कर्ष i.i.d. शासन से टाइम-सीरीज़ और अन्य आश्रित डेटा के लिए ज्यामितिक अंतर्ज्ञान और स्थानीय-विधि डिजाइन सिद्धांतों (जैसे, बैंडविड्थ चयन, पड़ोस आकार ट्यूनिंग) के हस्तांतरण को न्यायसंगत बनाता है। यह सुझाव देता है कि i.i.d. डेटा के लिए विकसित कई ह्यूरिस्टिक्स (heuristics) आश्रित सेटिंग्स में भी लागू रहने योग्य हैं, बशर्ते कि आश्रयता इतनी मजबूत न हो कि मिक्सिंग धारणाओं को अमान्य कर दे।

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