📊 statistics

Power properties of the two-sample test based on the nearest neighbors graph

यह शोध पत्र उन मामलों के लिए डिटेक्शन थ्रेशोल्ड (detection thresholds) स्थापित करके निकटतम पड़ोसी ग्राफ (nearest neighbor graphs) पर आधारित टू-सैंपल टेस्ट की सैद्धांतिक समझ का विस्तार करता है जहाँ पड़ोसियों की संख्या नमूना आकार के साथ बढ़ती है, एक एक्सपोनेंट गैप (exponent gap) को भरने के लिए एक टू-साइडेड टेस्ट प्रस्तावित करता है, और यह प्रदर्शित करता है कि ग्राफ घनत्व में वृद्धि सांख्यिकीय शक्ति (statistical power) को बढ़ाती है।

मूल लेखक: Rahul Raphael Kanekar

प्रकाशित 2026-07-21

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

CC BY 4.0

मूल लेखक: Rahul Raphael Kanekar

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

कल्पना कीजिए कि आप एक जासूस हैं जो यह पता लगाने की कोशिश कर रहे हैं कि क्या दो समूहों के लोग वास्तव में एक ही भीड़ से हैं या वे गुप्त रूप से अलग हैं। शायद आपके पास गर्मियों की पार्टी की तस्वीरों का एक ढेर है और सर्दियों के गाला (gala) का दूसरा ढेर है, और आप जानना चाहते हैं: "क्या ये वही लोग हैं, बस अलग तरह के कपड़े पहने हुए हैं, या ये दो पूरी तरह से अलग समूह हैं?" सांख्यिकी (statistics) की दुनिया में, इसे "टू-सैंपल प्रॉब्लम" (two-sample problem) कहा जाता है। आमतौर पर, यदि आपके पास केवल एक संख्या है जिसे देखना है (जैसे ऊंचाई), तो उन्हें छोटे से बड़े क्रम में रैंक करना और अंतर को पहचानना आसान होता है। लेकिन क्या होगा यदि आपको एक साथ एक दर्जन गुणों के आधार पर लोगों की तुलना करनी हो—ऊंचाई, वजन, जूते का आकार, पसंदीदा रंग, और वे कितनी बार पलकें झपकाते हैं? अचानक, आपके पास रैंक करने का कोई सरल तरीका नहीं बचता। आप यह नहीं कह सकते कि एक व्यक्ति दूसरे से "बड़ा" है जब वे इतने कई तरीकों से अलग हों।

इसे हल करने के लिए, सांख्यिकीविदों ने एक चतुर तरकीब निकाली: वे एक मानचित्र (map) बनाते हैं। रैंकिंग करने के बजाय, वे बिंदुओं को जोड़ते हैं। कल्पना कीजिए कि हर व्यक्ति एक विशाल कागज पर एक बिंदु है। यदि दो बिंदु एक-दूसरे के करीब हैं, तो आप उनके बीच एक रेखा खींचते हैं। इन रेखाओं के पैटर्न को देखकर, आप देख सकते हैं कि क्या दो समूह आपस में मिल रहे हैं या अलग रह रहे हैं। यदि समूह एक ही हैं, तो रेखाएं हर जगह एक-दूसरे को काटेंगी, दोनों समूहों के बिंदुओं को जोड़ते हुए। यदि समूह अलग हैं, तो रेखाएं मुख्य रूप से अपने स्वयं के समूहों के भीतर ही रहेंगी, जैसे दो अलग पड़ोस जो एक-दूसरे से बात नहीं करते। यही "ग्राफ-आधारित परीक्षण" (graph-based testing) का सार है।

अब, यहाँ एक मोड़ है: आपको कितनी रेखाएं खींचनी चाहिए? क्या आपको हर बिंदु को उसके केवल एक सबसे करीबी पड़ोसी से जोड़ना चाहिए, या आपको उसे उसके शीर्ष 10, 50, या यहाँ तक कि 100 करीबी पड़ोसियों से जोड़ना चाहिए? लंबे समय तक, वैज्ञानिकों ने सोचा कि केवल कुछ पड़ोसियों से जोड़ना सबसे सुरक्षित दांव है। लेकिन इस शोध पत्र में, स्टैनफोर्ड यूनिवर्सिटी के राहुल रैफेल कनेकर एक साहसी प्रश्न पूछते हैं: क्या होगा यदि हम अधिक डेटा मिलने पर अधिक पड़ोसियों को जोड़ते हैं? क्या मानचित्र को "सघन" (dense) बनाने से हमें अंतर पहचानने में मदद मिलती है, या यह केवल रेखाओं का एक उलझा हुआ जाल बन जाता है जो हमें भ्रमित कर देता है?

यह शोध पत्र इस प्रश्न की गहराई में जाने के लिए "के-नेरेस्ट नेबर्स ग्राफ" (K-nearest neighbors graph) नामक एक विशिष्ट प्रकार के मानचित्र का उपयोग करता है। "K" का अर्थ है कि आप कितने पड़ोसियों को जोड़ते हैं। लेखक की मुख्य खोज यह है कि K को बढ़ाना (ग्राफ को सघन बनाना) परीक्षण की शक्ति को बढ़ाता है, लेकिन केवल तभी जब आप इसे सावधानी से करें। उन्होंने पाया कि यदि आप अपने नमूना आकार (sample size) के बढ़ने के साथ K को बढ़ने देते हैं, तो आप उन अंतरों का पता लगा सकते हैं जो पहले अदृश्य थे। हालाँकि, एक पेंच है: डेटा का विश्लेषण करने का तरीका इस बात पर निर्भर करता है कि ग्राफ कितना "सघन" है और आप कितने आयामों (traits) को माप रहे हैं।

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

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

तकनीकी सारांश: निकटतम पड़ोसी ग्राफ (Nearest Neighbors Graph) पर आधारित दो-नमूना परीक्षण के शक्ति गुण (Power Properties)

समस्या विवरण
यह शोध पत्र गैर-पैरामीट्रिक दो-नमूना समस्या को संबोधित करता है: बिना किसी विशिष्ट पैरामीट्रिक रूपों की धारणा के, दो बहुभिन्नरूपी वितरणों (multivariate distributions) की समानता $H_0: F = G$ बनाम $H_1: F \neq G$ का परीक्षण करना। जबकि ग्राफ-आधारित परीक्षण, जो ग्राफ (जैसे कि मिनिमल स्पैनिंग ट्री या $K$ -निकटतम पड़ोसी ग्राफ) बनाने के लिए बिंदुओं के बीच की दूरियों का उपयोग करते हैं, रैंक-आधारित विधियों के एक वितरण-मुक्त विकल्प के रूप में कार्य करते हैं, उनकी सैद्धांतिक समझ सीमित रही है। विशेष रूप से, मौजूदा स्पर्शोन्मुखी सिद्धांत (asymptotic theory) पेनरोज़ और युकिच के "स्थिरता ग्राफ" (stabilizing graphs) ढांचे पर निर्भर करता है, जो उन ग्राफों पर लागू होता है जहाँ स्थानीय संरचना दूर के बिंदुओं से स्वतंत्र होती है। यह ढांचा तब तक तो मान्य है जब $K$ स्थिर रहता है, लेकिन यह तब विफल हो जाता है जब नमूना आकार $N$ के साथ पड़ोसियों की संख्या $K$ बढ़ती है। यह शोध पत्र $K$ -निकटतम पड़ोसी ( $K$ -NN) परीक्षण के शक्ति गुणों की जांच करता है जब $K = k_N$ बढ़ता है, जो कि एक ऐसा क्षेत्र है जिसे पहले कठोर सैद्धांतिक औचित्य की कमी थी।

कार्यप्रणाली
लेखक स्पर्शोन्मुखी विश्लेषण (asymptotic analysis) को सुगम बनाने के लिए एक पॉइसनयुक्त (Poissonized) सेटिंग का उपयोग करते हैं, जहाँ नमूना आकार एक पॉइसन वितरण का अनुसरण करता है, जिससे स्थानिक स्वतंत्रता गुणों का उपयोग करना संभव हो जाता है। परीक्षण सांख्यिकी $T(G)$ उस निर्मित ग्राफ में किनारा (edge) की संख्या गिनती है जो दो अलग-अलग नमूनों के बिंदुओं को जोड़ते हैं।

मुख्य कार्यप्रणाली संबंधी चरण शामिल हैं:

गैर-स्थिरता (Non-Stabilization) पर विजय: चूंकि $k_N$ -NN ग्राफ गैर-स्थिर (not stabilizing) है जब $k_N \to \infty$ , लेखक स्थिर कार्यात्मकों (stabilizing functionals) के लिए मानक सीमा प्रमेयों (limit theorems) पर भरोसा नहीं कर सकते। इसके बजाय, वे परीक्षण सांख्यिकी का एक "हैंड्स-ऑन" विश्लेषण करते हैं, जो बढ़ते पड़ोसियों की संख्या द्वारा प्रेरित स्थानीय निर्भरता संरचना को स्पष्ट रूप से मात्रात्मक रूप से निर्धारित करता है।
स्पर्शोन्मुखी सामान्यता (Asymptotic Normality): सांख्यिकी के एक खंडित संस्करण (truncated version) पर लागू डिपेंडेंसी ग्राफ के स्टाइन विधि (Stein's method) का उपयोग करते हुए, लेखक सामान्य विकल्पों के तहत परीक्षण सांख्यिकी के लिए एक केंद्रीय सीमा प्रमेय (CLT) स्थापित करते हैं। वे सिद्ध करते हैं कि $k_N = o(N^{1/4})$ के लिए, मानकीकृत सांख्यिकी एक सामान्य वितरण की ओर अभिसरित होती है।
सशर्त बनाम असंशर्त विश्लेषण (Conditional vs. Unconditional Analysis): लेखक असंशर्त सांख्यिकी और एक सशर्त सांख्यिकी (बिंदुओं के स्थानों पर आधारित, जो क्रमपरिवर्तन परीक्षणों के लिए प्रासंगिक है) दोनों के लिए CLT व्युत्पन्न करते हैं। सशर्त CLT $k_N$ की एक व्यापक श्रेणी ( $k_N = o(N)$ ) के लिए मान्य है, जबकि असंशर्त CLT के लिए अधिक सख्त $k_N = o(N^{1/4})$ की आवश्यकता होती है क्योंकि मार्जिनल वितरण में बिंदुओं के बीच उच्च निर्भरता होती है।
स्थानीय शक्ति विश्लेषण (Local Power Analysis): लेखक स्थानीय विकल्पों के लिए डिटेक्शन थ्रेशोल्ड का विश्लेषण करते हैं जहाँ पैरामीटर अंतर $\|\theta_N - \theta_1\|$ एक दर $\epsilon_N$ पर घटता है। वे परीक्षण के व्यवहार को वर्गीकृत करने के लिए एक महत्वपूर्ण आयाम $d_c(\gamma) = \lfloor 8(1-\gamma) \rfloor$ (यह मानते हुए कि $k_N = N^\gamma$ ) को परिभाषित करते हैं।

मुख्य योगदान

सैद्धांतिक ढांचे का विस्तार: यह शोध पत्र बढ़ते $K$ के मामले के लिए, विशेष रूप से $K$ -NN ग्राफ के लिए, स्थिरता ढांचे से परे ग्राफ-आधारित परीक्षणों की सैद्धांतिक समझ का विस्तार करता है।
डिटेक्शन थ्रेशोल्ड (Detection Thresholds): लेखक एक-पक्षीय (1-sided) और दो-पक्षीय (2-sided) दोनों संस्करणों के लिए सटीक डिटेक्शन थ्रेशोल्ड व्युत्पन्न करते हैं। वे प्रदर्शित करते हैं कि जब आयाम $d$ महत्वपूर्ण आयाम $d_c(\gamma)$ से अधिक होता है, तो इन परीक्षणों का व्यवहार काफी भिन्न हो जाता है।
"एक्सपोनेंट गैप" (Exponent Gap) का समाधान: एक प्राथमिक योगदान एक दो-पक्षीय परीक्षण का प्रस्ताव और विश्लेषण है। लेखक दिखाते हैं कि पारंपरिक एक-पक्षीय परीक्षण उच्च आयामों ( $d > d_c(\gamma)$ ) में एक "एक्सपोनेंट गैप" से ग्रस्त है, जहाँ इसकी शक्ति विकल्प की दिशा पर निर्भर करती है (कुछ दिशाओं में "आयाम का अभिशाप" या curse of dimensionality का सामना करती है)। दो-पक्षीय परीक्षण इस गैप को समाप्त करता है, जो विकल्प की दिशा के बावजूद स्थिर डिटेक्शन थ्रेशोल्ड प्रदान करता है।
ग्राफ घनत्व के माध्यम से शक्ति संवर्धन: परिणाम ग्राफ घनत्व (दिए गए $K$ को बढ़ाने) के माध्यम से परीक्षण की शक्ति बढ़ाने के लिए सैद्धांतिक औचित्य प्रदान करते हैं, विशेष रूप से दो-पक्षीय संस्करण के लिए, क्योंकि जैसे-जैसे $k_N$ बढ़ता है, डिटेक्शन थ्रेशोल्ड पैरामीट्रिक दर ( $N^{-1/2}$ ) के करीब पहुँच जाता है।

परिणाम

महत्वपूर्णता से नीचे ( $d \leq d_c(\gamma)$ ): दोनों एक-पक्षीय और दो-पक्षीय परीक्षणों का समान डिटेक्शन थ्रेशोल्ड $N^{-1/4}$ है। सीमित शक्ति (limiting power) मानक सामान्य CDF द्वारा निर्धारित होती है।
महत्वपूर्णता के ऊपर ( $d > d_c(\gamma)$ ):
- एक-पक्षीय परीक्षण: एक्सपोनेंट गैप प्रदर्शित करता है। इसका डिटेक्शन थ्रेशोल्ड या तो $N^{-1/2 - 2(1-\gamma)/d}$ ("आयाम का आशीर्वाद" या blessing of dimensionality) या $N^{-2(1-\gamma)/d}$ ("आयाम का अभिशाप" या curse of dimensionality) होता है, जो विकल्प की दिशा पर निर्भर करता है। इन दरों के बीच के अंतराल में, शक्ति एक विशिष्ट दिशात्मक पद $b(h, \theta_1)$ के चिह्न के आधार पर या तो 0 या 1 होती है।
- दो-पक्षीय परीक्षण: एकल डिटेक्शन थ्रशहोल्ड $N^{-1/2 - 2(1-\gamma)/d}$ के साथ स्थिर व्यवहार प्रदर्शित करता है। यह एक्सपोनेंट गैप से ग्रस्त नहीं है और इसका आयाम के साथ शक्ति में सुधार होता है, जो $k_N$ बढ़ने पर पैरामीट्रिक दर $N^{-1/2}$ के करीब पहुँच जाता है।
सिमुलेशन: कृत्रिम डेटा (गौसियन स्केल परटर्बेशन, लॉग-नॉर्मल परिवार) और वास्तविक डेटा (20 न्यू्सग्रुप्स) पर अनुभवजन्य परिणाम सैद्धांतिक निष्कर्षों की पुष्टि करते हैं। वे पुष्टि करते हैं कि उच्च आयामों में एक-पक्षीय परीक्षण की शक्ति विकल्प की दिशा के प्रति अत्यधिक संवेदनशील है, जबकि दो-पक्षीय परीक्षण मजबूत बना रहता है। सिमुलेशन यह भी सुझाव देते हैं कि $K$ को बढ़ाने से शक्ति में सुधार होता है, जिसमें $K \leq N/30$ शक्ति और सामान्य सन्निकटन (normal approximation) की वैधता के बीच एक व्यावहारिक समझौता प्रदान करता है।

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

इसी तरह के और पेपर