📊 statistics

Learning with Monotone Adversarial Corruptions

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

मूल लेखक: Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

प्रकाशित 2026-06-25

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

CC BY 4.0

मूल लेखक: Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

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

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

यह शोध पत्र इस बात की खोज करता है कि क्या होता है जब एक "मददगार" लेकिन चालाक शिक्षक इस प्रक्रिया में हस्तक्षेप करता है।

"मददगार" साज़िशकर्ता: मोनोटोन एडवर्सरी (The Monotone Adversary)

लेखक एक पात्र पेश करते हैं जिसे मोनोटोन एडवर्सरी कहा जाता है। इस एडवर्सरी को एक ऐसे शिक्षक के रूप में सोचें जो आपकी मदद करने के लिए बहुत अधिक उत्सुक है।

सेटअप: शिक्षक आपके $n$ रैंडम सेब और संतरों की टोकरी को देखता है।
ट्विस्ट: फिर शिक्षक टोकरी में $m$ अतिरिक्त फल जोड़ देता है।
कैच (पेंच): ये अतिरिक्त फल नकली नहीं हैं। वे असली सेब और संतरे हैं, और शिक्षक उन्हें बाग के वास्तविक नियमों के अनुसार 100% सही ढंग से लेबल करता है।
धोखा: शिक्षक यह तय करने के लिए कि कौन से अतिरिक्त फल जोड़ने हैं, ठीक उसी आधार पर चुनाव करता है जो पहले से आपकी टोकरी में मौजूद था। वे आपको भ्रमित करने के लिए हजारों अतिरिक्त सेब जोड़ सकते हैं यदि वे देखते हैं कि आपके पास केवल संतरे हैं, या वे पैटर्न को बिगाड़ने के लिए विशिष्ट दुर्लभ फल जोड़ सकते हैं।

डरावनी बात क्या है? सभी लेबल सही हैं। डेटा "साफ" है (सत्य के मामले में), लेकिन डेटा का मिश्रण अब यादृच्छिक नहीं रहा। इसे हेरफेर किया गया है ताकि "सभी डेटा बिंदु स्वतंत्र हैं" वाले अनुमान को तोड़ा जा सके।

बड़ी हैरानी: "अधिक डेटा" बुरा भी हो सकता है

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

लेखकों ने दो प्रसिद्ध प्रकार की शिक्षण रणनीतियों का परीक्षण किया:

1. "लीव-वन-आउट" रणनीति (The One-in-Graph Algorithm)

यह कैसे काम करती है: कल्पना करें कि एक छात्र इस विचार से सीखता है, "यदि मैं अपनी टोकरी से एक फल निकाल दूँ, तो क्या मैं बाकी फलों का सही अनुमान लगा पाऊँगा?" वे अपना अंतिम अनुमान लगाने के लिए इसी तर्क का उपयोग करते हैं। इसे सीखने का सबसे इष्टतम (optimal) तरीका माना जाता है।
विफलता: एडवर्सरी बस इतने अतिरिक्त फल जोड़ सकता है कि इस छात्र को धोखा दिया जा सके। भले ही छात्र सबसे अच्छा संभव तर्क का उपयोग कर रहा हो, एडवर्सरी उसे 25% समय (एक स्थिर त्रुटि) गलत अनुमान लगाने के लिए मजबूर कर सकता है, भले ही छात्र एक बहुत ही सरल नियम (जैसे केवल दो प्रकार के फलों के बीच अंतर करना) सीख रहा हो।
सबक: यह रणनीति पूरी तरह से इस विचार पर निर्भर करती है कि डेटा एक रैंडम शफल (यादृच्छिक क्रम) है। एक बार जब एडवर्सरी शफल में हेरफेर कर देता है, तो यह रणनीति ढह जाती है।

2. "मेजोरिटी वोट" रणनीति (The Ensemble)

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

नायक: "सिंपल" लर्नर (ERM)

यदि फैंसी और इष्टतम रणनीतियाँ विफल हो जाती हैं, तो क्या कोई बच सकता है?

हाँ, शोध पत्र एम्पिरिकल रिस्क मिनिमाइज़र (ERM) की ओर संकेत करता है।

यह कैसे काम करती है: यह एक "ब्रूट फोर्स" छात्र है। वे बस पूरी टोकरी को देखते हैं और कहते हैं, "मैं एक ऐसा नियम ढूँढूँगा जो इस टोकरी के हर एक फल पर पूरी तरह फिट बैठता हो।"
सफलता: क्योंकि एडवर्सरी लेबल के बारे में झूठ नहीं बोल सकता (उन्हें सही होना ही होगा), वास्तविक नियम (ग्राउंड ट्रूथ) हमेशा एक वैध नियम होता है जो डेटा पर फिट बैठता है। "ब्रूट फोर्स" छात्र एक ऐसा नियम ढूँढ लेगा जो डेटा पर अच्छी तरह फिट बैठता है, भले ही अतिरिक्त फल मौजूद हों।
परिणाम: हालांकि यह छात्र सबसे तेज़ या सबसे कुशल शिक्षक नहीं हो सकता (यह वास्तविक सर्वश्रेष्ठ से थोड़ा धीमा हो सकता है), लेकिन यह मजबूत (robust) है। इसे हेरफेर से धोखा नहीं दिया जा सकता। इसकी त्रुटि दर कम और अनुमानित रहती है।

"ओब्लिवियस" अपवाद

शोध पत्र यह भी नोट करता है कि "लीव-वन-आउट" रणनीति कब फिर से काम करती है: यदि एडिवर्सरी ओब्लिवियस (Oblivious) है।

अंतर: एक ओब्लिवियस एडवर्सरी आपकी टोकरी को देखे बिना अपने अतिरिक्त फल जोड़ता है। वे बस रैंडम फल चुनते हैं और उन्हें जोड़ देते हैं।
परिणाम: क्योंकि उन्होंने हेरफेर करने के लिए आपके विशिष्ट डेटा को नहीं देखा, इसलिए यादृच्छिकता (randomness) बनी रहती है। फैंसी एल्गोरिदम यहाँ ठीक से काम करते हैं।

सारांश

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

परिष्कृत एल्गोरिदम (Leave-One-Out, Majority Voting) नाजुक होते हैं; जब डेटा की स्वतंत्रता का उल्लंघन होता है, तो वे टूट जाते हैं।
सरल एल्गोरिदम (ERM/Loss Minimization) मजबूत होते हैं; वे काम करते रहते हैं क्योंकि वे बस सत्य को फिट करने की कोशिश करते हैं, चाहे डेटा को कैसे भी बदला गया हो।

यह सुझाव देता है कि वास्तविक दुनिया में, जहाँ डेटा अक्सर अनुकूल रूप से (adaptively) क्यूरेट या चुना जाता है, पूरे डेटासेट पर त्रुटि को कम करने का "सरल" दृष्टिकोण हमारी सोच से कहीं अधिक विश्वसनीय हो सकता है, जबकि हमारे फैंसी सैद्धांतिक आश्वासन बहुत नाजुक हो सकते हैं।

तकनीकी सारांश: मोनोटोन एडवर्सरियल करप्शन के साथ सीखना (Learning with Monotone Adversarial Corruptions)

समस्या विवरण (Problem Statement)
यह शोध पत्र इस बात की जांच करता है कि मानक मशीन लर्निंग एल्गोरिदम किस हद तक डेटा स्वतंत्रता (data independence) और विनिमय क्षमता (exchangeability) के अनुमानों पर निर्भर करते हैं। लेखक सामान्यीकरण (generalization) में इन धारणाओं की भूमिका को अलग करने के लिए एक मोनोटोन एडवर्सरियल करप्शन मॉडल (monotone adversarial corruption model) पेश करते हैं। इस मॉडल में, एक विरोधी (adversary) वितरण $D$ से लिए गए $n$ स्वच्छ, i.i.d. नमूनों के एक सेट और एक लक्ष्य परिकल्पना (target hypothesis) $h^\star$ को देखता है। इसके बाद, विरोधी डेटासेट में $m$ अतिरिक्त "करप्टेड" (corrupted) बिंदु सम्मिलित करता है। महत्वपूर्ण रूप से, ये करप्टेड बिंदु मोनोटोन (monotone) हैं: उन्हें ग्राउंड-ट्रुथ फंक्शन $h^\star$ के अनुसार लेबल किया गया है। हालांकि लेबल ईमानदार हैं, लेकिन विरोधी के पास $D$ , परिकल्पना वर्ग $\mathcal{H}$ , और $h^\star$ का पूर्ण ज्ञान है, और वह स्वच्छ नमूनों के आधार पर अनुकूल रूप से (adaptively) इन करप्टेड बिंदुओं को चुन सकता है। लर्निंग एल्गोरिदम को $n+m$ बिंदुओं का संयुक्त डेटासेट (यादृच्छिक रूप से शफल किया गया) प्राप्त होता है और उसे $D$ से लिए गए एक नए टेस्ट पॉइंट पर कम त्रुटि वाली परिकल्पना आउटपुट करनी होती है।

मुख्य तनाव यह है कि जबकि जोड़ा गया डेटा "स्वच्छ" (सही ढंग से लेबल किया गया) है, इन बिंदुओं का अनुकूल चयन डेटासेट की विनिमय क्षमता (exchangeability) का उल्लंघन करता है। शोध पत्र पूछता है कि क्या मानक इष्टतम लर्निंग एल्गोरिदम, जो आमतौर पर i.i.d. डेटा का अनुमान लगाते हैं, इस सेटिंग में अपने गारंटियों को बनाए रख सकते हैं।

कार्यप्रणाली और ढांचा (Methodology and Framework)
लेखक एक मोनोटोन एडवर्सरी (Monotone Adversary) (परिभाषा 2.1) को औपचारिक रूप देते हैं, जहाँ विरोधी स्वच्छ बिंदुओं के फलन (function) के रूप में करप्टेड बिंदु $A(x_1, \dots, x_n)$ उत्पन्न करता है। वे एक ऑब्लिवियस मोनोटोन एडवर्सरी (Oblivious Monotone Adversary) (परिभाषा 2.2) को भी परिभाषित करते हैं, जहाँ विरोधी स्वच्छ नमूनों से स्वतंत्र रूप से करप्टेड बिंदु उत्पन्न करता है, हालांकि उसके पास $D$ और $h^\star$ का ज्ञान होता है।

अध्ययन बाइनरी क्लासिफिकेशन और $d$ VC डायमेंशन वाले एक हाइपोथीसिस क्लास $\mathcal{H}$ पर केंद्रित है। शोध पत्र तीन प्राथमिक लर्निंग एल्गोरिदम वर्गों का विश्लेषण करता है:

एम्पिरिकल रिस्क मिनिमाइज़र (ERM): वे एल्गोरिदम जो प्रशिक्षण डेटा के अनुरूप एक परिकल्पना आउटपुट करते हैं।
मेजोरिटी वोटिंग एल्गोरिदम (Majority Voting Algorithms): वे एल्गोरिदम जो डेटा के उपसमुच्चयों (subsets) पर ERM को प्रशिक्षित करते हैं और मेजोरिटी वोट के माध्यम से भविष्यवाणियों को एकत्रित करते हैं (जैसे, Bagging, Majority-of-Three, Hanneke's algorithm)।
वन-इनक्लूजन ग्राफ (OIG) एल्गोरिदम: वे एल्गोरिदम जो हाइपोथीसिस क्लास के संरचनात्मक गुणों पर आधारित हैं, विशेष रूप से मानक i.i.d. सेटिंग में इष्टतम त्रुटि दरों को प्राप्त करने के लिए वन-इनक्लूजन ग्राफ में अधिकतम आउट-डिग्री को न्यूनतम करने पर।

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

1. इष्टतम i.i.d. एल्गोरिदम की भंगुरता (Fragility of Optimal i.i.d. Algorithms)
शोध पत्र प्रदर्शित करता है कि मानक i.i.d. सेटिंग में इष्टतम त्रुटि दर ( $\Theta(d/n)$ ) प्राप्त करने वाले एल्गोरिदम को एक मोनोटोन एडवर्सरी द्वारा उप-इष्टतम प्रदर्शन के लिए मजबूर किया जा सकता है।

OIG की विफलता: वन-इनक्लूजन ग्राफ एल्गोरिदम, जो VC क्लास के लिए i.i.d. सेटिंग में इष्टतम है, दिखाया गया है कि जब $n$ स्वच्छ और $n$ करप्टेड बिंदुओं का सामना करता है, तो वह एक निरंतर अपेक्षित त्रुटि (विशेष रूप से $1/4$ ) का शिकार होता है (Theorem 1.1, Theorem 4.4)। यह "प्राकृतिक" ओरिएंटेशन रणनीति के लिए भी सत्य है जो अधिकतम आउट-डिग्री को न्यूनतम करती है।
मेजोरिटी वोटिंग की विफलता: कोई भी मेजोरिटी वोटिंग एल्गोरिदम जो कम से कम $t$ आकार के उपसमुच्चयों का उपयोग करता है, उसे केवल $2n/t$ करप्टेड बिंदुओं का उपयोग करके $\Omega(d \log(n/d)/n)$ की अपेक्षित त्रुटि झेलने के लिए मजबूर किया जा सकता है (Theorem 1.2, Theorem 4.2, Theorem 4.3)। यह Bagging और Majority-of-Three जैसे अत्याधुनिक इष्टतम लर्नर्स पर भी लागू होता है, जो आमतौर पर $\Omega(n)$ आकार के उपसमुच्चयों का उपयोग करते हैं। एडवर्सरी वोटिंग एल्गोरिदम द्वारा उपयोग किए जाने वाले उपसमुच्चयों को सह-संबंधित (correlate) करने के लिए भ्रष्टाचार की अनुकूल प्रकृति का लाभ उठाता है, जिससे वे एक साथ विफल हो जाते हैं।

2. यूनिफॉर्म कन्वर्जेंस की मजबूती (Robustness of Uniform Convergence - ERM)
इसके विपरीत, शोध पत्र दिखाता है कि एम्पिरिकल रिस्क मिनिमाइजेशन (ERM) मोनोटोन करप्शन के प्रति मजबूत है।

ऊपरी सीमा (Upper Bound): लेखक सिद्ध करते हैं कि संयुक्त डेटासेट (स्वच्छ + करप्टेड) पर कोई भी ERM, करप्टेड बिंदुओं की संख्या की परवाह किए बिना, $O(d \log(n/d)/n)$ की अपेक्षित त्रुटि प्राप्त करता है (Theorem 1.3, Theorem 3.1)।
तंत्र (Mechanism): प्रमाण इस अवलोकन पर आधारित है कि चूंकि एडवर्सरी लेबल को करप्ट नहीं कर सकता, इसलिए पूरे डेटासेट के साथ सुसंगत (consistent) कोई भी ERM स्वच्छ उपसमुच्चय के साथ भी सुसंगत होता है। डेटा के रैंडम परम्यूटेशन पर विचार करने से, स्वच्छ बिंदु $D$ से i.i.d. बने रहते हैं। इस प्रकार, मानक यूनिफॉर्म कन्वर्जेंस तर्क स्वच्छ उपसमुच्चय पर लागू होते हैं, जो यह सुनिश्चित करते हैं कि ERM स्वच्छ वितरण की कीमत पर करप्टेड बिंदुओं पर ओवरफिट न हो।
महत्व: यह सुझाव देता है कि i.i.d. सेटिंग में ERM की उप-इष्टतमता (एक $\log(n/d)$ फैक्टर के साथ $d/n$ की तुलना में) इस विशिष्ट प्रकार की निर्भरता के विरुद्ध मजबूती के लिए चुकाई गई "कीमत" है।

3. विनिमय क्षमता की भूमिका (The Role of Exchangeability)
शोध पत्र इस बात पर प्रकाश डालता है कि OIG और मेजोरिटी वोटिंग की विफलता सीधे तौर पर विनिमय क्षमता (exchangeability) की कमी के कारण है।

ऑब्लिवियस एडवर्सरी: यदि एडवर्सरी को ऑब्लिवियस होने के लिए बाध्य किया जाता है (करप्टेड बिंदु स्वच्छ नमूनों से स्वतंत्र हैं), तो OIG एल्गोरिदम अपनी इष्टतम अपेक्षित त्रुटि $O(d/n)$ को पुनः प्राप्त कर लेता है (Theorem 1.4, Theorem 3.2)। यह पुष्टि करता है कि मोनोटोन एडवर्सरी द्वारा पेश की गई अनुकूल निर्भरता ही इन एल्गोरिदम को तोड़ने वाला विशिष्ट तंत्र है।

महत्व और दावे (Significance and Claims)
लेखक दावा करते हैं कि उनके परिणाम इष्टतम लर्निंग एल्गोरिदम में विनिमय क्षमता (exchangeability) पर अत्यधिक निर्भरता को उजागर करते हैं।

सैद्धांतिक अंतर्दृष्टि: यह कार्य इस अंतर्ज्ञान को चुनौती देता है कि "अधिक डेटा बेहतर है," भले ही अतिरिक्त डेटा सही ढंग से लेबल किया गया हो। यह प्रदर्शित करता है कि मानक सेटिंग में इष्टतम दरों के लिए डिज़ाइन किए गए परिष्कृत तकनीक (जैसे लीव-वन-आउट और एन्सेम्बल मेथड्स) को दिखने में सहायक मोनोटोन करप्शन भी प्रमाणित रूप से तोड़ सकते हैं।
व्यावहारिक निहितार्थ: परिणाम बताते हैं कि आधुनिक मशीन लर्निंग अभ्यास में लॉस मिनिमाइजेशन (ERM) की सफलता इसके डेटा मिसस्पेसिफिकेशन और निर्भरता के कुछ रूपों के प्रति अंतर्निहित मजबूती से उत्पन्न हो सकती है, जबकि i.i.d. सेटिंग्स में इष्टतम दरों के लिए डिज़ाइन किए गए अधिक परिष्कृत तकनीक नाजुक हो सकती हैं।
खुले प्रश्न: शोध पत्र मोनोटोन एडवर्सरीज के तहत लर्निंग के लिए इष्टतम अपेक्षित त्रुटि को एक खुला प्रश्न बताता है। जबकि ERM $O(d \log(n/d)/n)$ का ऊपरी स्तर प्रदान करता है, यह अज्ञात है कि क्या कोई एल्गोरिदम $O(d/n)$ की इष्टतम दर प्राप्त कर सकता है। इसके अलावा, इस मॉडल के तहत लिटिलस्टोन क्लासेस (Littlestone classes) और पार्शियल/मल्टीक्लास क्लासेस की सीखने की क्षमता एक खुला प्रश्न बनी हुई है, क्योंकि यूनिफॉर्म कन्वर्जेंस सिद्धांत इन सेटिंग्स में लागू नहीं होते हैं।

संक्षेप में, शोध पत्र स्थापित करता है कि जबकि ERM मोनोटोन करप्शन की उपस्थिति में एक मजबूत, हालांकि थोड़ी उप-इष्टतम गारंटी प्रदान करता है, वर्तमान में ज्ञात इष्टतम एल्गोरिदम (जो i.i.d. के लिए हैं) अनुकूलित, लेबल-सही करप्शन के प्रति अत्यधिक संवेदनशील हैं जो विनिमय क्षमता का उल्लंघन करते हैं।

"मददगार" साज़िशकर्ता: मोनोटोन एडवर्सरी (The Monotone Adversary)

बड़ी हैरानी: "अधिक डेटा" बुरा भी हो सकता है

नायक: "सिंपल" लर्नर (ERM)

"ओब्लिवियस" अपवाद

सारांश

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