📊 statistics

Bagging Robustly Learns VC Classes with Linear Sample Complexity

यह शोध पत्र प्रदर्शित करता है कि बैगिंग (bagging) को रोबस्ट एम्पिरिकल रिस्क मिनिमाइजेशन (robust empirical risk minimization) के साथ संयोजित करने से VC वर्गों के लिए VC आयाम में रैखिक नमूना जटिलता (linear sample complexity) के साथ एडवरसेरियल रोबस्ट लर्निंग (adversarial robust learning) प्राप्त होती है, जो पिछले अनुमानों में महत्वपूर्ण सुधार करते हुए आवश्यक ओरेकल कॉल्स (oracle calls) पर एक मिलान करने वाला निचला स्तर (matching lower bound) स्थापित करता है।

मूल लेखक: Omar Montasser

प्रकाशित 2026-08-14

📖 4 मिनट में पढ़ें☕ कॉफ़ी ब्रेक में पढ़ें

CC BY 4.0

मूल लेखक: Omar Montasser

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

कल्पना कीजिए कि आप एक रोबोट को तस्वीरों में बिल्लियों को पहचानना सिखा रहे हैं। आप उसे हजारों तस्वीरें दिखाते हैं, और वह मूंछों और नुकीले कानों को पहचानना सीख जाता है। लेकिन क्या होगा यदि कोई बिल्ली की नाक पर एक छोटा सा, लगभग अदृश्य स्टिकर चिपका दे? एक इंसान के लिए, बिल्ली अभी भी बिल्ली ही दिखती है, लेकिन रोबोट अचानक सोचने लगता है कि वह एक टोस्टर है। यह "एडवर्सरियल एग्जांपल्स" (adversarial examples) की दुनिया है—छोटे, चालाकी भरे बदलाव जो स्मार्ट मशीनों को मूर्ख बना देते हैं। वैज्ञानिक ऐसे रोबोट बनाने की कोशिश कर रहे हैं जो इन चालों को अनदेखा कर सकें, लेकिन इसमें एक पेंच है: रोबोट का दिमाग (उसका "फंक्शन क्लास") जितना अधिक जटिल होगा, उसे इन चालों के खिलाफ सख्त बनाने के लिए लाखों उदाहरणों के बिना सिखाना उतना ही कठिन होगा।

समस्या को समझने के लिए, "सीखने" को एक विशाल पुस्तकालय में सबसे अच्छी नियम पुस्तिका खोजने के रूप में सोचें। "VC डायमेंशन" (VC dimension) बस एक फैंसी तरीका है यह गिनने का कि उस पुस्तकालय में कितने अलग-अलग नियम हैं। यदि पुस्तकालय बहुत बड़ा है, तो आपको सही नियम खोजने के लिए आमतौर पर बहुत सारे उदाहरणों की आवश्यकता होती है। लेकिन जब एडवर्सरियल चालें शामिल होती हैं, तो पुराने तरीकों ने सुझाव दिया था कि आपको एक खगोलीय संख्या में उदाहरणों की आवश्यकता हो सकती है—इतने अधिक कि जटिल नियमों के लिए यह असंभव सा लगे। एक अन्य प्रमुख विचार "ओरेकल" (oracle) है, जो एक जादुई ब्लैक बॉक्स की तरह है जो आपके लिए किसी विशिष्ट, कठिन पहेली को तुरंत हल कर सकता है। बड़ा सवाल यह है कि क्या हम एक ऐसा रोबोट बना सकते हैं जो हमारे जादुय ब्लैक बॉक्स से केवल कुछ ही बार पूछकर, उचित संख्या में उदाहरणों का उपयोग करके मजबूत (ट्रिक-प्रूफ) बनना सीख सके?

यह शोध पत्र, जिसका शीर्षक "बैगिंग रोबस्टली लर्न्स VC क्लासेस विद लीनियर सैंपल कॉम्प्लेक्सिटी" (Bagging Robustly Learns VC Classes with Linear Sample Complexity) है, इस प्रश्न का उत्तर एक जोरदार "हाँ, लेकिन एक ट्विस्ट के साथ" में देता है। लेखक, जो इस कार्य का नेतृत्व कर रहे हैं, यह सिद्ध करते हैं कि आपको मशीन को मजबूत बनाने के लिए असंभव संख्या में उदाहरणों की आवश्यकता नहीं है। वास्तव में, वे दिखाते हैं कि कई प्रकार की सीखने की समस्याओं के लिए, आपको आवश्यक उदाहरणों की संख्या नियमों की जटिलता (VC डायमेंशन) के साथ एक सरल, सीधी रेखा के संबंध में बढ़ती है। यह पिछले विचारों की तुलना में एक बहुत बड़ा सुधार है, जिन्होंने सुझाव दिया था कि उदाहरणों की संख्या तेजी से (exponentially) बढ़ेगी।

उनके नुस्खे का गुप्त तत्व दो पुराने विचारों का एक चतुर संयोजन है: "बैगिंग" (Bagging) और "रोबस्ट ट्रेनिंग" (Robust Training)। कल्पना कीजिए कि आपके पास एक मामला सुलझाने के लिए जासूसों की एक टीम है। केवल एक जासूस पर भरोसा करने के बजाय, आप कई लोगों को काम पर रखते हैं। आप प्रत्येक जासूस को सुरागों का थोड़ा अलग, यादृच्छिक चयन (एक "बूटस्ट्रैप सैंपल") देते हैं और उन्हें एक विशेष "रोबस्ट" पद्धति का उपयोग करके मामला सुलझाने के लिए कहते हैं जो चालाकी भरे नकली सुरागों को अनदेखा करती है। फिर, आप अंतिम उत्तर पर मतदान करने के लिए जासूसों को छोड़ देते हैं। यदि अधिकांश सहमत होते हैं, तो आप उसी उत्तर के साथ जाते हैं। पेपर सिद्ध करता है कि यदि आप पर्याप्त जासूसों को काम पर रखते हैं (विशेष रूप से, एक संख्या जो "ड्यूल VC डायमेंशन" से संबंधित है), तो आप बहुत कम उदाहरणों के साथ सही उत्तर पा सकते हैं।

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

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

तकनीकी सारांश: बैगिंग (Bagging) रैखिक सैंपल कॉम्प्लेक्सिटी के साथ VC क्लासेज को मजबूती से सीखता है

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

यह शोध पत्र उन प्रेडिक्टर्स (predictors) को सीखने की मौलिक चुनौती को संबोधित करता है जो टेस्ट-टाइम पर एडवरसेरियल उदाहरणों (adversarial examples) के प्रति मजबूत (robust) हों। एक इंस्टेंस स्पेस $\mathcal{X}$ , एक लेबल स्पेस $\mathcal{Y} = \{-1, 1\}$ , और एक एडवर्सरी (adversary) जिसे एक परटर्बेशन मैप $U: \mathcal{X} \to 2^\mathcal{X}$ द्वारा परिभाषित किया गया है, को देखते हुए, लक्ष्य एक ऐसा प्रेडिक्टर $\hat{f}$ सीखना है जो पॉपुलेशन रोबस्ट रिस्क (population robust risk) को कम करे:
$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$
जहाँ $P$ , $\mathcal{X} \times \mathcal{Y}$ पर एक अज्ञात वितरण (distribution) है।

यह शोध पत्र उन फंक्शन क्लासेज $\mathcal{F}$ की सीखने की क्षमता पर ध्यान केंद्रित करता है जिनका विनैपिक-चर्वोनिक (VC) डायमेंशन $d$ परिमित (finite) है। पूर्ववर्ती कार्यों ने स्थापित किया कि जबकि मानक PAC सेटिंग में VC क्लासेज सीखने योग्य हैं, एडवरसेरियली रोबस्ट लर्निंग महत्वपूर्ण बाधाओं का सामना करती है। विशेष रूप से, मोंटासर, हनेके और स्रेब्रो [2019] ने दिखाया कि:

प्रॉपर लर्निंग (आउटपुट को $\mathcal{F}$ के भीतर सीमित रखना) यहाँ तक विफल हो सकता है जहाँ VC डायमेंशन 1 हो।
इम्प्रापर लर्निंग (Improper learning) संभव है, लेकिन ज्ञात सर्वोत्तम ऊपरी सीमा (upper bound) $d$ में घातांकीय (exponential) थी।
मौजूदा इम्प्रापर एल्गोरिदम कम्प्यूटेशनल रूप से अक्षम हैं, जिन्हें अत्यधिक ओवरहेड के साथ $O(nd)$ बार एक रोबस्ट एम्पेरिकल रिस्क मिनिमाइजेशन (RERM) ऑरेकल (oracle) को कॉल करने की आवश्यकता होती है।

मुख्य प्रश्न यह है कि क्या ऐसे एल्गोरिदम डिजाइन किए जा सकते हैं जो सैंपल-कुशल (linear in $d$ ) और ऑरेकल-कुशल (RERM के कम कॉल्स) दोनों हों।

कार्यप्रणाली (Methodology)

लेखक एक सरल इम्प्रापर लर्निंग एल्गोरिदम का प्रस्ताव करते हैं जो बैगिंग (बूटस्ट्रैप एग्रीगेशन) को रोबस्ट एम्पेरिकल रिस्क मिनिमाइजेशन (RERM) के साथ जोड़ता है।

एल्गोरिदम (Bagging Robust ERMs)

आकार $n$ के एक ट्रेनिंग सेट $S$ और कॉन्फिडेंस पैरामीटर $\delta$ तथा एक RERM ऑरेकल $\hat{f}$ के लिए:

बूटस्ट्रैप नमूनों की संख्या $N = O(d^\star + \log(1/\delta))$ निर्धारित करें, जहाँ $d^\star$ क्लास $\mathcal{F}$ का ड्यूल VC डायमेंशन (dual VC dimension) है।
प्रत्येक $i \in \{1, \dots, N\}$ $i \in {1, \dots, N}$ के लिए:
- एक विशिष्ट रेंज $J_n = \{n/4, \dots, n-1\}$ से एक रैंडम आकार $t$ चुनें।
- $S$ के लंबाई $t$ वाले प्रीफिक्स (prefix) से रिप्लेसमेंट के साथ $t$ आकार का एक बूटस्ट्रैप डेटासेट $S'_i$ सैंपल करें।
- प्रेडिक्टर $\hat{f}_{S'_i} \in \mathcal{F}$ प्राप्त करने के लिए $S'_i$ पर RERM ऑरेकल चलाएं।
$N$ प्रेडिक्टर्स का बहुमत वोट (majority vote) आउटपुट करें: $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$ ।

सैद्धांतिक दृष्टिकोण (Theoretical Approach)

विश्लेषण पिछले सैंपल-कंप्रेशन तर्कों से अलग है। इसके बजाय, यह रोबस्ट रिस्क के लिए तैयार किए गए लीव-वन-आउट विश्लेषण (leave-one-out analysis) का उपयोग करता है:

RERMs पर वितरण: लेखक रैंडम सबसेट्स पर प्रशिक्षित RERMs द्वारा की गई त्रुटियों के वितरण का विश्लेषण करते हैं। वे सिद्ध करते हैं कि किसी भी रैंडम टेस्ट उदाहरण $(X, Y)$ और किसी भी परटर्बेशन $Z \in U(X)$ के लिए, RERMs का अंश जो गलत वर्गीकरण (misclassify) करता है, अपेक्षा (expectation) में छोटा है ( $\tilde{O}(d/n)$ )।
लीव-वन-आउट बाउंड: इस अपेक्षा को एक एम्पेरिकल वितरण पर लागू करके, वे "फुल बैगिंग" प्रेडिक्टर (सभी संभावित बूटस्ट्रैप्स का एक आदर्श औसत) के रोबस्ट रिस्क पर एक सीमा स्थापित करते हैं।
स्पारसिफिकेशन (Sparsification): चूंकि फुल बैगिंग प्रेडिक्टर अव्यवहारिक है, इसलिए लेखक एग्रीगेट वोट को केवल $N = O(d^\star)$ स्वतंत्र बूटस्ट्रैप नमूनों का उपयोग करके अनुमानित करने के लिए स्पारसिफिकेशन तकनीक (मोरान और येहुदायाऑफ [2016]) का उपयोग करते हैं। यह चरण ऑरेकल कॉम्प्लेक्सिटी को सीधे ड्यूल VC डायमेंशन $d^\star$ से जोड़ता है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

1. ऊपरी सीमा: रैखिक सैंपल कॉम्प्लेक्सिटी (Upper Bound: Linear Sample Complexity)

प्राथमिक परिणाम (थ्योरम 1) स्थापित करता है कि VC क्लासेज को VC डायमेंशन $d$ में रैखिक सैंपल कॉम्प्लेक्सिटी के साथ एडवरसेरियली रोबस्ट रूप से सीखा जा सकता है।

सैंपल कॉम्प्लेक्सिटी: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$ । यह पिछले $O(\exp(d))$ बाउंड की तुलना में घातांकीय सुधार प्रदान करता है।
ऑरेकल कॉम्प्लेक्सिटी: एल्गोरिदम RERM ऑरेकल को $N = O(d^\star)$ बार कॉल करता है।
कम्प्यूटेशनल दक्षता: एल्गोरिदम समानांतर (parallelizable) है (बूस्टिंग-आधारित दृष्टिकोणों के विपरीत) और इसमें केवल $O(d^\star n)$ कम्प्यूटेशनल ओवरहेड होता है।
एग्नोस्टिक सेटिंग (Agnostic Setting): इस रियलाइजेबल परिणाम को एग्नोस्टिक सेटिंग से एक रिडक्शन (Montasser et al. [2019]) के साथ जोड़कर, लेखक $\tilde{O}(\sqrt{d/n})$ सैंपल कॉम्प्लेक्सिटी और $O(d^\star \log n)$ ऑरेकल कॉम्प्लेक्सिटी के साथ एक एग्नोस्टिक लर्नर प्राप्त करते हैं।

2. निचली सीमा: ड्यूल VC डायमेंशन की आवश्यकता (Lower Bound: Necessity of Dual VC Dimension)

शोध पत्र सिद्ध करता है कि ऑरेकल कॉम्प्लेक्सिटी में ड्यूल VC डायमेंशन $d^\star$ पर निर्भरता अपरिहार्य है (थ्योरम 2)।

परिणाम: ऐसी क्लासेज मौजूद हैं जिनका VC डायमेंशन $d$ और ड्यूल VC डायमेंशन $d^\star = 2^{d+1}-1$ है, जहाँ कोई भी एल्गोरिदम जो RERM ऑरेकल को $d^\star - 1$ से कम बार कॉल करता है, वह पर्याप्त ट्रेनिंग सैंपल्स होने के बावजूद भी मजबूती से सीखने में विफल रहता है।
निहितार्थ: शास्त्रीय PAC लर्निंग में जहाँ $O(\log n)$ या स्थिर ERM कॉल्स पर्याप्त होते हैं, एडवरसेरियल रूप से रोबस्ट लर्निंग स्वाभाविक रूप से $\Omega(d^\star)$ ऑरेकल क्वेरी की मांग करती है। यह मानक और रोबस्ट लर्निंग कॉम्प्लेक्सिटी के बीच एक मौलिक अलगाव को रेखांकित करता है।

3. तकनीकी लक्षण वर्णन (Technical Characterization)

परिणाम यह संकेत देते कि मोंटासर, हनेके और स्रेब्रो [2022] द्वारा प्रस्तावित परिष्कृत कॉम्प्लेक्सिटी माप $\dim(\mathcal{F}, U)$ का मान $d$ द्वारा सीमित है, जो इस धारणा को हल करता है कि यह माप काफी बड़ा हो सकता है।

महत्व और दावे (Significance and Claims)

शोध पत्र कम्प्यूटेशनल रूप से कुशल रोबस्ट PAC लर्निंग के लिए एक "रेसिपी" प्रदान करने का दावा करता है। यह प्रदर्शित करके कि एक सरल बैगिंग ह्यूरिस्टिक (heuristic) RERM के साथ मिलकर इष्टतम सैंपल कॉम्प्लेक्सिटी प्राप्त करती है, यह कार्य सैद्धांतिक मजबूती और व्यावहारिक एल्गोरिद्मिक दक्षता के बीच के अंतर को पाटता है।

शोध पत्र के योगदान के संबंध में प्रमुख दावे इस प्रकार हैं:

घातांकीय सुधार: $d$ में घातांकीय से रैखिक सैंपल कॉम्प्लेक्सिटी की ओर बढ़ना।
ऑरेकल दक्षता: ऑरेकल कॉल्स को $O(nd) $से घटाकर$ O(d^\star)$ करना, जिससे यह उन क्लासेज के लिए व्यवहार्य हो जाता है जहाँ RERM कम्प्यूटेशनल रूप से सुलभ है।
मौलिक सीमा: यह स्थापित करना कि ड्यूल VC डायमेंशन ऑरेकल दक्षता के लिए सही अवरोध (barrier) है, जो मानक लर्निंग में VC डायमेंशन की भूमिका के विपरीत है।
व्यावहारिक प्रासंगिकता: एल्गोरिदम की समानांतर क्षमता और मानक RERM ऑरेकल पर इसकी निर्भरता (जो वास्तव में आधुनिक डीप लर्निंग संदर्भों में उपयोग किए जाने वाले एडवरसेरियल ट्रेनिंग ह्यूरिस्टिक्स के अनुरूप है) यह सुझाव देती है कि ये सैद्धांतिक सुधार सीधे तौर पर लागू किए जा सकते हैं।

लेखक नोट करते हैं कि हालांकि एल्गोरिदम इम्प्रापर (improper) है (एक एकल फंक्शन $\mathcal{F}$ के बजाय बहुमत वोट आउटपुट करना), यह इन सीमाओं को प्राप्त करने के लिए आवश्यक है, जो रोबस्ट सेटिंग में प्रॉपर और इम्प्रापर लर्निंग के बीच के अंतर को दर्शाता है। यह कार्य ड्यूल VC डायमेंशन का लाभ उठाते हुए और इम्प्रापर लर्नर्स को स्वीकार करते हुए, एल्गोरिद्मिक दक्षता को प्रमाणित मजबूती के साथ एकीकृत करता है।