🤖 machine learning

Optimal Learning Under Tsybakov Noise

यह शोधपत्र ट्सयाकोव नॉइज़ (Tsyakanov noise) के तहत लर्निंग के लिए इष्टतम त्रुटि गारंटी (optimal error guarantee) स्थापित करके बीस साल पुराने एक खुले प्रश्न को हल करता है, जो शोर के स्तरों द्वारा इंस्टेंस स्पेस को विभाजित करने वाले एक एडेप्टिव एल्गोरिदम के माध्यम से ज्ञात ऊपरी और निचली सीमाओं के बीच के अंतर को समाप्त करता है।

मूल लेखक: Steve Hanneke, Hongao Wang, Mingyue Xu

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

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

CC BY 4.0

मूल लेखक: Steve Hanneke, Hongao Wang, Mingyue Xu

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

कल्पना कीजिए कि आप एक रोबोट को तस्वीरों में बिल्लियों को पहचानना सिखाने की कोशिश कर रहे हैं। कंप्यूटर विज्ञान के शुरुआती आदर्श युग में, हर तस्वीर को पूरी तरह से लेबल किया गया था: यदि उसमें बिल्ली थी, तो लेबल कहता था "बिल्ली"; यदि नहीं थी, तो वह कहता था "बिल्ली नहीं"। इसे "रियलाइज़ेबल" (realizable) सेटिंग कहा जाता है, और दशकों तक, वैज्ञानिकों ने इन आदर्श स्थितियों में सीखने के सबसे अच्छे तरीके खोज निकाले। लेकिन वास्तविक दुनिया अव्यवस्थित है। कभी-कभी फोटो धुंधली होती है, या कोई बिल्ली पर्दे के पीछे छिपी होती है, या कोई मानव लेबलर का बस बुरा दिन चल रहा होता है। रोबोट एक बिल्ली की तस्वीर देख सकता है और लेबल गलती से "कुत्ता" कह सकता है। इसे "नॉइज़" (noise) कहा जाता है।

मुख्य प्रश्न यह रहा है कि: हम एक रोबोट को प्रभावी ढंग से सीखना कैसे सिखाएं जब लेबल शोर-शराबे वाले (noisy) हों, लेकिन यह शोर केवल यादृच्छिक अराजकता नहीं है? कभी-कभी शोर हल्का होता है (जैसे कि थोड़ी धुंधली छवि), लेकिन कभी-कभी यह अत्यधिक (जैसे कि पूरी तरह से गलत लेबल वाली छवि) होता है। बीस वर्षों से, वैज्ञानिक "त्सिबाकोव नॉइज़" (Tsybakov noise) नामक शोर के एक विशिष्ट प्रकार में फंसे हुए थे। वे जानते थे कि एक रोबोट कितनी तेजी से सीख सकता है (लोअर बाउंड), और वे एक ऐसी विधि जानते थे जो लगभग उतनी ही तेज़ थी (अपर बाउंड), लेकिन उनके बीच एक छोटा सा, परेशान करने वाला अंतर था, एक लॉगरिदमिक फैक्टर (logarithmic factor), जैसे कि पहेली का एक गायब हिस्सा जो फिट ही नहीं हो रहा था। उन्हें उस अंतर को पाटने और इस अव्यवस्थित वातावरण में सीखने की वास्तविक, इष्टतम गति खोजने की आवश्यकता थी।

पर्ड्यू यूनिवर्सिटी के स्टीव हनेके, होंगाओ वांग और मिंगयू एक्स द्वारा लिखा गया यह शोध पत्र अंततः उस बीस साल पुराने पहेली को हल करता है। वे एक नया लर्निंग एल्गोरिदम पेश करते हैं जिसे MERIT (Massart Error Regions Isolation under Tsybakov noise) कहा जाता है। MERIT को एक चतुर जासूस के रूप में समझें जो एक बार में पूरा मामला सुलझाने की कोशिश नहीं करता है। इसके बजाय, जासूस अपराध स्थल (डेटा) को इस आधार पर अलग-अलग क्षेत्रों में विभाजित करता है कि प्रत्येक क्षेत्र कितना "भ्रमित करने वाला" या "शोर-शराबे वाला" है।

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

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

तकनीकी सारांश: ट्सयाकोव शोर (Tsybakov Noise) के तहत इष्टतम शिक्षण

समस्या विवरण
यह शोध पत्र ट्सयाकोव शोर (Tsybakov noise) की स्थिति के तहत बाइनरी क्लासिफिकेशन के लिए प्रोबेबली एप्रोक्सिमेटली करेक्ट (PAC) लर्निंग की समस्या को संबोधित करता है। इस सेटिंग में, एक शिक्षार्थी (learner) एक इंस्टेंस स्पेस $\mathcal{X} \times \{0, 1\}$ पर वितरण $D$ से i.i.d. लेबल वाले उदाहरण प्राप्त करता है। लक्ष्य एक अवधारणा वर्ग (concept class) $\mathcal{H}$ (जिसका VC डायमेंशन $d$ है) से एक परिकल्पना (hypothesis) $\hat{h}$ आउटपुट करना है जो बेयस-इष्टतम क्लासिफायर $h^*_D \in \mathcal{H}$ के सापेक्ष अतिरिक्त त्रुटि (excess error) को कम करता है।

त्याकोव शोर की स्थिति मासार्ट शोर (Massart noise) मॉडल का सामान्यीकरण करती है, जो लेबल बदलने की संभावना को इंस्टेंस स्पेस के एक उपसमुच्चय (subset) पर $1/2$ (सबसे कठिन शोर) के करीब पहुँचने की अनुमति देती है, बशर्ते कि इस उपसमुच्चय का संभाव्यता द्रव्यमान (probability mass) कम हो। विशेष रूप से, मापदंडों $(a, \alpha)$ के लिए, शर्त यह है कि:
$P_{x \sim D_X}(|\eta_D(x) - 1/2| \le t) \le a' t^{\frac{\alpha}{1-\alpha}}$
जहाँ $\eta_D(x) = P(Y=1|X=x)$ रिग्रेशन फंक्शन है। पैरामीटर $\alpha \in (0, 1)$ शोर के स्तर को नियंत्रित करता है; छोटा $\alpha$ अधिक चुनौतीपूर्ण शोर वितरण को दर्शाता है, जो मासार्ट शोर ( $\alpha \to 1$ ) और एगोस्टिक (agnostic) सेटिंग ( $\alpha \to 0$ ) के बीच के अंतर को पाटता है।

खुला प्रश्न
पूर्व कार्य द्वारा [MN06] स्थापित किया गया था कि एम्पिरिकल रिस्क मिनिमाइजेशन (ERM) एल्गोरिदम लगभग $\tilde{O}((d/n)^{\frac{1}{2-\alpha}})$ का अतिरिक्त जोखिम ऊपरी बाउंड (excess risk upper bound) प्राप्त करता है, जहाँ टिल्डे ( $\sim$ ) लॉगरिदमिक कारकों को छिपाता है। हालाँकि, इस समस्या के लिए ज्ञात मिनिमैक्स लोअर बाउंड $\Omega((d/n)^{\frac{1}{2-\alpha}})$ है। दो दशकों तक, यह एक खुला प्रश्न बना रहा कि क्या लॉगरिदमिक गैप को बंद किया जा सकता है, और विशेष रूप से, क्या एक प्रॉपर लर्नर (एक जो मूल वर्ग $\mathcal{H}$ के भीतर एक परिकल्पना आउटपुट करता है) इष्टतम दर प्राप्त कर सकता है।

कार्यप्रणाली: MERIT एल्गोरिदम
लेखक एक नया लर्निंग एल्गोरिदम प्रस्तावित करते हैं जिसे "मासार्ट" एरर रीजन आइसोलेशन अंडर ट्सयाकोव नॉइज़ (MERIT) कहा जाता है। मुख्य वैचारिक नवाचार पूरे स्थान को समान रूप से मानने के बजाय, अलग-अलग शोर स्तरों वाले इंस्टेंस स्पेस $\mathcal{X}$ का अनुकूल रूप से विभाजन (adaptive partitioning) करना है।

अनुकूल विभाजन (Adaptive Partitioning): एल्गोरिदम पुनरावर्ती रूप से उन "एरर रीजन" $\Delta_t$ को अलग करता है जहाँ शोर अधिक है। स्पेस को विलगित क्षेत्रों $(\Delta_{t-1} \setminus \Delta_t)$ और एक अंतिम क्षेत्र $\Delta_T$ में विभाजित किया गया है।
शोर शेड्यूलिंग (Noise Scheduling): एल्गोरिदम शोर रेजोल्यूशन मापदंडों $\beta_t$ $β_{t}$ और प्रूनिंग थ्रेशोल्ड $\gamma_t$ $γ_{t}$ के एक अनुक्रम के साथ कार्य करता है।
- क्षेत्रों $(\Delta_{t-1} \setminus \Delta_t)$ में, एल्गोरिदम यह सुनिश्चित करता है कि वितरण एक विशिष्ट मार्जिन पैरामीटर के साथ मासार्ट शोर (या एक रैखिक बर्नस्टीन स्थिति) के समान स्थिति को संतुष्ट करता है।
- यह वर्तमान जीवित वर्ग (surviving class) में हाइपोथीसिस के जोड़ों $(f, g)$ की पहचान करता है जिनका एम्पिरिकल डिसएग्रीमेंट (स्यूडो-डिस्टेंस) बड़ा है लेकिन अतिरिक्त जोखिम कम है। ऐसे डिसएग्रीमेंट उच्च-शोर वाले क्षेत्रों के सूचक हैं।
- एल्गोरिदम इन डिसएग्रीमेंट क्षेत्रों को $\Delta_t$ में अलग करता है, जिससे वर्तमान लर्निंग टास्क से "शोर वाले" बिंदुओं को प्रभावी रूप से हटा दिया जाता है।
डिसीजन लिस्ट्स के माध्यम से प्रॉपर लर्निंग:
- एल्गोरिदम प्रत्येक क्षेत्र $(\Delta_{t-1} \setminus \Delta_t)$ पर प्रतिबंधित डेटा पर स्वतंत्र रूप से ERM चलाता है।
- यह इन क्षेत्रीय ERM प्रेडिक्टर्स के डिसीजन-लिस्ट एग्रीगेशन के रूप में एक अंतिम हाइपोथीसिस का निर्माण करता है।
- महत्वपूर्ण रूप से, लेखक दिखाते हैं कि मूल वर्ग $\mathcal{H}$ में एक एकल हाइपोथीसिस मौजूद है जो सभी क्षेत्रों की त्रुटि बाधाओं को एक साथ संतुष्ट करता है। अतः, एल्गोरिदम एक प्रॉपर लर्नर (एक अवधारणा $\mathcal{H}$ में) लौटाता है, न कि केवल एक इमप्रॉपर एग्रीगेशन।
नमूना आवंटन (Sample Allocation): क्षेत्र अलगाव प्रक्रिया और अंतिम जोखिम अनुमान के बीच स्वतंत्रता सुनिश्चित करने के लिए, एल्गोरिदम निम्नलिखित के लिए ताजे नमूनों ( $S_1, S_2, S_3$ $S_{1}, S_{2}, S_{3}$ ) को सावधानीपूर्वक आवंटित करता है:
- प्रून्ड कॉन्सेप्ट क्लास का अनुमान लगाना।
- डिसएग्रीमेंट क्षेत्रों की पहचान करने के लिए स्यूडो-डिस्टेंस का अनुमान लगाना।
- अलग किए गए क्षेत्रों पर अंतिम ERM प्रेडिक्टर्स को प्रशिक्षित करना।

मुख्य योगदान और परिणाम

लॉगरिदमिक गैप का समाधान: यह शोध पत्र सिद्ध करता है कि ट्सयाकोव शोर के तहत इष्टतम मिनिमैक्स लर्निंग रेट $\Theta((d/n + \log(1/\delta)/n)^{\frac{1}{2-\alpha}})$ है। यह सर्वोत्तम ज्ञात लोअर बाउंड से मेल खाता है, जिससे पिछले ERM-आधारित अपर बाउंड्स में मौजूद लॉगरिदमिक कारक समाप्त हो जाता है।
इष्टतम प्रॉपर लर्नर: MERIT एल्गोरिदम इस इष्टतम दर को प्राप्त करता है जबकि यह एक प्रॉपर लर्नर है। यह महत्वपूर्ण है क्योंकि, रियलाइज़ेबल सेटिंग में, इष्टतम दरएं पहले केवल इमप्रॉपर लर्नर्स (जैसे हन्नेके का एल्गोरिदम [Han16a]) द्वारा प्राप्त करने योग्य मानी जाती थीं, जबकि एगोस्टिक सेटिंग में, प्रॉपर लर्नर्स (जैसे ERM) को उप-इष्टतम (sub-optimal) माना जाता है। MERIT इसे सिद्ध करके एक सेतु बनाता है कि ट्सयाकोक शोर के तहत प्रॉपर ऑप्टिमलिटी संभव है।
तकनीकी उपकरण: प्रमाण एक परिष्कृत यूनिफॉर्म बर्नस्टीन इनइक्वेलिटी (लेम्मा 15) और अलग किए गए क्षेत्रों पर ट्सयाकोव शोर द्वारा प्रेरित बर्नस्टीन क्लास कंडीशन के सावधानीपूर्ण विश्लेषण पर निर्भर करता है। लेखक प्रदर्शित करते हैं कि कॉन्सेप्ट क्लास को अनुकूल रूप से प्रून करके और उच्च-विचरण (high-variance) वाले क्षेत्रों को अलग करके, प्रत्येक उप-क्षेत्र पर सीखने की प्रभावी जटिलता कम हो जाती है, जिससे ERM टाइट बाउंड प्राप्त करने में सक्षम होता है।

महत्ता और दावे
लेखक दावा करते हैं कि उन्होंने लर्निंग थ्योरी की एक सुप्रसिद्ध खुली समस्या को हल कर दिया है जो बीस वर्षों से बनी हुई थी। इसकी प्राथमिक महत्ता यह स्थापित करना है कि ट्सयाकोव शोर के तहत लर्निंग के लिए इष्टतम त्रुटि गारंटी (optimal error guarantee) क्या है और यह कि यह एक प्रॉपर लर्निंग एल्गोरिदम द्वारा प्राप्त की जा सकती है।

लेख स्पष्ट रूप से निम्नलिखित सीमाओं और दायरे को नोट करता है:

एल्गोरिदम को ट्सयाकोव शोर मापदंडों $(a, \alpha)$ के पूर्व ज्ञान की आवश्यकता होती है।
एल्गोरिदम $\delta$ -डिपेंडेंट है (इसे विश्वास को पहले से सेट करने की आवश्यकता होती है), जो कुछ इष्टतम रियलाइज़ेबल लर्नर्स के विपरीत है।
यह दावा नहीं किया गया है कि यह तकनीक एगोस्टिक सेटिंग को प्रॉपर लर्नर के साथ इष्टतम रूप से हल करती है (जो कि फर्स्ट-ऑर्डर टर्म्स के लिए असंभव माना जाता है), लेकिन लेखक अनुमान लगाते हैं कि शोर अलगाव तकनीक एगोस्टिक लर्निंग में लोअर-ऑर्डर टर्म्स को परिष्कृत कर सकती है।
विशिष्ट वर्गों (जैसे हाफस्पेस) के लिए कम्प्यूटेशनल दक्षता एक खुला प्रश्न है, हालांकि यह पेपर [DKK+21] द्वारा हाफस्पेस के लिए ट्सयाकोव शोर के तहत बहुपद-समय (polynomial-time) सीखने योग्य परिणामों का संदर्भ देता है।

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

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