तकनीकी सारांश: न्यूनतम ओवरपैरामीट्राइजेशन के तहत सर्किट और ट्रांसफॉर्मर के लिए उदाहरणों से प्रमाणन कठिन है

समस्या विवरण

जैसे-जैसे अत्याधुनिक न्यूरल नेटवर्क तर्क और एल्गोरिथम कार्यों पर तैनात किए जा रहे हैं, उनकी सटीक शुद्धता सुनिश्चित करना महत्वपूर्ण होता जा रहा है। उच्च औसत-मामले की सटीकता (average-case accuracy) अक्सर असंगत व्यवहारों को छिपा देती है, जिससे उन विफलताओं का पता लगाना कठिन हो जाता है जो इच्छित तर्क तर्क (reasoning logic) से विचलित होती हैं। यह शोध पत्र सटीक प्रमाणन (exact certification) की समस्या को संबोधित करता है: एक लक्षित परिकल्पना $f^*$ को एक परिकल्पना वर्ग $\mathcal{H}$ के भीतर विशिष्ट रूप से पहचानने के लिए आवश्यक लेबल किए गए इनपुट-आउटपुट उदाहरणों की न्यूनतम संख्या निर्धारित करना, ताकि $\mathcal{H}$ में कोई अन्य परिकल्पना पूरे डोमेन पर $f^*$ के साथ सहमत न हो।

केंद्रीय प्रश्न यह है कि प्रमाणन की यह जटिलता आसपास के परिकल्पना वर्ग के आकार के प्रति कितनी संवेदनशील है। विशेष रूप से, लेखक यह जांचते हैं कि क्या परिकल्पना वर्ग का एक न्यूनतम विस्तार (जैसे, एक एकल गेट या स्थिरांक संख्या में पैरामीटर जोड़ना) प्रमाणन को घातीय रूप से कठिन बना सकता है, यहाँ तक कि उन लक्ष्यों के लिए भी जो पहले प्रमाणित करने में आसान थे।

कार्यप्रणाली

यह शोध पत्र बाइनरी जोड़ (binary addition) कार्यों पर अनुभवजन्य सत्यापन के साथ मिलकर शिक्षण जटिलता (teaching complexity) और सर्किट जटिलता (circuit complexity) पर आधारित एक सैद्धांतिक ढांचे का उपयोग करता है।

सैद्धांतिक ढांचा

1. प्रमाणपत्र आकार परिभाषा (Certificate Size Definition): लेखक प्रमाणपत्र आकार, $\text{cert}(f^*, \mathcal{H})$, को एक लेबल किए गए नमूने $S$ के न्यूनतम आकार के रूप में परिभाषित करते हैं जहाँ वर्ज़न स्पेस $V_S^{\mathcal{H}}$ ( $S$ के साथ सुसंगत परिकल्पनाओं का सेट) में केवल $f^*$ शामिल है।
2. विजातीय-असहमति सिद्धांत (Disjoint-Disagreement Principle): मुख्य प्रमाण रणनीति "धोखेबाज" (deceiver) परिकल्पनाओं के निर्माण पर आधारित है। एक लक्ष्य $f^*$ के लिए, लेखक परिकल्पनाओं के एक परिवार $\{g_\pi\}$ का निर्माण करते हैं जो विशिष्ट, युग्मवार विजातीय "ट्रिगर ब्लॉक्स" $B_\pi$ पर को छोड़कर $f^*$ के साथ हर जगह सहमत होते हैं।
   • यदि एक परिकल्पना वर्ग में ऐसे धोखेबाज परिवारों का समूह है जहाँ असहमति सेट विजातीय हैं, तो किसी भी सटीक प्रमाणन में प्रत्येक असहमति सेट से कम से कम एक उदाहरण शामिल होना चाहिए।
   • फलस्वरूप, प्रमाणन आकार इन विजातीय ब्लॉकों की संख्या द्वारा निम्न-बद्ध (lower-bounded) होता है।
3. ओवरपैरामीट्राइजेशन विश्लेषण (Overparametrization Analysis): लेखक विश्लेषण करते हैं कि कैसे न्यूनतम क्षमता जोड़ना (जैसे, सर्किट में एक अतिरिक्त गेट, ट्रांसफॉर्मर में एक अतिरिक्त अटेंशन हेड और स्थिरांक एम्बेडिंग चौड़ाई) इन घातीय धोखेबाज परिवारों के निर्माण की अनुमति देता है जो मूल, छोटे वर्ग के प्रत्येक लक्ष्य के लिए मौजूद हैं।

अनुभवजन्य विश्लेषण

लेखक बाइनरी जोड़ पहचान पर दो प्रयोगों के माध्यम से सिद्धांत को पूरक बनाते हैं:

1. निर्मित सर्किट (Constructed Circuits): वे जोड़ को पहचानने वाले थ्रेशोल्ड सर्किट ($TC_0$) के लिए सैद्धांतिक धोखेबाज निर्माण को लागू करते हैं। वे $2^n$ गलत सर्किट उत्पन्न करते हैं, जिनमें से प्रत्येक इनपुट के एक अलग ब्लॉक पर लक्ष्य से भिन्न होता है, और मापते हैं कि प्रमाणन उम्मीदवारों के समान वितरण (uniform sampling) से कितने जीवित रहते हैं।
2. प्रशिक्षित ट्रांसफॉर्मर (Trained Transformers): वे 10-बिट जोड़ के लिए एनकोडर-ओनली ट्रांसफॉर्मर को प्रशिक्षित करते हैं। सख्त सत्यापन जांच (99.9% सटीकता) पास करने वाले मॉडलों को चुनने के बाद, वे एक बड़े होल्ड-आउट टेस्ट सेट पर उनका मूल्यांकन करते हैं। वे इन अपूर्ण मॉडलों (धोखेबाजों) के "उत्तरजीविता" (survival) का विश्लेषण करते हैं, जब उन्हें समान रूप से नमूना लिए गए प्रमाणन उम्मीदवारों के अधीन किया जाता है, यह परीक्षण करते हुए कि क्या अवशिष्ट त्रुटियों (residual errors) का पता घातीय संख्या में त्रुटियों के बिना लगाया जा सकता है।

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

1. न्यूनतम ओवरपैरामीट्राइजेशन से घातीय कठोरता

प्राथमिक सैद्धांतिक योगदान यह प्रदर्शित करना है कि प्रमाणन परिकल्पना वर्ग के आकार के प्रति अत्यधिक संवेदनशील है।

• थ्रेशोल्ड सर्किट ($TC_0$): गहराई $d \ge 2$ वाले सर्किट के लिए, एक अतिरिक्त थ्रेशोल्ड गेट जोड़ने से (गेट बजट को $s$ से $s+1$ बढ़ाकर) मूल वर्ग $TC_{d,s}$ के प्रत्येक लक्ष्य के लिए प्रमाणन आकार इनपुट आयाम $n$ में घातीय हो जाता है। विशेष रूप से, $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$।
• ट्रांसफॉर्मर: लॉग-प्रिसिजन ट्रांसफॉर्मर के लिए जिसमें एवरेजिंग हार्ड अटेंशन (AHAT) है, अंतिम परत में एक अटेंशन हेड और छह सहायक एम्बेडिंग/रेसिड्यूअल कोऑर्डिनेट्स जोड़ने से एक विस्तारित वर्ग बन जाता है जहाँ प्रमाणन घातीय रूप से कठिन हो जाता है। भले ही एक लक्ष्य $f^*$ का छोटा आर्किटेक्चर में बहुपद (polynomial) प्रमाण आकार हो, लेकिन थोड़े बड़े आर्किटेक्चर के विरुद्ध प्रमाणित करने के लिए घातीय संख्या में उदाहरणों की आवश्यकता होती है।
• गैर-रिक्तता (Non-Vacuity): लेखक सिद्ध करते हैं कि ये निम्न-सीमाएँ रिक्त नहीं हैं। वे दिखाते हैं कि छोटे वर्ग ($TC_{d,s}$ और मानक ट्रांसफॉर्मर) में ऐसे लक्ष्य शामिल हैं जिनका प्रमाण आकार बहुपद है (विशेष रूप से $O(\log |\mathcal{H}|)$), फिर भी ये समान लक्ष्य घातीय रूप से कठिन हो जाते हैं जैसे ही वर्ग को न्यूनतम रूप से बढ़ाया जाता है।

2. अनुमानित प्रमाणन कठोरता (Approximate Certification Hardness)

यह शोध पत्र अपने परिणामों को अनुमानित प्रमाणन तक विस्तारित करता है:

• पूर्ण त्रुटि सहनशीलता (Absolute Error Tolerance): यदि प्रमाणन केवल एक बहुपद संख्या में गलतियों ($R = \text{poly}(n)$) की अनुमति देता है, तो प्रमाणन आकार घातीय ($2^{\Omega(n)}$) बना रहता है।
• सापेक्ष त्रुटि सहनशीलता (Relative Error Tolerance): यदि प्रमाणन एक स्थिरांक सापेक्ष त्रुटि ($\epsilon$) की अनुमति देता है, तो प्रमाण आकार छोटा ( $1/\epsilon$ में बहुपद) हो सकता है। हालाँकि, इसके लिए घातीय संख्या में पूर्ण गलतियों की अनुमति देनी पड़ती है। लेखक दिखाते हैं कि स्थिरांक सापेक्ष-त्रुटि गारंटी कई घातीय गलतियों को छिपा सकती है, जबकि बहुपद पूर्ण-त्रुटि गारंटी अभी भी घातीय प्रमाणन की आवश्यकता रखती है।

3. अनुभवजन्य सत्यापन

• सर्किट प्रयोग: निर्मित $TC_0$ धोखेबाजों ने सैद्धांतिक बाधा की पुष्टि की। यहाँ तक कि बहुपद-आकार के प्रमाणन उम्मीदवारों के साथ भी, लगभग सभी निर्मित धोखेबाज लेबल के साथ सुसंगत रहे, जिन्हें समाप्त करने के लिए घातीय नमूनाकरण की आवश्यकता थी।
• ट्रांसफॉर्मर प्रयोग: व्यापक सत्यापन पास करने वाले 150 प्रशिक्षित मॉडलों में से, 63 में होल्ड-आउट टेस्ट सेट पर अवशिष्ट त्रुटियां थीं। विश्लेषण ने दिखाया कि त्रुटि-समृद्ध उदाहरणों के लक्षित उपसमुच्चय के साथ भी, समान रूप से नमूना लिए गए बहुपद आकार के प्रमाणन उम्मीदवार सभी गैर-सटीक परिकल्पनाओं को समाप्त करने में विफल रहे। अपूर्ण मॉडल बड़े, समान रूप से नमूना लिए गए उम्मीदवारों द्वारा भी पता लगाने से बच सकते थे।

महत्व और दावे

शोध पत्र का दावा है कि यह सटीक शिक्षण के लिए प्रमाणन कठोरता का एक मात्रात्मक रूप प्रदान करता है। इसका महत्व निम्नलिखित दावों में निहित है:

1. मॉडल क्षमता के प्रति संवेदनशीलता: प्रमाणन केवल लक्ष्य फलन का गुण नहीं है बल्कि यह "परिवेशी" (ambient) परिकल्पना वर्ग पर भी महत्वपूर्ण रूप से निर्भर करता है। मॉडल क्षमता में न्यूनतम वृद्धि (स्थिरांक ओवरहेड) मॉडल की शुद्धता को सत्यापित करने की कठिनाई को मौलिक रूप से बदल सकती है।
2. निष्क्रिय प्रमाणन की सीमाएं: निष्क्रिय सेटिंग्स (जहाँ मॉडल को क्वेरी किए बिना उदाहरणों का नमूना लिया जाता है) में, यदि परिकल्पना वर्ग थोड़ा ओवरपैरामीटराइज्ड है, तो बहुपद-आकार के डेटासेट यह प्रमाणित करने के लिए अपर्याप्त हैं कि मॉडल ने इच्छित गणना सीख ली है।
3. सीखने की क्षमता से अंतर: परिणाम सीखने की क्षमता (learnability) और प्रमाणन के बीच के अंतर को उजागर करते हैं। जबकि एक फलन (एक प्रतिबंधित वर्ग में) सीखने योग्य हो सकता है (या उसका छोटा प्रमाण हो सकता है), थोड़े बड़े वर्ग के विरुद्ध उसे प्रमाणित करना कठिन हो सकता है।
4. तर्क मॉडलों के लिए निहितार्थ: एल्गोरिथम कार्यों (जैसे जोड़) पर तैनात मॉडलों के लिए, उच्च सत्यापन सटीकता सटीक होने की गारंटी नहीं देती है। यह शोध पत्र सुझाव देता है कि बिना मजबूत प्रोटोकॉल (जैसे, सक्रिय शिक्षण या विशिष्ट प्रश्न) के, बड़े समान रूप से नमूना लिए गए डेटासेट तर्क मॉडलों में सूक्ष्म, संरचित विसंगतियों का पता लगाने में विफल हो सकते हैं।

लेखक निष्कर्ष निकालते हैं कि जबकि सटीक प्रमाणन एक मौलिक चुनौती है, यह बाधा केवल एक वर्स्ट-केस विसंगति नहीं है बल्कि आधुनिक तर्क कार्यों के लिए प्रासंगिक वर्गों में न्यूनतम ओवरपैरामीट्राइजेशन का एक संरचनात्मक परिणाम है। वे सुझाव देते हैं कि भविष्य के कार्य इन निष्क्रिय बाधाओं को दूर करने के लिए संभावित रूप से सक्रिय प्रमाणन प्रोटोकॉल की खोज कर सकते हैं।