एक मार्टिंगेल कर्नल दो-नमूना परीक्षण

बुनियादी जानकारी

• पेपर ID: 2510.11853
• शीर्षक: A Martingale Kernel Two-Sample Test
• लेखक: Anirban Chatterjee (शिकागो विश्वविद्यालय), Aaditya Ramdas (कार्नेगी मेलन विश्वविद्यालय)
• वर्गीकरण: stat.ME, math.ST, stat.TH
• प्रकाशन तिथि: 13 अक्टूबर 2025
• पेपर लिंक: https://arxiv.org/abs/2510.11853

सारांश

अधिकतम माध्य विसंगति (Maximum Mean Discrepancy, MMD) दो-नमूना परीक्षणों में व्यापक रूप से उपयोग की जाने वाली बहुभिन्न दूरी मीट्रिक है। मानक MMD परीक्षण सांख्यिकी में कठिन शून्य वितरण होता है, जिसके लिए आमतौर पर महंगे पुनः-नमूनाकरण या क्रमपरिवर्तन विधियों की आवश्यकता होती है। यह पेपर वर्ग MMD के अनुमान की मार्टिंगेल व्याख्या का उपयोग करके मार्टिंगेल MMD (mMMD) प्रस्तावित करता है - एक द्विघात समय सांख्यिकी जिसका शून्य परिकल्पना के तहत सीमांत मानक गाऊसी वितरण होता है। इसके अतिरिक्त, हम सिद्ध करते हैं कि परीक्षण किसी भी निश्चित वैकल्पिक परिकल्पना के लिए सुसंगत है, बड़े नमूना आकारों के लिए, mMMD मानक MMD परीक्षण की तुलना में महत्वपूर्ण कम्प्यूटेशनल बचत प्रदान करता है, और शक्ति हानि न्यूनतम है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या विवरण

दो-नमूना परीक्षण सांख्यिकी में एक शास्त्रीय समस्या है, जिसका उद्देश्य स्वतंत्र नमूनों के आधार पर दो वितरण P और Q समान हैं या नहीं यह परीक्षण करना है: $H_0: P = Q \quad \text{बनाम} \quad H_1: P \neq Q$

मौजूदा विधियों की सीमाएं

1. पैरामीट्रिक विधियां: मॉडल गलत विनिर्देश या गैर-यूक्लिडियन डेटा पर अक्सर विफल होती हैं
2. शास्त्रीय गैर-पैरामीट्रिक विधियां: मुख्य रूप से एकल-आयामी डेटा के लिए उपयुक्त, बहुआयामी विस्तार कठिन है
3. मानक MMD परीक्षण: शून्य वितरण अनंत भारित χ² चर के योग के रूप में होता है, भार अज्ञात वितरण पर निर्भर करते हैं, कम्प्यूटेशनल रूप से गहन पुनः-नमूनाकरण या क्रमपरिवर्तन विधियों की आवश्यकता होती है

अनुसंधान प्रेरणा

• MMD कर्नल विधियों के रूप में सामान्य डोमेन में वितरण अंतर का पता लगाने में उत्कृष्ट प्रदर्शन करता है
• थ्रेशोल्ड τα का निर्धारण MMD परीक्षण की मुख्य व्यावहारिक चुनौती है
• मौजूदा आघूर्ण-आधारित पैरामीट्रिक सन्निकटन में सुसंगतता या सटीकता की गारंटी का अभाव है
• आसानी से संभाले जाने वाले शून्य वितरण के साथ एक कुशल विकल्प की आवश्यकता है

मुख्य योगदान

1. mMMD परीक्षण प्रस्तावित करना: मार्टिंगेल संरचना पर आधारित नई MMD विविधता, मानक गाऊसी शून्य वितरण के साथ
2. सैद्धांतिक गारंटियां:
   • शून्य परिकल्पना के तहत स्पर्शोन्मुख सामान्यता सिद्ध की गई (प्रमेय 2, 3)
   • निश्चित वैकल्पिक परिकल्पना के लिए सुसंगतता स्थापित की गई (प्रमेय 6, 7)
   • वैकल्पिक परिकल्पना के तहत वितरण अभिसरण दिया गया (प्रमेय 8)
3. कम्प्यूटेशनल दक्षता: पुनः-नमूनाकरण से बचा जाता है, O(n²) जटिलता बनाए रखता है लेकिन वास्तविक रन समय में महत्वपूर्ण कमी
4. विस्तारित अनुप्रयोग:
   • बहु-कर्नल परीक्षण (mmMMD)
   • सामान्य सांख्यिकी परिवार Tn,γ, जिसमें मानक MMD और mMMD विशेष मामले हैं

विधि विवरण

कार्य परिभाषा

दो वितरण P और Q से मीट्रिक स्पेस X पर स्वतंत्र नमूने दिए गए:

• Xn = {X₁, ..., Xn} ~ P
• Yn = {Y₁, ..., Yn} ~ Q

उद्देश्य: H₀: P = Q बनाम H₁: P ≠ Q परीक्षण करना

मुख्य विचार: मार्टिंगेल संरचना

मुख्य अवलोकन: वर्ग MMD अनुमानक के संशोधित रूप में मार्टिंगेल संरचना होती है।

साक्षी फलन विधि:

• सैद्धांतिक रूप से इष्टतम साक्षी फलन: f₀ = (νP - νQ)/‖νP - νQ‖K
• प्रत्येक 2 ≤ i ≤ n के लिए, ऐतिहासिक डेटा का उपयोग करके अनुमान लगाएं: $\hat{f}_i = \frac{1}{i}\sum_{j=1}^{i-1}[K(X_j, \cdot) - K(Y_j, \cdot)]$

mMMD सांख्यिकी

$T_n := \frac{1}{n}\sum_{i=2}^n \langle \hat{f}_i, K(X_i, \cdot) - K(Y_i, \cdot) \rangle_K$

कर्नल ट्रिक का उपयोग करके, इसे सरल बनाया जा सकता है: $T_n = \frac{1}{n}\sum_{i=2}^n \frac{1}{i}\sum_{j=1}^{i-1}[K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)]$

मानकीकृत सांख्यिकी

स्पर्शोन्मुख सामान्यता प्राप्त करने के लिए, विचरण अनुमान को परिभाषित करें: $\sigma_n^2 := \frac{1}{n^2}\sum_{i=2}^n \left(\frac{1}{i}\sum_{j=1}^{i-1}K(X_i, X_j) - K(X_i, Y_j) - K(X_j, Y_i) + K(Y_i, Y_j)\right)^2$

अंतिम परीक्षण सांख्यिकी: $\eta_n = T_n/\sigma_n$

परीक्षण नियम

$\Psi_n := \mathbf{1}\{\eta_n > z_{1-\alpha}\}$ जहां z₁₋α मानक सामान्य वितरण का (1-α) मात्रा है।

तकनीकी नवाचार बिंदु

1. मार्टिंगेल संरचना की पहचान: पहली बार MMD अनुमानक में मार्टिंगेल अंतर अनुक्रम की पहचान की गई
2. पुनः-नमूनाकरण से बचना: मार्टिंगेल केंद्रीय सीमा प्रमेय का उपयोग करके सीधे मानक गाऊसी वितरण प्राप्त करना
3. आयाम स्वतंत्रता: उपयुक्त शर्तों के तहत, शून्य वितरण डेटा आयाम पर निर्भर नहीं करता है
4. एकीकृत ढांचा: Tn,γ परिवार कई MMD विविधताओं को एकीकृत करता है

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन प्रयोग

शून्य वितरण सत्यापन:

• आयाम: d ∈ {10, 100, 250, 500}
• डेटा वितरण: Nd(0d, Id) और td(10)
• कर्नल फलन: गाऊसी और लाप्लास कर्नल (माध्यिका अनुमानी बैंडविड्थ)
• नमूना आकार: n = 200, 2000 बार दोहराया गया

शक्ति तुलना प्रयोग

सेटअप:

• P = Nd(0d, Id), Q = Nd(μd,j,ε, Id)
• कॉन्फ़िगरेशन: (d,j,ε) = (10,5,0.3), (50,5,0.3), (100,5,0.5)
• तुलना विधियां: मानक MMD, रैखिक समय MMD (LMMD), ब्लॉक MMD (BMMD), क्रॉस MMD (xMMD), BetMMD

वास्तविक डेटा प्रयोग

MNIST डेटासेट:

• 5 अंकों की जोड़ी तुलना: क्रमिक रूप से बढ़ती ओवरलैप
• प्रत्येक समूह से 100 नमूने निकाले गए, 100 बार दोहराया गया
• महत्व स्तर: α = 0.05

बहु-कर्नल प्रयोग

कॉन्फ़िगरेशन:

• mmMMD गाऊसी: 3 गाऊसी कर्नल, बैंडविड्थ (1,2,4)λmed
• mmMMD लाप्लास: 3 लाप्लास कर्नल, समान बैंडविड्थ
• mmMMD मिश्रित: गाऊसी और लाप्लास कर्नल का मिश्रण

प्रायोगिक परिणाम

शून्य वितरण सत्यापन

• मुख्य निष्कर्ष: सभी सेटअप में, ηn का अनुभवजन्य वितरण मानक गाऊसी वितरण से निकटता से मेल खाता है
• दृढ़ता: परिणाम डेटा वितरण, कर्नल चयन और आयाम के लिए दृढ़ता प्रदर्शित करते हैं
• तुलना लाभ: मानक MMD के जटिल शून्य वितरण के साथ तीव्र विपरीतता

शक्ति तुलना

मुख्य निष्कर्ष:

• mMMD शक्ति मानक MMD के करीब है, अन्य कम्प्यूटेशनल रूप से कुशल विविधताओं से बेहतर है
• xMMD के साथ तुलनीय प्रदर्शन, लेकिन नमूना विभाजन से बचा जाता है

कम्प्यूटेशनल दक्षता

परिणाम: mMMD मानक MMD से लगभग 100 गुना तेज है, अन्य कुशल विधियों के साथ तुलनीय है।

MNIST प्रयोग परिणाम

• प्रवृत्ति: समूह बढ़ने के साथ (ओवरलैप बढ़ता है), सभी विधियों की शक्ति घटती है
• प्रदर्शन क्रम: mMMD और xMMD > BMMD > LMMD
• व्यावहारिक महत्व: वास्तविक डेटा पर सैद्धांतिक लाभ को सत्यापित करता है

संबंधित कार्य

कर्नल दो-नमूना परीक्षण विकास

1. प्रारंभिक विधियां: बड़े विचलन सीमा पर आधारित रूढ़िवादी विधियां
2. वर्णक्रमीय विधियां: Gretton et al. (2009) का वर्णक्रमीय सन्निकटन, मजबूत धारणाओं की आवश्यकता
3. अधूरे U-सांख्यिकी: रैखिक समय MMD, ब्लॉक MMD, आदि
4. नमूना विभाजन रणनीति: Kübler et al. (2022), Shekhar et al. (2022)

इस पेपर के सापेक्ष लाभ

• सैद्धांतिक पूर्णता: शून्य परिकल्पना और वैकल्पिक परिकल्पना दोनों के तहत वितरण सिद्धांत स्थापित करता है
• कम्प्यूटेशनल दक्षता: क्रमपरिवर्तन परीक्षण के कम्प्यूटेशनल बोझ से बचा जाता है
• व्यावहारिकता: नमूना विभाजन की आवश्यकता नहीं है, पूर्ण नमूना जानकारी बनाए रखता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. सैद्धांतिक योगदान: पहली बार मार्टिंगेल संरचना का उपयोग करके मानक गाऊसी शून्य वितरण के साथ MMD परीक्षण का निर्माण
2. व्यावहारिक मूल्य: कम्प्यूटेशनल लागत में महत्वपूर्ण कमी, अच्छे सांख्यिकीय प्रदर्शन को बनाए रखता है
3. विस्तारशीलता: ढांचा बहु-कर्नल सेटिंग और अधिक सामान्य सांख्यिकी परिवार तक विस्तारित हो सकता है

सीमाएं

1. सैद्धांतिक सीमाएं:
   • माध्यिका अनुमानी बैंडविड्थ चयन में सैद्धांतिक समर्थन की कमी
   • γ > 1/2 के लिए मिनिमैक्स इष्टतमता अनिर्धारित है
2. व्यावहारिक सीमाएं:
   • अभी भी O(n²) कम्प्यूटेशनल जटिलता की आवश्यकता है
   • कुछ सेटिंग में शक्ति मानक MMD से थोड़ी कम है

भविष्य की दिशाएं

1. सैद्धांतिक विस्तार:
   • डेटा-निर्भर कर्नल के लिए सैद्धांतिक गारंटियां
   • अधिक सामान्य कर्नल फलन की प्रयोज्यता
   • मिनिमैक्स इष्टतमता का पूर्ण लक्षण वर्णन
2. विधि सुधार:
   • कर्नल सन्निकटन तकनीकों के साथ जटिलता को कम करने के लिए संयोजन
   • स्वतंत्रता परीक्षण तक विस्तार
   • दूरी-आधारित परीक्षण के अनुप्रयोग

गहन मूल्यांकन

शक्तियां

1. नवाचार शक्तिशाली: मार्टिंगेल दृष्टिकोण MMD अनुसंधान में नया योगदान है
2. सैद्धांतिक कठोरता: पूर्ण स्पर्शोन्मुख सिद्धांत, Berry-Esseen प्रकार अभिसरण दर सहित
3. उच्च व्यावहारिक मूल्य: MMD परीक्षण की व्यावहारिक कम्प्यूटेशनल बाधा को हल करता है
4. पर्याप्त प्रयोग: सैद्धांतिक सत्यापन से वास्तविक अनुप्रयोग तक व्यापक मूल्यांकन
5. स्पष्ट लेखन: तकनीकी विवरण और सहज व्याख्या के बीच अच्छा संतुलन

कमियां

1. सैद्धांतिक अंतराल: डेटा-निर्भर बैंडविड्थ का सैद्धांतिक विश्लेषण अधूरा है
2. शक्ति हानि: कुछ परिस्थितियों में शक्ति वास्तव में मानक MMD से कम है
3. प्रयोज्यता सीमा: मुख्य रूप से यूक्लिडियन स्पेस के मामले को सत्यापित किया गया है
4. कम्प्यूटेशनल जटिलता: अभी भी O(n²) है, मौलिक सुधार नहीं हुआ है

प्रभाव

1. शैक्षणिक मूल्य: MMD सिद्धांत के लिए नया दृष्टिकोण प्रदान करता है, अधिक मार्टिंगेल-आधारित विधियों को प्रेरित कर सकता है
2. व्यावहारिक मूल्य: बड़े पैमाने पर दो-नमूना परीक्षण कार्यों के लिए सीधे लागू होता है
3. पुनरुत्पादनीयता: विधि सरल और स्पष्ट है, कार्यान्वयन और सत्यापन में आसान
4. विस्तारशीलता: ढांचे में अच्छी विस्तार क्षमता है

प्रयोज्य परिदृश्य

1. बड़े पैमाने पर डेटा: कम्प्यूटेशनल दक्षता लाभ स्पष्ट है
2. उच्च-आयामी डेटा: आयाम-स्वतंत्र शून्य वितरण विशेषता में लाभ है
3. वास्तविक समय अनुप्रयोग: क्रमपरिवर्तन परीक्षण की तत्काल आवश्यकता से बचा जाता है
4. बहु-कर्नल परिदृश्य: कर्नल चयन अनिश्चित होने पर mmMMD में लाभ है

संदर्भ

1. Gretton, A., et al. (2012a). A kernel two-sample test. JMLR, 13(1), 723-773.
2. Shekhar, S., Kim, I., & Ramdas, A. (2022). A permutation-free kernel two-sample test. NeurIPS, 35, 18168-18180.
3. Li, T. & Yuan, M. (2024). On the optimality of Gaussian kernel based nonparametric tests against smooth alternatives. JMLR, 25(334), 1-62.
4. Fan, X. & Shao, Q. M. (2018). Berry–Esseen bounds for self-normalized martingales. Communications in Mathematics and Statistics, 6(1), 13-27.

सारांश: यह एक उच्च गुणवत्ता वाला सांख्यिकीय सिद्धांत पेपर है जो चतुर मार्टिंगेल संरचना की पहचान के माध्यम से शास्त्रीय MMD परीक्षण समस्या के लिए एक नया समाधान प्रदान करता है। सैद्धांतिक योगदान दृढ़ है, प्रायोगिक सत्यापन व्यापक है, और इसमें महत्वपूर्ण शैक्षणिक और व्यावहारिक मूल्य है।