बीम खोज एक अनुमानी खोज एल्गोरिथ्म है जिसका उपयोग कंप्यूटर विज्ञान में एक सीमित सेट में सबसे आशाजनक नोड का विस्तार करके एक ग्राफ का अन्वेषण करने के लिए किया जाता है। यह सर्वोत्तम-प्रथम खोज का एक संशोधन है जो केवल पूर्व-निर्धारित संख्या में सर्वोत्तम आंशिक समाधानों को उम्मीदवारों के रूप में रखकर मेमोरी आवश्यकताओं को कम करता है, जिससे यह एक लालची एल्गोरिथ्म बन जाता है। यह एल्गोरिथ्म व्यापक रूप से अनुक्रम डिकोडिंग कार्यों में लागू होता है, जैसे कि मशीन अनुवाद और वाक् पहचान, जहाँ यह आउटपुट गुणवत्ता को कम्प्यूटेशनल व्यावहारिकता के साथ संतुलित करता है।
बीम खोज का मूल विचार सबसे आशाजनक आंशिक समाधानों का एक सेट बनाए रखना है, जिसे बीम कहा जाता है, और प्रत्येक चरण में केवल उन्हीं का विस्तार करना है। यह दृष्टिकोण व्यापक खोज विधियों के विपरीत है जो सभी संभावित पथों पर विचार करते हैं, जो बड़े खोज स्थानों के लिए कम्प्यूटेशनल रूप से निषेधात्मक हो सकता है। कम आशाजनक उम्मीदवारों को छाँटकर, बीम खोज दक्षता प्राप्त करता है जबकि पूर्णता और इष्टतमता की गारंटी का त्याग करता है।
एल्गोरिथ्मिक विवरण
बीम खोज अपने खोज वृक्ष का निर्माण करने के लिए चौड़ाई-प्रथम खोज रणनीति का उपयोग करके संचालित होती है। वृक्ष के प्रत्येक स्तर पर, यह वर्तमान स्तर पर राज्यों के सभी उत्तराधिकारियों को उत्पन्न करता है और उन्हें अनुमानी लागत के बढ़ते क्रम में क्रमबद्ध करता है। हालाँकि, यह केवल एक पूर्व-निर्धारित संख्या, जिसे β (बीम चौड़ाई) के रूप में दर्शाया जाता है, के सर्वोत्तम राज्यों को प्रत्येक स्तर पर संग्रहीत करता है। केवल उन्हीं राज्यों का अगले चरण में विस्तार किया जाता है, और बाकी को त्याग दिया जाता है।
बीम चौड़ाई β एक महत्वपूर्ण पैरामीटर है जो खोज गुणवत्ता और संसाधन उपयोग के बीच व्यापार-बंद को नियंत्रित करता है। एक बड़ी बीम चौड़ाई अधिक राज्यों को बनाए रखती है, छाँटे गए उम्मीदवारों की संख्या को कम करती है और संभावित रूप से समाधान गुणवत्ता में सुधार करती है, लेकिन यह मेमोरी और कम्प्यूटेशनल आवश्यकताओं को भी बढ़ाती है। अनंत बीम चौड़ाई के साथ, कोई राज्य नहीं छाँटा जाता है, और बीम खोज सर्वोत्तम-प्रथम खोज के समान हो जाती है। इसके विपरीत, 1 की बीम चौड़ाई एक पहाड़ी-चढ़ाई एल्गोरिथ्म से मेल खाती है, जो केवल एकल सर्वोत्तम पथ का लालची ढंग से अनुसरण करती है।
बीम चौड़ाई खोज करने के लिए आवश्यक मेमोरी को सीमित करती है, जिससे यह सीमित मेमोरी वाले बड़े सिस्टम के लिए उपयुक्त हो जाती है। हालाँकि, क्योंकि एक लक्ष्य राज्य संभावित रूप से छाँटा जा सकता है, बीम खोज पूर्णता का त्याग करती है - यह गारंटी कि एक एल्गोरिथ्म एक समाधान के साथ समाप्त होगा यदि एक मौजूद है। इसके अतिरिक्त, बीम खोज इष्टतम नहीं है, जिसका अर्थ है कि कोई गारंटी नहीं है कि यह सबसे अच्छा संभव समाधान खोजेगा।
ऐतिहासिक विकास
जो बाद में बीम खोज के रूप में जाना जाने लगा, उसका पहला उपयोग हार्पी वाक् पहचान प्रणाली में था, जिसे 1976 के एक शोध-प्रबंध में पेश किया गया था। इस प्रक्रिया को मूल रूप से "खोज का लोकस मॉडल" कहा जाता था, लेकिन "बीम खोज" शब्द 1977 तक पहले से ही उपयोग में था। हार्पी को कार्नेगी मेलन विश्वविद्यालय में विकसित किया गया था और इसने वाक् पहचान तकनीक में एक महत्वपूर्ण प्रगति का प्रतिनिधित्व किया, जो वास्तविक दुनिया के अनुप्रयोगों में अनुमानी खोज की व्यावहारिक उपयोगिता को प्रदर्शित करता है।
बीम खोज का विकास 1970 के दशक में कृत्रिम बुद्धिमत्ता प्रणालियों के लिए कुशल खोज एल्गोरिथ्म की ओर एक व्यापक प्रवृत्ति का हिस्सा था। शोधकर्ताओं ने माना कि व्यापक खोज विधियाँ अक्सर जटिल समस्याओं के लिए अव्यावहारिक थीं, जिससे अनुमानी दृष्टिकोणों का विकास हुआ जो अच्छे समाधान जल्दी पा सकते थे। हार्पी प्रणाली की सफलता ने क्षेत्र में एक मौलिक तकनीक के रूप में बीम खोज को स्थापित करने में मदद की।
मशीन अनुवाद में अनुप्रयोग
बीम खोज का सबसे प्रमुख रूप से मशीन अनुवाद प्रणालियों में उपयोग किया गया है, जहाँ यह कई संभावित उम्मीदवारों में से सर्वोत्तम अनुवाद का चयन करने में मदद करता है। पारंपरिक सांख्यिकीय मशीन अनुवाद में, एक वाक्य के प्रत्येक भाग को संसाधित किया जाता है, और शब्दों का अनुवाद करने के कई अलग-अलग तरीके उत्पन्न होते हैं। बीम खोज उनके वाक्य संरचनाओं के अनुसार शीर्ष सर्वोत्तम अनुवादों को रखता है और बाकी को त्याग देता है, फिर शेष अनुवादों का एक दिए गए मानदंड के अनुसार मूल्यांकन करता है ताकि उसका चयन किया जा सके जो लक्ष्यों को सबसे अच्छा पूरा करता है।
आधुनिक तंत्रिका मशीन अनुवाद में, जो मुख्य रूप से बड़े भाषा मॉडल और ट्रांसफॉर्मर आर्किटेक्चर का उपयोग करता है, बीम खोज एक प्रमुख डिकोडिंग रणनीति बनी हुई है। पीढ़ी के दौरान, मॉडल प्रत्येक चरण पर संभावित अगले टोकन पर एक संभाव्यता वितरण उत्पन्न करता है। बीम खोज कई आंशिक अनुक्रमों को बनाए रखता है, उनके संचयी संभावनाओं के आधार पर सबसे आशाजनक का विस्तार करता है। यह दृष्टिकोण लालची डिकोडिंग की तुलना में उच्च गुणवत्ता वाले अनुवाद उत्पन्न करता है, जो प्रत्येक चरण पर केवल सबसे संभावित टोकन का चयन करता है।
मशीन अनुवाद में बीम खोज के अनुप्रयोग का व्यापक अध्ययन किया गया है, शोधकर्ताओं ने प्रदर्शन में सुधार के लिए विभिन्न संशोधनों की खोज की है। उदाहरण के लिए, लंबाई सामान्यीकरण अक्सर छोटे अनुक्रमों की ओर पूर्वाग्रह से बचने के लिए लागू किया जाता है, और विविध बीम खोज तकनीकों को उम्मीदवार अनुक्रमों के बीच विविधता को प्रोत्साहित करने के लिए विकसित किया गया है।
विविधताएँ और विस्तार
बीम खोज की कई विविधताएँ इसकी सीमाओं को संबोधित करने के लिए विकसित की गई हैं, विशेष रूप से इसकी पूर्णता और इष्टतमता की कमी। एक दृष्टिकोण बीम खोज को गहराई-प्रथम खोज के साथ जोड़ता है, जिसके परिणामस्वरूप बीम स्टैक खोज और गहराई-प्रथम बीम खोज होती है। ये एल्गोरिथ्म किसी भी समय एल्गोरिथ्म हैं जो बीम खोज की तरह अच्छे लेकिन संभावित रूप से उप-इष्टतम समाधान जल्दी पाते हैं, फिर पीछे हटते हैं और एक इष्टतम समाधान में अभिसरण तक बेहतर समाधान खोजना जारी रखते हैं।
एक और विविधता, सीमित विसंगति बैकट्रैकिंग का उपयोग करके बीम खोज (BULB), बीम खोज को सीमित विसंगति खोज के साथ जोड़ती है। यह दृष्टिकोण भी किसी भी समय एल्गोरिथ्म उत्पन्न करता है जो समय के साथ समाधान में सुधार कर सकता है। स्थानीय खोज के संदर्भ में, स्थानीय बीम खोज एक विशिष्ट एल्गोरिथ्म है जो β यादृच्छिक रूप से उत्पन्न राज्यों का चयन करके शुरू होता है और फिर, खोज वृक्ष के प्रत्येक स्तर के लिए, वर्तमान राज्यों के सभी संभावित उत्तराधिकारियों के बीच β नए राज्यों पर विचार करता है जब तक कि एक लक्ष्य तक नहीं पहुँच जाता।
चूँकि स्थानीय बीम खोज अक्सर स्थानीय मैक्सिमा पर समाप्त होती है, एक सामान्य समाधान अगले β राज्यों को एक यादृच्छिक तरीके से चुनना है, जिसमें संभावना राज्यों के अनुमानी मूल्यांकन पर निर्भर करती है। इस प्रकार की खोज को स्टोकेस्टिक बीम खोज कहा जाता है। अन्य विविधताओं में लचीली बीम खोज और पुनर्प्राप्ति बीम खोज शामिल हैं, जो बीम चौड़ाई को गतिशील रूप से समायोजित करते हैं या खराब छंटाई निर्णयों से पुनर्प्राप्ति की अनुमति देते हैं।
आधुनिक AI प्रणालियों में भूमिका
बीम खोज आधुनिक कृत्रिम बुद्धिमत्ता प्रणालियों में एक महत्वपूर्ण भूमिका निभाता है, विशेष रूप से जनरेटिव AI अनुप्रयोगों में। गहन शिक्षण मॉडलों में, विशेष रूप से ट्रांसफॉर्मर आर्किटेक्चर पर आधारित, बीम खोज का उपयोग अनुमान के दौरान पाठ, कोड या वाक् जैसे अनुक्रम उत्पन्न करने के लिए किया जाता है। OpenAI, Anthropic और Google DeepMind जैसी कंपनियाँ अपने भाषा मॉडलों में सुसंगत और संदर्भ-उपयुक्त आउटपुट उत्पन्न करने के लिए बीम खोज का उपयोग करती हैं।
यह तकनीक अन्य अनुक्रम पीढ़ी कार्यों में भी उपयोग की जाती है, जैसे कि छवि कैप्शनिंग, वाक् पहचान और प्रोटीन संरचना भविष्यवाणी। इन अनुप्रयोगों में, बीम खोज उत्पन्न आउटपुट की गुणवत्ता को आवश्यक कम्प्यूटेशनल संसाधनों के साथ संतुलित करने में मदद करता है। बीम चौड़ाई को कार्य की विशिष्ट आवश्यकताओं के आधार पर ट्यून किया जा सकता है, बड़ी चौड़ाई बेहतर गुणवत्ता प्रदान करती है लेकिन बढ़ी हुई गणना की लागत पर।
सैद्धांतिक गुण
बीम खोज के सैद्धांतिक गुणों का अनुमानी खोज के संदर्भ में विश्लेषण किया गया है। एक लालची एल्गोरिथ्म के रूप में, यह प्रत्येक चरण पर स्थानीय रूप से इष्टतम विकल्प बनाता है, जो उप-इष्टतम वैश्विक समाधानों को जन्म दे सकता है। एल्गोरिथ्म का प्रदर्शन राज्यों का मूल्यांकन करने के लिए उपयोग किए जाने वाले अनुमानी फ़ंक्शन की गुणवत्ता पर भारी निर्भर करता है। एक अच्छी तरह से डिज़ाइन किया गया अनुमानी खोज को अच्छे समाधानों की ओर मार्गदर्शन कर सकता है, जबकि एक खराब अनुमानी एल्गोरिथ्म को इष्टतम पथों को याद करने का कारण बन सकता है।
बीम चौड़ाई और समाधान गुणवत्ता के बीच व्यापार-बंद व्यावहारिक अनुप्रयोगों में एक केंद्रीय विचार है। शोध से पता चला है कि बीम चौड़ाई बढ़ाने से आम तौर पर समाधान गुणवत्ता में सुधार होता है, लेकिन घटते रिटर्न के साथ। कुछ मामलों में, एक बीम चौड़ाई जो बहुत बड़ी है, महत्वपूर्ण गुणवत्ता सुधार के बिना अति-पीढ़ी और बढ़ी हुई कम्प्यूटेशनल लागतों को जन्म दे सकती है। इसके विपरीत, एक बीम चौड़ाई जो बहुत छोटी है, अत्यधिक छंटाई के कारण खराब समाधानों में परिणामित हो सकती है।
कम्प्यूटेशनल विचार
बीम खोज की कम्प्यूटेशनल जटिलता मुख्य रूप से बीम चौड़ाई और खोज स्थान के शाखा कारक द्वारा निर्धारित की जाती है। प्रत्येक स्तर पर, एल्गोरिथ्म बीम में सभी राज्यों के लिए उत्तराधिकारी उत्पन्न करता है, जिसके लिए β × b संचालन की आवश्यकता होती है, जहाँ b शाखा कारक है। इन उत्तराधिकारियों की छंटाई प्रति स्तर log(β × b) का एक अतिरिक्त कारक जोड़ती है। कुल जटिलता इसलिए O(β × b × L × log(β × b)) है, जहाँ L खोज की अधिकतम गहराई है।
मेमोरी उपयोग बीम चौड़ाई से सीमित है, क्योंकि प्रत्येक स्तर पर केवल β राज्य संग्रहीत किए जाते हैं। यह बीम खोज को सीमित मेमोरी वाले अनुप्रयोगों के लिए विशेष रूप से आकर्षक बनाता है, जैसे कि एम्बेडेड सिस्टम या वास्तविक समय प्रसंस्करण। मेमोरी उपयोग और समाधान गुणवत्ता को संतुलित करने की एल्गोरिथ्म की क्षमता ने शैक्षणिक अनुसंधान और औद्योगिक अनुप्रयोगों दोनों में इसकी स्थायी लोकप्रियता में योगदान दिया है।
अन्य खोज विधियों के साथ तुलना
बीम खोज की तुलना अक्सर अन्य खोज एल्गोरिथ्मों के साथ की जाती है, जैसे कि लालची खोज, सर्वोत्तम-प्रथम खोज और मशीन लर्निंग-आधारित डिकोडिंग विधियाँ। लालची खोज, जो 1 की बीम चौड़ाई के साथ बीम खोज से मेल खाती है, कम्प्यूटेशनल रूप से कुशल है लेकिन अक्सर निम्न-गुणवत्ता वाले परिणाम उत्पन्न करती है। सर्वोत्तम-प्रथम खोज, जो सभी आंशिक समाधानों पर विचार करती है, इष्टतम समाधान पा सकती है लेकिन पूरे खोज स्थान के आनुपातिक मेमोरी की आवश्यकता होती है।
तंत्रिका अनुक्रम पीढ़ी के संदर्भ में, बीम खोज की तुलना कभी-कभी नमूनाकरण-आधारित विधियों के साथ की जाती है, जो उनके संभाव्यता वितरण के आधार पर यादृच्छिक रूप से टोकन का चयन करते हैं। नमूनाकरण अधिक विविध आउटपुट उत्पन्न कर सकता है लेकिन सुसंगतता का त्याग कर सकता है, जबकि बीम खोज अधिक नियतात्मक और उच्च-गुणवत्ता वाले परिणाम उत्पन्न करता है। हाल के शोध ने गुणवत्ता और विविधता के बीच संतुलन प्राप्त करने के लिए बीम खोज को नमूनाकरण के साथ जोड़ने वाले हाइब्रिड दृष्टिकोणों की खोज की है।
भविष्य की दिशाएँ
2020 के दशक की शुरुआत तक, बीम खोज अनुसंधान का एक सक्रिय क्षेत्र बना हुआ है, विशेष रूप से बड़े भाषा मॉडलों के संदर्भ में। शोधकर्ता अनुकूली बीम चौड़ाई रणनीतियों की खोज कर रहे हैं जो मॉडल की भविष्यवाणियों के आत्मविश्वास के आधार पर समायोजित होती हैं, साथ ही बीम खोज प्रक्रिया में बाहरी बाधाओं को शामिल करने के तरीके भी। NVIDIA और AMD जैसी कंपनियों से विशेष AI त्वरक जैसे अधिक कुशल हार्डवेयर के विकास ने वास्तविक समय अनुप्रयोगों में बड़ी बीम चौड़ाई और अधिक जटिल खोज रणनीतियों को सक्षम किया है।
बीम खोज का अन्य AI तकनीकों के साथ एकीकरण, जैसे कि सुदृढीकरण लर्निंग और तंत्रिका नेटवर्क, भी चल रही जांच का एक क्षेत्र है। ये प्रयास प्राकृतिक भाषा प्रसंस्करण से लेकर वैज्ञानिक खोज तक, अनुप्रयोगों की एक विस्तृत श्रृंखला में अनुक्रम पीढ़ी की दक्षता और प्रभावशीलता में सुधार करने का लक्ष्य रखते हैं।