🤖 machine learning

A Rate Separation for Agnostic Direct Sums

यह शोध पत्र यह प्रदर्शित करता है कि अवधारणा वर्गों (concept classes) के डायरेक्ट सम (direct sum) की एगोस्टिक पीएसी (agnostic PAC) लर्निंग दर केवल इसके घटकों की सिंगल-इंस्टेंस लर्निंग दरों द्वारा निर्धारित नहीं होती है, जैसा कि दो ऐसे वर्गों का निर्माण करके दिखाया गया है जिनकी लर्निंग कर्व्स समान $n^{-1/2}$ हैं लेकिन संयोजित होने पर वे अलग-अलग दरें प्रदान करते हैं।

मूल लेखक: Mihir More, Aritra Das, Debayan Gupta

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

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

CC BY 4.0

मूल लेखक: Mihir More, Aritra Das, Debayan Gupta

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

कल्पना कीजिए कि एक ऐसी दुनिया है जहाँ मशीनें एक अनुमान लगाने वाले खेल को खेलकर सीखती हैं। कंप्यूटर विज्ञान के क्षेत्र में जिसे "मशीन लर्निंग" कहा जाता है, हम अक्सर पूछते हैं: किसी कार्य में वास्तव में कुशल होने के लिए एक कंप्यूटर को कितने उदाहरणों की आवश्यकता होती है? यह "लर्निंग कर्व्स" (सीखने के वक्र) का अध्ययन है। इसे एक पिल्ले (puppy) को प्रशिक्षित करने की तरह समझें। यदि आप चाहते हैं कि एक पिल्ला बैठना सीखे, तो आपको दस बार इनाम (treats) देने पड़ सकते हैं। यदि आप चाहते हैं कि वह लुढ़कना (roll over) सीखे, तो आपको बीस बार इनाम देना पड़ सकता है। "लर्निंग कर्व" बस एक ग्राफ है जो दिखाता है कि जैसे-जैसे पिल्ला अधिक इनाम खाता है, उसकी गलतियाँ कैसे कम होती जाती हैं।

अब, कल्पना कीजिए कि आपके पास एक सुपर-पिल्ला है जो न केवल एक करतब सीखता है, बल्कि एक साथ कई करतबों का एक पूरा समूह सीखता है। शायद उसे एक ही सत्र में बैठना, लुढ़कना और भौंकना सीखना है। गणित में, इसे "डायरेक्ट सम" (direct sum) कहा जाता है। आप एक सरल सीखने की समस्या को लेते हैं और उसे कई बार खुद से गुणा करके एक बड़ी, अधिक जटिल चुनौती बना देते हैं। लंबे समय तक, वैज्ञानिकों ने यह सोचा कि इस बड़े समूह की कठिनाई क्या केवल एक साधारण गणितीय समस्या थी: यदि आप जानते हैं कि एक एकल करतब कितना कठिन है, और आप जानते हैं कि आप कितने करतबों को एक साथ जोड़ रहे हैं, तो क्या आप बस गणित लगाकर जान सकते हैं कि पूरा समूह कितना कठिन होगा? यह तर्कसंगत लग रहा था कि यदि एक करतब आसान है, तो दस करतबों को दस गुना कठिन, या शायद थोड़ा अधिक कठिन होना चाहिए। लेकिन जैसा कि हम देखने जा रहे हैं, सीखने का ब्रह्मांड आश्चर्यों से भरा है, और कभी-कभी, संपूर्ण हिस्सा अपने भागों के योग से बहुत अलग होता है।

यह शोध पत्र, जिसका शीर्षक "ए रेट सेपरेशन फॉर एगोस्टिक डायरेक्ट sums" (A Rate Separation for Agnostic Direct Sums) है, उसी प्रश्न की गहराई में जाता है। लेखक, मिहिर मोर, अरित्र दास और देबयान गुप्ता ने एक लोकप्रिय विचार का परीक्षण करने का प्रयास किया: कि जिस गति से एक मशीन एक कार्य को सीखती है (जिसे "सिंगल-इंस्टेंस लर्निंग रेट" कहा जाता है), वही यह निर्धारित करती है कि वह कार्यों के एक समूह (direct-sum rate) को कितनी तेज़ी से सीखेगी। वे यह देखना चाहते थे कि क्या एक समस्या के सीखने की गति को जानना उस समस्या के विशाल, संयुक्त संस्करण को सीखने की गति का अनुमान लगाने के लिए पर्याप्त है।

शोधकर्ताओं ने पाया कि इसका उत्तर स्पष्ट रूप से "नहीं" है। उन्होंने सिद्ध किया कि दो पूरी तरह से अलग सीखने की समस्याएँ एक अकेली परीक्षा के दौरान समान दिख सकती हैं, लेकिन एक बार जब आप उन्हें एक साथ जोड़ देते हैं, तो वे बिल्कुल विपरीत व्यवहार करती हैं। इसे दिखाने के लिए, उन्होंने दो काल्पनिक "कॉन्सेप्ट क्लासेस" (जो नियमों के ऐसे सेट हैं जिन्हें मशीन सीखने की कोशिश करती है) बनाए। आइए उन्हें "कांस्टेंट क्लास" (Constant Class) और "आइडेंटिटी क्लास" (Identity Class) कहें।

पहला वर्ग, "कांस्टेंट क्लास", एक टूटी हुई घड़ी की तरह है जो हमेशा एक ही समय बताती है, चाहे कुछ भी हो। मशीन को बस उस स्थिर समय का अनुमान लगाना होता है। दूसरा वर्ग, "आइडेंटिटी क्लास", एक दर्पण की तरह है; आप इसे जो भी इनपुट देते हैं, यह उसे वापस कॉपी कर देता है। जब मशीन इनमें से किसी एक नियम को सीखने की कोशिश करती है, तो दोनों समान रूप से आसान होती हैं। दोनों एक ऐसे लर्निंग कर्व का पालन करती हैं जहाँ गलतियाँ $n^{-1/2}$ की दर से कम होती हैं (जिसका अर्थ है कि यदि आप अपने अभ्यास डेटा को दोगुना करते हैं, तो आप थोड़े बेहतर होते हैं, लेकिन दोगुना बेहतर नहीं)। यह एक मानक, अनुमानित गति है।

हालाँकि, कहानी में मोड़ तब आता है जब लेखक इन नियमों को एक साथ जोड़ते हैं। उन्होंने एक "डायरेक्ट सम" बनाया है जिसमें कांस्टेंट क्लास की 100 कॉपियाँ और आइडेंटिटी क्लास की 100 कॉपियाँ ली गईं और मशीन को उन्हें एक साथ सीखने के लिए कहा गया। यहाँ जादू होता है: कांस्टेंट का समूह आसान बना रहा, उसी स्थिर सीखने की गति को बनाए रखते हुए। लेकिन आइडेंटिटी का समूह एक दुःस्वप्न बन गया। जैसे-जैसे कॉपियों की संख्या ( $r$ ) बढ़ती गई, आइडेंटिटी के समूह के लिए लर्निंग कर्व नाटकीय रूप से धीमा हो गया, जो कांस्टेंट के समूह की तुलना में सीखना बहुत कठिन हो गया।

यह शोध पत्र गणितीय रूप से सिद्ध करता है कि आइडेंटिटी समूह के लिए, सीखने की दर कॉपियों की संख्या पर बहुत अधिक निर्भर करती है, जबकि कांस्टेंट समूह के मामले में ऐसा नहीं है। विशेष रूप से, जब कॉपियों की संख्या ( $r$ ) बड़ी होती है, तो आइडेंटिटी समूह के लिए त्रुटि दर (error rate) काफी ऊँची बनी रहती है, जो कांस्टेंट समूह की तरह तेजी से कम होने से इनकार कर देती है। वास्तव में, यदि आपके पास पर्याप्त कॉपियाँ हैं, तो मशीन चाहे कितना भी डेटा दे दे, वह एक उच्च त्रुटि दर पर अटकी रह सकती है, जबकि कांस्टेंट समूह में सुधार होता रहता है।

लेखकों ने एक अटूट प्रमाण बनाने के लिए "असू का लेम्मा" (Assouad's lemma) नामक एक प्रसिद्ध लेम्मा और "ले कैम की टू-पॉइंट इनइक्वालिटी" (Le Cam's two-point inequality) जैसी तकनीक सहित कठोर गणितीय उपकरणों का उपयोग किया। उन्होंने इसे केवल कंप्यूटर पर सिम्युलेट नहीं किया; उन्होंने दिखाया कि यह पृथक्करण (separation) लर्निंग थ्योरी का एक मौलिक नियम है। उन्होंने प्रदर्शित किया कि आप केवल यह देखकर यह मान नहीं सकते कि एक मशीन एक चीज़ को कितनी तेज़ी से सीखती है और फिर यह मान सकते हैं कि वह उन चीज़ों के सौ को कितनी तेज़ी से सीखेगी। नियमों की संरचना उतनी ही महत्वपूर्ण है जितनी कि नियमों की संख्या।

अंत में, यह शोध पत्र एक सरल धारणा को गलत साबित करता है। यह हमें बताता है कि मशीन लर्निंग की दुनिया में, संदर्भ (context) ही सर्वोपरि है। दो समस्याएँ जो अलगाव में एक जैसी दिखती हैं, मिश्रण होने पर तेल और पानी की तरह व्यवहार कर सकती हैं। एक एकल कार्य को सीखने की गति, एक जटिल प्रणाली को सीखने की गति के लिए भविष्य बताने वाला कोई जरिया नहीं है। लेखकों ने दिखाया है कि सिंगल-इंस्टेंस लर्निंग और डायरेक्ट-सम लर्निंग के बीच का संबंध पहले की तुलना में कहीं अधिक रहस्यमय और जटिल है, जो यह सिद्ध करता है कि सीखने के इस महान खेल में, संपूर्ण हिस्सा निश्चित रूप से उसके भागों का योग नहीं है।

तकनीकी सारांश: एगोस्टिक डायरेक्ट सम्स के लिए एक रेट सेपरेशन (Rate Separation)

समस्या विवरण
यह शोध पत्र एगोस्टिक PAC लर्निंग के संबंध में एक मौलिक प्रश्न को संबोधित करता है जो कॉन्सेप्ट क्लासेस के डायरेक्ट सम (direct sum) के व्यवहार से संबंधित है। विशेष रूप से, यह जांच करता है कि क्या $r$ -फोल्ड डायरेक्ट सम, जिसे $C^r$ द्वारा दर्शाया गया है, का एगोस्टिक लर्निंग कर्व केवल सिंगल-इंस्टेंस लर्निंग कर्व $\varepsilon_{\text{agn}}(n \mid C)$ और कारकों की संख्या $r$ द्वारा निर्धारित होता है। यह प्रश्न हनेके, मोरन और वकनीन [HMW24] द्वारा उठाया गया था। मुख्य जांच यह है कि क्या एकल उदाहरण के लिए लर्निंग रेट का क्रम (order), और कॉपियों की संख्या, अनियंत्रित, डिस्ट्रीब्यूशन-फ्री सेटिंग के तहत प्रोडक्ट क्लास के लर्निंग रेट की भविष्यवाणी करने के लिए पर्याप्त है।

कार्यप्रणाली और सेटअप
लेखक मानक एगोस्टिक PAC लर्निंग फ्रेमवर्क का उपयोग करते हैं जहाँ लक्ष्य कॉन्सेप्ट क्लास $C$ के सर्वोत्तम सदस्य के सापेक्ष अतिरिक्त जोखिम (excess risk) को कम करना है।

डायरेक्ट सम परिभाषा: क्लासेस $C_1 \subseteq Y^{X_1}$ और $C_2 \subseteq Y^{X_2}$ के लिए, डायरेक्ट सम $C_1 \otimes C_2$ उन फलनों (functions) का समूह है जो $(c_1 \otimes c_2)(x_1, x_2) = (c_1(x_1), c_2(x_2))$ को परिभाषित करते हैं। $r$ -फोल्ड डायरेक्ट सम $C^r = \bigotimes_{i=1}^r C$ है।
लॉस फंक्शन (Loss Function): लॉस को पूर्ण आउटपुट वेक्टर पर ज़ीरो-वन लॉस (zero-one loss) के रूप में परिभाषित किया गया है, न कि कोऑर्डिनेट-वाइज हैमिंग लॉस के रूप में।
लर्निंग कर्व: एगोस्टिक लर्निंग कर्व को $\varepsilon_{\text{agn}}(n \mid C) = \inf_A \sup_D (L_{D,n}(A) - L_D(C))$ के रूप में परिभाषित किया गया है, जहाँ इन्फिमम (infimum) सभी लर्निंग रूल्स $A$ पर है और सुप्रीमकम (supremum) सभी डिस्ट्रीब्यूशन्स $D$ पर है।

इस समस्या को हल करने के लिए, लेखक डोमेन और लेबल स्पेस $X = Y = \{0, 1\}$ पर दो विशिष्ट कॉन्सेप्ट क्लासेस $F$ और $G$ का निर्माण करते हैं:

क्लास $F$ : इसमें दो कॉन्स्टेंट बाइनरी फंक्शन्स ( $f_0(x)=0, f_1(x)=1$ ) शामिल हैं।
क्लास $G$ : इसमें ज़ीरो फंक्शन और आइडेंटिटी फंक्शन ( $g_0(x)=0, g_1(x)=x$ ) शामिल हैं।

लेखक सिद्ध करते हैं कि जबकि दोनों क्लासेस का समान सिंगल-इंस्टेंस लर्निंग रेट है, उनके $r$ -फोल्ड डायरेक्ट सम मौलिक रूप से भिन्न लर्निंग रेट प्रदर्शित करते हैं।

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

सिंगल-इंस्टेंस समानता:
शोध पत्र स्थापित करता है कि $F$ और $G$ दोनों का एगोस्टिक लर्निंग कर्व $n^{-1/2}$ के क्रम का है।
- $F$ के लिए, यह परिणाम कॉन्स्टेंट फंक्शन्स और एम्पिरिकल रिस्क मिनिमाइजेशन के मानक विश्लेषण से प्राप्त होता है।
- $G$ के लिए, यह परिणाम मुख्य प्रमेय (Theorem 1) में $r=1$ लेकर प्राप्त किया गया है, जो $\varepsilon_{\text{agn}}(n \mid G) \asymp n^{-1/2}$ देता है।
डायरेक्ट सम में रेट सेपरेशन (मुख्य प्रमेय):
केंद्रीय योगदान थ्योरम 1 है, जो $F^r$ और $G^r$ के बीच "रेट सेपरेशन" को प्रदर्शित करता है:
- $F^r$ के लिए (कॉन्स्टेंट क्लास): लर्निंग रेट $r$ के बावजूद $\Theta(n^{-1/2})$ बना रहता है। प्रमाण यह दर्शाता है कि अतिरिक्त जोखिम सबसे संभावित कॉन्स्टेंट वेक्टर के एस्टिमेशन एरर द्वारा नियंत्रित होता है, जो $1/\sqrt{n}$ के रूप में स्केल करता है।
- $G^r$ के लिए (ज़ीरो/आइडेंटिटी क्लास): लर्निंग रेट $\Theta(\min\{1, \sqrt{r/n}\})$ $Θ (min {1, r / n})$ के रूप में स्केल करता है।
  - जब $r \le n$ हो, तो दर $\Theta(\sqrt{r/n})$ होती है।
  - जब $r > n$ हो, तो मिनिमैक्स एक्स्ट्रा रिस्क एक धनात्मक स्थिरांक (positive constant) से बंधा होता है (अर्थात, सीमा में सीखना असंभव है)।
परिणामस्वरूप, जबकि $\varepsilon_{\text{agn}}(n \mid F) \asymp \varepsilon_{\text{agn}}(n \mid G)$ , जैसे-जैसे $r$ बढ़ता है, $\varepsilon_{\text{agn}}(n \mid F^r)$ और $\varepsilon_{\text{agn}}(n \mid G^r)$ के एगोस्टिक लर्निंग कर्व के एसिम्प्टोटिक ऑर्डर्स अलग हो जाते हैं।
प्रूफ तकनीकें:
- अपर बाउंड्स (Upper Bounds): इन्हें परिमित क्लासेस (finite classes) के लिए मानक एम्पिरिकल रिस्क मिनिमाइजेशन बाउंड्स का उपयोग करके निकाला गया है। $G^r$ के लिए, बाउंड $|G^r| = 2^r$ के तथ्य का उपयोग करती है, जिससे $\sqrt{\frac{r \log 2}{n}}$ के समान एक पद प्राप्त होता है।
- लोअर बाउंड्स (Lower Bounds): इन्हें सूचनात्मक-सैद्धांतिक (information-theoretic) उपकरणों का उपयोग करके स्थापित किया गया है।
  - $F^r$ के लिए, दो-बिंदु ले कैम मेथड (two-point Le Cam method) का उपयोग यह दिखाने के लिए किया जाता है कि दो प्रमुख कॉन्स्टेंट लेबल्स के बीच अंतर करना कठिन है।
  - $G^r$ के लिए, लेखक असौड के लेम्मा (Assouad's Lemma) को पिंस्कर की असमानता (Pinsker's inequality) के साथ नियोजित करते हैं। वे $\theta \in \{-1, +1\}^r$ द्वारा पैरामीटराइज्ड डिस्ट्रीब्यूशन का एक परिवार बनाते हैं। इस निर्माण में, एक इनपुट कोऑर्डिनेट $J$ को $\{1, \dots, r\}$ में से समान रूप से चुना जाता है, जहाँ $X = e_J$ है। $J=j$ होने की स्थिति में, लेबल $Y$ प्रायिकता $1/2 + \theta_j \alpha$ के साथ $e_j$ होता है और $1/2 - \theta_j \alpha$ की प्रायिकता के साथ $0^r$ होता है। प्रमाण $\theta$ के अनुमान के लिए हैमिंग डिस्टेंस को एक्स्ट्रा रिस्क से जोड़ता है, यह दिखाते हुए कि $r$ -डायमेंशनल पैरामीटर वेक्टर का अनुमान लगाने के लिए $r$ के समान अनुपात में सैंपल साइज की आवश्यकता होती है।

महत्व और दावे
यह शोध पत्र [HMW24] द्वारा पूछे गए प्रश्न के नकारात्मक उत्तर को प्रदान करता है। यह दावा करता है कि सिंगल-इंस्टेंट लर्निंग रेट और कारक $r$ की संख्या, $C^r$ के लर्निंग कर्व के एसिम्प्टोटिक ऑर्डर को निर्धारित करने के लिए पर्याप्त नहीं है।

लेखक नोट करते हैं कि जबकि बाद के कार्यों (जैसे [Sur24], [HMS26]) ने विभिन्न जटिलता फ्रेमवर्क या संरचनात्मक डिस्ट्रीब्यूशनल धारणाओं के तहत डायरेक्ट सम का अध्ययन किया है, और हालिया मल्टीक्लास लर्निंग पर कार्य कॉम्बिनेटोरियल बाउंड्स प्रदान करते हैं, इनमें से कोई भी परिणाम अनियंत्रित डिस्ट्रीब्यूशन-फ्री सेटिंग में सिंगल-इंस्टेंस कर्व के फलन के रूप में डायरेक्ट-सम कर्व को व्यक्त नहीं करता है। यह शोध पत्र स्पष्ट रूप से उस अंतराल को हल करता है, एक ऐसा काउंटर-एग्जांपल पेश करके जहाँ क्लास की संरचनात्मक विशेषताएं (कॉन्स्टेंट बनाम आइडेंटिटी) प्रोडक्ट स्पेस में भिन्न व्यवहार की ओर ले जाती हैं, बावजूद इसके कि उनका सिंगल-इंस्टेंस प्रदर्शन समान है।

निष्कर्ष इस बात पर जोर देता है कि किसी भी मनमाने कॉन्सेप्ट क्लास के लिए, $\varepsilon_{\text{agn}}(n \mid C)$ और $r$ का ज्ञान $\varepsilon_{\text{agn}}(n \mid C^r)$ की भविष्यवाणी करने की अनुमति नहीं देता है। विशेष रूप से, $G^r$ के लिए, जोखिम $r \ge n$ होने पर शून्य से दूर रह सकता है, जबकि $F^r$ के लिए, यह $n^{-1/2}$ के रूप में घटता रहता है।

तकनीकी सारांश: एगोस्टिक डायरेक्ट सम्स के लिए एक रेट सेपरेशन (Rate Separation)

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