🤖 machine learning

Tropical Circuits with Scalar Multiplication Gates

यह शोध पत्र अधिकतम भार वाले निर्देशित स्पैनिंग ट्री और द्विपक्षीय पूर्ण मिलान (bipartite perfect matchings) की गणना करने के लिए स्केलर गुणन गेट्स वाले ट्रॉपिकल सर्किटों के लिए घातीय निचली सीमाएं (exponential lower bounds) स्थापित करता है, जो यह प्रदर्शित करता है कि न्यूरल नेटवर्क में उत्तलता बाधाओं (convexity constraints) को लागू करना उनके अनियंत्रित समकक्षों की तुलना में घातीय रूप से बड़े मॉडलों को आवश्यक बना सकता है।

मूल लेखक: Christoph Hertrich, Moritz Stargalla

प्रकाशित 2026-07-14

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

CC BY 4.0

मूल लेखक: Christoph Hertrich, Moritz Stargalla

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

कल्पना कीजिए कि आप लेगो ब्रिक्स (Lego bricks) से एक विशाल, सुपर-स्मार्ट कैलकुलेटर बना रहे हैं। कंप्यूटर विज्ञान की दुनिया में, इन कैलकुलेटरों को सर्किट (circuits) कहा जाता है। आमतौर पर, ये सर्किट दो मुख्य प्रकार के ईंटों से बने होते हैं: एक जो संख्याओं को जोड़ते हैं और दूसरे जो एक सूची में से सबसे बड़ी संख्या चुनते हैं। इसे हम "ट्रोपिकल सर्किट" (tropical circuit) कहते हैं।

लेकिन क्या होगा अगर हम इन कैलकुलेटर्स को एक सुपरपावर दे दें? क्या होगा अगर हम इसमें एक विशेष ईंट जोड़ दें जो किसी संख्या को तुरंत एक धनात्मक स्थिरांक (positive constant) से गुणा कर सके, जैसे कि सिर्फ एक हिस्सा जोड़ने से 2 को सीधे 500 में बदल देना? इस पेपर के लेखक, क्रिस्टोफ हर्ट्रिच और मोरिट्ज़ स्टारगाला ने ठीक यही परीक्षण करने का निर्णय लिया। उन्होंने एक नया प्रकार का कैलकुलेटर बनाया जिसे स्केलर ट्रोपिकल सर्किट (STC) कहा जाता है और उन्होंने एक सरल प्रश्न पूछा: क्या यह नया "गुणा करने वाला सुपरपावर" कैलकुलेटर को काफी स्मार्ट या छोटा बनाता है?

बड़ी खोज: सुपरपावर ज्यादातर बेकार है

टीम ने एक आश्चर्यजनक तथ्य सिद्ध किया: नहीं, सुपरपावर ज्यादा मदद नहीं करता है।

इन शानदार गुणा वाली ईंटों के साथ भी, कैलकुलेटर को दो बहुत विशिष्ट, कठिन पहेलियों को हल करने के लिए घातांकीय रूप से विशाल (exponentially huge) होना पड़ेगा:

परफेक्ट मैच (The Perfect Match): दो समूहों के लोगों को आपस में जोड़ने का सबसे अच्छा तरीका खोजना (जैसे कि डांसर्स को मैच करना) ताकि हर कोई खुश हो।
ट्री बिल्डर (The Tree Builder): एक ऐसा वन-वे रोड नेटवर्क बनाने का सबसे अच्छा तरीका खोजना जो हर शहर को एक केंद्रीय केंद्र से बिना किसी लूप के जोड़ता हो।

लेखकों ने दिखाया कि इन विशिष्ट समस्याओं के लिए, गुणा करने वाली ईंटें जोड़ने से कैलकुलेटर छोटा नहीं होता है। इसे अभी भी इतने चरणों की आवश्यकता होती है जो $2^{\Omega(n)}$ की तरह बढ़ता है। इसे समझने के लिए, यदि समस्या का आकार थोड़ा भी बढ़ता है, तो आवश्यक कैलकुलेटर का आकार अरबों, ट्रिलियनों और उससे भी आगे निकल जाता है। यह एक ऐसे हथौड़े के साथ गगनचुंबी इमारत बनाने की कोशिश करने जैसा है जो कीलों को सोने में बदल सकता है; यह सुनने में अच्छा लगता है, लेकिन टावर बनाने के लिए आपको अभी भी पहाड़ों के बराबर कीलों की आवश्यकता होगी।

"ब्रेन" कंप्यूटर्स (न्यूरल नेटवर्क) के लिए इसका क्या अर्थ है

यह केवल लेगो कैलकुलेटरों के बारे में नहीं है; यह न्यूरल नेटवर्क (Neural Networks) के बारे में है, जो AI के पीछे के "दिमाग" हैं।

एक मानक न्यूरल नेटवर्क को एक लचीले कलाकार के रूप में सोचें जो किसी भी चित्र को बना सकता है, भले ही इसके लिए उसे नकारात्मक संख्याओं (चित्र के कुछ हिस्सों को मिटाने) का उपयोग करना पड़े। लेकिन कभी-कभी, हम चाहते हैं कि AI एक "मोनोटोन" (monotone) कलाकार हो—एक ऐसा जो केवल रंग भरता है और कभी मिटाता नहीं है। यह इसलिए उपयोगी है क्योंकि यह AI के निर्णयों को समझने में आसान और भरोसेमंद बनाता है। इन्हें इनपुट-कॉन्वेक्स न्यूरल नेटवर्क (ICNNs) कहा जाता है।

यह पेपर सिद्ध करता है कि "परफेक्ट मैच" और "ट्री बिल्डर" पहेलियों के लिए, यह "मोनोटोन" कलाकार, लचीले कलाकार की तुलना में घातांकीय रूप से कम कुशल (exponentially less efficient) है।

एक लचीला कलाकार "ट्री बिल्डर" पहेली को अपेक्षाकृत छोटे नेटवर्क (लगभग $O(n^3)$ आकार) के साथ हल कर सकता है।
हालांकि, एक मोनोटोन कलाकार को ठीक वही काम करने के लिए एक घातांकीय रूप से बड़े ( $2^{\Omega(n)}$ ) नेटवर्क की आवश्यकता होती है।

लेखक इस बारे में बहुत स्पष्ट हैं: उन्होंने सिद्ध किया है कि इन विशिष्ट कार्यों के लिए, AI को "मोनोटोन" (या कॉनवेक्स) होने के लिए मजबूर करना, आकार के मामले में इसे नाटकीय रूप से कम शक्तिशाली बना देता है। यह केवल एक हाथ का उपयोग करके उत्कृष्ट कृति पेंट करने की कोशिश करने जैसा है; आप यह कर सकते हैं, लेकिन समान परिणाम प्राप्त करने के लिए आपको एक शहर के आकार के कैनवास की आवश्यकता होगी।

उन्होंने क्या खारिज किया (और क्या नहीं)

पेपर सावधानीपूर्वक अपनी सीमाओं को स्पष्ट करता है।

उन्होंने यह विचार खारिज कर दिया कि गुणा गेट्स (multiplication gates) ट्रोपिकल सर्किटों को इन विशिष्ट समस्याओं को छोटा करने के लिए पर्याप्त शक्तिशाली बनाते हैं। उन्होंने सिद्ध किया कि इन दो मामलों के लिए, आकार विशाल ही रहता है।
उन्होंने यह खारिज नहीं किया कि गुणा गेट्स अन्य प्रकार की समस्याओं में मदद कर सकते हैं। उन्होंने वास्तव में पूछा, "क्या कोई ऐसी समस्या है जहाँ ये गेट मदद करते हैं?" और स्वीकार किया कि वे अभी नहीं जानते।
उन्होंने यह रहस्य हल नहीं किया कि क्या एक मानक "लचीला" न्यूरल नेटवर्क (जो घटाव कर सकता है) "परफेक्ट मैच" समस्या को कुशलतापूर्वक हल कर सकता है। उन्होंने सिद्ध किया कि "मोनोटोन" संस्करण बहुत बड़ा है, लेकिन उन्होंने "लचीले" संस्करण के लिए संभावना का द्वार खुला रखा है। यह अभी भी एक रहस्य है कि क्या इस विशिष्ट पहेली के लिए एक पॉलीनोमियल-साइज़ वाला लचीला नेटवर्क मौजूद है।

वे कितने आश्वस्त हैं?

लेखकों ने केवल अनुमान नहीं लगाया या सिमुलेशन नहीं चलाया। उन्होंने कठोर गणितीय प्रमाणों का उपयोग करके यह दिखाया कि इन विशिष्ट कार्यों के लिए एक छोटा कैलकुलेटर बनाना असंभव है, भले ही उसमें गुणा करने का सुपरपावर हो।

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

निष्कर्ष

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

तकनीकी सारांश: स्केलर मल्टीप्लिकेशन गेट्स के साथ ट्रॉपिकल सर्किट्स (Tropical Circuits with Scalar Multiplication Gates)

समस्या विवरण (Problem Statement)

यह शोध पत्र स्केलर ट्रॉपिकल सर्किट्स (STCs) की कम्प्यूटेशनल शक्ति की जांच करता है, जो कि एक ऐसा मॉडल है जो मानक ट्रॉपिकल (max-plus) सर्किट्स का विस्तार करता है और इसमें धनात्मक वास्तविक स्थिरांकों (positive real constants) द्वारा गुणा करने वाले गेट्स की अनुमति दी जाती है। मानक ट्रॉपिकल सर्किट्स केवल max और + गेट्स का उपयोग करते हैं और उन्हें शुद्ध डायनेमिक प्रोग्राम्स को मॉडल करने के लिए जाना जाता है। यह स्थापित है कि न्यूरल नेटवर्क (विशेष रूप से ReLU और maxout नेटवर्क) ट्रॉपिकल सर्किट्स की तुलना में काफी अधिक शक्तिशाली हैं—मुख्यतः ऋणात्मक भार (negative weights) के माध्यम से घटाव (subtraction) को लागू करने की उनकी क्षमता के कारण—लेकिन स्केलर मल्टीप्लिकेशन (घटाव के बिना) के विशिष्ट योगदान से कम्प्यूटेशनल शक्ति में होने वाले बदलाव पर प्रश्न अनसुलझा रहा है।

केंद्रित समस्या यह है कि क्या धनात्मक स्थिरांकों के साथ स्केलर मल्टीप्लिकेशन की अनुमति देने से विशिष्ट पॉलीटोप्स (polytopes) के सपोर्ट फंक्शन्स (support functions) को कंप्यूट करने के लिए आवश्यक सर्किट आकार में महत्वपूर्ण कमी आती है, विशेष रूप से वे जिनमें 0-1 गुणांक (multilinear tropical polynomials) होते हैं। विशेष रूप से, लेखक पूछते हैं: क्या ऐसे पॉलीटोप्स मौजूद हैं जिनका एक्सटेंशन कॉम्प्लेक्सिटी (extension complexity) बहुपद (polynomial) है, लेकिन जिन्हें कंप्यूट करने के लिए घातांकीय (exponential) आकार के STCs की आवश्यकता होती है?

कार्यप्रणाली (Methodology)

1. मॉडल परिभाषा (Model Definition)

लेखक एक STC को तीन प्रकार के गेट्स वाले एक निर्देशित अचक्रीय ग्राफ (directed acyclic graph) के रूप में परिभाषित करते हैं:

Max गेट्स: $\max(u, w)$ की गणना करते हैं।
Plus गेट्स: $u + w$ की गणना करते हैं।
Scalar गेट्स: $\lambda u$ की गणना करते हैं जहाँ $\lambda \in \mathbb{R}_{>0}$ एक स्थिरांक है।
एक STC का आकार max और + गेट्स की संख्या द्वारा परिभाषित किया जाता है, जिसमें स्केलर गेट्स को शामिल नहीं किया जाता है।

2. ज्यामितीय द्वैतता (Geometric Duality)

यह विश्लेषण सपोर्ट फंक्शन्स और पॉलीटोप्स के बीच द्वैतता (duality) पर आधारित है। एक STC जो फलन $f$ को कंप्यूट करता है, वह एक पॉलीटोप $P$ (न्यूटन पॉलीटोप) के निर्माण के अनुरूप होता है ताकि $f$ , $P$ का सपोर्ट फंक्शन हो।

max गेट्स पॉलीटोप्स के यूनियन के कॉनवेक्स हल (convex hull) के अनुरूप होते हैं: $P_{max} = \text{conv}(P_u \cup P_w)$ ।
+ गेट्स मिंकोव्स्की सम (Minkowski sum) के अनुरूप होते हैं: $P_{+} = P_u + P_w$ ।
स्केलर गेट्स डायलेशन (dilation) के अनुरूप होते हैं: $P_{\lambda} = \lambda P_u$ ।

3. अपघटन लेम्मा (Decomposition Lemma - सामान्य निचला स्तर रणनीति)

मुख्य तकनीकी योगदान एक सामान्यीकृत अपघटन लेम्मा (लेम्मा 3.5) है जिसे STCs के लिए अनुकूलित किया गया है। मानक ट्रॉपिकल सर्किट्स के विपरीत जहाँ न्यूटन पॉलीटोप में केवल पूर्णांक वर्टिक्स (integral vertices) होते हैं, STCs गैर-पूर्णांक वर्टिक्स वाले पॉलीटोप्स भी उत्पन्न कर सकते हैं।
लेम्मा बताता है कि यदि एक पॉलीटोप $Q$ को आकार $t$ वाले STC द्वारा कंप्यूट किया जाता है, तो $Q$ को इस प्रकार अपघटित किया जा सकता है:
$Q = \text{conv}\left(A_0 \cup \bigcup_{i=1}^k (A_i + B_i)\right)$
जहाँ $k \le t$ , और पॉलीटोप्स $A_i$ एक चुने गए माप $\mu$ के संबंध में "सरल" (simple) हैं। माप $\mu$ को मिंकोव्स्की सम और कॉनवेक्स हल के तहत उप-योगात्मक (sub-additivity) गुण प्रदर्शित करने चाहिए।

4. माप चयन (Measure Selection)

निचले स्तर (lower bounds) को सिद्ध करने के लिए, लेखक लक्षित पॉलीटोप्स के लिए विशेष रूप से तैयार किए गए विशिष्ट मापों $\mu$ का निर्माण करते हैं। रणनीति यह दिखाने की है कि ऊपर दिए गए किसी भी अपघटन के लिए बड़ी संख्या में पद ( $k$ ) की आवश्यकता होगी क्योंकि एक एकल मिंकोव्स्की सम $A_i + B_i$ (जहाँ $A_i$ "सरल" है) लक्षित पॉलीटोप के वर्टिक्स का केवल एक छोटा हिस्सा ही धारण कर सकता है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

1. STCs के लिए घातांकीय निचले स्तर (Exponential Lower Bounds for STCs)

यह शोध पत्र सिद्ध करता है कि स्केलर मल्टीप्लिकेशन दो मौलिक कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्याओं के लिए सर्किट्स के आकार को महत्वपूर्ण रूप से कम नहीं करता है:

बर्कहॉफ पॉलीटोप ( $P_{PERM}$ ): एक पूर्ण द्विपक्षीय ग्राफ $K_{n,n}$ में परफेक्ट मैचिंग्स का कॉनवेक्स हल।
- परिणाम: $P_{PERM}$ का सपोर्ट फंक्शन कंप्यूट करने वाले किसी भी STC को $\Omega(2^n)$ प्लस गेट्स की आवश्यकता होती है (थ्योरम 1.1)।
- संदर्भ: जबकि $P_{PERM}$ की एक्सटेंशन कॉम्प्लेक्सिटी बहुपद ( $O(n^2)$ ) है, STC का आकार घातांकीय है। यह दर्शाता है कि एक्सटेंशन कॉम्प्लेक्सिटी पर आधारित निचला स्तर घातांकीय रूप से ढीला (loose) हो सकता है।
डायरेक्टेड स्पैनिंग ट्री पॉलीटोप ( $P_{DST}$ ): एक पूर्ण निर्देशित ग्राफ में नोड $n$ पर रूटेड अर्बोरेसेन्सेस (arborescences) का कॉनवेक्स हल।
- परिणाम: यह मानक ट्रॉपिकल सर्किट्स के लिए जेरूम और स्निर [JS82] के क्लासिक परिणाम को स्केलर केस के लिए विस्तारित करता है। किसी भी STC को $P_{DST}$ का सपोर्ट फंक्शन कंप्यूट करने के लिए $\Omega(2^n)$ प्लस गेट्स की आवश्यकता होती है (थ्योरम 1.2)।

2. मोनोटोन और नॉन-मोनोटोन न्यूरल नेटवर्क का पृथक्करण (Separation of Monotone and Non-Monotone Neural Networks)

लेखक न्यूरल नेटवर्क के संबंध में उप-निष्कर्ष (corollaries) प्राप्त करते हैं:

परिभाषाएं:
- $nnc(P) $:$ f_P$ को कंप्यूट करने वाले रैंक-2 मैक्सआउट नेटवर्क का न्यूनतम आकार।
- $mnnc(P) $:$ f_P$ को कंप्यूट करने वाले न्यूनतम आकार के रैंक-2 मैक्सआउट इनपुट-कॉन्वेक्स न्यूरल नेटवर्क (ICNN) (केवल इनपुट किनारों पर मोनोटोन भार की अनुमति) का आकार।
उप-निष्कर्ष 1.3: $mnnc(P_{PERM}) \in 2^{\Omega(n)}$ ।
उप-निष्कर्ष 1.4: डायरेक्टेड स्पैनिंग ट्री पॉलीटोप के लिए, $nnc(P_{DST}) \in O(n^3)$ (बहुपद) जबकि $mnnc(P_{DST}) \in 2^{\Omega(n)}$ (घातांकीय) है।
महत्व: यह मोनोटोन (ICNN) और नॉन-मोनोटोन न्यूरल नेटवर्क के बीच एक घातांकीय आकार पृथक्करण स्थापित करता है। यह सिद्ध करता है कि कॉन्वेक्सिटी बाधाओं (जैसे ICNN में) को लागू करने से समान कार्यों को प्रदर्शित करने के लिए अनियंत्रित नेटवर्क की तुलना में घातांकीय रूप से बड़े नेटवर्क की आवश्यकता हो सकती है।

3. STCs द्वारा मोनोटोन नेटवर्क का सिमुलेशन (Simulation of Monotone Networks by STCs)

प्रमाण का एक महत्वपूर्ण चरण लेम्मा 3.3 है, जो यह दिखाता है कि आकार $s$ वाला एक बायस-मुक्त मोनोटोन रैंक- $k$ मैक्सआउट नेटवर्क, आकार $O(s^2)$ वाले STC द्वारा सिम्युलेट किया जा सकता है। यह STCs के लिए प्राप्त निचले स्तरों को सीधे मोनोटोन मैक्सआउट नेटवर्क पर स्थानांतरित करने की अनुमति देता है।

महत्व और दावे (Significance and Claims)

लेखक निम्नलिखित महत्व का दावा करते हैं:

स्केलर मल्टीप्लिकेशन की सीमाएं: यह प्रदर्शित करता है कि 0-1 गुणांकों वाले कार्यों (0-1 पॉलीटोप्स के सपोर्ट फंक्शन्स) के लिए, धनात्मक स्केलर द्वारा गुणा करने की क्षमता मानक ट्रॉपिकल सर्किट्स की तुलना में सर्किट आकार में कोई महत्वपूर्ण लाभ प्रदान नहीं करती है।
डायनेमिक प्रोग्रामिंग की सीमाएं: परिणाम दर्शाते हैं कि "शुद्ध" डायनेमिक प्रोग्राम, जिन्हें धनात्मक स्केलर मल्टीप्लिकेशन के साथ बढ़ाया गया है, अधिकतम भार वाले डायरेक्टेड स्पैनिंग ट्री और बाइपार्टाइट परफेक्ट मैचिंग समस्याओं को हल करने के लिए अभी भी घातांकीय पुनरावृत्तियों (iterations) की आवश्यकता रखते हैं।
न्यूरल नेटवर्क सिद्धांत: यह कार्य इस अवलोकन को एक कठोर सैद्धांतिक औचित्य प्रदान करता है कि इनपुट-कॉन्वेक्स न्यूरल नेटवर्क (ICNN) अक्सर अनियंत्रित मॉडलों की तुलना में खराब प्रदर्शन करते हैं या अधिक संसाधनों की आवश्यकता रखते हैं। यह सिद्ध करता है कि विशिष्ट प्रकार के कार्यों (जैसे डायरेक्टेड स्पैनिंग ट्री से संबंधित) के लिए, मोनोटोन/कॉन्वेक्स आर्किटेक्चर तक सीमित करना नेटवर्क के आकार में घातांकीय वृद्धि (exponential blow-up) को मजबूर करता है।
लोअर बाउंड तकनीकों का परिशोधन: यह पेपर एक पॉलीटोपल अपघटन तकनीक पेश करता है जो गैर-पूर्णांक वर्टिक्स को संभालती है, जिससे अंकगणितीय और ट्रॉपिकल सर्किट्स के लिए उपयोग की जाने वाली पिछली विधियों का सामान्यीकरण होता है।

सीमाएं और खुले प्रश्न (Limitations and Open Questions)

लेखक विनम्रतापूर्वक नोट करते हैं कि हालांकि वे घातांकीय निचले स्तर सिद्ध करते हैं, लेकिन घातांक में स्थिरांक (constants) मानक ट्रॉपिकल सर्किट्स (जैसे बर्कहॉफ पॉलीटोप के लिए $2^{0.91 \dots n}$ बनाम $2^n$ ) की तुलना में कमजोर हैं। वे यह भी रेखांकित करते हैं कि यह एक खुला प्रश्न बना हुआ है कि क्या अनडायरेक्टेड (undirected) स्पैनिंग ट्री पॉलीटोप के लिए बहुपद-आकार के STCs मौजूद हैं, क्योंकि डायरेक्टेड केस के लिए उपयोग की जाने वाली तकनीकें उन कॉम्बिनेटरियल संरचनाओं पर निर्भर करती हैं जो स्केलर मल्टीप्लिकेशन के साथ बनी न रहें। इसके अलावा, यह भी एक खुला प्रश्न है कि क्या परमानेंट (permanent) के लिए बहुपद-आकार के (max, +, -) सर्किट्स मौजूद हैं (और इस प्रकार क्या $nnc(P_{PERM})$ बहुपद है)।