🤖 machine learning

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

यह शोध पत्र यह स्थापित करता है कि वैज्ञानिक खोज के लिए कंपोजिशनल फंक्शन ट्रीज़ (compositional function trees) सीखने की सैंपल कॉम्प्लेक्सिटी, प्रतीकात्मक संरचनाओं (symbolic structures) के कॉम्बिनेटोरियल विस्फोट के बजाय, ट्री डेप्थ और ऑपरेटर लिप्सचिट्ज़ कॉन्स्टेंट्स (operator Lipschitz constants) द्वारा नियंत्रित होती है, जो PAC लर्नैबिलिटी बाउंड्स और यह अनुभवजन्य सत्यापन (empirical validation) प्रदान करता है कि जनरलाइजेशन गैप $\mathcal{O}(L^d/\sqrt{n})$ के रूप में स्केल करता है।

मूल लेखक: Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

प्रकाशित 2026-06-30

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

CC BY 4.0

मूल लेखक: Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

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

कल्पना कीजिए कि आप एक कंप्यूटर को डेटा पॉइंट्स के ढेर को देखकर "भौतिकी के नियमों" (जैसे $F=ma$ या गुरुत्वाकर्षण कैसे काम करता है) को खोजना सिखाने की कोशिश कर रहे हैं। आमतौर पर, वैज्ञानिक एक विधि का उपयोग करते हैं जिसे सिंबोलिक रिग्रेशन (Symbolic Regression) कहा जाता है। एक ब्लैक-बॉक्स न्यूरल नेटवर्क देने के बजाय, वे कंप्यूटर से बुनियादी गणितीय क्रियाओं जैसे जोड़ ( $+$ ), गुणा ( $\times$ ), साइन ( $\sin$ ), और एक्सपोनेंशियल ( $e^x$ ) जैसे बुनियादी लेगो ब्रिक्स (Lego bricks) का उपयोग करके एक फॉर्मूला बनाने के लिए कहते हैं।

बड़ी समस्या हमेशा यह रही है: "इन लेगो ब्रिक्स को जोड़ने के कितने सारे तरीके हैं!"

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

यह पेपर कहता है: "जरूरी नहीं कि ऐसा ही हो।"

यहाँ लेखकों द्वारा दिए गए निष्कर्षों का सरल विवरण दिया गया है, जो रोजमर्रा के उदाहरणों का उपयोग करता है:

1. "लेगो टॉवर" बनाम "डगमगाता हुआ ढेर"

एक फॉर्मूला बनाने को लेगो ब्रिक्स के टॉवर को स्टैक करने के रूप में सोचें।

पुराना डर: लोगों को लगा कि क्योंकि आप कई अलग-अलग आकारों के टॉवर बना सकते हैं, इसलिए कंप्यूटर भ्रमित हो जाएगा और यह पता लगाने के लिए कि कौन सा सही है, उसे लाखों डेटा पॉइंट्स की आवश्यकता होगी।
नया अंतर्दृष्टि: लेखक तर्क देते हैं कि कठिनाई इस बात में नहीं है कि कितने आकार मौजूद हैं। यह इस बारे में है कि टॉवर कितना स्थिर (stable) है।

यदि आप एक ऐसा टॉवर बनाते हैं जहाँ हर ईंट डगमगाती और फिसलन भरी है (गणितीय रूप से, यदि क्रियाएं "अस्थिर" हैं या उच्च लिप्सचिट्ज़ स्थिरांक (Lipschitz constants) वाली हैं), तो इनपुट में मामूली बदलाव के साथ पूरा ढांचा ढह सकता है या बुरी तरह हिल सकता है।

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

2. "रिपल इफेक्ट" (गहराई और जटिलता)

लेखक सिद्ध करते हैं कि फॉर्मूले की "जटिलता" एक विशिष्ट तरीके से बढ़ती है:

गहराई ( $d$ ): गणित की कितनी परतें एक के ऊपर एक रखी गई हैं।
स्थिरता ( $L$ ): प्रत्येक गणितीय क्रिया छोटी त्रुटियों को कितना बढ़ा देती है।

उन्होंने पाया कि सीखने की कठिनाई लगभग $L^d / \sqrt{n}$ की तरह स्केल करती है।

$L^d$ : यदि आपकी ईंटें थोड़ी डगमगाती हैं ( $L > 1$ ), तो उन्हें गहराई ( $d$ ) तक स्टैक करने से डगमगाहट कई गुना बढ़ जाती है। यह "बुरी खबर" है।
$\sqrt{n}$ : लेकिन, यदि आप कंप्यूटर को अधिक डेटा ( $n$ ) देते हैं, तो सीखना आसान हो जाता है। आपके पास जितना अधिक डेटा होगा, आप डगमगाहट को उतना ही अधिक सुचारू (smooth out) कर पाएंगे।

उदाहरण: कल्पना कीजिए कि आप किताबों का एक ढेर संतुलित करने की कोशिश कर रहे हैं।

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

3. "फिजिक्स लैब" प्रयोग

यह साबित करने के लिए कि यह केवल कागज पर गणित नहीं है, लेखकों ने एक कंप्यूटर प्रोग्राम बनाया जो प्रयोगशाला में एक वैज्ञानिक की तरह कार्य करता है:

उन्होंने ज्ञात फॉर्मूलों (विभिन्न गहराइयों जैसे 1 परत, 2 परत, 4 परत तक) के साथ नकली "भौतिकी" डेटा (जैसे एक पहाड़ी से लुढ़कती गेंद) बनाया।
उन्होंने अपने "लेगो बिल्डर" को डेटा की छोटी मात्रा (50 से 5,000 उदाहरण) पर प्रशिक्षित किया।
परिणाम: उन्होंने मापा कि कंप्यूटर ने नए डेटा (जिसे उसने पहले नहीं देखा था) पर फॉर्मूले का कितनी अच्छी तरह से अनुमान लगाया (जिसे "जनरलाइजेशन गैप" कहा जाता है)।

उन्होंने पाया कि कंप्यूटर की गलतियाँ उनके पूर्वानुमान से पूरी तरह मेल खाती थीं:

जब फॉर्मूला गहरा था या उसमें "फिसलन भरी" गणित (जैसे $e^x$ ) का उपयोग किया गया था, तो गलतियाँ बढ़ गईं।
जब उन्होंने अधिक डेटा जोड़ा, तो गलतियाँ कम हो गईं, ठीक वैसा ही जैसा उनके फॉर्मूले ने भविष्यवाणी की थी।

4. "वैज्ञानिक खोज" के लिए इसका क्या अर्थ है

पेपर निष्कर्ष निकालता है कि सिंबोलिक रिग्रेशन, गहरे फॉर्मूलों के लिए भी सांख्यिकीय रूप से "सीखने योग्य" (learnable) है, बशर्ते उपयोग की जाने वाली गणितीय क्रियाएं स्थिर हों।

अच्छी खबर: हमें वैज्ञानिक नियमों की खोज करने के लिए अनंत डेटा की आवश्यकता नहीं है। यदि हम जिन नियमों की तलाश कर रहे हैं वे स्थिर, सुचारू गणित से बने हैं, तो एक कंप्यूटर सीमित डेटा के साथ उन्हें खोज सकता है।
चेतावनी: पेपर यह नहीं कहता कि फॉर्मूला खोजना आसान है। यह केवल यह कहता है कि एक बार जब आपके पास सही संरचना हो, तो उसे सीखना संभव है। अरबों संभावित लेगो आकारों में से खोजने का "कठिन हिस्सा" अभी भी एक कंप्यूटर की गति की समस्या है, न कि डेटा की समस्या।

संक्षेप में:
पेपर हमें बताता है कि वैज्ञानिक फॉर्मूले खोजने की "सांख्यिकीय कठिनाई" संभावित फॉर्मूलों की विशाल संख्या के बारे में नहीं है। यह इस बारे में है कि गणित कितना "डगमगाता" (wobbly) है। यदि गणित स्थिर है, तो हम अपेक्षाकृत छोटे डेटासेट के साथ भी गहरे, जटिल नियमों को खोज सकते हैं। कंप्यूटर को बस इतना डेटा चाहिए ताकि डगमगाते हुए टॉवर को गिरने से बचाया जा सके।

तकनीकी सारांश: वैज्ञानिक खोज की नमूना जटिलता (Sample Complexity)

समस्या विवरण
प्रतीकात्मक प्रतिगमन (Symbolic Regression - SR) के माध्यम से वैज्ञानिक खोज को अक्सर सांख्यिकीय और गणनात्मक रूप से अव्यवहार्य (intractable) माना जाता है। प्रचलित दृष्टिकोण यह सुझाव देता है कि प्रतीकात्मक अभिव्यक्तियों का परिकल्पना स्थान (hypothesis space) गहराई के साथ संयोजन संबंधी (combinatorially) रूप से बढ़ता है, जिससे इष्टतम अभिव्यक्तियों की खोज NP-hard हो जाती है और ऐसे मॉडलों का सांख्यिकीय सामान्यीकरण (statistical generalization) अविश्वसनीय हो जाता है। यह शोध पत्र कम्प्यूटेशनल कठिनाई और सांख्यिकीय सीखने की क्षमता (statistical learnability) के बीच के भ्रम को चुनौती देता है। यह तर्क देता है कि हालांकि इष्टतम प्रतीकात्मक संरचना खोजना कम्प्यूटेशनल रूप से कठिन है, लेकिन कंपोजिशनल फंक्शन ट्रीज़ का सांख्यिकीय सामान्यीकरण सुव्यवस्थित हो सकता है यदि अंतर्निहित ऑपरेटरों में स्थिरता (stability) के गुण हों। मुख्य प्रश्न यह है कि क्या कंपोजिशनल ऑपरेटर ट्रीज़ को सीखने की नमूना जटिलता (sample complexity) गहराई के साथ तेजी से (exponentially) बढ़ती है, या यह ऑपरेटरों की स्थिरता (Lipschitzness) और ट्री की गहराई द्वारा नियंत्रित होती है।

कार्यप्रणाली
लेखक समस्या को प्रोबेबली एप्रोक्सिमेटली करेक्ट (PAC) लर्निंग थ्योरी के लेंस से देखते हैं, विशेष रूप से सामान्यीकरण त्रुटि (generalization error) को सीमित करने के लिए रेडमेकर कॉम्प्लेक्सिटी (Rademacher complexity) का उपयोग करते हैं।

परिकल्पना स्थान की परिभाषा: अध्ययन एक कंपोजिशनल परिकल्पना स्थान, $H^d_{comp}$ को परिभाषित करता है, जो गहराई $d$ के रूटेड ऑपरेटर ट्रीज़ से बना है। आंतरिक नोड्स एक सीमित शब्दावली से लिए गए हैं जो स्मूथ और डिफरेंशिएबल ऑपरेटरों ( $H_{base}$ ) से बनी है, जैसे कि $\{+, \times, \sin, \cos, \exp\}$ और एफाइन मैप्स। लीव्स (leaves) या तो इनपुट कोऑर्डिनेट्स हैं या बाउंडेड एफाइन फंक्शन्स हैं।
सैद्धांतिक ढांचा:
- लिप्सचिट्ज़ धारणाएं (Lipschitz Assumptions): विश्लेषण यह मानता है कि बेस ऑपरेटर्स प्रासंगिक डेटा रेंज पर स्थानीय रूप से लिप्सचिट्ज़ निरंतर (locally Lipschitz continuous) हैं, जिनके लिए स्थिरांक $L_h$ है। बाउंडिंग के लिए एक ग्लोबल लिप्सचिट्ज़ स्थिरांक $L = \max L_h$ का उपयोग किया गया है।
- रेडमेकर कॉम्प्लेक्सिटी: लेखक एम्पिरिकल रेडमेकर कॉम्प्लेक्सिटी, $R_n(H^d_{comp})$ पर बाउंड प्राप्त करने के लिए सीमाएं निर्धारित करते हैं। वे क्लासिकल कॉन्ट्रैक्शन आर्गुमेंट्स (Ledoux & Talagrand, 1991) और वेक्टर कॉन्ट्रैक्शन इनइक्वेलिटीज (Maurer, 2016) को ट्री-स्ट्रक्चर्ड कंपोजिशन के लिए विस्तारित करते हैं।
- रिकर्सिव बाउंड्स: सीमित ऑपरेटर शब्दावली ( $K = |H_{base}|$ ) पर यूनियन बाउंड लागू करके और $b$ बच्चों (जहाँ $b$ अरिटी है) के कंपोजिशन के लिए वेक्टर कॉन्ट्रैक्शन का उपयोग करके, लेखक गहराई $d$ और गहराई $d-1$ के बीच एक रिकर्सिव संबंध स्थापित करते हैं।
प्रायोगिक सत्यापन:
- सिंथेटिक डेटा: लेखकों ने नियंत्रित गहराई ( $d \in \{1, 2, 3, 4\}$ ) और ज्ञात ग्राउंड-ट्रुथ स्ट्रक्चर के साथ सिंथेटिक "फिजिक्स-लाइक" टारगेट्स उत्पन्न करने के लिए एक मॉड्यूलर PyTorch कोडबेस बनाया।
- डिफरेंशिएबल ट्रीज़: जेनेटिक प्रोग्रामिंग या डिस्क्रीट सर्च के बजाय, उन्होंने ऑपरेटरों के गुणांकों (coefficients) को फिट करने के लिए ग्रेडिएंट डिसेंट (Adam) का उपयोग करके डिफरेंशिएबल ऑपरेटर ट्रीज़ (MLP नहीं) को प्रशिक्षित किया।
- मेट्रिक्स: उन्होंने जनरललाइजेशन गैप (टेस्ट MSE बनाम ट्रेन MSE) को मापा और इसकी तुलना सैद्धांतिक कॉम्प्लेक्सिटी टर्म $(bL^d)/\sqrt{n}$ से की, जहाँ $\hat{L}$ ग्रेडिएंट नॉर्म्स से प्राप्त लिप्सचिट्ज़ स्थिरांक का एक एम्पिरिकल एस्टिमेटर है।

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

SR की सांख्यिकीय सीखने की क्षमता: यह शोध पत्र सिद्ध करता है कि कंपोजिशनल ट्रीज़ की सामान्यीकरण क्षमता (generalization capacity) अलग-अलग प्रतीकात्मक संरचनाओं की संख्या के साथ आवश्यक रूप से विस्फोट नहीं करती है। इसके बजाय, यह ऑपरेटरों के लिप्सचिट्ज़ स्थिरांक और गहराई $d$ द्वारा शासित होती है।
स्पष्ट जटिलता बाउंड्स: लेखक एक ठोस ऊपरी सीमा (upper bound) प्राप्त करते हैं:
$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$
परिणामस्वरूप, अतिरिक्त जोखिम (excess risk) $O(L^d / \sqrt{n})$ के रूप में स्केल करता है जब शब्दावली आकार $K$ और अरिटी $b$ को स्थिरांक माना जाता है। यह उन बाउंड्स के विपरीत है जो डिस्क्रीट सिंटैक्स स्पेस की कार्डिनैलिटी पर निर्भर करते हैं।
खोज और अनुमान का पृथक्करण: यह कार्य डिस्क्रीट ऑप्टिमाइजेशन समस्या (ट्री स्ट्रक्चर की खोज) को निरंतर रिग्रेशन समस्या (गुणांकों को फिट करना) से औपचारिक रूप से अलग करता है। प्राप्त बाउंड्स दूसरे भाग पर लागू होते हैं, जिससे यह स्पष्ट होता है कि एक स्ट्रक्चर प्रस्तावित होने के बाद किस प्रकार के सांख्यिकीय स्केलिंग की अपेक्षा की जानी चाहिए।
प्रायोगिक सहसंबंध: प्रयोगों से पता चलता है कि देखे गए जनरललाइजेशन गैप और प्रेडिक्टेड कॉम्प्लेक्सिटी टर्म $(bL^d)/\sqrt{n}$ के बीच एक सकारात्मक सहसंबंध है। डेटा दिखाता है कि जबकि गैप गहराई (लिप्सचिट्ज़ स्थिरांक के संचय के कारण) और नमूना आकार ( $1/\sqrt{n}$ ) के साथ बदलता है, इसका स्केलिंग सैद्धांतिक भविष्यवाणी के अनुरूप है।

परिणाम

सैद्धांतिक: थ्योरम 4.9 स्थापित करता है कि बाउंडेड आउटपुट्स और लिप्सचिट्ज़ ऑपरेटर्स के लिए, अतिरिक्त जोखिम $1/\sqrt{n}$ के रूप में घटता है, जिसमें स्थिरांक कारक लिप्सचिट्ज़ स्थिरांकों के गुणन के माध्यम से गहराई के साथ घातीय (exponentially) रूप से निर्भर करता है। कोरोलरी 4.11 इसे एक PAC सैंपल कॉम्प्लेक्सिटी बाउंड में अनुवादित करता है, जो दिखाता है कि सैंपल कॉम्प्लेक्सिटी पेड़ों की कॉम्बिनेटोरियल गिनती के बजाय $L^{2d}$ के साथ स्केल करती है।
प्रायोगिक: गहराई ( $d$ $d$ ) और नमूना आकार ( $n$ $n$ ) को बदलने वाले 400 प्रायोगिक रन के माध्यम से, जनरललाइजेशन गैप को सैद्धांतिक टर्म के साथ ट्रैक करने वाला पाया गया।
- उथले डेप्थ ( $d=1, 2$ ) के लिए, लिप्सचिट्ज़ प्रॉक्सी $\hat{L}$ स्थिर रहा, और गैप मुख्य रूप से $1/\sqrt{n}$ के साथ स्केल हुआ।
- $\exp$ जैसे नॉन-लीनियरिटी वाले गहरे कंपोजिशन ( $d=3, 4$ ) के लिए, $\hat{L}$ बढ़ गया, जिससे बड़े गैप मिले, जो स्थिरता स्थिरांकों के मल्टीप्लिकेटिव संचय के अनुरूप है।
- लॉग-लॉग स्केल पर पावर-लॉ फिट ने 0.48 का सहसंबंध दिया, जो इंगित करता है कि कंपोजिशनल कॉम्प्लेक्सिटी टर्म जनरललाइजेशन गैप के वेरिएंस के एक सार्थक हिस्से को कैप्चर करता है, हालांकि अन्य कारक (ऑप्टिमाइजेशन एरर, नॉइज़) भी भूमिका निभाते हैं।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह सिम्बोलिक रिग्रेशन का उपयोग करके वैज्ञानिक खोज के लिए एक "लर्नैबिलिटी सर्टिफिकेट" प्रदान करता है। इसका प्राथमिक महत्व प्रतीकात्मक संरचनाओं के कॉम्बिनेटोरियल विस्फोट से हटकर ऑपरेटरों की कंपोजिशनल स्थिरता (compositional stability) की ओर जाने में निहित है।

छोटे डेटा से खोज की व्यवहार्यता: लेखक तर्क देते हैं कि स्थिर ऑपरेटर वोकैबुलरी और मध्यम गहराई के लिए, छोटे डेटासेट से वैज्ञानिक खोज सांख्यिकीय रूप से व्यवहार्य है। सांख्यिकीय सामान्यीकरण बाधा नहीं है; बल्कि, चुनौती संरचनाओं के लिए कम्प्यूटेशनल सर्च और इंडक्टिव बायस (inductive biases) का डिज़ाइन करना है।
स्केलिंग का स्पष्टीकरण: यह कार्य स्पष्ट करता है कि नॉन-लीनियर गुणांक अनुमान (coefficient estimation) का सांख्यिकीय स्केलिंग कंप्यूटेशन ग्राफ के साथ लिप्सचिट्ज़ स्थिरांकों के संचय द्वारा निर्धारित होता है, न कि संभावित ट्री शेप्स की गणना द्वारा।
सीमाएं: लेखक विनम्रतापूर्वक नोट करते हैं कि उनके गारंटी यूनिफॉर्म बाउंड्स हैं और वे ऑकम के रेज़र (Occam's razor) का उतना प्रभावी ढंग से उपयोग नहीं करते जितना कि PAC-बायेस दृष्टिकोण कर सकते हैं। इसके अलावा, प्रायोगिक सत्यापन नियंत्रित, इन-डिस्ट्रीब्यूशन सिंथेटिक डेटा पर निर्भर करता है; डिस्ट्रीब्यूशन शिफ्ट या मिसस्पेसिफिकेशन के तहत व्यवहार इस बाउंड द्वारा गारंटीकृत नहीं है। $\hat{L}$ एस्टिमेटर फिट किए गए मैप पर स्थिरता को मापता है, न कि वर्स्ट-केस ग्लोबल कांस्टेंट को प्रमाणित करता है।

निष्कर्षतः, यह शोध पत्र दावा करता है कि जब सिम्बोलिक रिग्रेशन मॉडल्स को स्थिर प्रिमिटिव्स वाले कंपोजिशनल फंक्शन ट्रीज़ के रूप में देखा जाता है, तो उनमें अनुकूल सांख्यिकीय गुण होते हैं जो सीमित डेटा के साथ भी सामान्यीकरण की अनुमति देते हैं, बशर्ते कि गहराई और ऑपरेटर स्थिरता को प्रबंधित किया जाए।

1. "लेगो टॉवर" बनाम "डगमगाता हुआ ढेर"

2. "रिपल इफेक्ट" (गहराई और जटिलता)

3. "फिजिक्स लैब" प्रयोग

4. "वैज्ञानिक खोज" के लिए इसका क्या अर्थ है

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