🤖 machine learning

Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders

यह शोध पत्र आंशिक क्रमों (partial orders) पर इन-कॉन्टेक्स्ट लर्निंग के लिए एक सैद्धांतिक ढांचा स्थापित करता है जो एक सटीक पूर्णता त्रिक (exact completion trichotomy) के माध्यम से तार्किक पहचान क्षमता (logical identifiability) को परिभाषित करता है, ओपन-वर्ल्ड टीचिंग नंबर को कवर और ब्लॉकर-सेट लागतों के योग के रूप में अभिलक्षित करता है, और यह सिद्ध करता है कि $s$ -कोऑर्डिनेट डिकोडर्स केवल तभी पोसेट्स (posets) का सटीक प्रतिनिधित्व कर सकते हैं जब उनका आयाम (dimension) $s$ से अधिक न हो।

मूल लेखक: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

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

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

CC BY 4.0

मूल लेखक: Faizanuddin Ansari, Debanjan Dutta, Swagatam Das

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

जासूसी दुविधा: जब सुराग पर्याप्त नहीं होते

कल्पना कीजिए कि आप एक रहस्य सुलझाने की कोशिश कर रहे हैं एक जासूस के रूप में, लेकिन अपराध स्थल के बजाय, आप सुरागों के एक समूह को देख रहे हैं जो बताते हैं कि चीजें एक-दूसरे से कैसे संबंधित हैं। आर्टिफिशियल इंटेलिजेंस (AI) की दुनिया में, "इन-कॉन्टेक्स्ट लर्निंग" (in-context learning) नामक एक सुपरपावर है। यह एक स्मार्ट कंप्यूटर को चैट प्रॉम्प्ट में किसी नियम के कुछ उदाहरण देने जैसा है, और बिना अपने मस्तिष्क (अपने आंतरिक सेटिंग्स) को बदले, वह उस नियम का पालन करने का तरीका समझ जाता है। आमतौर पर, हम इसे सरल गणित या भाषा के पैटर्न सीखने के रूप में देखते हैं। लेकिन क्या होगा यदि नियम "क्रम" (order) के बारे में हो? क्या होगा यदि सुराग आपको बताते हैं कि A, B से बड़ा है, और B, C से बड़ा है, लेकिन वे A और C के बारे में कुछ नहीं कहते? या इससे भी बुरा, क्या होगा यदि सुराग कहते हैं कि A, B से छोटा नहीं है, लेकिन यह नहीं बताते कि क्या वे बराबर हैं या क्या A वास्तव में बड़ा है?

यह शोध पत्र तर्क के उस पेचीदा कोने में जाता है जिसे "पार्शियल ऑर्डर" (partial orders) कहा जाता है। एक पार्शियल ऑर्डर को एक उलझे हुए पारिवारिक वृक्ष (family tree) की तरह समझें जहाँ कुछ चचेरे भाई स्पष्ट रूप से दूसरों से बड़े हैं, लेकिन कुछ चचेरे भाई केवल "तुलनाहीन" (incomparable) हैं—आप यह नहीं कह सकते कि कौन बड़ा है क्योंकि वे अलग-अलग शाखाओं पर हैं। लेखक मुख्य सवाल यह पूछते हैं: एक कंप्यूटर को पूरा पारिवारिक वृक्ष समझने के लिए वास्तव में कितने सुरागों की आवश्यकता होती है? और अधिक महत्वपूर्ण बात यह है कि, कब यह जानना असंभव है कि उत्तर क्या है, चाहे वह कितना भी स्मार्ट क्यों न हो? यह महत्वपूर्ण है क्योंकि यदि हम इन सुरागों की सीमाओं को नहीं समझते हैं, तो हम ऐसे AI सिस्टम बना सकते हैं जो आत्मविश्वास के साथ गलत अनुमान लगाते हैं, या हम उन्हें बहुत अधिक उदाहरण देकर अपना समय बर्बाद कर सकते हैं जब थोड़े से उदाहरण ही काफी होते।

शोध पत्र की कहानी: अज्ञात का मानचित्रण

इस शोध पत्र के लेखकों, फैजानुद्दीन अनसारी, देबंजन दत्ता और स्वागतम दास ने AI की सीखने की प्रक्रिया को तर्क पहेलियों के खेल की तरह लेने का निर्णय लिया। उन्होंने केवल यह देखने के लिए प्रयोग नहीं किए कि AI सही है या नहीं; उन्होंने एक गणितीय मानचित्र बनाया ताकि यह साबित किया जा सके कि कब एक पहेली हल करने योग्य है और कब वह एक बंद रास्ता है।

एक सुराग के तीन परिणाम
सबसे पहले, उन्होंने इस प्रश्न को हल किया: "यदि मैं आपको 'A, B से बड़ा है' और 'B, C से बड़ा नहीं है' सुरागों की एक सूची दूँ, तो क्या आप बता सकते हैं कि क्या A, C से बड़ा है?"
उन्होंने सिद्ध किया कि किसी भी सीमित सेट के लिए, केवल तीन संभावित उत्तर होते हैं, और कंप्यूटर ठीक से जान सकता है कि वह कौन सा है:

अनिवार्य सत्य (Forced True): सुराग इतने मजबूती से जुड़े हैं कि A का C से बड़ा होना अनिवार्य है।
अनिवार्य असत्य (Forced False): सुराग एक विरोधाभास पैदा करते हैं यदि A, C से बड़ा होता (जैसे कि टाइम-ट्रैवल पैराडॉक्स), इसलिए A, C से बड़ा नहीं हो सकता।
वास्तविक रूप से संदिग्ध (Genuinely Ambiguous): सुराग बस पर्याप्त जानकारी नहीं देते। A बड़ा हो सकता है, या छोटा, या बराबर, और वे सभी परिदृश्य सुरागों में पूरी तरह फिट बैठते हैं।

उन्होंने दिखाया कि यदि AI एक "ओपन वर्ल्ड" (खुली दुनिया) में है (जहाँ अनकही चीजें सच हो सकती हैं), तो वह इस "संदिग्ध" क्षेत्र में बहुत अधिक बार फंसता है, बजाय इसके कि वह यह मान ले कि सुराग एक पूर्ण चित्र हैं। वास्तव में, उन्होंने सभी संभावित 4-आइटम पहेलियों (कुल 219 पहेलियाँ) पर एक विशाल सिमुलेशन चलाया और पाया कि भले ही आप AI को 12 में से 11 संभावित सुराग दिखा दें, फिर भी शेष प्रश्नों में से लगभग 45% वास्तव में संदिग्ध होते हैं। AI "मूर्ख" नहीं है; जानकारी बस गायब है।

पहेली सिखाने की लागत
इसके बाद, लेखकों ने पूछा: "हमें AI को एक विशिष्ट संबंध सिखाने के लिए कितने सुरागों की आवश्यकता है?"
उन्होंने पाया कि उत्तर संबंध के आकार पर निर्भर करता है।

यदि वस्तुएं एक सीधी रेखा में हैं (जैसे कमांड की एक श्रृंखला), तो आपको केवल पड़ोसियों के बीच के सीधे संबंधों को दिखाने की आवश्यकता होती है।
यदि वस्तुएं आपस में असंबंधित हैं (जैसे अजनबियों का एक समूह जो एक-दूसरे को नहीं जानते), तो लागत बहुत अधिक है। AI को यह सिखाने के लिए कि कोई भी किसी से संबंधित नहीं है, आपको स्पष्ट रूप से बताना होगा कि हर जोड़ा असंबंधित है।
उन्होंने एक कठिन सीमा सिद्ध की: $n$ वस्तुओं के समूह के लिए, सबसे खराब स्थिति (एक "antichain") में ठीक $n(n-1)$ सुरागों की आवश्यकता होती है। किसी भी संबंध को सिखाने के लिए आवश्यक अधिकतम प्रयास यही है। उन्होंने एक विशिष्ट "ब्लॉकर" लागत भी पहचानी: वे अतिरिक्त सुराग जिनकी आवश्यकता इसलिए होती है क्योंकि हम एक "ओपन वर्ल्ड" में हैं जहाँ हम यह नहीं मान सकते कि चुप्पी का अर्थ "नहीं" है।

मानचित्र बनाम दिशा-सूचक यंत्र (The Map vs. The Compass)
अंत में, उन्होंने देखा कि AI इन संबंधों को अपने "मस्तिष्क" के भीतर कैसे दर्शाता है। उन्होंने पूछा: "क्या AI इसे सरल निर्देशांकों (coordinates) के एक सेट का उपयोग करके हल कर सकता है?"
कल्पना कीजिए कि आप केवल एक 2D मानचित्र का उपयोग करके एक 3D वस्तु का वर्णन करने का प्रयास कर रहे हैं। यदि वस्तु बहुत जटिल है, तो मानचित्र विफल हो जाएगा। लेखकों ने सिद्ध किया कि संबंध की "जटिलता" को "ऑर्डर डायमेंशन" (order dimension) द्वारा मापा जाता है।

यदि संबंध सरल है (जैसे एक सीधी रेखा), तो इसका आयाम 1 है।
यदि यह एक जटिल जाल है (जैसे कि एक Boolean lattice), तो इसे सटीक रूप से वर्णित करने के लिए 5, 10 या अधिक आयामों की आवश्यकता हो सकती है।
उन्होंने एक सख्त सीमा स्थापित की: यदि संबंध को उन आयामों से अधिक आयामों की आवश्यकता है जितने उसके AI के "कोऑर्डिनेट डिकोडर" के पास हैं, तो AI उसे सटीक रूप से नहीं सीख सकता, चाहे आप उसे कितने भी सुराग क्यों न दें। यह प्रशिक्षण की समस्या नहीं है; यह ज्यामिति (geometry) की समस्या है।

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

तकनीकी सारांश: आंशिक क्रम (Partial Orders) पर इन-कॉन्टेक्स्ट लर्निंग की पहचान क्षमता (Identifiability) और क्रम-आयाम सीमाएँ (Order-Dimension Limits)

1. समस्या विवरण

यह शोध पत्र इन-कॉन्टेक्स्ट लर्निंग (ICL) के सैद्धांतिक सीमाओं को संबोधित करता है जब इसे एकल-मान वाले फलनों (single-valued functions) के बजाय आंशिक क्रमों (posets) द्वारा परिभाषित रिलेशनल कार्यों पर लागू किया जाता है। जबकि मौजूदा ICL सिद्धांत अक्सर अज्ञात फलनों से लिए गए प्रॉम्प्ट्स की धारणा बनाते हैं, रिलेशनल रीजनिंग में संक्रामकता (transitivity), प्रति-समरूपता (antisymmetry), और अतुलनीयता (incomparability) शामिल होती है। एक परिमित प्रॉम्प्ट (finite prompt) क्वेरी के परिणाम (जैसे, क्या $a \preceq b$ ) को तार्किक रूप से निर्धारित करने में विफल हो सकता है क्योंकि:

साक्ष्य की कमी बनाम अतुलनीयता (Missing Evidence vs. Incomparability): सूचना की कमी और एक स्थापित संबंध के अभाव के बीच अंतर करना।
संरचनात्मक जटिलता (Structural Complexity): एक क्वेरी को हल करने के लिए कई स्वतंत्र समन्वय निर्देशांकों (independent ordering coordinates) या लंबी संक्रामक श्रृंखलाओं (transitive chains) की संभावित आवश्यकता।
सिमेंटिक अस्पष्टता (Semantic Ambiguity): ओपन-वर्ल्ड सिमेंटिक्स (जहाँ अनकहे संबंध मौजूद हो सकते हैं) और क्लोज्ड-वर्ल्ड सिमेंटिक्स (जहाँ प्रदर्शित हासे आरेख (Hasse diagram) को पूर्ण घोषित किया जाता है) के बीच का अंतर।

मुख्य उद्देश्य यह औपचारिक रूप करना है कि एक रिलेशनल प्रॉम्प्ट तार्किक रूप से क्या निर्धारित करता है, एक परिमित पोसेट (poset) को सिखाने के लिए कितने लेबल आवश्यक हैं, और इन संरचनाओं का प्रतिनिधित्व करने के लिए फॉर्मल कोऑर्डिनेट-डिकोडर क्लास की सटीक क्षमता क्या है।

2. कार्यप्रणाली और औपचारिक मॉडल

लेखक एक निश्चित, ज्ञात परिमित ब्रह्मांड (universe) $U$ पर वर्जन-स्पेस सिमेंटिक्स (version-space semantics) पर आधारित एक ढांचा विकसित करते हैं।

प्रॉम्प्ट प्रतिनिधित्व (Prompt Representation): एक प्रॉम्प्ट को एक लेबल किए गए प्रदर्शन सेट $D = (D^+, D^-)$ के रूप में परिभाषित किया गया है, जहाँ $D^+$ सकारात्मक कथनों ( $x \preceq y$ ) को और $D^-$ नकारात्मक कथनों ( $x \not\preceq y$ ) को समाहित करता है।
वर्जन स्पेस ( $V_B(D)$ ): बैकग्राउंड थ्योरी $B$ (जैसे, पोसेट एक्सिओम्स) और प्रदर्शनों $D$ के सुसंगत सभी पोसेट्स का समूह।
पहचान क्षमता (Identifiability): एक क्वेरी $q=(a,b)$ तब पहचानी जाती है यदि वर्जन स्पेस के सभी पोसेट्स $a \preceq b$ के सत्य मान पर सहमत हों।
डिकोडर क्लास (Decoder Class): शोध पत्र प्रॉम्प्ट-डिपेंडेंट मोनोटोनिक कोऑर्डिनेट डिकोडर्स का विश्लेषण करता है, जो एक प्रॉम्प्ट को $s$ कोऑर्डिनेट फलनों $\phi_1, \dots, \phi_s$ में मैप करते हैं, ताकि $x \preceq y$ तभी हो जब $\phi_i(x) \le \phi_i(y)$ सभी $i$ के लिए हो।

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

A. तार्किक पहचान क्षमता: ओपन-वर्ल्ड त्रिक (The Open-World Trichotomy)
सकारात्मक और नकारात्मक प्रदर्शनों वाले परिमित ओपन-वर्ल्ड प्रॉम्प्ट्स के लिए, शोध पत्र एक सटीक पूर्णता त्रिक (exact completion trichotomy) (प्रमेय 3) सिद्ध करता है। $D^+$ के रिफ्लेक्सिव ट्रांसिटिव क्लोजर $R$ को देखते हुए, एक क्वेरी $(a,b)$ ठीक तीन श्रेणियों में से एक में आती है:

फोर्स्ड ट्रू (Forced True): $a R b$ । संबंध संक्रामकता द्वारा निहित है।
फोर्स्ड फॉल्स (Forced False): $a \not R b$ और साथ ही ( $b R a$ ) या $(a,b)$ को जोड़ने से होने वाला ट्रांसिटिव क्लोजर $D^-$ के किसी नकारात्मक प्रदर्शन का उल्लंघन करेगा।
वास्तविक रूप से संदिग्ध (Genuinely Ambiguous): इनमें से कोई भी स्थिति लागू नहीं होती। क्वेरी अनिर्धारित रहती है क्योंकि वर्जन स्पेस के भीतर दोनों (सत्य और असत्य) पूर्णताएँ अस्तित्व में हैं।

परिणाम: यह क्वेरी परिणामों के लिए एक मॉडल-फ्री क्लासिफायर प्रदान करता है। एक 4-एलिमेंट पोसेट पर 12 में से 11 लेबल देखे जाने के बावजूद, ओपन-वर्ल्ड सिमेंटिक्स के तहत एक महत्वपूर्ण हिस्सा (लगभग 45%) क्वेरी संदिग्ध रहती है।

B. प्रॉम्प्ट टीचिंग कॉम्प्लेक्सिटी (Prompt Teaching Complexity)
शोध पत्र ओपन-वर्ल्ड टीचिंग नंबर $\tau_{ow}(P)$ को परिभाषित करता है, जो एक लक्षित पोसेट $P$ को विशिष्ट रूप से पहचानने के लिए आवश्यक न्यूनतम लेबल की संख्या है।

सटीक लक्षण वर्णन (प्रमेय 6): $\tau_{ow}(P) = |Cov(P)| + \beta(P)$ , जहाँ $|Cov(P)| $स्ट्रिक्ट कवर संबंधों की संख्या है और$ \beta(P)$ एक न्यूनतम ब्लॉकर-सेट हिटिंग सेट (blocker-set hitting set) का आकार है। एक अतुलनीय जोड़ी $(a,b)$ के लिए ब्लॉकर सेट उन जोड़ियों का समूह है जो ट्रांसिटिव उल्लंघन पैदा करेंगे यदि $a \preceq b$ को जोड़ा जाता है।
चरम मान (Extremal Values): $n$ -एलिमेंट यूनिवर्स के लिए अधिकतम टीचिंग नंबर $n(n-1)$ है, जो अद्वितीय रूप से एंटीचेन (antichain) (जहाँ कोई भी तत्व तुलनीय नहीं है) द्वारा प्राप्त किया जाता है। इसके विपरीत, एक चेन (chain) के लिए केवल $n-1$ लेबल की आवश्यकता होती है।
ओपन-वर्ल्ड सिमेंटिक्स की कीमत: ओपन-वर्ल्ड और क्लोज्ड-वर्ल्ड टीचिंग लागतों के बीच का अंतर ठीक $\beta(P)$ है, जो अपूर्णता को संभालने की लागत को अलग करता है।

C. संरचनात्मक जटिलता और प्रतिनिधित्व सीमाएँ
शोध पत्र संरचनात्मक कठिनाई को स्वतंत्र अक्षों में विभाजित करता है: ऊंचाई (height), चौड़ाई (width), क्रम आयाम (order dimension), और प्रमाण लंबाई (certificate lengths)।

कोऑर्डिनेट-डिकोडर सीमा (अनुवर्ती 12): एक कार्य परिवार के लिए एक सटीक $s$ -कोऑर्डिनेट डिकोडर तभी मौजूद होता है जब प्रत्येक लक्षित पोसेट का क्रम आयाम (Dushnik-Miller dimension) अधिकतम $s$ हो।
निहितार्थ: जबकि चौड़ाई $\le s$ होना आयाम $\le s$ के लिए एक पर्याप्त शर्त है, यह आवश्यक शर्त नहीं है। उच्च आयाम (जैसे, Boolean lattices या divisor lattices में) मोनोटोनिक कोऑर्डिनेट डिकोडर्स की प्रतिनिधित्व क्षमता को सख्ती से सीमित करता है, चाहे प्रॉम्प्ट की लंबाई कुछ भी हो।
प्रमाण (Certificates): शोध पत्र पॉजिटिव सर्टिफिकेट्स (सबसे छोटे हासे पाथ, लंबाई $\lambda^+$ ) और नेगेटिव सर्टिफिकेट्स (लक्ष्य को बाहर रखने वाले फॉरवर्ड-क्लोज्ड सेट्स, आकार $\nu^-$ ) के बीच अंतर करता है। नेगेटिव नॉन-रीचेबिलिटी के लिए एक बड़े रीचेबल क्षेत्र को उजागर करने की आवश्यकता हो सकती है, जबकि पॉजिटिव रीचेबिलिटी स्थानीय हो सकती है।

4. महत्व और दावे

यह शोध पत्र दावा करता है कि यह एक एकीकृत ढांचा प्रदान करता है जो रिलेशनल ICL में विफलता के चार अलग-अलग स्रोतों को अलग करता है:

गैर-पहचान क्षमता (Non-identifiability): एक सूचना-सैद्धांतिक सीमा जहाँ प्रॉम्प्ट तार्किक रूप से कई उत्तरों की अनुमति देता है (प्रमेय 3 द्वारा शासित)।
प्रॉम्प्ट बजट (Prompt Budget): एक विशिष्ट संरचना को सिखाने की लागत (प्रमेय 6 द्वारा शासित)।
प्रमाण जटिलता (Certificate Complexity): स्थानीय पथों या वैश्विक पहुँच (reachability) के माध्यम से संबंध को सिद्ध करने की कठिनाई (अनुवर्ती 13 और लेम्मा 14 द्वारा शासित)।
प्रतिनिधित्व क्षमता (Representation Capacity): उच्च-आयामी संरचनाओं का प्रतिनिधित्व करने में विशिष्ट डिकोडर क्लास (जैसे, मोनोटोनिक कोऑर्डिनेट मैप्स) की अक्षमता (अनुवर्ती 12 द्वारा शासित)।

बेंचमार्क डिजाइन के लिए महत्व:
लेखक तर्क देते हैं कि वर्तमान बेंचमार्क अक्सर इन कारकों को मिला देते हैं। वे प्रस्तावित करते हैं कि:

बेंचमार्क को स्पष्ट रूप से ब्रह्मांड (universe) और बैकग्राउंड थ्योरी (जैसे, अमूर्त प्रतीक बनाम पूर्व-प्रशिक्षित संख्यात्मक ज्ञान) का उल्लेख करना चाहिए।
"अज्ञात" (Unknown) को ओपन-वर्ल्ड प्रॉम्प्ट्स के लिए एक वैध आउटपुट होना चाहिए, क्योंकि कई क्वेरी उच्च लेबल कवरेज के बावजूद तार्किक रूप से संदिग्ध रहती हैं।
ओपन-वर्ल्ड (हासे आरेख अधूरा है) और क्लोज्ड-वर्ल्ड (हासे आरेख पूर्ण है) के बीच का अंतर महत्वपूर्ण है, क्योंकि वे अलग-अलग टीचिंग लागत और पहचान मानदंड प्रदान करते हैं।

यह शोध पत्र यह दावा नहीं करता है कि यह ट्रांसफार्मर एक्सप्रेसिविटी की सामान्य समस्या को हल करता है या प्रशिक्षण एल्गोरिदम प्रदान करता है। इसके बजाय, यह परिमित पोसेट्स के लिए तार्किक निचली सीमाओं (logical lower bounds) और सटीक प्रतिनिधित्व सीमाओं को स्थापित करता है, जिससे यह स्पष्ट होता है कि एक परिमित प्रॉम्प्ट क्या दर्शा सकता है और क्या नहीं, चाहे अंतर्निहित मॉडल आर्किटेक्चर कुछ भी हो।