लेखक:
(1) ब्रैंडन टी. विलार्ड, नॉर्मल कंप्यूटिंग;
(2) रेमी लौफ, नॉर्मल कंप्यूटिंग।
सटीकता के लिए, हम 5-टपल परिमित ऑटोमेटन रूप में नियमित अभिव्यक्तियों पर विचार करते हैं [सिपसर, 1996, परिभाषा 1.5]:
परिभाषा 1 (परिमित ऑटोमेटन) । एक परिमित ऑटोमेटन, या परिमित-अवस्था मशीन, (Q, Σ, δ, q0, F) द्वारा दी जाती है, जहाँ Q अवस्थाओं का परिमित समूह है, Σ एक परिमित वर्णमाला है, δ : Q × Σ → Q संक्रमण फलन है, q0 ∈ Q प्रारंभिक अवस्था है, और F ⊆ Q स्वीकृत अवस्थाओं का समूह है।
V में स्ट्रिंग्स को शामिल करने वाले अक्षर Σ से लिए गए हैं: यानी V ⊂ P(Σ)। पूरे FSM में, Q को सरलता के लिए पूर्णांक मानों द्वारा दर्शाया जाएगा।
उदाहरण 1. हम नियमित अभिव्यक्ति ([0-9]*)?\.?[0-9]* के लिए चित्र 1 में FSM नमूनाकरण प्रक्रिया को दर्शाते हैं, जिसका उपयोग फ़्लोटिंगपॉइंट संख्याएँ उत्पन्न करने के लिए किया जा सकता है। सरलता के लिए, शब्दावली, V, में केवल स्ट्रिंग्स शामिल होने दें: "A", ".", "42", ".2", और "1"।
जब जनरेशन शुरू होता है, तो FSM स्टेट 0 में होता है, इसलिए हमारा एल्गोरिदम स्ट्रिंग "A" को मास्क करता है, क्योंकि इसे FSM द्वारा स्वीकार नहीं किया जाएगा। हम इस मामले में केवल ".", "42", ".2", और "1" का नमूना ले सकते हैं।
यदि हम ".2" का नमूना लेते हैं, तो हम FSM को अवस्था 3 तक आगे बढ़ाते हैं। इस मामले में, केवल "42" और "1" ही वैध पूर्णताएं हैं, इसलिए हम नमूना लेने से पहले अन्य मानों को छिपाते हैं। यदि हम इसके बजाय "1" का नमूना लेते हैं, तो हम FSM को अवस्था 1 तक आगे बढ़ाते हैं, जिस स्थिति में ".", ".42", ".2", और "1" वैध पूर्णताएं हैं और मुखौटा अपरिवर्तित रहता है।
वैध अगले टोकन निर्धारित करने के लिए शब्दावली के माध्यम से लूपिंग करना अभी भी सबसे बड़ा मुद्दा है। इसके लिए, हम नियमित अभिव्यक्ति के FSM का उपयोग करके शब्दावली को पूर्व-संसाधित करते हैं और एक सूचकांक बनाते हैं। महत्वपूर्ण हिस्सा यह है कि हम हर व्यवहार्य FSM स्थिति में शुरू करने पर विचार करते हैं, क्योंकि शब्दावली में स्ट्रिंग्स नियमित अभिव्यक्ति के मनमाने भागों से मेल खा सकती हैं, और वे भाग स्पष्ट रूप से FSM स्थितियाँ हैं।
एफएसएम में किसी भी बिंदु से मिलान उत्पन्न करने की प्रक्रिया एल्गोरिथम 3 में दी गई है। परिणाम उप-अनुक्रमों की एक सूची है, जिसमें उन अवस्थाओं का विवरण होता है, जिनसे होकर एफएसएम, प्रदान की गई स्ट्रिंग को स्वीकार करते समय गुजरेगा।
इन उप-अनुक्रमों की आरंभिक अवस्थाओं को एल्गोरिथम 2 में लूप के एक ही चरण में प्राप्त अंतिम FSM अवस्था से मिलान करके, हम एक मानचित्र, σ : Q → P(V) के साथ शब्दावली को कुशलतापूर्वक अनुक्रमित कर सकते हैं, जो FSM अवस्थाओं और शब्दावली के तत्वों के सेटों को जोड़ता है जिन्हें उन अवस्थाओं में FSM द्वारा स्वीकार किया जाएगा।
एल्गोरिथ्म 4 σ के निर्माण का वर्णन करता है।
σ के लिए हैश-मैप का उपयोग करने से एल्गोरिथ्म 2 में m चरण की लागत औसतन केवल O(1) हो सकती है। इसके अलावा, चूंकि σ को टोकन सैंपलिंग प्रक्रिया के बाहर बनाया गया है, इसलिए इसकी रन-टाइम लागत प्रभावी रूप से अप्रासंगिक है, हालांकि सैद्धांतिक रूप से इसके लिए FSM में राज्यों की संख्या के बराबर मेमोरी की आवश्यकता होती है (यानी |Q|)। सौभाग्य से, नियमित अभिव्यक्तियों और शब्दावली के गैर-रोगजनक संयोजनों के लिए, शब्दावली में प्रत्येक स्ट्रिंग को FSM द्वारा स्वीकार नहीं किया जाएगा, और प्रत्येक FSM स्थिति को V में एक स्ट्रिंग द्वारा दर्शाया नहीं जाएगा।
इस अनुभाग में हम GPT2-मीडियम (355M पैरामीटर) का उपयोग यह दर्शाने के लिए करते हैं कि नियमित अभिव्यक्ति निर्देशित जनरेशन व्यवहार में कैसे काम करता है। हम उन्हें जनरेट करने के लिए आउटलाइन लाइब्रेरी का उपयोग करते हैं:
सूची 3.1 – जारी
सूची 3.3 – जारी
यहाँ वर्णित और आउटलाइन में लागू किए गए इंडेक्सिंग दृष्टिकोण की दक्षता को दर्शाने के लिए, हम गाइडेंस लाइब्रेरी के साथ एक सरल तुलना करते हैं। इस लेखन के अनुसार, गाइडेंस लाइब्रेरी आंशिक नियमित अभिव्यक्ति मिलान का उपयोग करती है - प्रत्येक बार नमूना अनुक्रम की शुरुआत से लागू होती है - और प्रत्येक चरण पर LLM की शब्दावली (N = 50, 257) पर पुनरावृत्ति करनी चाहिए।
इस तुलना के लिए प्रयुक्त मार्गदर्शन कोड और संकेत इस प्रकार हैं:
सूची 3.4 – जारी
संबंधित आउटलाइन कोड इस प्रकार है:
सूची 3.5 – जारी
max_tokens का मान बदलता है और टाइमिंग को एक लूप और एक रिपीट मान के लिए timeit के साथ रिकॉर्ड किया जाता है (यानी max_tokens के प्रत्येक मान के लिए केवल एक नमूना एकत्र किया जाता है)। परिणाम अनुभाग 3.2 में दर्शाए गए हैं।
किसी भी कॉन्फ़िगरेशन संबंधी चूक को छोड़कर, जो बड़ी रनटाइम विसंगति पैदा कर सकती है, सैंपल किए गए टोकनों की अधिकतम संख्या में देखी गई स्केलिंग आश्चर्यजनक है और यह दृष्टिकोण द्वारा निहित बढ़ती कम्प्यूटेशनल समस्या का संकेत है।
यह पेपर CC 4.0 लाइसेंस के अंतर्गत arxiv पर उपलब्ध है।