📊 statistics

Leave-One-Out Neighborhood Smoothing for Graphons: Berry-Esseen Bounds, Confidence Intervals, and Honest Tuning

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

मूल लेखक: Behzad Aalipur, Rachel Kilby

प्रकाशित 2026-03-17

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

CC BY 4.0

मूल लेखक: Behzad Aalipur, Rachel Kilby

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

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

यह ग्राफोन एस्टिमेशन (Graphon Estimation) की समस्या है। यह शोध पत्र इस समस्या को हल करने का एक नया तरीका प्रस्तावित करता है, और इससे भी महत्वपूर्ण बात यह है कि यह इस समस्या का समाधान करता है कि: आप अपने अनुमान के प्रति कितने आश्वस्त हो सकते हैं?

यहाँ इस शोध पत्र की कहानी है, जिसे सरल अवधारणाओं में विभाजित किया गया है।

1. पुराना तरीका: "डबल-डिप्पिंग" (दोहरी चोरी) की गलती

अतीत में, जासूस नेबरहुड स्मूथिंग (Neighborhood Smoothing) नामक एक विधि का उपयोग करते थे।

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

2. नया समाधान: "लीव-वन-आउट" (एक को छोड़ देना) सर्जरी

लेखक एक चतुर समाधान प्रस्तावित करते हैं जिसे लीव-वन-आउट (LOO) नेबरहुड स्मूथिंग कहा जाता है।

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

3. परिणाम: ईमानदार कॉन्फिडेंस इंटरवल (विश्वास अंतराल)

क्योंकि गणित अब साफ है, लेखक अंततः कॉन्फिडेंस इंटरवल (Confidence Intervals) बना सकते हैं।

कॉन्फिडेंस इंटरवल क्या है? यह संख्याओं की एक सीमा है जो कहती है, "हम 95% आश्वस्त हैं कि वास्तविक उत्तर 0.4 और 0.6 के बीच है।"
नवाचार: पिछली विधियाँ आपको एक संख्या (जैसे, "0.5") दे सकती थीं, लेकिन वे ईमानदारी से यह नहीं बता सकती थीं कि वह संख्या कितनी गलत हो सकती है। यह शोध पत्र आपको वह सुरक्षा जाल बनाने के दो तरीके प्रदान करता है:
1. "सुपर-सेफ" नेट (एम्पेरिकल बर्नस्टीन): यह एक बहुत ही विस्तृत, रूढ़िवादी जाल है। यह कम डेटा के साथ भी काम करता है और गारंटी देता है कि आप सच्चाई को नहीं चूकेंगे, लेकिन जाल इतना बड़ा है कि यह बहुत सटीक नहीं हो सकता है।
2. "शार्प" नेट (नॉर्मल एप्रोक्सिमेशन): यह एक तंग, अधिक सटीक जाल है। यह बहुत अधिक डेटा होने पर सबसे अच्छा काम करता है। यह एक बहुत छोटा दायरा देता है, जिससे आपकी भविष्यवाणी बहुत उपयोगी हो जाती है।

4. "ईमानदार" ट्यूनिंग नॉब (ट्यूनिंग बटन)

आमतौर पर, जब आप कोई मॉडल बनाते हैं, तो आपको एक "नॉब" (जैसे कि कितने दोस्तों को देखना है) चुनना होता है। यदि आप उसी डेटा का उपयोग करके इस नॉब को ट्यून करते हैं जिस पर आप परीक्षण कर रहे हैं, तो आप धोखाधड़ी करते हैं।

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

5. निचोड़ (Bottom Line)

समस्या: हम नेटवर्क कनेक्शन का अनुमान तो लगा सकते थे, लेकिन हम अपने "त्रुटि की सीमा" पर भरोसा नहीं कर सकते थे क्योंकि डेटा का पुन: उपयोग करने से गणित टूट गया था।
समाधान: एक सरल नियम: समूह चुनने से पहले लक्ष्य को छिपा दें।
लाभ: अब हमारे पास ऐसे अनुमान हैं जो पुराने तरीकों जितने ही सटीक हैं, लेकिन हमारे पास अंततः गणितीय रूप से सिद्ध तरीका है जिससे हम कह सकते हैं, "मैं 95% आश्वस्त हूँ कि यह भविष्यवाणी सही है।"

संक्षेप में: लेखकों ने यह तरीका खोज लिया है जिससे जासूस को सुरागों का पीछा करने के लिए समूह चुनते समय उत्तर कुंजी (answer key) में झांकने से रोका जा सके। अब, जासूस मामला सुलझा भी सकता है और यह भी साबित कर सकता है कि उनके सही होने की कितनी संभावना है।

यहाँ शोध पत्र "Leave-One-Out Neighborhood Smoothing for Graphons: Berry-Esseen Bounds, Confidence Intervals, and Honest Tuning" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र सांख्यिकीय नेटवर्क विश्लेषण में एक मौलिक चुनौती—एंट्रीवाइज अनसर्टेन्टी क्वांटिफिकेशन (entrywise uncertainty quantification)—को संबोधित करता है। जबकि एक एकल अवलोकित एडजेसेंसी मैट्रिक्स $A$ से लेटेंट एज प्रोबेबिलिटीज ( $P_{ij}$ ) का अनुमान लगाना अच्छी तरह से अध्ययन किया गया है (जैसे कि Zhang et al., 2017 द्वारा उपयोग की गई नेबरहुड स्मूथिंग विधियों के माध्यम से), वैध एंट्रीवाइज कॉन्फिडेंस इंटरवल्स (entrywise confidence intervals) का निर्माण करना सैद्धांतिक रूप से कठिन बना हुआ है।

मुख्य बाधा: "डबल-डिप्पिंग" (Double-Dipping)
क्लासिकल नेबरहुड स्मूथिंग एस्टिमेटर्स एक संरचनात्मक निर्भरता (structural dependency) की समस्या से ग्रस्त होते हैं:

नेबरहुड सिलेक्शन: एल्गोरिदम टोपोलॉजिकल दूरियों की गणना करने और समान नोड्स के एक सेट (नेबरहुड $N_i$ ) को चुनने के लिए एडजेसेंसी मैट्रिक्स $A$ का उपयोग करता है।
एस्टिमेशन: फिर उसी मैट्रिक्स $A$ का उपयोग उस चुने हुए नेबरहुड के भीतर के किनारों (edges) का औसत निकालने के लिए किया जाता है ताकि $P_{ij}$ का अनुमान लगाया जा सके।
चूंकि नेबरहुड का चयन उन्हीं किनारों पर निर्भर करता है जिनका औसत निकाला जा रहा है, इसलिए एस्टिमेटर में पद (summands) कंडीशनली इंडिपेंडेंट (conditionally independent) नहीं होते। यह "डबल-डिप्पिंग" मानक कंसंट्रेशन इनइक्वेलिटीज (जैसे बर्नस्टीन) और सेंट्रल लिमिट थ्योरम्स (बेरी-एसियन) को अमान्य कर देती है, जिससे बिना कम्प्यूटेशनल रूप से महंगी री-सैंपलिंग विधियों के कठोर सांख्यिकीय निष्कर्ष निकालना असंभव हो जाता है।

2. कार्यप्रणाली: लीव-वन-आउट (LOO) नेबरहुड स्मूथिंग

लेखक इस निर्भरता को तोड़ने के लिए नेबरहुड स्मूथिंग एस्टिमेटर में एक संरचनात्मक संशोधन का प्रस्ताव करते हैं।

LOO निर्माण:
एक विशिष्ट एंट्री $P_{ij}$ का अनुमान लगाने के लिए:

डेटा एक्सक्लूजन: पूर्ण मैट्रिक्स $A$ से $j$ -वीं पंक्ति और कॉलम को हटाकर एक घटा हुआ एडजेसेंसी मैट्रिक्स $A^{(-j)}$ तैयार करें।
नेबरहुड फॉर्मेशन: टोपोलॉजिकल दूरियों (दो-हॉप मैट्रिसेस के आधार पर) की गणना करें और नोड $i$ के $h_n$ निकटतम पड़ोसियों को केवल $A^{(-j)}$ का उपयोग करके चुनें। यह नेबरहुड $N_i^{(-j)}$ को परिभाषित करता है।
एस्टिमेशन: नेबरहुड को स्थिर करने के बाद ही, पूर्ण मैट्रिक्स $A$ से मूल किनारों $\{A_{kj} : k \in N_i^{(-j)}\}$ का औसत निकालें।

सैद्धांतिक आधार (Theoretical Lever):
चयन के लिए उपयोग किए जाने वाले डेटा ( $A^{(-j)}$ ) और एस्टिमेशन के लिए उपयोग किए जाने वाले डेटा (मैट्रिक्स $A$ का कॉलम $j$ ) को सख्ती से अलग करके, लेखक लेटेंट प्रोबेबिलिटी मैट्रिक्स $P$ के सापेक्ष सेंटर्ड समैंड्स $(A_{kj} - P_{kj})$ के बीच सटीक कंडीशनल इंडिपेंडेंस को बहाल करते हैं। यह क्लासिकल एम्पिरिकल प्रोसेस टूल्स के अनुप्रयोग की अनुमति देता है।

3. मुख्य योगदान (Key Contributions)

A. वेरिएंस-एडाप्टिव कंसंट्रेशन (फाइनाइट-सैंपल)

एम्पिरिकल बर्नस्टीन बाउंड्स: बहाल की गई स्वतंत्रता का लाभ उठाते हुए, लेखक स्टोकैस्टिक फ्लक्चुएशन टर्म के लिए नॉन-एसिम्प्टोटिक कंसंट्रेशन इनइक्वेलिटीज व्युत्पन्न करते हैं।
डेटा-ड्रिवन इंटरवल्स: वे एम्पिरिकल बर्नस्टीन बाउंड (Maurer and Pontil, 2009) का उपयोग करके कॉन्फिडेंस इंटरवल्स का निर्माण करते हैं, जो अज्ञात वास्तविक वेरिएंस के स्थान पर सैंपल वेरिएंस का उपयोग करता है। यह एसिम्प्टोटिक नॉर्मलिटी पर निर्भर किए बिना पूरी तरह से डेटा-ड्रिवन, फाइनाइट-सैंपल वैध अंतराल प्रदान करता है।

B. एसिम्प्टोटिक नॉर्मलिटी (बेरी-एसियन बाउंड्स)

यूनिफॉर्म बेरी-एसियन बाउंड: शोध पत्र नॉर्मलाइज्ड स्टोकैस्टिक फ्लक्चुएशन के कन्वर्जेंस रेट पर एक यूनिफॉर्म बाउंड स्थापित करता है।
अंडरस्मूथिंग रिजीम (Undersmoothing Regime): पूरे एस्टिमेटर (बायस सहित) के लिए एसिम्प्टोटिक नॉर्मलिटी प्राप्त करने के लिए, लेखक एक अंडरस्मूथिंग रिजीम का प्रस्ताव करते हैं जहाँ नेबरहुड साइज $h_n$ , ऑप्टिमल MSE रेट की तुलना में तेजी से बढ़ता है (विशेष रूप से $h_n \sim \sqrt{n}/\log n$ )। यह सुनिश्चित करता है कि बायस टर्म, सेंट्रल लिमिट स्केल पर वेरिएंस की तुलना में नगण्य हो जाए।
बायस कंट्रोल: वे ग्राफोन के "रेगुलर इंटीरियर" (ब्लॉक सीमाओं से दूर) के नोड्स के लिए डिटर्मिनिस्टिक बायस को कड़ाई से बाउंड करते हैं, यह दिखाते हुए कि यह $O((\log n/n)^{1/4})$ की दर से घटता है।

C. ऑनेस्ट क्रॉस-वैलिडेशन (Honest Cross-Validation)

LOO संरचना बैंडविड्थ $h_n$ को ट्यून करने के लिए एक अनबायस्ड क्रॉस-वैलिडेशन (CV) योजना को स्वाभाविक रूप से सक्षम बनाती है।
चूंकि $A_{ij}$ के लिए प्रेडिक्टर का निर्माण कॉलम $j$ का उपयोग किए बिना किया जाता है, इसलिए होल्ड-आउट सेट पर प्रेडिक्शन एरर, वास्तविक रिस्क का एक अनबायस्ड एस्टिमेट है। यह "ऑनेस्ट" ट्यूनिंग की अनुमति देता है जो बाद के निष्कर्षों (inference) को अमान्य नहीं करता है।

4. सैद्धांतिक परिणाम और धारणाएं (Theoretical Results & Assumptions)

मॉडल: डेंस ग्राफोन मॉडल जहाँ $P_{ij} = f(\xi_i, \xi_j)$ है, जहाँ $\xi_i \sim \text{Unif}[0,1]$ ।
धारणाएं (Assumptions):
- नॉन-डेजेनरेसी: किनारे की संभावनाएँ 0 और 1 से दूर (डेंस रिजीम) हैं।
- स्मूथनेस: ग्राफोन $f$ पीसवाइज लिप्सचिट्ज़ (piecewise Lipschitz) है जिसमें स्पष्ट रूप से अलग ब्लॉक हैं।
- आइडेंटिफिएबिलिटी: ब्लॉक्स के भीतर, पंक्तियों की $L^2$ निकटता लेटेंट स्पेस में निकटता को दर्शाती है।
रिस्क बाउंड्स: LOO एस्टिमेटर क्लासिकल विधियों के मिनिमैक्स ऑप्टिमल रो-वाइज मीन स्क्वेर्ड एरर (MSE) रेट ( $O((\log n/n)^{1/2})$ ) को बनाए रखता है, जो यह सिद्ध करता है कि डीकप्लिंग से एफिशिएंसी में कोई कमी नहीं आती है।
बायस-वेरिएंस ट्रेड-ऑफ: कंडीशनल रिस्क बाउंड दिखाता है कि क्रॉस-टर्म पूरी तरह से शून्य हो जाता है:
$\mathbb{E}[(\tilde{P}_{ij} - P_{ij})^2 | N_i^{(-j)}, P] = \text{Variance} + \text{Bias}^2$
जहाँ इंडिपेंडेंस के कारण क्रॉस-टर्म बिल्कुल शून्य है।

5. सिमुलेशन परिणाम (Simulation Results)

लेखकों ने $n=500$ के साथ पांच ग्राफोन टोपोलॉजी (Smooth, Block, Wiggly, Rank-one, Spiky) में व्यापक सिमुलेशन किए।

पॉइंट एस्टिमेशन: एसिमेट्रिक LOO एस्टिमेटर, MSE के मामले में क्लासिकल सिमेट्राइज्ड एस्टिमेटर के बराबर या उससे थोड़ा बेहतर प्रदर्शन करता है।
कवरेज रेट्स:
- एम्पिरिकल बर्नस्टीन इंटरवल्स: लगभग पूर्ण कवरेज (लगभग 1.00) प्राप्त किया लेकिन ये बहुत कंजर्वेटिव (बहुत चौड़े अंतराल) थे।
- नॉर्मल एप्रोक्सिमेशन इंटरवल्स: स्मूथ ग्राफ पर लगभग 0.98 जैसे नाममात्र 95% स्तर के करीब कवरेज प्राप्त किया, जो बर्नस्टीन इंटरवल्स की तुलना में काफी संकीर्ण अंतराल थे।
- एज केसेस: "Wiggly" ग्राफोन ने नॉर्मल एप्रोक्सिमेशन के लिए थोड़ा कम कवरेज (0.919) दिखाया, जिसका कारण हाई-फ्रीक्वेंसी ग्रेडिएंट्स द्वारा बायस को बढ़ाना है, जो 'बायस कुशन टर्म' की आवश्यकता को प्रमाणित करता है।

6. महत्व और प्रभाव (Significance and Impact)

अंतराल को पाटना (Bridging the Gap): यह कार्य नॉनपैरामेट्रिक ग्राफोन मॉडल्स में एंट्रीवाइज अनसर्टेन्टी क्वांटिफिकेशन के लिए पहला कठोर सैद्धांतिक ढांचा प्रदान करता है, जो ग्लोबल या लो-डायमेंशनल फंक्शनल्स से आगे जाता है।
मेथोडोलॉजिकल सादगी: इसका समाधान जटिल री-सैंपलिंग या बूटस्ट्रैप विधियों के बजाय एक सरल "टोपोलॉजिकल सर्जरी" (एक कॉलम हटाना) पर आधारित है, जो इसे कम्प्यूटेशनल रूप से कुशल बनाता है।
व्यावहारिक उपयोगिता: व्यक्तिगत एज प्रोबेबिलिटीज के लिए वैध कॉन्फिडेंस इंटरवल्स जोड़ने की क्षमता, अधिक मजबूत डाउनस्ट्रीम वैज्ञानिक कार्यों को सक्षम बनाती है, जैसे कि विशिष्ट नेटवर्क कनेक्शन पर हाइपोथेसिस टेस्टिंग या महत्वपूर्ण संरचनात्मक परिवर्तनों की पहचान करना।
भविष्य की दिशाएं: यह फ्रेमवर्क निर्देशित/वेटेड (directed/weighted) नेटवर्क के लिए सामान्यीकरण योग्य है, और सिमल्टेनियस कॉन्फिडेंस बैंड्स के लिए एक मार्ग प्रदान करता है, हालांकि स्पार्स रिजीम और डिग्री-करेक्टेड मॉडल्स के लिए विस्तार अभी भी खुले विषय हैं।

संक्षेप में, यह शोध पत्र "डबल-डिप्पिंग" डिपेंडेंसी को सफलतापूर्वक हल करता है, जिससे मौजूदा विधियों के ऑप्टिमल एस्टिमेशन रेट्स को संरक्षित करते हुए वैध, एंट्रीवाइज इन्फरेंस संभव हो पाता है।