🤖 machine learning

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

यह शोध पत्र एक हाइब्रिड सर्च फ्रेमवर्क पेश करता है जो LABS सर्च स्पेस में कंप्यूटेशनल संसाधनों को अनुकूल रूप से आवंटित करने के लिए थॉम्पसन सैंपलिंग (Thompson sampling) को समानांतर सेल्फ-अवॉइडिंग वॉक्स (parallel self-avoiding walks) और GPU त्वरण (GPU acceleration) के साथ जोड़ता है, जो 35 अनुक्रम लंबाई (sequence lengths) के लिए सर्वोत्तम ज्ञात परिणामों में सफलतापूर्वक सुधार करता है और 8.0 से अधिक मेरिट फैक्टर वाले एक नए सबसे लंबे अनुक्रम की खोज करता है।

मूल लेखक: Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

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

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

CC BY 4.0

मूल लेखक: Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

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

कल्पना कीजिए कि आप एक विशाल, ब्रह्मांडीय ताले के लिए एक एकल, सटीक संयोजन खोजने की कोशिश कर रहे हैं। यह ताला स्विचों की एक लंबी श्रृंखला से बना है, जिनमें से प्रत्येक को या तो "Up" (+1) या "Down" (-1) पर सेट किया जा सकता है। लक्ष्य क्या है? स्विचों को इस तरह व्यवस्थित करना ताकि पैटर्न गलती से खुद को थोड़ा बाएं या दाएं खिसकने पर भी न पहचान सके। वास्तविक दुनिया में, इसे लो ऑटोकोरिलेशन बाइनरी सीक्वेंस (LABS) समस्या कहा जाता है, और यह उपग्रह नेविगेशन और स्पष्ट रेडियो संकेतों जैसी चीजों के पीछे का असली रहस्य है।

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

पुराना तरीका: अनुमान लगाना और जांचना

पहले, वैज्ञानिक इस समस्या को हल करने के लिए ताले के की-होल (keyholes) के "आकार" को देखने की कोशिश करते थे। उन्होंने उन गणितीय नियमों का उपयोग किया जिनसे यह अनुमान लगाया जा सके कि कौन से शुरुआती पैटर्न आशाजनक दिखते हैं। यह चमकने वाली सुइयों को खोजने के लिए केवल उन्हीं सुइयों को देखने जैसा था जो चमकदार दिखती थीं। कभी-कभी यह काम करता था, लेकिन अक्सर वे चमकदार दिखने वाली सुइयों पर समय बर्बाद कर देते थे जो अंततः बेकार साबित होती थीं।

नई रणनीति: स्मार्ट डिटेक्टिव (चतुर जासूस)

मारिबोर विश्वविद्यालय की टीम के लेखकों ने अनुमान लगाना बंद करने और सीखना शुरू करने का निर्णय लिया। उन्होंने एक हाइब्रिड सर्च इंजन बनाया है जो थॉम्पसन सैंपलिंग (Thompson sampling) नामक एक तरकीब का उपयोग करने वाले एक सुपर-स्मार्ट डिटेक्टिव की तरह काम करता है।

यहाँ उनका डिटेक्टिव कैसे काम करता है:

विभाजन और विजय (Divide and Conquer): पूरे रेगिस्तान को एक साथ देखने के बजाय, वे खोज क्षेत्र को अलग-अलग "पड़ोस" (जिन्हें पार्टिशन कहा जाता है) में विभाजित करते हैं।
मल्टी-आर्म्ड बैंडिट (The Multi-Armed Bandit): कल्पना कीजिए कि स्लॉट मशीनों (arms) की एक पंक्ति है। कुछ मशीनें बड़े जैकपॉट (उच्च गुणवत्ता वाले अनुक्रम) देती हैं, और कुछ केवल कुछ सिक्के देती हैं। डिटेक्टिव को नहीं पता कि विजेता मशीन कौन सी है।
चलते-चलते सीखना: डिटेक्टिव एक लीवर खींचता है (एक पड़ोस की खोज करता है)। यदि वह अच्छा भुगतान करता है, तो डिटेक्टिव उत्साहित हो जाता है और उस लीवर को फिर से खींचता है। यदि वह बेकार है, तो डिटेक्टिव आगे बढ़ जाता है। लेकिन यहाँ जादू है: डिटेक्टिव थोड़ा जिज्ञासु भी है। वह कभी-कभी "बोरिंग" मशीनों को भी आजमाता है, क्योंकि हो सकता है कि वे गुप्त रूप से सबसे अच्छी हों। एक्सप्लोइटेशन (जहाँ पैसा है वहां जाना) और एक्सप्लोरेशन (अज्ञात की जांच करना) के बीच का यह संतुलन उनके तरीके का मूल है।

सुपर-स्पीड इंजन

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

उन्होंने एक दो-चरणीय रणनीति का भी उपयोग किया:

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

परिणाम: रिकॉर्ड तोड़ना

इस प्रयोग के परिणाम प्रभावशाली हैं। टीम ने 450 से 527 की लंबाई वाली बाइनरी अनुक्रमों और 573 की लंबाई के लिए अपने तरीके का परीक्षण किया।

नए रिकॉर्ड: उन्होंने उस सीमा में 35 अलग-अलग अनुक्रम लंबाई के लिए पहले देखे गए किसी भी समाधान से बेहतर समाधान खोजे।
सबसे बड़ी उपलब्धि: सबसे रोमांचक खोज लंबाई L = 451 के लिए थी। उन्होंने एक ऐसा अनुक्रम खोजा जिसका "मेरिट फैक्टर" (एक अनुक्रम कितना अच्छा है इसका स्कोर) 8.0555 था। यह सबसे लंबी अनुक्रम है जिसे अब तक 8.0 से अधिक मेरिट फैक्टर के साथ रिपोर्ट किया गया है। इससे पहले, सबसे लंबा अनुक्रम केवल 309 लंबाई का था।
एक और मील का पत्थर: लंबाई L = 573 के लिए, उन्होंने स्कोर को सुधार कर 7.2774 कर दिया, जो उस लंबाई के लिए अब तक का सबसे उच्चतम मेरिट फैक्टर (7.0 से ऊपर) है।

उन्होंने क्या नहीं किया (और क्यों यह महत्वपूर्ण है)

यह ध्यान रखना महत्वपूर्ण है कि इस पेपर ने क्या नहीं किया। उन्होंने यह दावा नहीं किया कि उन्होंने हर संभव लंबाई के लिए LABS समस्या को हल कर दिया है। जैसा कि पेपर में उल्लेख किया गया है, जैसे-जैसे अनुक्रम लंबे होते जाते हैं, परिदृश्य "तेजी से ऊबड़-खाबड़" (increasingly rugged) होता जाता है, जिसका अर्थ है कि सुधार छोटे और कठिन होते जाते हैं। उन्होंने इस समस्या को हल करने के लिए क्वांटम कंप्यूटर का उपयोग नहीं किया; उन्होंने एक स्मार्ट एल्गोरिदम के साथ क्लासिकल कंप्यूटर (GPUs) का उपयोग किया। उन्होंने केवल परिणामों का सिमुलेशन नहीं किया; उन्होंने वास्तव में इन नए अनुक्रमों को उत्पन्न और सत्यापित किया, दूसरों द्वारा जांच के लिए विशिष्ट बाइनरी पैटर्न (हेक्साडेसिमल प्रारूप में) प्रदान किए।

निष्कर्ष

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

तकनीकी सारांश: लो ऑटोकोरिलेशन बाइनरी सीक्वेंस (LABS) समस्या में सर्च स्पेस क्षेत्रों को प्राथमिकता देना

समस्या की परिभाषा
लो ऑटोकोरिलेशन बाइनरी सीक्वेंस (LABS) समस्या एक चुनौतीपूर्ण कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन कार्य है, जिसका उद्देश्य ऐसे बाइनरी सीक्वेंस $S = \{s_1, \dots, s_L\}$ खोजना है जहाँ $s_i \in \{+1, -1\}$ हो, जो स्क्वेयर्ड एपीरियॉडिक ऑटोकोरिलेशन के योग को न्यूनतम करते हैं। इसका उद्देश्य मेरिट फैक्टर $F$ को अधिकतम करना है, जिसे $F(S) = L^2 / 2E(S)$ के रूप में परिभाषित किया गया है, जहाँ $E(S)$ सीक्वेंस एनर्जी है। इसका सर्च स्पेस $2^L$ के साथ तेजी से बढ़ता है, जो कई स्थानीय मिनिमा (local minima) और दुर्लभ, अलग-थलग ग्लोबल मिनिमा द्वारा चिह्नित एक रग्ड लैंडस्केप (rugged landscape) है। जबकि स्क्यू-सिमेट्रिक सीक्वेंस (जहाँ $s_{k+1+i} = (-1)^i s_{k+1-i}$ ) सर्च स्पेस को कम करते हैं और विषम-शिफ्ट (odd-shift) ऑटोकोरिलेशन को समाप्त करते हैं, बड़े $L$ के लिए इष्टतम सीक्वेंस खोजना थ्योरिटिकल एग्जॉस्टिव विधियों के लिए कम्प्यूटेशनल रूप से कठिन बना हुआ है।

कार्यप्रणाली (Methodology)
लेखक एक हाइब्रिड सर्च फ्रेमवर्क, TS-SAW प्रस्तावित करते हैं, जो ऑनलाइन निर्णय लेने (online decision-making) को समानांतर स्टोकेस्टिक सर्च (parallel stochastic search) के साथ एकीकृत करता है ताकि LABS सर्च स्पेस में कंप्यूटेशनल संसाधनों को गतिशील रूप से आवंटित किया जा सके। यह कार्यप्रणाली तीन मुख्य घटकों से बनी है:

पार्टिशन प्रायोरिटाइजेशन के लिए थॉमसन सैंपलिंग (Thompson Sampling for Partition Prioritization):
सर्च स्पेस को "रेस्ट्रिक्शन क्लासेस" या पार्टिशन में विभाजित किया जाता है, जिन्हें सीक्वेंस के पहले $p$ तत्वों को फिक्स करके परिभाषित किया जाता है। इन पार्टिशन्स को मल्टी-आर्मेड बैंडिट समस्या में "आर्म्स" (arms) के रूप में मॉडल किया गया है। पार्टिशन्स को रैंक करने के लिए स्टेटिक ह्यूरिस्टिक्स (जैसे पोटेंशियल वैल्यूज) पर निर्भर रहने के बजाय, लेखक पार्टिशन्स को अनुकूल रूप से चुनने के लिए थॉमसन सैंपलिंग का उपयोग करते हैं।
- प्रत्येक पार्टिशन $k$ एक अज्ञात पैरामीटर $\theta_k$ से जुड़ा होता है, जो इसके अपेक्षित मेरिट फैक्टर का प्रतिनिधित्व करता है।
- एक बीटा वितरण $Beta(\alpha_k, \beta_k)$ $\theta_k$ के लिए प्रायर (prior) के रूप में कार्य करता है।
- एल्गोरिदम निरंतर रिवॉर्ड्स (नॉर्मलाइज्ड मेरिट फैक्टर्स) को संभालने के लिए फ्रैक्शनल थॉमसन सैंपलिंग का उपयोग करता है। जब एक पार्टिशन पर खोज से रिवॉर्ड $r_t \in [0, 1]$ प्राप्त होता है, तो पैरामीटर्स को $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$ के रूप में अपडेट किया जाता है।
- यह तंत्र उन पार्टिशन्स की ओर कंप्यूटेशनल प्रयास को गतिशील रूप से स्थानांतरित करता है जो अनुभवजन्य रूप से उच्च मेरिट फैक्टर प्रदान करते हैं, जबकि कम-सैंपल किए गए क्षेत्रों की खोज (exploration) को भी बनाए रखता है।
GPU पर समानांतर सेल्फ-अवॉइडिंग वॉक्स (Parallel Self-Avoiding Walks - SAW on GPU):
एक बार पार्टिशन का चयन हो जाने के बाद, एल्गोरिदम प्रतिबंधित स्थान के भीतर सीक्वेंस को अनुकूलित करने के लिए एक सेल्फ-अवॉइडिंग वॉक करता है।
- कार्यान्वयन: वॉक्स को NVIDIA GPUs (CUDA) पर समानांतर में निष्पादित किया जाता है। प्रत्येक वॉक CUDA ब्लॉक के भीतर एक स्वतंत्र एजेंट के रूप में कार्य करता है।
- साइकिल रोकथाम: अत्यधिक मेमोरी उपयोग के बिना विज़िट किए गए स्टेट्स को रोकने के लिए, एक ब्लूम फ़िल्टर (Bloom filter) विज़िट किए गए सीक्वेंस के हैश को स्टोर करता है।
- दक्षता: नेबरहुड इवैल्यूएशन के लिए स्क्यू-सिमेट्रिक सीक्वेंस के लिए लीनियर-टाइम फ्लिप ऑपरेशन्स का उपयोग किया जाता है, जो कम मेमोरी फुटप्रिंट और उच्च थ्रूपुट सुनिश्चित करता है।
- साझा लर्निंग: जबकि वॉक्स समानांतर में चलते हैं, वे एक वैश्विक पोस्टीरियर बिलीफ ( $\alpha_k, \beta_k$ ) साझा करते हैं जिसे वॉक्स के प्रत्येक बैच के बाद अपडेट किया जाता है, जिससे लर्निंग प्रक्रिया तेज हो जाती है।
दो-चरणीय अनुकूलन पाइपलाइन (Two-Stage Optimization Pipeline):
फ्रेमवर्क समाधानों को रिफाइन करने के लिए एक दो-चरणीय रणनीति अपनाता है:
- चरण 1 (प्रतिबंधित/Constrained): समानांतर SAWs विभाजित स्क्यू-सिमेट्रिक सर्च स्पेस का अन्वेषण करते हैं। शीर्ष $m$ उम्मीदवारों को (क्विकसेलेक्ट एल्गोरिदम के माध्यम से चयनित) अगले चरण में भेजा जाता है।
- चरण 2 (अप्रतिबंधित/Unconstrained): इन उम्मीदवारों को अनरिस्ट्रिक्टेड सर्च स्पेस में और अधिक रिफाइनमेंट के लिए उपयोग किया जाता है। यह चरण स्क्यू-सिमेट्री और पार्टिशन बाधाओं को हटा देता है, और एक व्यापक क्षेत्र का अन्वेषण करने तथा समाधान की गुणवत्ता में सुधार करने के लिए प्रायोरिटी क्यू और सीक्वेंस ऑपरेटर्स (रोटेशन और फ्लिप्स) का उपयोग करता है।
- सीक्वेंस ऑपरेटर्स: सम-लंबाई वाले सीक्वेंसों को संभालने के लिए, विधि विषम-लंबाई वाले अनुकूलित सीक्वेंसों को सम-लंबाई वाले वेरिएंट में बदलने के लिए ऑपरेटर्स लागू करती है, जिन्हें फिर रिफाइनमेंट चरण में वापस भेजा जाता है।

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

अनुकूली संसाधन आवंटन (Adaptive Resource Allocation): एक नवीन ऑनलाइन विधि जो स्टेटिक ह्यूरिस्टिक रैंकिंग से आगे बढ़कर, पार्टिशन्स को गतिशील रूप से प्राथमिकता देने के लिए थॉमसन सैंपलिंग का उपयोग करती है।
हाइब्रिड एल्गोरिदम (TS-SAW): एक नया एल्गोरिदम जो मल्टी-आर्मेड बैंडिट निर्णय लेने के साथ GPU-एक्सेलेरेटेड समानांतर सेल्फ-अवॉइडिंग वॉक्स को जोड़ता है।
स्केलेबल आर्किटेक्चर: एक दो-चरणीय पाइपलाइन जो प्रारंभिक अन्वेषण के लिए व्यापक समानांतरता (massive parallelism) और अंतिम अनुकूलन के लिए अनकन्स्ट्रेंड रिफाइनमेंट का लाभ उठाती है।
नए सर्वश्रेष्ठ-ज्ञात समाधान: 35 अलग-अलग लंबाई ( $450 \le L \le 527$ की सीमा में) और $L = 573$ के लिए नए रिकॉर्ड सीक्वेंस का निर्माण।

प्रायोगिक परिणाम
प्रयोग NVIDIA A100 GPUs के साथ Vega सुपरकंप्यूटर पर किए गए थे। विधि का परीक्षण $450 \le L \le 527$ और $L = 573$ की लंबाई वाले बाइनरी सीक्वेंसों पर किया गया था, जिसमें प्रारंभिक चरण के लिए 100,000 इटरेशन चलाए गए।

मेरिट फैक्टर सुधार: प्रस्तावित विधि ने परीक्षण किए गए सभी 35 लंबाई के लिए पिछले सर्वश्रेष्ठ मेरिट फैक्टर्स में सुधार किया। सुधारे गए सीक्वेंसों में औसत मेरिट फैक्टर वृद्धि 0.1967 थी।
रिकॉर्ड तोड़ना:
- $L = 451$ के लिए, विधि ने $F = 8.0555$ का मेरिट फैक्टर प्राप्त किया, जो पिछले सर्वश्रेष्ठ से 0.8248 अधिक है। इसे साहित्य में 8.0 से अधिक मेरिट फैक्टर वाला सबसे लंबा सीक्वेंस बताया गया है।
- $L = 573$ के लिए, मेरिट फैक्टर में 0.2564 का सुधार हुआ, जो $F > 7.0$ वाले ज्ञात सबसे लंबे सीक्वेंस का प्रतिनिधित्व करता है।
पार्टिशन विश्लेषण: $L=461$ के साथ एक प्रयोग ने प्रदर्शित किया कि थॉमसन सैंपलिंग उच्च-प्रदर्शन करने वाले पार्टिशन्स की प्रभावी ढंग से पहचान करता है। एल्गोरिदम ने उच्च सैद्धांतिक "नॉर्मलाइज्ड पोटेंशियल" वाले पार्टिशन्स से हटकर उन पार्टिशन्स पर ध्यान केंद्रित किया जो अनुभवजन्य रूप से बेहतर परिणाम देते थे, जो स्टेटिक ह्यूरिस्टिक्स के बजाय डेटा-संचालित आवंटन के महत्व की पुष्टि करता है।

महत्व और दावे
पेपर का दावा है कि प्रस्तावित फ्रेमवर्क LABS समस्या में मेरिट फैक्टर्स को अधिकतम करने के लिए एक स्केलेबल और प्रभावी रणनीति प्रदान करता है। मल्टी-आर्मेड बैंडिट निर्णय लेने को हाई-परफॉर्मेंस समानांतर कंप्यूटिंग के साथ एकीकृत करके, यह दृष्टिकोण अत्यधिक रग्ड सर्च स्पेस में एक्सप्लोरेशन और एक्सप्लोइटेशन (exploration and exploitation) के बीच सफलतापूर्वक संतुलन बनाता है। लेखक तर्क देते हैं कि जबकि जैसे-जैसे सीक्वेंस की लंबाई बढ़ती है, सुधार करना कठिन होता जाता है, उनका डेटा-संचालित, पार्टिशन-गाइडेड स्टोकेस्टिक ऑप्टिमाइज़ेशन अत्याधुनिक तकनीक (state-of-the-art) को आगे बढ़ाने के लिए एक आशाजनक दिशा है। परिणाम इस बात की पुष्टि करते कि इस श्रेणी की कॉम्बिनेटोरियल समस्याओं के लिए ऑनलाइन, अनुकूली संसाधन आवंटन, स्टेटिक ह्यूरिस्टिक प्रायोरिटाइजेशन की तुलना में श्रेष्ठ है। लेखक निष्कर्ष निकालते हैं कि यह फ्रेमवर्क अन्य कठिन कॉम्बिनेटोरियल समस्याओं के लिए एक मार्ग प्रदान करता है जहाँ सर्च स्पेस को सार्थक रूप से विभाजित किया जा सकता है।