🤖 machine learning

A computational phase transition for learning-to-sample from Ising models

यह शोध पत्र बाउंडेड-विड्थ आइसिंग मॉडल्स (bounded-width Ising models) के स्पेक्ट्रल थ्रेशोल्ड (spectral threshold) पर लर्निंग-टू-सैंपल (learning-to-sample) के लिए एक तीव्र कम्प्यूटेशनल फेज ट्रांजिशन (computational phase transition) स्थापित करता है, जो यह प्रदर्शित करता है कि जबकि पैरामीटर लर्निंग (parameter learning) सुलभ बना रहता है, इस थ्रेशोल्ड के ठीक परे सैंपलिंग मानक क्रिप्टोग्राफिक धारणाओं (standard cryptographic assumptions) के तहत कम्प्यूटेशनल रूप से कठिन हो जाता है, जो किसी भी कुशल शिक्षार्थी को या तो प्रशिक्षण डेटा को याद करने या नगण्य-प्रायिकता वाली कॉन्फ़िगरेशन (negligible-probability configurations) को मतिभ्रम (hallucinate) करने के लिए मजबूर करता है।

मूल लेखक: Andrej Risteski, Thuy-Duong Vuong

प्रकाशित 2026-05-26

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

CC BY 4.0

मूल लेखक: Andrej Risteski, Thuy-Duong Vuong

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

कल्पना कीजिए कि आप एक रोबोट को किसी विशिष्ट कलाकार के काम की तरह दिखने वाले चित्र बनाना सिखाने की कोशिश कर रहे हैं। आप रोबोट को दो चीजें देते हैं:

रेसिपी (विधि): वह सटीक गणितीय सूत्र (पैरामीटर्स) जिसका उपयोग कलाकार ने अपनी शैली बनाने के लिए किया था।
पोर्टफोलियो: कलाकार के वास्तविक चित्रों का एक संग्रह (ट्रेनिंग डेटा)।

आमतौर पर, हम यह मान लेते हैं कि यदि आपके पास रेसिपी और कुछ उदाहरण हों, तो रोबोट नए चित्र बना सकेगा जो कलाकार के काम जैसे ही दिखेंगे, बिना केवल उन्हीं चित्रों की नकल किए जिन्हें उसने पहले देखा है। यही "लर्निंग-टू-सैंपल" (सीखने-से-नमूने-बनाने) का लक्ष्य है।

यह शोध पत्र तर्क देता है कि आइसिंग मॉडल (Ising model) नामक एक विशिष्ट प्रकार के गणितीय मॉडल के लिए (जो एक विशाल ग्रिड की तरह है जिसमें छोटे चुंबक ऊपर या नीचे की ओर इशारा करते हैं), यह धारणा गलत है। सही रेसिपी और पर्याप्त उदाहरण होने के बावजूद भी, एक कंप्यूटर कुशलतापूर्वक नए, प्रामाणिक दिखने वाले चित्र उत्पन्न नहीं कर सकता।

यहाँ उनकी खोज का सरल उपमाओं के माध्यम से विवरण दिया गया है:

1. "जादुई सीमा" (स्पेक्ट्रल थ्रेशोल्ड)

आइसिंग मॉडल को एक जटिल मशीन के रूप में सोचें जिसमें एक "कठिनाई डायल" (difficulty dial) है।

डायल के नीचे (आसान क्षेत्र): यदि मशीन को कम कठिनाई पर सेट किया जाता है, तो रेसिपी सीखना और नए नमूने बनाना आसान होता है। यह एक स्टिक फिगर (रेखाचित्र) बनाना सीखने जैसा है; एक बार जब आप नियम जान जाते हैं, तो आप अनंत नए स्टिक फिगर बना सकते हैं।
डायल के ऊपर (कठिन क्षेत्र): यदि मशीन को उच्च कठिनाई पर सेट किया जाता है, तो नए नमूने कुशलतापूर्वक बनाना असंभव हो जाता है। यह एक अराजक तूफान के सटीक परिणाम की भविष्यवाणी करने की कोशिश करने जैसा है।

शोध पत्र उस सटीक क्षण पर ध्यान केंद्रित करता है जब डायल "आसान" से "कठिन" की ओर पार करता है। उन्होंने पाया कि यदि आप डायल को "आसान" रेखा से बस एक मामूली अंश भी आगे घुमा देते हैं, तो कंप्यूटर के लिए यह कार्य असंभव हो जाता है, भले ही आपके पास रेसिपी और उदाहरण हों।

2. "याद करना बनाम मतिभ्रम" (Memorize vs. Hallucinate) दुविधा

यह पेपर इस पहेली को हल करने की कोशिश करने वाले किसी भी कंप्यूटर के लिए एक सख्त नियम सिद्ध करता है। कंप्यूटर के पास केवल दो विकल्प हैं, और दोनों ही विफलताएँ हैं:

विकल्प A: फोटोकॉपी करने वाला (याद करना/Memorization)
कंप्यूटर ट्रेनिंग डेटा को देखता है और सीधे वही चित्र आउटपुट करता है जो उसने पहले देखा है (या उसका एक बहुत मामूली बदलाव)। उसने निर्माण करना नहीं सीखा है; उसने केवल पोर्टफोलियो को याद कर लिया है।
- उपमा: यह उस छात्र की तरह है जो नया निबंध लिखने के बजाय, केवल पाठ्यपुस्तक से एक वाक्य कॉपी करता है क्योंकि वह कुछ नया उत्पन्न नहीं कर सकता।
विकल्प B: सपने देखने वाला (मतिभ्रम/Hallucination)
कंप्यूटर रचनात्मक होने की कोशिश करता है और एक बिल्कुल नया चित्र बनाता है। लेकिन क्योंकि गणित बहुत कठिन है, यह नया चित्र इतना अजीब और अवास्तविक होता है कि वास्तविक दुनिया में इसकी संभावना लगभग शून्य होती है। यह एक "मतिभ्रम" (hallucination) है।
- उपमा: यह एक छात्र की तरह है जो पनीर के बादल पर उड़ते हुए ड्रैगन की कहानी लिख रहा है। यह नया तो है, लेकिन यह इतना अवास्तविक है कि यह बेकार है।

यह पेपर सिद्ध करता है कि एक कंप्यूटर दोनों नहीं कर सकता। वह नया, वास्तविक डेटा उत्पन्न करना नहीं सीख सकता। उसे या तो नकल करने के लिए मजबूर होना होगा या कल्पनाओं में खो जाना होगा।

3. "डिजिटल लॉक" की उपमा

उन्होंने इसे कैसे सिद्ध किया? उन्होंने डिजिटल सिग्नेचर (जैसे आपके बैंक खाते के सुरक्षा कोड) का उपयोग करके एक गणितीय जाल बनाया।

उन्होंने आइसिंग मॉडल के भीतर एक "गुप्त ताला" छिपा दिया।
उन्हें दिए गए "ट्रेनिंग डेटा" वैध, खुले दरवाजे (वैध सिग्नेचर) थे।
"रेसिपी" ताले की पब्लिक की (public key) थी।
कार्य एक नया खुला दरवाजा (एक नया वैध सिग्नेचर) उत्पन्न करना था, जिसे कंप्यूटर ने पहले कभी नहीं देखा था।

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

4. यह क्यों महत्वपूर्ण है (पेपर के संदर्भ में)

यह पेपर तीन मुख्य बातें बताता है:

फेज ट्रांजिशन (Phase Transition) तीव्र है: एक बहुत स्पष्ट रेखा है जहाँ सीखना असंभव हो जाता है। यह धीरे-धीरे होने वाली गिरावट नहीं है; यह एक ढलान (cliff) है।
नियम जानना पर्याप्त नहीं है: केवल इसलिए कि आपके पास मॉडल के पैरामीटर्स (रेसिपी) और डेटा है, इसका मतलब यह नहीं है कि आप नया डेटा उत्पन्न कर सकते हैं। कभी-कभी, "सीखने" का हिस्सा "नियमों को समझने" के हिस्से से अधिक कठिन होता है।
"याद करना या मतिभ्रम" का जाल: यदि किसी AI को इन कठिन मॉडलों से सीखने के लिए मजबूर किया जाता है, तो वह अनिवार्य रूप से या तो वही दोहराएगा जो उसने देखा है या अजीबोगरीब चीजें बनाएगा। वह वास्तव में नया, वास्तविक डेटा बनाना नहीं सीख सकता।

संक्षेप में: यह पेपर दिखाता है कि कुछ जटिल गणितीय प्रणालियों के लिए, कंप्यूटर को ब्लूप्रिंट और उदाहरण देना भी नया, प्रामाणिक उदाहरण बनाना सिखाने के लिए पर्याप्त नहीं है। कंप्यूटर एक ऐसी स्थिति में फंस जाता है जहाँ उसे या तो कॉपी-पेस्ट करना होगा या असंभव परिदृश्यों की कल्पना करनी होगी।

तकनीकी सारांश: आइसिंग मॉडल से सीखने-के-लिए-नमूना लेने (Learning-to-Sample) हेतु एक कम्प्यूटेशनल फेज़ ट्रांज़िशन

समस्या विवरण
यह शोध पत्र "सीखने-के-लिए-नमूना लेने" (learning-to-sample) के एल्गोरिद्मिक कार्य की जांच करता है, जो आधुनिक जनरेटिव मॉडलिंग का एक मौलिक आधार है। लक्ष्य एक कुशल प्रक्रिया डिजाइन करना है जो, एक अज्ञात लक्षित वितरण $\nu$ से $k$ i.i.d. नमूनों (samples) को प्राप्त करने के बाद, लगभग उसी नियम का पालन करने वाले नए नमूने उत्पन्न कर सके। लेखक इसके लिए आइसिंग मॉडल (Ising models) पर ध्यान केंद्रित करते हैं, जो सैद्धांतिक कंप्यूटर विज्ञान और मशीन लर्निंग में एक मानक परीक्षण स्थल है।

एक केंद्रीय प्रश्न जिसका समाधान किया गया है, वह यह है कि क्या प्रशिक्षण नमूनों तक पहुंच, मॉडल मापदंडों (parameters) तक स्पष्ट पहुंच के साथ मिलकर, उन कम्प्यूटेशनल बाधाओं को दूर कर सकती है जो केवल मापदंडों के ज्ञात होने पर मौजूद होती हैं। पैरामीटर सीखना (डेटा से मॉडल मापदंडों का अनुमान लगाना) और घनत्व अनुमान (density estimation) अलग-अलग कार्य हैं, लेकिन सीखने-के-लिए-नमूना लेना नए नमूने उत्पन्न करने की मांग करता है। यह शोध पत्र विशेष रूप से उस "स्पेक्ट्रल थ्रेशोल्ड" (spectral threshold) के पास के क्षेत्र को लक्षित करता है जहाँ $\lambda_{\max}(J) - \lambda_{\min}(J) = 1$ है, जहाँ $J$ इंटरेक्शन मैट्रिक्स है। पूर्ववर्ती कार्यों ने स्थापित किया है कि इस थ्रेशोल्ड से नीचे नमूना लेना (sampling) सुलभ है, लेकिन निकट-क्रिटिकल (near-critical) शासन में सीखने-के-लिए-नमूना लेने की कम्प्यूटेशनल जटिलता खुली हुई थी।

कार्यप्रणाली
लेखक सीमित-चौड़ाई वाले आइसिंग मॉडलों का एक परिवार निर्मित करते हैं जिन्हें सीखने-के-लिए-नमूना लेना कम्प्यूटेशनल रूप से कठिन है, भले ही शिक्षार्थी (learner) को मॉडल मापदंड और बहुपद संख्या में प्रशिक्षण नमूने प्रदान किए गए हों। प्रमाण डिजिटल सिग्नेचर स्कीमों की सुरक्षा से, विशेष रूप से कम्प्यूटेशनल डिफी-हेलमैन (Computational Diffie-Hellman - CDH) धारणा के तहत, रिडक्शन (reduction) पर आधारित है।

निर्माण दो मुख्य चरणों में आगे बढ़ता है:

सिग्नेचर वेरिफिकेशन को आइसिंग मॉडलों में एम्बेड करना:
लेखक आइसिंग मॉडलों में सर्किट एम्बेड करने की तकनीक को अनुकूलित करते हैं (मोइत्रा एट अल और बोगदानोव एट अल का अनुसरण करते हुए)। वे एक निश्चित सार्वजनिक कुंजी $pk $के लिए एक आइसिंग मॉडल$ \mu_{pk}$ का निर्माण करते हैं ताकि इसके उच्च-संभाव्यता वाले विन्यास (configurations) एक सिग्नेचर स्कीम के लिए वैध संदेश-हस्ताक्षर युग्मों $(msg, \sigma)$ को एनकोड करें जिसका सत्यापन नियत (deterministic) हो।

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

फेज़-गैजेट निर्माण (निकट-क्रिटिकल एम्बेडिंग):
प्रारंभिक निर्माण संभावित रूप से सघन (dense) आइसिंग मॉडल और मनमाने इंटरेक्शन स्ट्रेंथ प्रदान करता है। स्पेक्ट्रल थ्रेशोल्ड को संबोधित करने के लिए, लेखक एक "फेज़-गैजेट" (phase-gadget) निर्माण पेश करते हैं।

मूल आइसिंग मॉडल के प्रत्येक शीर्ष (vertex) को एक गैजेट ग्राफ द्वारा प्रतिस्थापित किया जाता है जिसमें एक "कोर" स्पिन सेट ( $R_v$ ) और पड़ोसियों से जुड़े "इंटरफेस" सेट ( $S_v$ ) होते हैं।
गैजेट को दो प्रमुख चरणों (प्रमुख स्पिन $+1$ या $-1$) के साथ डिज़ाइन किया गया है जो मूल शीर्ष के प्रभावी स्पिन का अनुकरण करते हैं।
गैजेट मापदंडों (सेट के आकार और किनारों के भार) को सावधानीपूर्वक ट्यून करके, लेखक यह सुनिश्चित करते हैं कि परिणामी आइसिंग मॉडल $\tilde{\mu}$ का एक सीमित इंटरेक्शन विड्थ ( $O(1)$ ) हो और इसकी स्पेक्ट्रल विड्थ $\lambda_{\max}(\tilde{J}) - \lambda_{\min}(\tilde{J})$ मनमाने रूप से 1 के करीब हो (विशेष रूप से, $1 < \lambda_{\max} - \lambda_{\min} \le \gamma$ किसी भी स्थिरांक $\gamma > 1$ के लिए)।
महत्वपूर्ण रूप से, यह रूपांतरण "सीखने-के-लिए-सामान्यीकरण" (learning-to-generalize) की कठिनाई को संरक्षित करता है। लेखक यह सिद्ध करते हैं कि यदि एक कुशल शिक्षार्थी $\tilde{\mu}$ से नमूना ले सकता है, तो वह मूल कठिन उदाहरण $\mu$ से नमूना लेने के लिए एक कुशल एल्गोरिदम का निर्माण कर सकता है, जिससे सिग्नेचर स्कीम टूट जाएगी।

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

स्पेक्ट्रल थ्रेशोल्ड के पास कठिनाई: मानक CDH धारणा के तहत, लेखक सीमित चौड़ाई और स्पेक्ट्रल विड्थ $1 < \lambda_{\max}(J) - \lambda_{\min}(J) \le \gamma$ (किसी भी $\gamma > 1$ के लिए) वाले आइसिंग मॉडलों का एक परिवार निर्मित करते हैं, जिनके लिए सीखने-के-लिए-नमूना लेना कम्प्यूटेशनल रूप से कठिन है। यह तब भी सत्य है जब शिक्षार्थी को स्पष्ट मापदंड $(J, h)$ और बहुपद i.i.d. नमूने दिए जाते हैं।
पैरामीटर लर्निंग से अलगाव: निर्मित कठिन उदाहरण उस शासन में आते हैं जहाँ पैरामीटर सीखना कुशल ज्ञात है (क्लिवांस और मेका, वु एट अल, और वुफ़्रे एट अल के परिणामों के आधार पर)। यह एक पृथक्करण स्थापित करता है: पैरामीटर सीखना आसान है, लेकिन सीखने-के-लिए-नमूना लेना कठिन है।
मेमोराइजेशन-हैलुसिनेशन द्वैत (Dichotomy): इन कठिन उदाहरणों के लिए किसी भी कुशल शिक्षार्थी के लिए यह शोध पत्र एक द्वैत को औपचारिक रूप देता है। कोई भी ऐसा शिक्षार्थी या तो:
1. मेमोराइज (Memorize): ऐसे विन्यास आउटपुट करता है जो एक सरल रूपांतरण के बाद, प्रशिक्षण डेटा से मेल खाते हैं।
2. हैलुसिनेट (Hallucinate): ऐसे विन्यासों पर पर्याप्त संभाव्यता द्रव्यमान (probability mass) रखता है जिनका लक्षित वितरण के तहत नगण्य संभाव्यता है ("हैलुसिनेशन सेट")।
  यह परिणाम इन वितरणों के लिए कुशल शिक्षार्थी या सैंपल एम्प्लीफिकेशन को विश्वसनीय रूप से सीखने-के-लिए-नमूना लेने या करने की संभावना को खारिज करता है।
तीव्र फेज़ ट्रांज़िशन (Sharp Phase Transition): स्पेक्ट्रल थ्रेशोल्ड के नीचे सीखने-के-लिए-नमूना लेने की सुलभता के हालिया परिणामों (अनारी एट अल, कोहलर एट अल) के साथ मिलकर, यह कार्य सीखने-के-लिए-नमूना लेने के कार्य के लिए स्पेक्ट्रल थ्रेशोल्ड पर एक तीव्र कम्प्यूटेशनल फेज़ ट्रांज़िशन स्थापित करता है।

महत्व
शोध पत्र का दावा है कि इसके परिणाम जनरेटिव मॉडलिंग की सीमाओं की एक मौलिक समझ प्रदान करते हैं। यह प्रदर्शित करके कि सीखना-के-लिए-नमूना लेना पैरामीटर सीखने की तुलना में स्पष्ट रूप से कठिन हो सकता है, यहाँ तक कि उन शासनों में जहाँ मॉडल मापदंड ज्ञात हैं और सीखना सैद्धांतिक रूप से संभव है, यह कार्य इस अंतर्ज्ञान को चुनौती देता है कि डेटा और मापदंडों तक पहुँच कुशल पीढ़ी (generation) की गारंटी देती है।

मेमोराइजेशन-हैलुसिनेशन ट्रेडऑफ़ का औपचारिकीकरण इन जनरेटिव मॉडलों में देखे गए अनुभवजन्य (empirical) घटनाओं के लिए एक सैद्धांतिक लेंस प्रदान करता है, जो यह सुझाव देता है कि कुछ वितरणों के लिए, एक जनरेटर नए डेटा के लिए सामान्यीकरण (generalize) करने के लिए या तो ओवरफिटिंग (मेमोराइजेशन) या अवास्तविक आउटपुट (हैलुसिनेशन) के बिना नहीं कर सकता है। परिणामों को एक क्रिप्टोग्राफिक पृथक्करण के रूप में तैयार किया गया है, जो अपुष्ट जटिलता अनुमानों के बजाय मानक धारणाओं (CDH) पर निर्भर करता है, जिससे सीखने-के-लिए-नमूना लेने की कठिनाई को सुस्थापित क्रिप्टोग्राफिक प्रिमिटिव्स में निहित किया गया है।

लेखक नोट करते हैं कि जबकि वे किसी भी निश्चित $\gamma > 1$ के लिए कठिनाई सिद्ध करते हैं, सटीक थ्रेशोल्ड $\gamma = 1 + o(1)$ पर व्यवहार एक खुला प्रश्न बना हुआ है। इसके अतिरिक्त, वे यह भी खुला छोड़ देते हैं कि क्या अन्य वितरण परिवार समान फेज़ ट्रांज़िशन प्रदर्शित करते हैं या क्या अन्य संदर्भों में नमूना लेने और सीखने-के-लिए-नमूना लेने के थ्रेशोल्ड भिन्न हो सकते हैं।

1. "जादुई सीमा" (स्पेक्ट्रल थ्रेशोल्ड)

2. "याद करना बनाम मतिभ्रम" (Memorize vs. Hallucinate) दुविधा

3. "डिजिटल लॉक" की उपमा

4. यह क्यों महत्वपूर्ण है (पेपर के संदर्भ में)

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