🤖 machine learning

Two Dimensions Govern Agnostic Multiclass Transductive Learning

यह शोध पत्र इस खुले प्रश्न का समाधान करता है कि क्या मल्टीक्लास सेटिंग्स में अग्नोस्टिक ट्रांसडक्टिव (agnostic transductive) और PAC लर्निंग समान मिनिमैक्स दरों (minimax rates) को साझा करते हैं, यह सिद्ध करके कि किसी भी मनमाने लेबल स्पेस के लिए, इष्टतम अतिरिक्त त्रुटि (optimal excess error) DS आयाम और नटराजियन आयाम (Natarajan dimension) को संयोजित करने वाले एक दो-आयामी नियम द्वारा शासित होती है, विशेष रूप से $\widetilde\Theta\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right)$ ।

मूल लेखक: Pahan Dewasurendra

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

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

CC BY 4.0

मूल लेखक: Pahan Dewasurendra

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

मशीन लर्निंग की दुनिया में, कंप्यूटर उदाहरणों का अध्ययन करके भविष्यवाणियां करना सीखते हैं। कल्पना कीजिए कि एक छात्र एक परीक्षा के प्रश्न का उत्तर देने का अनुमान लगाने की कोशिश कर रहा है। सीखने के मानक तरीके में, जिसे "PAC लर्निंग" कहा जाता है, छात्र फ्लैशकार्डों के एक सेट पर अभ्यास करता है, और फिर नए, अनदेखे कार्डों पर परीक्षा देता है। लक्ष्य कई संभावित परीक्षणों पर औसतन अच्छा प्रदर्शन करना है। लेकिन, सीखने का एक अन्य, अधिक विशिष्ट तरीका है जिसे "ट्रांसडक्टिव लर्निंग" (transductive learning) कहा जाता है। यहाँ, छात्र को पहले से ही पूरा प्रश्न पत्र दिया जाता है, जिसमें प्रत्येक प्रश्न शामिल होता है, लेकिन केवल एक विशिष्ट प्रश्न का उत्तर छिपा हुआ होता है। छात्र अन्य सभी उत्तरों को देखता है और उस एक छिपे हुए उत्तर का अनुमान लगाता है। यह सेटअप अधिक सख्त है क्योंकि छात्र औसत प्रदर्शन पर भरोसा नहीं कर सकता; उसे उन विशिष्ट, निश्चित प्रश्नों के लिए सही होना ही होगा।

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

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

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

उनके द्वारा विकसित समाधान "रैंडम रिजर्वेशन" (random reservation) की एक रणनीति पर आधारित है। दृश्य उदाहरणों का उपयोग करके भविष्यवाणी बनाने के बजाय, शिक्षार्थी दृश्य डेटा के एक बड़े हिस्से को बेतरतीब ढंग से अलग रख देता है, और इसे उसी तरह मानता है जैसे कि वह छिपा हुआ परीक्षण बिंदु हो। इन आरक्षित लेबलों को अनदेखा करके, शिक्षार्थी डेटा का एक बड़ा, अनदेखा ब्लॉक बनाता है जो नियम द्वारा निर्मित नियम से सांख्यिकीय रूप से स्वतंत्र होता है। यह उन्हें शक्तिशाली गणितीय उपकरणों का उपयोग करने की अनुमति देता है जो सामान्यीकरण (generalization) के विचार पर निर्भर करते हैं—यानी उस डेटा पर अच्छी भविष्यवाणी करना जिसका उपयोग मॉडल बनाने के लिए नहीं किया गया था। शिक्षार्थी भविष्यवाणी को परिष्कृत करने के लिए तीन-चरणीय प्रक्रिया का उपयोग करता है। पहले, वे संभावित भविष्यवाणी नियमों की एक सीमित सूची बनाने के लिए दृश्य डेटा के एक छोटे नमूने का उपयोग करते हैं। दूसरा, वे संभावित उत्तरों की सूची को कम करने के लिए एक भारित मतदान प्रणाली (weighted voting system) का उपयोग करते हैं, जो प्रभावी रूप से समस्या की जटिलता को कम करता है। अंत में, वे इस संकुचित सूची से सबसे अच्छे नियम का चयन करने के लिए शेष दृश्य डेटा का उपयोग करते हैं।

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

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

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

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

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

तकनीकी सारांश: एग्नोस्टिक मल्टीक्लास ट्रांसडक्शन को दो आयाम नियंत्रित करते हैं

समस्या विवरण
यह शोध पत्र इस मौलिक प्रश्न को संबोधित करता है कि क्या एग्नोस्टिक मल्टीक्लास ट्रांसडक्टिव लर्निंग के मिनिमैक्स दरें (minimax rates), एग्नोस्टिक मल्टीक्लास PAC (प्रोबेबली एप्रोक्सिमेटली करेक्ट) लर्निंग की दरों से मेल खाती हैं। ट्रांसडक्टिव सेटिंग में, एक एडवर्सरी (adversary) आकार $n$ की एक लेबल वाली जनसंख्या को फिक्स कर देता है, जिसमें से एक लेबल को समान रूप से यादृच्छिक (uniformly at random) रूप से छिपा दिया जाता है, और शिक्षार्थी (learner) छिपे हुए लेबल की भविष्यवाणी करने के लिए अन्य सभी लेबल और उदाहरणों के पूर्ण सेट को देखता है। जबकि यह स्थापित है कि बाइनरी क्लासिफिकेशन के लिए, एग्नोस्टिक ट्रांसडक्टिव और PAC का अनुकूलतम दर $\Theta(\sqrt{d/n})$ (जहाँ $d$ VC डायमेंशन है) समान है, मल्टीक्लास मामले में यह खुला प्रश्न बना हुआ था।

मनमानी (संभावित रूप से अनबाउंडेड) लेबल स्पेस पर मल्टीक्लास लर्निंग एक अनूठी चुनौती पेश करती है: कोई भी एकल आयाम सैंपल कॉम्प्लेक्सिटी को नियंत्रित नहीं करता है। इसके बजाय, दो आयामों की आवश्यकता होती है:

DS डायमेंशन ( $d_{DS}$ ): जो रियलाइजेबल लर्नेबिलिटी (realizable learnability) को दर्शाता है।
नटराज डायमेंशन ( $d_N$ ): जो स्मॉल-एक्सेस रिजीम (small-excess regime) में एग्नोस्टिक लर्नेबिलिटी को दर्शाता है।

हाल के कार्य ने स्थापित किया है कि एग्नोस्टिक PAC सैंपल कॉम्प्लेक्सिटी इन दोनों आयामों के योग द्वारा नियंत्रित होती है: $\tilde{\Theta}(d_{DS}/\epsilon + d_N/\epsilon^2)$ । खुला प्रश्न यह था कि क्या यह "दो-डायमेंशन लॉ" ट्रांसडक्टिव सेटिंग में भी लागू होता है, जहाँ सीमित जनसंख्या पर एम्पिरिकल रिस्क मिनिमाइजेशन (empirical risk minimization) अस्थिरता (उच्च लीव-वन-आउट एरर) का शिकार हो सकता है, भले ही हाइपोथीसिस क्लासेस छोटी हों।

कार्यप्रणाली (Methodology)
यह शोध पत्र एक विशिष्ट ट्रांसडक्टिव लर्नर का निर्माण करके और मिलान वाले लोअर बाउंड्स (lower bounds) सिद्ध करके इस प्रश्न को हल करता है। मुख्य पद्धतिगत नवाचार एक रैंडम-रिजर्वेशन सिद्धांत (random-reservation principle) है।

रैंडम रिजर्वेशन: सभी दृश्यमान लेबल्स का उपयोग करने के बजाय, लर्नर दृश्यमान उदाहरणों के एक निरंतर अंश (constant fraction) को जानबूझकर अनदेखा करता है। विशेष रूप से, $n-1$ दृश्यमान उदाहरणों में से, लर्नर आकार $q \approx n/4$ के तीन विलगित (disjoint) रैंडम ब्लॉक्स ( $A, B, C$ ) चुनता है और शेष को अनदेखा कर देता है। छिपा हुआ इंडेक्स इन ब्लॉक्स के पूरक (complement) के भीतर ("अनसीन ब्लॉक") समान रूप से वितरित होता है। यह एकल छिपे हुए लेबल को एक बड़े अनसीन पॉपुलेशन के भीतर एक समान यादृच्छिक बिंदु में बदल देता है, जिससे लीव-वन-आउट स्टेबिलिटी पर निर्भर किए बिना फाइनाइट-पॉपुलेशन जनरलाइजेशन संभव हो पाता है।
थ्री-स्टेज लर्निंग आर्किटेक्चर: लर्नर इस स्ट्रक्चर्ड PAC आर्किटेक्चर को इस फाइनाइट-पॉपुलेशन स्प्लिट के अनुकूल बनाता है:
- स्टेज 1 (रियलाइजेबल कम्प्रेशन): ब्लॉक $A$ का उपयोग करके, लर्नर एक रियलाइजेबल कम्प्रेशन स्कीम का उपयोग करके हाइपोथीसिस स्पेस का एक फाइनाइट कवर बनाता है। यह अनंत हाइपोथीसिस क्लास को उन उम्मीदवारों के एक सीमित सेट ( $F_A$ ) में कम कर देता है जो डेटा के रियलाइजेबल भाग के अनुरूप (consistent) हैं।
- स्टेज 2 (लेबल-स्पेस रिडक्शन): ब्लॉक $B$ का उपयोग करके, लर्नर फाइनाइट सेट $F_A$ पर एक विदाउट-रिप्लेसमेंट मल्टीप्लिकेटिव वेट्स (without-replacement multiplicative weights) एल्गोरिदम चलाता है। यह प्रत्येक इंस्टेंस के लिए एक "मेन्यू" (उम्मीदवार लेबल्स का एक छोटा सेट) तैयार करता है, जो प्रभावी रूप से लेबल स्पेस को कम करता है।
- स्टेज 3 (इनसाइड-मेन्यू एग्नोस्टिक कम्प्रेशन): ब्लॉक $C$ का उपयोग करके, लर्नर अंतिम प्रेडिक्टर बनाने के लिए उत्पन्न मेन्यू के लेबल्स तक सीमित एग्नोस्टिक कम्प्रेशन करता है।
प्रमुख तकनीकी लेम्मा (Technical Lemmas):
- फाइनाइट-पॉपुलेशन कम्प्रेशन कवर: कम्प्रेशन बाउंड्स को फिक्स्ड-पॉपुलेशन तक विस्तारित करता है, यह दिखाते हुए कि एक सबसेट से पुनर्गठित प्रेडिक्टर अनसीन शेष भाग पर अच्छा प्रदर्शन करता है।
- विदाउट-रिप्लेसमेंट मल्टीप्लिकेटिव वेट्स लेम्मा: एक नया लेम्मा जो यह सिद्ध करता है कि बिना प्रतिस्थापन (without replacement) के लिए सैंपल किए गए एक्सपर्ट्स के लिए, अपेक्षित संचयी रिवॉर्ड (expected cumulative reward) सीमित रहता है, जो स्वतंत्रता की कमी के बावजूद तेज़ $1/n$ एप्रोक्सिमेशन टर्म (जो $d_{DS}$ टर्म के लिए महत्वपूर्ण है) को सुरक्षित रखता है।
- रैंडम-स्प्लिट एग्नोस्टिक कम्प्रेशन: सैंपलिंग बिना प्रतिस्थापन (sampling without replacement) के लिए होफडिंग के इनइक्वलिटी (Hoeffding's inequality) का उपयोग करके एक रैंडम ब्लॉक से दूसरे ब्लॉक में एम्पिरिकल ऑप्टिमलिटी को स्थानांतरित करता है।

प्रमुख परिणाम
शोध पत्र स्थापित करता है कि इष्टतम एग्नोस्टिक ट्रांसडक्टिव एक्सेस एरर $\epsilon_{tr}^H(n)$ उन्हीं दो आयामों द्वारा नियंत्रित होता है जो PAC लर्निंग के लिए हैं, केवल लॉगरिदमिक कारकों के अंतर के साथ।

अपर बाउंड (Upper Bound):
$\epsilon_{tr}^H(n) \leq C \min \left\{ 1, \frac{d_{DS} \log^2(en)}{n} + \sqrt{\frac{d_N \log^3(en)}{n}} \right\}$
लोअर बाउंड (Lower Bound):
$\epsilon_{tr}^H(n) \geq c \min \left\{ 1, \frac{d_{DS}}{n} + \sqrt{\frac{d_N}{n}} \right\}$

ये बाउंड्स मनमानी लेबल स्पेस (अनंत और अनकाउंटेबल सहित) के लिए मान्य हैं। फलस्वरूप, ट्रांसडक्टिव लर्निंग की सैंपल कॉम्प्लेक्सिटी है:
$m_{tr}^H(\epsilon) = \tilde{\Theta} \left( \frac{d_{DS}}{\epsilon} + \frac{d_N}{\epsilon^2} \right)$

लोअर बाउंड कंस्ट्रक्शन
लेखक दोनों पदों की आवश्यकता को विशिष्ट बाधाओं (obstructions) का उपयोग करके सिद्ध करते हैं:

नटराज ऑब्स्ट्रक्शन: दोहराए गए (repeated) शैटर्ड पॉइंट्स को असाइन करके, छिपा हुआ लेबल दृश्यमान डेटा से स्वतंत्र एक निष्पक्ष बिट (fair bit) बना रहता है, जो एरर रेट को $\sqrt{d_N/n}$ के अनुपात में रखता है।
DS ऑब्स्ट्रक्शन: एक स्यूडो-क्यूब (pseudo-cube) के कोऑर्डिनेट फाइबर्स को ओरिएंट करके, लेखक दिखाते हैं कि दोहराव के बावजूद, औसत आउटडिग्री (एरर) $d_{DS}$ डायमेंशन के समानुपाती रहता है, जिससे $d_{DS}/n$ टर्म आवश्यक हो जाता है।

योगदान और महत्व
शोध पत्र निम्नलिखित योगदानों का दावा करता है:

चरित्रीकरण (Characterization): यह अलग-अलग DS और नटराज टर्म्स के माध्यम से मनमानी लेबल स्पेस के लिए एग्नोस्टिक मल्टीक्लास ट्रांसडक्टिव एरर का पूर्ण चरित्रीकरण करता है।
रैंडम-रिजर्वेशन रिडक्शन: यह एक रिडक्शन तकनीक पेश करता है जो स्ट्रक्चर्ड PAC लर्नर्स को फिक्स्ड फाइनाइट पॉपुलेशन में स्थानांतरित करता है, जिससे डायरेक्ट लीव-वन-आउट ट्रांसफर की अस्थिरता से बचा जा सकता है।
नया लेम्मा: यह $O(\log |F|/n)$ मिस प्रोबेबिलिटी के साथ एक विदाउट-रिप्लेसमेंट मल्टीप्लिकेटिव-वेट्स मेन्यू लेम्मा सिद्ध करता है, जो तेज़ $d_{DS}/n$ दर को बनाए रखने के लिए आवश्यक है।
डायरेक्ट लोअर बाउंड्स: यह नटराज क्यूब्स और DS स्यूडो-क्यूब्स से प्राप्त प्रत्यक्ष ट्रांसडक्टिव लोअर बाउंड्स प्रदान करता है।

महत्व
यह शोध पत्र इस खुले प्रश्न को हल करता है कि क्या एग्नोस्टिक मल्टीक्लास PAC और ट्रांसडक्टिव लर्निंग समान सांख्यिकीय नियमों का पालन करते हैं। यह प्रदर्शित करता है कि, लॉगरिदमिक कारकों के अंतर के साथ, दोनों मॉडल DS और नटराज डायमेंशनों पर अपनी निर्भरता के मामले में समान हैं। यह परिणाम महत्वपूर्ण है क्योंकि यह पुष्टि करता है कि "दो-डायमेंशन लॉ" मल्टीक्लास लर्निंग का एक मौलिक गुण है, जो इस बात से स्वतंत्र है कि डेटा i.i.d. (PAC) है या फिक्स्ड (ट्रांसडक्टिव)। लेखक नोट करते हैं कि उनका परिणाम सूचना-सैद्धांतिक (information-theoretic) है और यह आवश्यक रूप से कम्प्यूटेशनल दक्षता का संकेत नहीं देता है, न ही यह सभी बाउंडेड लॉस फंक्शन्स के लिए ब्लैक-बॉक्स रिडक्शन प्रदान करता है, बल्कि यह विशेष रूप से मल्टीक्लास लर्निंग की संरचना का लाभ उठाता है ताकि दोनों मॉडलों के बीच के अंतर को भरा जा सके।

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