Local Regularization Does Not Characterize Multiclass PAC Learnability

तकनीकी सारांश: स्थानीय नियमितीकरण (Local Regularization) बहु-वर्ग PAC शिक्षणीयता (Multiclass PAC Learnability) को अभिलक्षित नहीं करता है

समस्या विवरण
सांख्यिकीय शिक्षण सिद्धांत (statistical learning theory) में एक केंद्रीय प्रश्न परिकल्पना वर्गों (hypothesis classes) की शिक्षणीयता को अभिलक्षित करने वाले सरल एल्गोरिद्मिक सिद्धांतों की पहचान करना है। बाइनरी वर्गीकरण (binary classification) में, एम्पिरिकल रिस्क मिनिमाइजेशन (ERM) PAC शिक्षणीयता को अभिलक्षित करता है। हालाँकि, बहु-वर्ग (multiclass) सेटिंग अधिक जटिल है; उचित शिक्षार्थी (proper learners) शिक्षणीय वर्गों के लिए भी विफल हो सकते हैं, और इष्टतम शिक्षार्थी अक्सर निश्चित परिकल्पना क्रमों (fixed hypothesis orderings) के बजाय नमूना-निर्भर संरचनाओं पर निर्भर करते हैं।

Asilis et al. ने बहु-वर्ग सेटिंग के लिए ERM के एक संभावित सामान्यीकरण के रूप में स्थानीय नियमितीकरण (local regularization) का प्रस्ताव दिया। एक स्थानीय रेगुलराइज़र प्रत्येक परीक्षण बिंदु $x$ पर प्रत्येक परिकल्पना $h$ के लिए एक निश्चित स्कोर $\psi(h, x)$ निर्दिष्ट करता है, जो प्रशिक्षण नमूने से स्वतंत्र होता है। ऐसे रेगुलराइज़र द्वारा प्रेरित शिक्षार्थी देखे गए नमूने के साथ सुसंगत (consistent) होने वाली परिकल्पनाओं में से न्यूनतम स्कोर वाली परिकल्पना के लेबल की भविष्यवाणी करता है। जबकि Jafar, Asilis, और Dughmi ने पहले ही ट्रांसडक्टिव (transductive) मॉडल (जहाँ एक विशिष्ट रोके गए बिंदु का परीक्षण किया जाता है) में स्थानीय नियमितीकरण की विफलता को प्रदर्शित किया था, यह एक खुला प्रश्न बना हुआ था कि क्या यह सिद्धांत PAC शिक्षणीयता को अभिलक्षित करता है, जहाँ रोका गया बिंदु नगण्य जनसंख्या द्रव्यमान (population mass) रख सकता है और बार-बार नमूना लेने से सैद्धांतिक रूप से वह प्रकट हो सकता है।

कार्यप्रणाली और निर्माण
यह शोध पत्र टूर्नामेंट्स (पूर्ण निर्देशित ग्राफ/complete directed graphs) पर आधारित एक गणनीय परिकल्पना वर्ग (countable hypothesis class) का उपयोग करके एक प्रति-उदाहरण (counterexample) का निर्माण करता है।

• परिकल्पना वर्ग ($H$): एक पूर्णांक $q \ge 3$ के लिए, परिकल्पनाएँ एक टूर्नामेंट इंस्टेंस $\tau$ के भीतर किनारे (edge) $e$ के किनारों (edges) के अनुरूप होती हैं। एक परिकल्पना $h_{q,e}$ किनारे $e$ के "हेड" (लक्ष्य शीर्ष/target vertex) की भविष्यवाणी करती है।
• इंस्टेंस स्पेस (Instance Space): इंस्टेंसस $(q, \tau)$ हैं, जहाँ $\tau$, $q$ शीर्षों वाला एक टूर्नामेंट है।
• कठिन वितरण (Hard Distributions): लेखक एक लक्ष्य किनारे $e=\{u,v\}$ और एंडपॉइंट $v$ के लिए "कठिन" वितरणों $D_{e,v}$ को परिभाषित करते हैं। ये वितरण उन टूर्नामेंट्स पर समान रूप से वितरित होते जहाँ किनारे $e$ को $v$ की ओर उन्मुख (oriented) किया गया है। फलस्वरूप, प्रशिक्षण नमूने में देखे गए सभी लेबल समान होते हैं: $(q, v)$।
• विफलता का तंत्र:
  1. फिल्टरिंग (Filtering): प्रशिक्षण नमूना (सभी लेबल $v$ के साथ) वर्ज़न स्पेस (version space) को फ़िल्टर करता है, केवल उन किनारों से संबंधित परिकल्पनाओं को बनाए रखता है जो $v$ से जुड़े हैं और नमूने गए टूर्नामेंट्स में $v$ की ओर उन्मुख हैं।
  2. निश्चित रैंकिंग (Fixed Ranking): स्थानीय रेगुलराइज़र $\psi$, नमूना देखे जाने से पहले परीक्षण बिंदु पर किनारों पर एक सख्त कुल क्रम (strict total ordering) लागू करता है।
  3. चक्रीय व्युत्क्रमण (Cyclic Inversions): मुख्य कठिनाई टूर्नामेंट में चक्रीय त्रिकोणों (cyclic triangles) से उत्पन्न होती है। भले ही प्रशिक्षण नमूना कई प्रतिस्पर्धियों को हटा देता है, फिर भी रेगुलराइज़र के निश्चित क्रम को वास्तविक लक्ष्य के सापेक्ष "उलट" (invert) किया जा सकता है। विशेष रूप से, यदि एक बहिर्मुखी किनारा (जो लक्ष्य नहीं होना चाहिए) फ़िल्टरिंग प्रक्रिया में जीवित रहता है और वास्तविक अंतर्वाह लक्ष्य किनारे (incoming target edge) की तुलना में रेगुलराइज़र की निश्चित रैंकिंग में पहले आता है, तो शिक्षार्थी त्रुटि करता है।

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

1. एक प्रति-उदाहरण का अस्तित्व: यह शोध पत्र एक गणनीय बहु-वर्ग परिकल्पना वर्ग $H$ के अस्तित्व को सिद्ध करता है जो PAC शिक्षणीय है लेकिन किसी भी स्थानीय रेगुलराइज़र द्वारा शिक्षणीय नहीं है।

   • शिक्षणीयता (Learnability): वर्ग $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$ के नमूना जटिलता (sample complexity) के साथ PAC शिक्षणीय है। एक स्पष्ट शिक्षक तब तक सफल होता है जब तक कि नमूने में दोनों एंडपॉइंट लेबल दिखाई नहीं देते।
   • डायमेंशन बाउंड (Dimension Bound): इस वर्ग का डेनिएली-शालेव-शर्वेट्ज़ (DS) डायमेंशन अधिकतम 2 है। यह स्थापित किया गया है कि प्रत्येक परिकल्पना का इमेज अधिकतम दो लेबल रखता है, जो 3-आयामी स्यूडो-क्यूब (pseudo-cube) के निर्माण को रोकता है।

2. असंभवता प्रमेय (Impossibility Theorem): किसी भी स्थानीय रेगुलराइज़र $\psi$ के लिए, एक प्रेरित शिक्षार्थी $A_\psi$ मौजूद है जो $H$ को PAC रूप से सीखने में विफल रहता है।

   • विफलता मोड (Failure Mode): किसी भी निश्चित रेगुलराइज़र के लिए, लेखक दिखाते हैं कि बड़े नमूना आकार $n$ के लिए भी, ऐसे 'रियलाइज़ेबल' वितरण मौजूद हैं जहाँ त्रुटि की संभावना एक स्थिरांक $\delta_0 = \frac{1}{192e}$ से अधिक हो जाती है।
   • मात्रात्मक सीमाएँ (Quantitative Bounds): त्रुटि की संभावना शून्य से दूर ($\varepsilon_0 = \frac{1}{96e}$) बनी रहती है क्योंकि टूर्नामेंट संरचना में "इनवर्जन" (बहिर्मुखी किनारों का अंतर्वाह किनारों से पहले रैंक होना) की अपेक्षित संख्या महत्वपूर्ण बनी रहती है। प्रमाण इस तथ्य का लाभ उठाता है कि एक यादृच्छिक टूर्नामेंट में $\Theta(q^3)$ चक्रीय त्रिकोण होते हैं, जिससे यह सुनिश्चित होता है कि किनारों के किसी भी सख्त क्रम के लिए, लक्ष्य घटनाओं का एक स्थिर अंश भविष्यवाणी त्रुटि का परिणाम होगा।

महत्व और दावे

यह शोध पत्र निष्कर्ष निकालता है कि स्थानीय नियमितीकरण बहु-वर्ग PAC शिक्षणीयता को अभिलक्षित नहीं करता है।

• ट्रांसडक्टिव परिणामों से अंतर: Jafar et al. के ट्रांसडक्टिव लोअर बाउंड के विपरीत, जो संभावित रूप से नगण्य द्रव्यमान वाले एकल रोके गए बिंदु पर निर्भर करता है, यह निर्माण त्रुटि को जनसंख्या में वितरित करता है। विफलता निरंतर बढ़ती नमूना आकारों के साथ भी बनी रहती है, जिससे शिक्षार्थी बार-बार नमूना लेने के माध्यम से छिपी हुई संरचना को "सीखने" में असमर्थ रहता है।
• निश्चित स्कोर की सीमा: परिणाम स्थानीय नियमितीकरण में एक मौलिक कठोरता को उजागर करता है: क्योंकि परीक्षण बिंदु पर परिकल्पनाओं की रैंकिंग नमूने को देखे बिना पहले से निश्चित होती है, शिक्षार्थी विशिष्ट प्रशिक्षण डेटा के आधार पर जीवित प्रतिस्पर्धियों के सापेक्ष क्रम को अनुकूलित नहीं कर सकता है। टूर्नामेंट सेटिंग में, पुनर्व्यवस्थित करने में यह अक्षमता निरंतर जनसंख्या त्रुटि की ओर ले जाती है, भले ही वर्ग का कम DS-डायमेंशन ($\le 2$) हो और अन्य तरीकों से कुशलतापूर्वक शिक्षणीय हो।
• क्षेत्र (Scope): यह परिणाम विशेष रूप से उन रेगुलराइज़र्स के लिए लागू होता है जहाँ स्कोर नमूने से स्वतंत्र रूप से निश्चित होते हैं। यह उन अनसुपरवाइज्ड फ्रेमवर्क को संबोधित नहीं करता है जहाँ रेगुलराइजेशन नियम अनलेबल नमूने पर निर्भर हो सकता है।

संक्षेप में, यह शोध पत्र स्थानीय नियमितीकरण के संबंध में एक निर्णायक नकारात्मक उत्तर प्रदान करता है कि क्या यह बहु-वर्ग PAC शिक्षणीयता को अभिलक्षित करता है, यह प्रदर्शित करते हुए कि कम कॉम्बिनेटोरियल डायमेंशन (DS-dim $\le 2$) और इष्टतम नमूना जटिलता वाले वर्गों के लिए भी, निश्चित-स्कोर रेगुलराइज़र सीखने में विफल हो सकते हैं।