फास्ट वर्डपीस टोकनाइज़ेशन: बर्ट और अन्य के लिए एक रैखिक-समय एल्गोरिदम

विषय सूची

1. परिचय

टोकनाइज़ेशन, भावना विश्लेषण से लेकर मशीन अनुवाद तक, लगभग सभी प्राकृतिक भाषा प्रसंस्करण (एनएलपी) कार्यों के लिए मूलभूत पूर्व-प्रसंस्करण चरण है। बर्ट, जीपीटी-3 और एक्सएलनेट जैसे आधुनिक मॉडल, पाठ को सार्थक इकाइयों में तोड़ने के लिए, विशेष रूप से वर्डपीस जैसे एल्गोरिदम पर निर्भर करते हैं, साथ ही शब्दावली से बाहर के शब्दों को संभालते हैं। यह शोध पत्र एक महत्वपूर्ण बाधा को संबोधित करता है: वर्डपीस टोकनाइज़ेशन एल्गोरिदम की स्वयं की दक्षता।

लेखक पहचानते हैं कि वर्डपीस में उपयोग की जाने वाली मानक लालची सबसे लंबी-मिलान-पहली (मैक्समैच) रणनीति की समय जटिलता उप-इष्टतम है—$O(n^2)$ या $O(nk)$, जहां $n$ इनपुट लंबाई है और $k$ अधिकतम टोकन लंबाई है। वे लिनमैक्समैच प्रस्तावित करते हैं, एक नया एल्गोरिदम जो एकल-शब्द टोकनाइज़ेशन के लिए सख्त $O(n)$ रैखिक-समय जटिलता प्राप्त करता है, और सामान्य पाठ के लिए एक एकीकृत एंड-टू-एंड (ई2ई) वर्डपीस एल्गोरिदम प्रस्तावित करता है।

2. पृष्ठभूमि और संबंधित कार्य

बर्ट में उपयोग किया जाने वाला वर्डपीस टोकनाइज़ेशन, दो चरणों को शामिल करता है: (1) रिक्त स्थान और विराम चिह्नों के आधार पर पाठ को शब्दों में पूर्व-टोकनाइज़ करना, और (2) प्रत्येक शब्द पर एक निश्चित शब्दावली के विरुद्ध मैक्समैच एल्गोरिदम लागू करना। मैक्समैच, जिसका उपयोग चीनी शब्द विभाजन में भी किया जाता है, बची हुई स्ट्रिंग के सबसे लंबे उपसर्ग का पुनरावृत्त रूप से चयन करता है जो एक शब्दावली टोकन से मेल खाता है।

पूर्व के कुशल एल्गोरिदम $O(n^2)$ या $O(nk)$ तक सीमित थे। $k$ कारक समस्याग्रस्त है क्योंकि शब्दावलियों में लंबे टोकन (जैसे, "supercalifragilisticexpialidocious") शामिल हो सकते हैं। इस शोध पत्र का योगदान इस शब्दावली-निर्भर कारक को पूरी तरह से समाप्त करने में निहित है।

3. लिनमैक्समैच एल्गोरिदम

3.1 मूल विचार और प्रेरणा

लिनमैक्समैच आहो-कोरासिक स्ट्रिंग मिलान एल्गोरिदम से प्रेरित है। मुख्य अंतर्दृष्टि यह है कि शब्दावली को पैटर्न के एक सेट के रूप में और इनपुट शब्द को पाठ के रूप में माना जाए। शब्दावली ट्राई पर सहायक डेटा संरचनाओं को पूर्व-गणना करके, एल्गोरिदम मिलान के दौरान बैकट्रैकिंग से बच सकता है, जो सरल मैक्समैच में द्विघात जटिलता का स्रोत है।

3.2 डेटा संरचनाएं: ट्राई, फेलियर लिंक्स और फेलियर पॉप्स

एल्गोरिदम तीन मुख्य डेटा संरचनाओं का उपयोग करता है जो एक ऑफ़लाइन पूर्व-प्रसंस्करण चरण के दौरान शब्दावली से निर्मित होती हैं:

• ट्राई: एक मानक उपसर्ग वृक्ष जहां प्रत्येक नोड एक वर्ण का प्रतिनिधित्व करता है और जड़ से पथ शब्दावली टोकन का प्रतिनिधित्व करते हैं।
• फेलियर लिंक (आहो-कोरासिक के समान): स्ट्रिंग $s$ का प्रतिनिधित्व करने वाले नोड के लिए, इसका फेलियर लिंक उस नोड की ओर इशारा करता है जो $s$ के सबसे लंबे उचित प्रत्यय का प्रतिनिधित्व करता है जो किसी शब्दावली टोकन का उपसर्ग भी है। यह एल्गोरिदम को कुशलतापूर्वक "फेल ओवर" करने की अनुमति देता है।
• फेलियर पॉप: एक नया अतिरिक्त। जब किसी नोड से उसके फेलियर लिंक के माध्यम से गुजरा जाता है, तो एल्गोरिदम एक या अधिक टोकन को "पॉप" कर सकता है जो उस नोड पर समाप्त होने वाले मिलान किए गए हैं। यह सूची पूर्व-गणना की जाती है और संग्रहीत की जाती है।

3.3 एल्गोरिदम का चरणबद्ध विवरण

लंबाई $n$ के इनपुट शब्द के लिए, एल्गोरिदम वर्णों को एक ही पास में बाएं से दाएं संसाधित करता है। यह ट्राई में एक वर्तमान नोड बनाए रखता है। प्रत्येक नए वर्ण के लिए:

1. वर्तमान नोड से मिलान वाले किनारे का अनुसरण करने का प्रयास करें।
2. यदि सफल हो, तो चाइल्ड नोड पर जाएं। यदि यह नोड एक शब्दावली टोकन समापन बिंदु है, तो इसे एक संभावित मिलान के रूप में रिकॉर्ड करें।
3. यदि कोई मिलान वाला किनारा मौजूद नहीं है, तो वर्तमान नोड के फेलियर लिंक का अनुसरण करें। संबद्ध "फेलियर पॉप" सूची में संग्रहीत किसी भी टोकन को एकत्र करें। फिर, नए नोड से उसी इनपुट वर्ण का मिलान करने का पुनः प्रयास करें।

यह प्रक्रिया सुनिश्चित करती है कि प्रत्येक वर्ण को ठीक एक बार संसाधित किया जाता है, जो $O(n)$ समय की गारंटी देता है।

4. एंड-टू-एंड (ई2ई) वर्डपीस टोकनाइज़ेशन

पूर्ण वाक्यों या दस्तावेजों को टोकनाइज़ करने के लिए, लेखक पूर्व-टोकनाइज़ेशन चरण (रिक्त स्थान/विराम चिह्नों पर विभाजन) को लिनमैक्समैच के साथ एक एकल, एकीकृत एल्गोरिदम में एकीकृत करने का प्रस्ताव करते हैं। यह ई2ई वर्डपीस एल्गोरिदम कुल पाठ लंबाई के सापेक्ष रैखिक समय में भी कार्य करता है, अलग-अलग चरणों के ओवरहेड से बचता है। यह एक ही ट्राई ट्रैवर्सल ढांचे के भीतर सीमा पहचान को सबवर्ड मिलान के साथ चतुराई से इंटरलीव करता है।

5. प्रायोगिक परिणाम और प्रदर्शन

शोध पत्र उनके कार्यान्वयन की तुलना दो व्यापक रूप से उपयोग की जाने वाली लाइब्रेरीज़: हगिंगफेस टोकनाइज़र्स और टेंसरफ्लो टेक्स्ट के विरुद्ध प्रभावशाली बेंचमार्क प्रस्तुत करता है।

परिणाम प्रदर्शित करते हैं कि सैद्धांतिक $O(n)$ लाभ महत्वपूर्ण वास्तविक-विश्व प्रदर्शन लाभ में परिवर्तित होता है, विशेष रूप से लंबे पाठों के लिए या मोबाइल अनुमान जैसे विलंबता-संवेदनशील वातावरण में।

6. मुख्य अंतर्दृष्टि और विश्लेषण

मूल अंतर्दृष्टि

शोध पत्र की मौलिक सफलता केवल एक तेज़ टोकनाइज़र नहीं है; यह टोकनाइज़ेशन को एक स्ट्रिंग मिलान समस्या के रूप में औपचारिक मान्यता है जो शास्त्रीय ऑटोमेटा सिद्धांत द्वारा हल की जा सकती है। वर्डपीस के मैक्समैच को एक सरल लालची खोज से एक आहो-कोरासिक प्रकार में पुनः परिभाषित करके, लेखक सैद्धांतिक कंप्यूटर विज्ञान और अनुप्रयुक्त एनएलपी इंजीनियरिंग के बीच दशकों पुराने अंतर को पाटते हैं। यह उसी तरह याद दिलाता है जैसे साइकलजीएएन शोध पत्र ने छवि अनुवाद को एक चक्र-संगत प्रतिकूल शिक्षण समस्या के रूप में पुनः परिभाषित किया, एक नया प्रतिमान बनाया।

तार्किक प्रवाह

तर्क तार्किक रूप से पूर्ण है: 1) बाधा की पहचान करें ($O(n^2)$/$O(nk)$ जटिलता)। 2) एक सिद्ध, इष्टतम एल्गोरिदम (आहो-कोरासिक) से प्रेरणा लें। 3) इसे मैक्समैच की विशिष्ट बाधाओं (सभी मिलान किए गए टोकन आउटपुट करने की आवश्यकता, केवल अस्तित्व नहीं) के अनुकूल बनाएं। 4) इन बाधाओं को संभालने के लिए नई डेटा संरचनाएं (फेलियर पॉप्स) प्रस्तुत करें। 5) समाधान को पूर्ण पाइपलाइन (ई2ई) तक विस्तारित करें। समस्या से प्रेरणा, अनुकूलन और सामान्यीकरण तक का प्रवाह अनुकरणीय अनुप्रयुक्त शोध है।

शक्तियां और कमियां

शक्तियां: $O(n)$ गारंटी सैद्धांतिक रूप से सुंदर और व्यावहारिक रूप से सत्यापित है। पूर्व-प्रसंस्करण लागत एक बार का ओवरहेड है। मोबाइल/एज एनएलपी पर प्रभाव महत्वपूर्ण हो सकता है, जैसा कि लेखकों द्वारा नोट किया गया है और गूगल एआई जैसे संस्थानों से डिवाइस-पर एआई शोध के रुझानों द्वारा समर्थित है।

संभावित कमियां/चूक: शोध पत्र संवर्धित ट्राई (फेलियर लिंक्स और पॉप्स) के लिए मेमोरी ओवरहेड को हल्के से छूता है लेकिन गहराई से विश्लेषण नहीं करता है। विशाल शब्दावलियों (जैसे, बहुभाषी मॉडल) के लिए, यह महत्वहीन नहीं हो सकता है। इसके अलावा, बेंचमार्क, हालांकि प्रभावशाली है, विशिष्ट कार्यान्वयनों के विरुद्ध है। अन्य अनुकूलित मैक्समैच प्रकारों (जैसे, सफ़िक्स एरेज़ का उपयोग करके) के साथ तुलना दावे को मजबूत करेगी।

कार्रवाई योग्य अंतर्दृष्टि

एनएलपी व्यवसायियों के लिए: अपने टोकनाइज़ेशन विलंबता का तुरंत प्रोफाइल बनाएं। यदि यह आपके कुल अनुमान समय का 1-2% से अधिक है, विशेष रूप से स्ट्रीमिंग या मोबाइल अनुप्रयोगों के लिए, तो लिनमैक्समैच जैसे एल्गोरिदम को अपनाना एक उच्च-आरओआई अनुकूलन है। शोधकर्ताओं के लिए: यह कार्य दरवाजा खोलता है। क्या बाइट-पेयर एन्कोडिंग (बीपीई) या सेंटेंसपीस को अनुकूलित करने के लिए समान ऑटोमेटा-आधारित दृष्टिकोण संभव हैं? मूल विचार—बैकट्रैकिंग को पूर्व-गणना की गई स्थिति संक्रमणों से बदलना—एनएलपी में अन्य लालची विभाजन एल्गोरिदम के लिए व्यापक रूप से लागू है।

7. तकनीकी विवरण और गणितीय सूत्रीकरण

लिनमैक्समैच के मूल को औपचारिक रूप दिया जा सकता है। मान लें:

• $V$ = शब्दावली, स्ट्रिंग्स का एक सेट।
• $T$ = $V$ से निर्मित ट्राई।
• ट्राई नोड $u$ के लिए, $L(u)$ को जड़ से $u$ तक के वर्णों द्वारा निर्मित स्ट्रिंग होने दें।
• फेलियर फ़ंक्शन $f(u)$: नोड $v$ ऐसा कि $L(v)$, $L(u)$ का सबसे लंबा उचित प्रत्यय है जहां $v$ भी $T$ में एक नोड है।
• फेलियर पॉप $P(u)$: शब्दावली टोकन $t \in V$ का सेट जहां $t$, $L(u)$ का एक प्रत्यय है और जड़ से $f(u)$ (या $u$ स्वयं) तक के पथ पर एक नोड $w$ मौजूद है जहां $L(w) = t$। यह सभी नोड्स के लिए पूर्व-गणना की जाती है।

इनपुट स्ट्रिंग $S[1..n]$ का टोकनाइज़ेशन एक वर्तमान नोड $u$ (प्रारंभ में जड़) और एक सूचकांक $i$ को बनाए रखकर आगे बढ़ता है। जबकि $i \leq n$:

1. यदि $u$ का कोई चाइल्ड $v$ एज लेबल $S[i]$ के साथ मौजूद है, तो $u = v$, $i = i+1$ सेट करें। यदि $u$ किसी शब्दावली टोकन के अंत को चिह्नित करता है, तो इसे नोट करें।
2. अन्यथा, $P(u)$ में सभी टोकन आउटपुट करें। $u = f(u)$ सेट करें। $i$ को बढ़ाएं नहीं। यदि $u$ जड़ है और कोई चाइल्ड $S[i]$ से मेल नहीं खाता है, तो $i = i+1$ (अज्ञात वर्णों को संभालें)।

इस लूप की $O(n)$ जटिलता स्पष्ट है, क्योंकि $i$ या तो बढ़ता है या $u$ फेलियर लिंक्स का अनुसरण करता है, जिसे प्रति चरण एक स्थिरांक में समायोजित किया जा सकता है।

8. विश्लेषण ढांचा: एक केस स्टडी

परिदृश्य: स्मार्टफोन पर एक रीयल-टाइम वॉयस असिस्टेंट के लिए टोकनाइज़ेशन का अनुकूलन। वर्तमान पाइपलाइन एक लोकप्रिय लाइब्रेरी से एक मानक वर्डपीस टोकनाइज़र का उपयोग करती है।

ढांचा अनुप्रयोग:

1. आधार रेखा माप: प्रोफाइल दर्शाती है कि टोकनाइज़ेशन प्रति क्वेरी ~15ms का उपभोग करता है, जो कुल पाइपलाइन विलंबता (125ms) का 12% है। लक्ष्य है <100ms।
2. बाधा विश्लेषण: क्वेरीज़ अक्सर लंबी होती हैं (बोले गए वाक्य)। $O(nk)$ कारक महत्वपूर्ण है क्योंकि शब्दावली में तकनीकी यौगिक शब्द शामिल होते हैं।
3. समाधान डिजाइन: टोकनाइज़र को लिनमैक्समैच से बदलें। फेलियर लिंक्स/पॉप्स के साथ संवर्धित ट्राई बनाने की एक बार की लागत मॉडल परिनियोजन के दौरान स्वीकार्य है।
4. अपेक्षित परिणाम: शोध पत्र के 5-8x गति वृद्धि के आधार पर, टोकनाइज़ेशन समय ~2-3ms तक गिरना चाहिए, कुल विलंबता को ~112ms तक कम करना चाहिए, लक्ष्य की ओर एक ठोस कदम। स्थिर-समय गारंटी विलंबता की भविष्यवाणी में भी सुधार करती है।

यह केस स्टडी दर्शाती है कि एल्गोरिदम के सैद्धांतिक गुण आधुनिक एआई प्रणालियों में व्यावहारिक बाधाओं को कैसे सीधे संबोधित करते हैं।

9. अनुप्रयोग संभावनाएं और भविष्य की दिशाएं

कुशल, रैखिक-समय टोकनाइज़ेशन के निहितार्थ बर्ट से परे फैले हुए हैं:

• डिवाइस-पर और एज एआई: जैसे-जैसे जीपीटी-जैसी आर्किटेक्चर वाले मॉडल फोन के लिए आसवित किए जाते हैं, पूर्व-प्रसंस्करण में बचाया गया हर मिलीसेकंड जुड़ जाता है। यह कार्य उत्तरदायी, ऑफ़लाइन-सक्षम एनएलपी अनुप्रयोगों की अगली पीढ़ी के लिए मूलभूत है।
• स्ट्रीमिंग टोकनाइज़ेशन: रीयल-टाइम अनुवाद या लाइव कैप्शनिंग के लिए, $O(n)$ जटिलता भविष्यवाणी योग्य प्रदर्शन सुनिश्चित करती है। भविष्य का कार्य अनंत स्ट्रीम के लिए वृद्धिशील टोकनाइज़ेशन का अन्वेषण कर सकता है।
• बहुभाषी और बड़ी शब्दावलियां: 100+ भाषाओं में 1M+ टोकन वाली शब्दावलियों तक स्केलिंग। पूर्व-गणना की गई संरचनाओं के मेमोरी फुटप्रिंट को अनुकूलित करने के लिए शोध की आवश्यकता है, शायद संपीड़ित ट्राई या अनुमानित विधियों का उपयोग करके।
• मॉडल आर्किटेक्चर के साथ एकीकरण: क्या टोकनाइज़ेशन आंशिक रूप से सीखा जा सकता है या ट्रांसफॉर्मर की पहली परत के साथ विलय किया जा सकता है? संदर्भ पर आधारित "डायनामिक टोकनाइज़ेशन" एक खुली चुनौती बनी हुई है, लेकिन इस जैसे कुशल आधार एल्गोरिदम ऐसे अन्वेषण के लिए एक पूर्वापेक्षा हैं।

10. संदर्भ

1. Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. NAACL-HLT.
2. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Communications of the ACM.
3. Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL.
4. Wolf, T., et al. (2020). HuggingFace's Transformers: State-of-the-art Natural Language Processing. arXiv preprint arXiv:1910.03771.
5. Google. (2020). TensorFlow Text. https://www.tensorflow.org/text
6. Brown, T. B., et al. (2020). Language Models are Few-Shot Learners. NeurIPS.
7. Zhu, J.-Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. ICCV. (पैराडाइम-शिफ्टिंग पुनःपरिभाषा के उदाहरण के रूप में उद्धृत)।