🤖 machine learning

Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

यह शोध पत्र क्रम-अपरिवर्तनीय (permutation-invariant) न्यूरल नेटवर्क के लिए सार्वभौमिकता (universality) सुनिश्चित करने हेतु आवश्यक एम्बेडिंग आयाम (embedding dimension) पर नए निम्नतम सीमा (lower bounds) स्थापित करता है, विशेष रूप से डीप सेट्स (Deep Sets) के लिए एक स्थिरांक कारक (constant factor) तक सही न्यूनतम आयाम को सिद्ध करता है और $k > 1$ के लिए $k$ -ary जेनोसी पूलिंग (Janossy pooling) हेतु प्रथम गैर-तुच्छ निम्नतम सीमा (non-trivial lower bound) प्रदान करता है।

मूल लेखक: Ali Syed, Aditya Nambiar, Jonathan W. Siegel

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

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

CC BY 4.0

मूल लेखक: Ali Syed, Aditya Nambiar, Jonathan W. Siegel

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

कल्पना कीजिए कि आप एक कंप्यूटर को कंचों (marbles) के एक थैले को समझना सिखाने की कोशिश कर रहे हैं। इससे कोई फर्क नहीं पड़ता कि आप कंचों को किस क्रम में बाहर निकालते हैं (लाल, नीला, हरा) या किसी अन्य क्रम में (हरा, लाल, नीला); थैला वही रहता है। AI की दुनिया में, इसे परम्यूटेशन इनवेरिएंस (permutation invariance) कहा जाता है। कंप्यूटर को यह सीखना होगा कि कंचों का समूह (set) मायने रखता है, न कि वे किस क्रम में दिखाई देते हैं।

इसे करने के लिए, वैज्ञानिक डीप सेट्स (Deep Sets) और जैनोसी पूलिंग (Janossy Pooling) नामक विशेष न्यूरल नेटवर्क आर्किटेक्चर का उपयोग करते हैं। इसे दो चरणों वाली प्रक्रिया के रूप में सोचें:

एन्कोडर (अनुवादक - The Encoder): यह प्रत्येक कंचे (या कंचों के छोटे समूहों) को देखता है और उन्हें एक गुप्त कोड, या "एम्बेडिंग (embedding)" में अनुवादित करता है।
एग्रीगेटर (सारांशकर्ता - The Aggregator): यह अंतिम उत्तर बनाने के लिए उन सभी गुप्त कोडों को जोड़ देता है।

बड़ा सवाल यह है कि: उस गुप्त कोड की लंबाई कितनी होनी चाहिए?

यदि कोड बहुत छोटा है, तो कंप्यूटर भ्रमित हो जाएगा। वह यह सोच सकता है कि दो पूरी तरह से अलग कंचों के थैले एक ही हैं। यदि कोड पर्याप्त लंबा है, तो कंप्यूटर किसी भी दो अलग-अलग थैलों के बीच अंतर कर सकता है। इस शोध पत्र का उद्देश्य यह पता लगाना था कि किसी भी संभावित कंचों के थैले के लिए यह काम करने हेतु कोड की न्यूनतम लंबाई क्या होनी चाहिए।

समस्या: "बहुत छोटा" कोड

कल्पना कीजिए कि आपके पास 10 कंचों का एक थैला है, और आप उन्हें एक गुप्त कोड का उपयोग करके वर्णित करना चाहते हैं।

यदि आप केवल 1 अंक वाले कोड (0 या 1) का उपयोग करते हैं, तो आप केवल दो चीजों का वर्णन कर सकते हैं। आप 10 अलग-अलग कंचों को विशिष्ट रूप से वर्णित करने में सक्षम नहीं हो सकते।
यदि आप 10 अंकों का उपयोग करते हैं, तो आप शायद ऐसा कर सकें, लेकिन शायद तब नहीं जब कंचे जटिल हों (जैसे केवल रंगों के बजाय 3D वस्तुएं)।

यह पेपर सिद्ध करता है कि इस कोड की लंबाई पर एक कठिन गणितीय सीमा है। यदि आप इस सीमा से नीचे जाते हैं, तो आपका कंप्यूटर कितना भी स्मार्ट क्यों न हो, वह कुछ अलग-अलग थैलों के बीच अंतर करने में विफल रहेगा।

नई खोज: एक "टोपोलॉजिकल" ट्रिक

लेखकों ने बोर्सुक-उलमार्क प्रमेय (Borsuk-Ulam theorem) नामक एक चतुर गणितीय उपकरण का उपयोग किया। इसे सरल रूप में समझने के लिए, एक ग्लोब (पृथ्वी) की कल्पना करें। यह प्रमेय मूल रूप से कहता है: "यदि आप पृथ्वी को कुछ रंगों से पेंट करते हैं, तो हमेशा दो विपरीत बिंदु (जैसे उत्तरी और दक्षिणी ध्रुव) होंगे जिनका रंग एक जैसा होगा।"

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

उन्होंने क्या पाया

पेपर विशिष्ट नियम देता है कि कोड कितना लंबा होना चाहिए, जो दो चीजों पर आधारित है:

$n$ : थैले में वस्तुओं की संख्या (जैसे, 10 कंचे)।
$d$ : प्रत्येक वस्तु कितनी जटिल है (जैसे, एक साधारण संख्या बनाम एक 3D बिंदु जिसमें x, y और z निर्देशांक हैं)।

यहाँ उनके मुख्य निष्कर्ष सरल अंग्रेजी (हिंदी संदर्भ में) में दिए गए हैं:

1. सरल मामले के लिए (Deep Sets):
यदि कंप्यूटर कंचों को एक-एक करके देखता है (उनके बीच की परस्पर क्रिया को अनदेखा करते हुए), तो कोड की लंबाई कम से कम $d \times (n - 1)$ होनी चाहिए।

उपमा: यदि आपके पास 3D स्पेस में 10 कंचे हैं ( $d=3$ ), तो आपको कम से कम $3 \times 9 = 27$ अंकों वाले कोड की आवश्यकता है।
महत्व: इससे पहले, हम जानते थे कि कोड को कम से कम $n$ (10) होना चाहिए। यह पेपर सिद्ध करता है कि इसे वास्तव में बहुत लंबा (27) होने की आवश्यकता है क्योंकि कंचे 3D वस्तुएं हैं। यह उस अंतर को पाटता है जो हम जानते थे कि आवश्यक है और जो हम जानते थे कि पर्याप्त है।

2. जटिल मामले के लिए (Janossy Pooling):
यदि कंप्यूटर एक साथ कंचों के समूहों को देखता है (जैसे, जोड़े या त्रिक), तो गणित अधिक जटिल हो जाता है। लेखकों ने पहली बार एक गैर-तुच्छ (non-trivial) नियम सिद्ध किया है।

उन्होंने पाया कि कोड की लंबाई वस्तुओं की जटिलता और वस्तुओं की संख्या के साथ बढ़ती है, जो मोटे तौर पर इस सूत्र का पालन करती है: $(d \times n)^{1/k}$ , जहाँ $k$ समूह का आकार है।
उपमा: भले ही आप वस्तुओं को बेहतर ढंग से समझने के लिए कंचों के जोड़ों को देखने की अनुमति दें, आप एक बहुत छोटे कोड के साथ काम नहीं चला सकते। कोड अभी भी बढ़ना चाहिए जैसे-जैसे कंचे अधिक जटिल होते हैं या थैला बड़ा होता है।

"फिक्स्ड" बनाम "फ्लेक्सिबल" ट्रांसलेटर

पेपर एक सूक्ष्म लेकिन महत्वपूर्ण अंतर पर भी प्रकाश डालता है:

फिक्स्ड ट्रांसलेटर (Fixed Translator): यदि आप कंप्यूटर को हर समस्या के लिए एक ही अनुवाद नियम का उपयोग करने के लिए मजबूर करते हैं, तो कोड बहुत लंबा होना चाहिए (कम से कम $d \times n$ )।
फ्लेक्सिबल ट्रांसलेटर (Flexible Translator): यदि आप कंप्यूटर को विशिष्ट समस्या के आधार पर अपने अनुवाद नियमों को बदलने की अनुमति देते हैं, तो आप थोड़े छोटे कोड के साथ काम चला सकते हैं।
पेपर का परिणाम: इस लचीलेपन के साथ भी, लेखकों ने सिद्ध किया कि आप अभी भी उनके द्वारा गणना की गई सीमाओं से नीचे नहीं जा सकते। एक कठोर आधार (floor) मौजूद है।

सारांश

यह पेपर AI वास्तुकारों के लिए एक निर्माण निरीक्षक (construction inspector) की तरह है। यह कहता है: "आप एक ऐसा घर (न्यूरल नेटवर्क) नहीं बना सकते जो वस्तुओं के सेट को समझ सके यदि आप बहुत कम सामग्री (एम्बेडिंग डायमेंशन) का उपयोग करते हैं। हमने सटीक गणना की है कि आपको कितनी न्यूनतम सामग्री की आवश्यकता है ताकि यह गारंटी दी जा सके कि घर ढहेगा नहीं (विभिन्न इनपुट के बीच अंतर करने में विफल नहीं होगा)।"

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

तकनीकी सारांश: डीप सेट्स और जेनोसी पूलिंग की सार्वभौमिकता के लिए एम्बेडिंग आयाम निचली सीमाएँ

समस्या विवरण
यह शोध पत्र क्रमपरिवर्तनीय (permutation-invariant) न्यूरल नेटवर्क आर्किटेक्चर, विशेष रूप से 'डीप सेट्स' (Deep Sets) और इसके सामान्यीकरण 'जेनोसी पूलिंग' (Janossy pooling) में सार्वभौमिकता (universality) के सैद्धांतिक प्रश्न को संबोधित करता है। हालांकि यह स्थापित है कि ये आर्किटेक्चर किसी भी निरंतर क्रमपरिवर्तनीय फलन (continuous permutation-invariant function) को सन्निकट (approximate) कर सकते हैं, लेकिन एक महत्वपूर्ण खुला प्रश्न यह बना हुआ है: न्यूनतम एम्बेडिंग आयाम $M$ (लैटेंट आयाम) क्या होना चाहिए जो सार्वभौमिकता की गारंटी दे सके।

पिछले कार्यों ने पर्याप्त ऊपरी सीमाएँ (जैसे, $d > 1$ के लिए डीप सेट्स हेतु $M = 2nd + 1 $) प्रदान की हैं, और केवल विशिष्ट मामलों में ही आवश्यक निचली सीमाएँ (जैसे,$ d=1 $के लिए$ M \ge n $) दी हैं।$ d > 1 $के लिए डीप सेट्स के मामले में, एम्बिएंट आयाम$ d $के साथ बढ़ने वाली कोई निचली सीमा ज्ञात नहीं थी।$ k$-ary जेनोसी पूलिंग (जहाँ $k > 1$ ) के लिए भी कोई गैर-तुच्छ (non-trivial) निचली सीमा मौजूद नहीं थी। यह शोध पत्र स्केलर-आउटपुट केस ( $p=1$ ) पर केंद्रित है जहाँ एनकोडर $\Phi$ लक्षित फलन (target function) $f$ पर निर्भर हो सकता है, एक ऐसा सेटिंग जहाँ मानक एम्बेडिंग बाधाएँ सीधे लागू नहीं होती हैं।

कार्यप्रणाली (Methodology)
लेखक निचली सीमाओं पर निचली सीमा प्राप्त करने के लिए बोर्सुक-उलम प्रमेय (Borsuk-Ulam theorem) पर आधारित एक नवीन तकनीक पेश करते हैं। कार्यप्रणाली निम्नलिखित तार्किक चरणों के माध्यम से आगे बढ़ती है:

इंडेक्स्ड जेनोसी पूलिंग में न्यूनीकरण (Reduction to Indexed Janossy Pooling): लेखक पहले यह स्थापित करते हैं कि यदि मानक $k$ -ary जेनोसी आर्किटेक्चर सार्वभौमिक है, तो कार्यों का एक बड़ा वर्ग, जिसे "इंडेक्स्ड जेनोसी पूलिंग" कहा जाता है, भी सार्वभौमिक होना चाहिए। इस इंडेक्स्ड क्लास में, एनकोडर $\Phi$ को इनपुट टुपल $(i_1, \dots, i_k)$ के विशिष्ट इंडेक्स पर निर्भर करने की अनुमति है, न कि एक साझा फलन $\Phi(x_{i_1}, \dots, x_{i_k})$ पर। यह न्यूनीकरण लेखकों को इंडेक्स्ड क्लास के लिए निचली सीमा सिद्ध करने की अनुमति देता है, जो स्वतः ही मानक क्लास पर लागू होती है।
फाइनाइट-डिफरेंस रिजिडिटी (Finite-Difference Rigidity): एक प्रमुख लेम्मा सिद्ध किया गया है जो यह दर्शाता है कि एक इंडेक्स्ड जेनोसी लैटेंट मैप के लिए, यदि मैप एक ग्रिड के "एक्सिस" (axis) उपसमुच्चय (जहाँ कम से कम एक समन्वय शून्य है) पर सहमत होता है, तो उसे पूरे ग्रिड पर सहमत होना चाहिए। यह गुण फाइनाइट-डिफरेंस तर्कों का उपयोग करके प्राप्त किया गया है।
बोर्सुक-उलम निर्माण (Borsuk-Ulam Construction): निचली सीमा को सिद्ध करने के लिए, लेखक इनपुट स्पेस के भीतर दो विलगित (disjoint) कॉम्पैक्ट सेट्स, $E_+$ और $E_-$ , का निर्माण करते हैं। वे बोर्सुक-उलम प्रमेय का उपयोग यह दिखाने के लिए करते हैं कि यदि एम्बेडिंग आयाम $M$ एक निश्चित सीमा से नीचे है, तो कोई भी निरंतर इंडेक्स्ड लैटेंट मैप $\Phi$ बिंदुओं के एक जोड़े $x_+ \in E_+$ और $x_- \in E_-$ को एक ही लैटेंट वेक्टर (एक टकराव/collision) पर मैप करेगा।
सेपरेशन तर्क (Separation Argument): एक निरंतर फलन $g$ का निर्माण करके जो $E_+$ पर मान 1 और $E_-$ पर 0 लेता है, वे प्रदर्शित करते हैं कि कोई भी आर्किटेक्चर जिसका लैटेंट आयाम प्राप्त निचली सीमा से कम है, $g$ को समान रूप से (uniformly) सन्निकट नहीं कर सकता है, जिससे सार्वभौमिकता का उल्लंघन होता है।

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

नई निचली सीमा तकनीक: शोध पत्र एक बोर्सुक-उलम-आधारित विधि प्रस्तुत करता है जो विशेष रूप से उस स्थिति को संभालने के लिए डिज़ाइन की गई है जहाँ एनकोडर लक्ष्य-निर्भर (target-dependent) होता है, जो मानक फिक्स्ड-फीचर एम्बेडिंग बाधाओं की सीमाओं को पार करती है।
डीप सेट्स ( $k=1$ ): $\mathbb{R}^d$ में $n$ बिंदुओं के सेट पर कार्य करने वाले डीप सेट्स के लिए, लेखक निचली सीमा सिद्ध करते हैं:
$M_{\text{univ}}(d, n, 1) \ge d(n - 1)$
यह $d > 1$ के लिए पहली निचली सीमा है जो एम्बिएंट आयाम $d$ के साथ बढ़ती है। मौजूदा ऊपरी सीमाओं के साथ मिलकर, यह स्थापित करता है कि आवश्यक लैटेंट आयाम स्थिरांक कारकों (constant factors) तक $\Theta(nd)$ के रूप में रैखिक रूप से स्केल करता है।
$k$ -ary जेनोसी पूलिंग ( $k > 1$ ): सामान्य $k$ -ary जेनोसी पूलिंग के लिए, शोध पत्र पहली गैर-तुच्छ निचली सीमा सिद्ध करता है:
$M_{\text{univ}}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$
यह परिणाम दर्शाता है कि उच्च-क्रम की अंतःक्रियाओं ( $k > 1$ ) के बावजूद, आवश्यक लैटेंट आयाम को $d$ और $n$ दोनों के साथ बढ़ना होगा।
सीमाओं का सारांश: शोध पत्र ज्ञात सीमाओं का एक व्यापक अवलोकन (तालिका 1) प्रदान करता है, जो यह उजागर करता है कि $k > 1$ के लिए, नई निचली सीमा पहली है जो स्पष्ट रूप से $d$ और $n$ पर गैर-तुच्छ रूप से निर्भर करती है।

महत्व और दावे
लेखक दावा करते हैं कि उनके परिणाम क्रमपरिवर्तनीय आर्किटेक्चर की सैद्धांतिक समझ में महत्वपूर्ण अंतराल को हल करते हैं:

डीप सेट्स: यह परिणाम पुष्टि करता है कि $d > 1$ के लिए, एम्बेडिंग आयाम को $d$ के साथ स्केल करना होगा, जो पिछले आयाम-निर्भर निचली सीमाओं के अभाव को सुधारता है। $d(n-1)$ की स्केलिंग को $2nd+1$ ऊपरी सीमा की तुलना में स्थिरांक कारकों तक सटीक (tight) दिखाया गया है।
जेनोसी पूलिंग: यह शोध पत्र स्थापित करता है कि परिमित-क्रम की अंतःक्रियाएं (finite-order interactions) बड़े लैटेंट आयामों की आवश्यकता को समाप्त नहीं करती हैं; आयाम को अभी भी समस्या के आकार और एम्बिएंट आयाम के साथ बढ़ना होगा।
पद्धतिगत प्रगति: बोर्सुक-उलम दृष्टिकोण उन सेटिंग्स में सार्वभौमिकता का विश्लेषण करने के लिए एक नया उपकरण प्रदान करता है जहाँ एनकोडर लक्ष्य-निर्भर होता है, एक ऐसी स्थिति जहाँ मानक टोपोलॉजिकल एम्बेडिंग बाधाएं विफल हो जाती हैं।

सीमाएं
लेखक नोट करते हैं कि प्राप्त सीमाएँ सभी क्षेत्रों (regimes) में सटीक (sharp) नहीं हैं।

डीप सेट्स के लिए, सीमा $d(n-1)$ है न कि $dn$, एक अंतर जो बाधा सेट्स (obstruction sets) को अलग करने के लिए एक इनपुट बिंदु की आवश्यकता वाले निर्माण के कारण है।
$k > 1$ के लिए, निचली सीमा में $1/k$ का घातांक (exponent) वर्तमान निर्माण (विशेष रूप से ग्रिड लेबलिंग रणनीति) की एक सीमा है। इस निचली सीमा और डीप सेट्स से विरासत में मिली $O(nd) $ऊपरी सीमा के बीच एक बड़ा अंतर बना हुआ है। परिमित-क्रम जेनोसी पूलिंग के लिए$ d, n, $और$ k$ पर सटीक निर्भरता निर्धारित करना एक खुला प्रश्न बना हुआ है।

समस्या: "बहुत छोटा" कोड

नई खोज: एक "टोपोलॉजिकल" ट्रिक

उन्होंने क्या पाया

"फिक्स्ड" बनाम "फ्लेक्सिबल" ट्रांसलेटर

सारांश

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