Tokenisation over Bounded Alphabets is Hard
यह शोध पत्र सिद्ध करता है कि बाउंडेड अल्फाबेट्स (bounded alphabets), जिसमें बाइनरी और यूनरी मामले भी शामिल हैं, पर टोकनाइज़ेशन मौलिक रूप से NP-कम्प्लीट और APX-हार्ड है, जो यह स्थापित करता है कि इसकी कम्प्यूटेशनल जटिलता एक अंतर्निहित बाधा है न कि बड़े इनपुट अल्फाबेट्स का कोई परिणाम, और वर्तमान व्यावहारिक एल्गोरिदम में ह्यूरिस्टिक दृष्टिकोणों की आवश्यकता को स्पष्ट करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप अपने एक दोस्त को एक गुप्त संदेश भेजने की कोशिश कर रहे हैं, लेकिन भेजने का एकमात्र तरीका यह है कि आप अपने शब्दों को छोटे, पूर्व-अनुमोदित टुकड़ों में तोड़ दें। यदि आप "superduper" भेजते हैं, तो आपको इसे "super" और "duper" में तोड़ना पड़ सकता है, बजाय पूरे शब्द के, क्योंकि आपके दोस्त के शब्दकोश में केवल ये दो हिस्से ही मौजूद हैं। यही टोकनाइज़ेशन (tokenization) का मूल है, जो कंप्यूटर को मानव भाषा समझने में सिखाने का पहला कदम है। इससे पहले कि एक कंप्यूटर एक वाक्य पढ़ सके, उसे इसे इन प्रबंधनीय "टोकन" (जैसे लेगो ब्रिक्स) में काटना होगा। लक्ष्य टेक्स्ट को इस तरह से काटना है जिससे कम से कम ईंटों का उपयोग हो, जिससे संदेश छोटा और भेजने में तेज़ हो जाए। इसे कंप्रेशन (compression) कहा जाता है। यदि आप एक किताब को कम ईंटों में कंप्रेस कर सकते हैं, तो कंप्यूटर इसे तेज़ी से पढ़ सकता है और इसे अधिक कुशलता से सीख सकता है। वर्षों से, वैज्ञानिक ऐसे चतुर, लालची एल्गोरिदम (algorithms) बना रहे हैं—जैसे कि एक बच्चा जो उपलब्ध सबसे बड़े लेगो टुकड़े को पकड़ने की कोशिश करता है—ताकि यह काटना स्वचालित रूप से किया जा सके। लेकिन एक बड़ा सवाल बना हुआ है: क्या किसी भी टेक्स्ट को काटने का कोई एकदम सही, गणितीय रूप से अनुकूल (optimal) तरीका है, या हम केवल "काफी अच्छे" अनुमानों तक ही सीमित हैं?
यह शोध पत्र, जिसका शीर्षक "Tokenisation Over Bounded Alphabets Is Hard" है, इस प्रश्न की गहराई में उतरता है। लेखक, जो ETH ज़्यूरिख और सोफिया विश्वविद्यालय के शोधकर्ताओं की एक टीम है, यह सिद्ध करने के लिए आगे बढ़े कि क्या उस सटीक काटने के तरीके को खोजना वास्तव में कंप्यूटरों के लिए एक दुःस्वप्न है, भले ही नियम सरल हों। वे काटने के दो मुख्य तरीकों पर ध्यान केंद्रित करते हैं: डायरेक्ट टोकनाइज़ेशन (Direct Tokenisation), जहाँ आप एक साथ ईंटों का सबसे अच्छा सेट (एक शब्दावली) चुनते हैं, और बॉटम-अप टोकनाइज़ेशन (Bottom-Up Tokenisation), जहाँ आप एकल अक्षरों से शुरू करते हैं और जब तक आपके पास गोंद खत्म न हो जाए, तब तक जोड़ियों को आपस में चिपकाते रहते हैं (merges)। उनकी कहानी का बड़ा मोड़ यह है कि वे इन तरीकों का परीक्षण मानव ध्वनियों के अनंत, अराजक वर्णमाला (alphabet) पर नहीं, बल्कि उन छोटे, निश्चित सेटों पर करते हैं जिनका उपयोग वास्तव में कंप्यूटरों में किया जाता है: बाइनरी (binary) (केवल 0 और 1, जैसे एक लाइट स्विच) और यूनरी (unary) (केवल एक एकल प्रतीक, जैसे समान प्रतीकों की एक माला)।
शोध पत्र का मुख्य निष्कर्ष एक स्पष्ट "नहीं, आप आसानी से सटीक समाधान नहीं खोज सकते" है। लेखक सिद्ध करते हैं कि सबसे सरल संभव वर्णमालाओं के साथ भी—जैसे कि केवल शून्य और एक से बनी दुनिया—टेक्स्ट को कंप्रेस करने का इष्टतम तरीका खोजना NP-complete और APX-hard है। सरल भाषा में, इसका अर्थ है कि आप कितनी भी कंप्यूटिंग शक्ति लगा दें, कोई भी तेज़, कुशल एल्गोरिदम सर्वोत्तम परिणाम की गारंटी नहीं दे सकता। यह केवल इसलिए कठिन नहीं है कि समस्या जटिल है; बल्कि यह मौलिक रूप से कठिन है। शोध पत्र स्पष्ट रूप से इस विचार को खारिज करता है कि कठिनाई मानव भाषा की जटिलता या विशाल वर्णमालाओं से आती है। इसके बजाय, वे दिखाते हैं कि बाधा सबसे सरल, सबसे प्रतिबंधित परिदृश्यों में भी मौजूद है। इसके अलावा, वे सिद्ध करते हैं कि आप एक उचित समय में सटीक उत्तर के "काफी करीब" भी नहीं पहुँच सकते; कोई बहुपद-समय सन्निकटन योजना (polynomial-time approximation scheme - PTAS) नहीं है जो सर्वोत्तम समाधान के करीब पहुँच सके, जब तक कि एक प्रमुख गणितीय रहस्य (P = NP) हल न हो जाए।
शोधकर्ता यूनरी (unary) मामले को भी संबोधित करते हैं, जहाँ वर्णमाला में केवल एक प्रतीक होता है (सोचिए कि एक संदेश पूरी तरह से "a" अक्षर से बना है)। आप सोच सकते हैं, "यदि मेरे पास केवल एक अक्षर है, तो यह कितना कठिन हो सकता है?" आश्चर्यजनक रूप से, वे यहाँ भी सिद्ध करते हैं कि टेक्स्ट को काटने का इष्टतम तरीका खोजना strongly NP-complete है। यह एक भारी गणितीय परिणाम है जो सुझाव देता है कि कठिनाई केवल बड़े डेटा सेटों की कोई विचित्रता नहीं है; यह टेक्स्ट को अनुकूलित रूप से कंप्रेस करने के तर्क में ही समाहित है।
तो, भविष्य के लिए इसका क्या अर्थ है? यह शोध पत्र समस्या को हल करने के लिए कोई नया, जादुई एल्गोरिदम पेश नहीं करता है। इसके बजाय, यह समझाता है कि क्यों आज के उपकरण, जैसे कि BPE (Byte-Pair Encoding) और UnigramLM, हेयुरिस्टिक (heuristic) होने के लिए मजबूर हैं—जिसका अर्थ है कि वे सटीक उत्तर की गणना करने के बजाय चतुर शॉर्टकट और अनुमानों का उपयोग करते हैं। लेखक तर्क देते हैं कि चूंकि सटीक उत्तर को जल्दी से खोजना कम्प्यूटेशनल रूप से असंभव है, इसलिए शोधकर्ताओं को "परफेक्ट टोकनाइज़र" के पवित्र लक्ष्य (holy grail) के पीछे भागना बंद कर देना चाहिए और इसके बजाय बेहतर, प्रमाणित रूप से अच्छे सन्निकटन (approximation) तरीकों पर ध्यान केंद्रित करना चाहिए। पूर्णता का द्वार बंद है, और चाबी मौजूद नहीं है; हम जो सर्वश्रेष्ठ कर सकते हैं वह यह है कि हमारे पास मौजूद सबसे अच्छे लॉक-पिक (ताला खोलने वाले औज़ार) को चुनना सीखें।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।