Strategic PAC Learnability via Geometric Definability

तकनीकी सारांश: ज्यामितीय परिभाषितता (Geometric Definability) के माध्यम से रणनीतिक PAC शिक्षणीयता

समस्या विवरण
रणनीतिक वर्गीकरण (Strategic classification) उन शिक्षण परिदृश्यों को संबोधित करता है जहाँ व्यक्ति किसी क्लासिफायर के निर्णय को प्रभावित करने के लिए एक लागत (cost) पर अपने लक्षणों (features) को संशोधित करते हैं। इस क्षेत्र में एक मौलिक प्रश्न यह है कि क्या मूल परिकल्पना वर्ग (hypothesis class) $\mathcal{H}$ की शिक्षणीयता (learnability) तब सुरक्षित रहती है जब व्यक्ति रणनीतिक रूप से कार्य करते हैं। विशेष रूप से, क्या प्रेरित रणनीतिक परिकल्पना वर्ग $\mathcal{H}^N$ (जहाँ $N$ लागत-प्रेरित पड़ोस संबंध है) PAC-शिक्षणीय रहता है, और इसकी नमूना जटिलता (sample complexity) $\mathcal{H}$ की जटिलता और लागत संरचना से कैसे संबंधित है?

पूर्व के कार्यों ने विशिष्ट सेटिंग्स के लिए सकारात्मक परिणाम स्थापित किए हैं, जैसे कि नॉर्म लागत (norm costs) के साथ रैखिक क्लासिफायर या इनपुट स्केलिंग के तहत बंद वर्ग। हालाँकि, 'संयोजन संबंधी सरलता' (combinatorial simplicity - जैसे कम VC dimension) और 'रणनीतिक शिक्षणीयता' के बीच सामान्य संबंध अनसुलझा रहा। यह शोध पत्र इस बात की जांच करता है कि क्या "सरल" लागत संरचनाएं और परिकल्पना वर्ग यह गारंटी देने के लिए पर्याप्त हैं कि रणनीतिक व्यवहार सीखने की समस्या को अगम्य (intractable) नहीं बनाएगा।

कार्यप्रणाली और ढांचा
लेखक एक दोहरी पद्धति का उपयोग करते हैं: सामान्य संयोजन संबंधी सेटिंग्स में शिक्षणीयता की विफलता को प्रदर्शित करना और मॉडल थ्योरी (model theory) में निहित ज्यामितीय परिभाषितता धारणाओं के माध्यम से इसे पुनः स्थापित करना।

1. नकारात्मक परिणाम (संयोजन संबंधी सरलता अपर्याप्त है):
   लेखक एक प्रति-उदाहरण (counterexample) निर्मित करते हैं जो यह दर्शाता है कि रणनीतिक व्यवहार शिक्षणीयता को नष्ट कर सकता है, यहाँ तक कि सबसे सरल सेटिंग्स में भी। वे वास्तविक रेखा $\mathbb{R}$ पर एक परिकल्पना वर्ग $\mathcal{H}$ को एक समान अंतराल पड़ोस प्रणाली (uniform interval neighborhood system - जहाँ बिंदु एक निश्चित त्रिज्या $r$ के भीतर घूम सकते हैं) के साथ परिभाषित करते हैं। वर्ग और लागत संरचना दोनों की न्यूनतम जटिलता के बावजूद, यह दिखाया गया है कि प्रेरित रणनीतिक वर्ग $\mathcal{H}^N$ का अनंत VC dimension है, जो इसे गैर-PAC-शिक्षणीय बनाता है। यह निर्माण विजातीय सूचकांकों (disjoint indices) के मनमाने उपसमुच्चयों को अलग-अलग अंतरालों में एनकोड करने पर निर्भर करता है, जिससे रणनीतिक रूपांतरण मनमाने बड़े परिमित सेटों को भी 'शैटर' (shatter) कर सकता है।

2. सकारात्मक परिणाम (ज्यामितीय परिभाषितता):
   इस नकारात्मक परिणाम से निपटने के लिए, लेखक एक संरचनात्मक धारणा पेश करते हैं: ज्यामितीय परिभाषितता (Geometric Definability)। वे $\mathbb{R}_{\exp}$ (एक्सपोनेंशियल फंक्शन के साथ विस्तारित वास्तविक क्षेत्र) पर प्रथम-क्रम सूत्रों (first-order formulas) का उपयोग करके परिकल्पना वर्ग और पड़ोस संबंध दोनों को मॉडल करते हैं।

• $\mathbb{R}_{\exp}$-परिभाषितता: परिकल्पनाएँ और पड़ोस अंकगणितीय संचालन ($+, \cdot$), तुलना ($<, =$), और एक्सपोनेंशियल फंक्शन ($\exp$) वाले सूत्रों द्वारा परिभाषित हैं, जिसमें लॉगरिदम (exp के माध्यम से) भी शामिल हैं। यह रैखिक क्लासिफायर, बहुपद थ्रेशोल्ड फंक्शन, मानक सक्रियण (standard activations) वाले न्यूरल नेटवर्क, और $\ell_p$ नॉर्म, वासेस्टीन दूरी (Wasserstein distance), और KL डाइवर्जेंस पर आधारित लागत कार्यों सहित कई प्राकृतिक वर्गों को समाहित करता है।
• रणनीतिक रूपांतरण के रूप में अस्तित्वगत परिमाणीकरण (Existential Quantification): प्रेरित रणनीतिक परिकल्पना $h^N(x) = 1$ यदि और केवल यदि $\exists x' \in N_x$ ऐसा है कि $h(x') = 1$। यह परिभाषित सूत्र में एक अस्तित्वगत परिमाणीकरण (existential quantifier) पेश करता है।
• मॉडल-थ्योरेटिक उपकरण: विश्लेषण इस तथ्य का लाभ उठाता है कि $\mathbb{R}_{\exp}$ एक o-minimal संरचना है (विल्की का प्रमेय)। o-minimal संरचनाओं में, परिभाषित सेटों में परिमित सेल अपघटन (finite cell decompositions) होता है और उनके पास बहुपद रूप से सीमित विकास फलन (polynomially bounded growth functions) होते हैं। लेखक टौम टोपोलॉजी (tame topology) और प्रभावी सेल अपघटन (विशेष रूप से प्रतिबंधित पफ़ाफियन सेटों के लिए) के परिणामों का उपयोग $\mathcal{H}^N$ के विकास फलन को सीमित करने के लिए करते हैं।

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

1. रणनीतिक गैर-शिक्षणीयता:
   यह पेपर सिद्ध करता है कि रणनीतिक व्यवहार एक शिक्षणीय समस्या (VC dimension 1) को एक गैर-शिक्षणीय समस्या (अनंत VC dimension) में बदल सकता है, यहाँ तक कि सरल अंतराल पड़ोस के तहत भी। यह दर्शाता है कि केवल संयोजन संबंधी सरलता रणनीतिक शिक्षणीयता की गारंटी देने के लिए अपर्याप्त है।

2. $\mathbb{R}_{\exp}$ के माध्यम से गुणात्मक शिक्षणीयता:
   मुख्य प्रमेय 2 स्थापित करता है कि यदि परिकल्पना वर्ग $\mathcal{H}$ और पड़ोस प्रणाली $N$ दोनों $\mathbb{R}_{\exp}$ में परिभाषित हैं, तो प्रेरित रणनीतिक वर्ग $\mathcal{H}^N$ PAC-शिक्षणीय है। नमूना जटिलता को परिभाषित सूत्रों में उपयोग किए गए मापदंडों (parameters) की संख्या $k$ द्वारा नियंत्रित किया जाता है। विशेष रूप से, विकास फलन $\Pi_{\mathcal{H}^N}(m)$ को $C m^k$ द्वारा सीमित किया गया है, जो परिमित VC dimension को दर्शाता है। यह परिणाम $\mathbb{R}_{\exp}$ की o-minimality और परिभाषित परिवारों के लिए बहुपद विकास प्रमेय पर निर्भर करता है।

3. मात्रात्मक सीमाएँ (अर्ध-बीजगणितीय मामला):
   मुख्य प्रमेय 3 उस मामले के लिए स्पष्ट, रचनात्मक सीमाएँ प्रदान करता है जहाँ परिभाषाएँ वास्तविक क्षेत्र $\mathbb{R}$ की भाषा (बहुपद वाले क्वांटिफायर-मुक्त सूत्र, यानी अर्ध-बीजगणितीय सेट) तक सीमित हैं। मात्रात्मक परिमाणीकरण उन्मूलन (Tarski-Seidenberg) को लागू करके, लेखक वर्णन जटिलता $D$ (बहुपदों की संख्या और उनकी डिग्री) के संदर्भ में VC dimension और नमूना जटिलता पर स्पष्ट सीमाएँ प्राप्त करते हैं।

• परिणाम: $VC(\mathcal{H}^N) = O(k^2 l \log D)$ और नमूना जटिलता भी इसी तरह स्केल करती है।

4. मात्रात्मक सीमाएँ (अस्तित्वगत $\mathbb{R}_{\exp}$ मामला):
   मुख्य प्रमेय 4 पूर्ण $\mathbb{R}_{\exp}$ सेटिंग के लिए मात्रात्मक विश्लेषण का विस्तार करता है, जो अस्तित्वगत सूत्रों ($\Sigma_1$) तक सीमित है। इसमें $\ell_p$ बॉल्स और अर्थ मूवर डिस्टेंस (Earth Mover Distance) जैसे कई प्राकृतिक रणनीतिक परिवेश शामिल हैं, जहाँ पड़ोस संबंध एक अस्तित्वगत परिमाणीकरण द्वारा परिभाषित होता है।

• लेखक इन सूत्रों के लिए "फॉर्मेट" ($F$) और "डिग्री" ($D$) को परिभाषित करते हैं।
• परिणाम: $VC(\mathcal{H}^N) = O_F(\log D)$ और नमूना जटिलता $O\left(\frac{k \log(1/\varepsilon) + \gamma(F) \log D + \log(1/\delta)}{\varepsilon}\right)$ है, जहाँ $\gamma$ एक स्पष्ट रूप से गणना योग्य फलन है।
• प्रमाण प्रतिबंधित पफ़ाफियन संरचनाओं के लिए प्रभावी सेल अपघटन प्रमेयों का उपयोग करके एक्सपोनेंशियल फंक्शन को संभालता है।

महत्व और दावे
यह पेपर यह दावा करता है कि उसने संयोजन संबंधी सरलता और रणनीतिक शिक्षणीयता के बीच के तनाव को ज्यामितीय तामeness (geometric tameness) को महत्वपूर्ण कारक के रूप में पहचानकर हल कर दिया है।

• संयोजन संबंधी मापों की सीमा: यह कार्य प्रदर्शित करता है कि आधार वर्ग का कम VC dimension रणनीतिक हेरफेर के तहत शिक्षणीयता को सुनिश्चित नहीं करता है; लागत फलन और परिकल्पना वर्ग की संरचना मौलिक रूप से मायने रखती है।
• परिभाषितता के माध्यम से बहाली: "तमीम" (tame) ज्यामितीय वर्गों (जो $\mathbb{R}_{\exp}$ में परिभाषित हैं) पर ध्यान केंद्रित करके, यह पेपर दिखाता है कि रणनीतिक शिक्षणीयता बहाल हो जाती है। रणनीतिक वर्ग की जटिलता को परिभाषित करने वाले सूत्रों की तार्किक जटिलता (मापदंडों की संख्या, फॉर्मेट और डिग्री) द्वारा नियंत्रित किया जाता है, न कि प्रेरित वर्ग की कच्ची संयोजन संबंधी जटिलता द्वारा।
• क्षेत्र (Scope): यह ढांचा कई व्यावहारिक सेटिंग्स को समाहित करता है, जिनमें बहुपद क्लासिफायर, निर्णय वृक्ष (decision trees), सामान्य सक्रियण वाले न्यूरल नेटवर्क और विभिन्न दूरी मेट्रिक्स ($\ell_p$, KL, Wasserstein) शामिल हैं।
• सीमाएँ: लेखक नोट करते हैं कि उनके सकारात्मक परिणाम संरचनाओं की "तामeness" पर निर्भर करते हैं। ऐसे पड़ोस जिनमें अनबाउंडेड ऑसिलेटरी या आवधिक संरचनाएं (जैसे $\sin$ द्वारा परिभाषित) होती हैं, $\mathbb{R}_{\exp}$ ढांचे के बाहर आती हैं और गैर-शिक्षणीयता की ओर ले जा सकती हैं। इसके अलावा, $\mathbb{R}_{\exp}$ के लिए मात्रात्मक सीमाएँ वर्तमान में केवल अस्तित्वगत सूत्रों तक सीमित हैं; सार्वभौमिक परिमाणीकरण (universal quantifiers) को केवल गुणात्मक रूप से संभाला गया है।

संक्षेप में, यह शोध पत्र स्थापित करता है कि जबकि रणनीतिक व्यवहार सामान्य रूप से सीखने की जटिलता को विनाशकारी रूप से बढ़ा सकता है, यह समस्या $\mathbb{R}_{\exp}$ पर प्रथम-क्रम तर्क के माध्यम से परिभाषित व्यापक और प्राकृतिक ज्यामितीय समस्याओं के लिए टाल दी जाती है। इन समस्याओं की नमूना जटिलता अंतर्निहित ज्यामितीय परिभाषाओं की वर्णनात्मक जटिलता द्वारा शासित होती है।