توکن‌سازی Fast WordPiece: یک الگوریتم خطی‌زمان برای BERT و فراتر از آن

فهرست مطالب

1. مقدمه

توکن‌سازی، گام پیش‌پردازش بنیادین برای تقریباً همه وظایف پردازش زبان طبیعی (NLP)، از تحلیل احساسات تا ترجمه ماشینی است. مدل‌های مدرنی مانند BERT، GPT-3 و XLNet به توکن‌سازی زیرواژه‌ای، به‌طور خاص الگوریتم‌هایی مانند WordPiece، متکی هستند تا متن را به واحدهای معنادار شکسته و همزمان با واژگان خارج از واژگان مقابله کنند. این مقاله به یک گلوگاه حیاتی می‌پردازد: کارایی خود الگوریتم توکن‌سازی WordPiece.

نویسندگان تشخیص می‌دهند که استراتژی استاندارد حریصانه «طولانی‌ترین تطابق اول» (MaxMatch) که در WordPiece استفاده می‌شود، پیچیدگی زمانی بهینه‌ای ندارد—$O(n^2)$ یا $O(nk)$، که در آن $n$ طول ورودی و $k$ حداکثر طول توکن است. آنها LinMaxMatch را پیشنهاد می‌دهند، یک الگوریتم نوآورانه که برای توکن‌سازی تک‌واژه به پیچیدگی زمانی خطی دقیق $O(n)$ دست می‌یابد، و یک الگوریتم یکپارچه End-to-End (E2E) WordPiece برای متن عمومی.

2. پیشینه و کارهای مرتبط

توکن‌سازی WordPiece، همان‌طور که در BERT استفاده می‌شود، شامل دو مرحله است: (1) پیش‌توکن‌سازی متن به کلمات بر اساس فاصله و علائم نگارشی، و (2) اعمال الگوریتم MaxMatch بر هر کلمه در برابر یک واژگان ثابت. MaxMatch، که در تقسیم‌بندی کلمات چینی نیز استفاده می‌شود، به‌طور تکراری طولانی‌ترین پیشوند باقی‌مانده از رشته را انتخاب می‌کند که با یک توکن واژگان مطابقت دارد.

الگوریتم‌های کارآمد قبلی به $O(n^2)$ یا $O(nk)$ محدود بودند. عامل $k$ مشکل‌ساز است زیرا واژگان می‌توانند شامل توکن‌های طولانی (مانند "supercalifragilisticexpialidocious") باشند. سهم این مقاله در حذف کامل این عامل وابسته به واژگان است.

3. الگوریتم LinMaxMatch

3.1 ایده اصلی و الهام‌بخش

LinMaxMatch از الگوریتم تطابق رشته Aho-Corasick الهام گرفته شده است. بینش کلیدی این است که واژگان را به عنوان مجموعه‌ای از الگوها و کلمه ورودی را به عنوان متن در نظر بگیریم. با پیش‌محاسبه ساختارهای داده کمکی روی درخت پیشوندی واژگان، الگوریتم می‌تواند از بازگشت به عقب در حین تطابق اجتناب کند، که منبع پیچیدگی درجه دوم در MaxMatch ساده است.

3.2 ساختارهای داده: درخت پیشوندی، پیوندهای شکست و پاپ‌های شکست

الگوریتم از سه ساختار داده اصلی استفاده می‌کند که در یک فاز پیش‌پردازش آفلاین از واژگان ساخته می‌شوند:

• درخت پیشوندی (Trie): یک درخت پیشوندی استاندارد که هر گره یک نویسه را نشان می‌دهد و مسیرها از ریشه نشان‌دهنده توکن‌های واژگان هستند.
• پیوند شکست (مشابه Aho-Corasick): برای یک گره که رشته $s$ را نشان می‌دهد، پیوند شکست آن به گره‌ای اشاره می‌کند که طولانی‌ترین پسوند صحیح $s$ را نشان می‌دهد که همچنین پیشوند برخی توکن‌های واژگان است. این به الگوریتم اجازه می‌دهد تا به طور کارآمد «شکست را مدیریت کند».
• پاپ شکست: یک افزودگی نوآورانه. هنگام پیمایش از یک گره از طریق پیوند شکست آن، الگوریتم ممکن است یک یا چند توکن را که در آن گره به پایان رسیده‌اند، «پاپ» کند. این لیست از پیش محاسبه و ذخیره می‌شود.

3.3 گام‌به‌گام الگوریتم

برای یک کلمه ورودی به طول $n$، الگوریتم نویسه‌ها را از چپ به راست در یک پاس پردازش می‌کند. یک گره جاری در درخت پیشوندی را حفظ می‌کند. برای هر نویسه جدید:

1. سعی کنید از گره جاری، یال تطابقی را دنبال کنید.
2. در صورت موفقیت، به گره فرزند بروید. اگر این گره نقطه پایان یک توکن واژگان باشد، آن را به عنوان یک تطابق بالقوه ثبت کنید.
3. اگر هیچ یال تطابقی وجود نداشت، پیوند شکست گره جاری را دنبال کنید. هر توکن ذخیره شده در لیست «پاپ شکست» مرتبط را جمع‌آوری کنید. سپس، تطابق همان نویسه ورودی را از گره جدید دوباره امتحان کنید.

این فرآیند تضمین می‌کند که هر نویسه دقیقاً یک بار پردازش می‌شود و زمان $O(n)$ را تضمین می‌کند.

4. توکن‌سازی End-to-End (E2E) WordPiece

برای توکن‌سازی جملات یا اسناد کامل، نویسندگان پیشنهاد می‌کنند که مرحله پیش‌توکن‌سازی (تقسیم بر اساس فاصله/علائم نگارشی) با LinMaxMatch در یک الگوریتم واحد و یکپارچه ادغام شود. این الگوریتم E2E WordPiece نیز نسبت به طول کل متن در زمان خطی عمل می‌کند و از سربار مراحل جداگانه اجتناب می‌کند. این الگوریتم به طور هوشمندانه‌ای تشخیص مرزها را با تطابق زیرواژه در همان چارچوب پیمایش درخت پیشوندی در هم می‌آمیزد.

5. نتایج تجربی و عملکرد

مقاله معیارهای قانع‌کننده‌ای را ارائه می‌دهد که پیاده‌سازی خود را با دو کتابخانه پرکاربرد مقایسه می‌کند: HuggingFace Tokenizers و TensorFlow Text.

نتایج نشان می‌دهد که مزیت نظری $O(n)$ به دستاوردهای عملکردی قابل توجهی در دنیای واقعی تبدیل می‌شود، به ویژه برای متون طولانی‌تر یا در محیط‌های حساس به تأخیر مانند استنتاج موبایل.

6. بینش‌های کلیدی و تحلیل

بینش اصلی

دستاورد بنیادی مقاله فقط یک توکن‌ساز سریع‌تر نیست؛ بلکه شناسایی رسمی توکن‌سازی به عنوان یک مسئله تطابق رشته است که توسط نظریه اتوماتای کلاسیک قابل حل است. با بازتعریف MaxMatch در WordPiece از یک جستجوی حریصانه ساده به یک گونه Aho-Corasick، نویسندگان پلی بین علوم کامپیوتر نظری و مهندسی NLP کاربردی ایجاد می‌کنند. این یادآور نحوه‌ای است که مقاله CycleGAN ترجمه تصویر را به عنوان یک مسئله یادگیری متخاصم با چرخه سازگار بازتعریف کرد و یک پارادایم جدید ایجاد نمود.

جریان منطقی

استدلال از نظر منطقی محکم است: 1) شناسایی گلوگاه (پیچیدگی $O(n^2)$/$O(nk)$). 2) الهام گرفتن از یک الگوریتم اثبات‌شده و بهینه (Aho-Corasick). 3) تطبیق آن با محدودیت‌های خاص MaxMatch (نیاز به خروجی همه توکن‌های تطبیق‌یافته، نه فقط وجود). 4) معرفی ساختارهای داده نوآورانه (پاپ‌های شکست) برای مدیریت این محدودیت‌ها. 5) گسترش راه‌حل به خط لوله کامل (E2E). جریان از مسئله به الهام به تطبیق به تعمیم، نمونه‌ای از پژوهش کاربردی است.

نقاط قوت و ضعف

نقاط قوت: تضمین $O(n)$ از نظر نظری زیبا و از نظر عملی تأیید شده است. هزینه پیش‌پردازش یک سربار یک‌باره است. تأثیر آن بر NLP موبایل/لبه می‌تواند قابل توجه باشد، همان‌طور که نویسندگان اشاره کرده‌اند و توسط روندهای پژوهش هوش مصنوعی روی دستگاه از مؤسساتی مانند Google AI پشتیبانی می‌شود.

نقاط ضعف/کاستی‌های بالقوه: مقاله به طور سطحی به سربار حافظه برای درخت پیشوندی تقویت‌شده (پیوندها و پاپ‌های شکست) می‌پردازد اما آن را به عمق تحلیل نمی‌کند. برای واژگان عظیم (مانند مدل‌های چندزبانه)، این می‌تواند قابل توجه باشد. علاوه بر این، معیارها، اگرچه چشمگیر هستند، در برابر پیاده‌سازی‌های خاصی هستند. مقایسه با سایر گونه‌های بهینه‌شده MaxMatch (مانند استفاده از آرایه‌های پسوندی) ادعا را تقویت می‌کند.

بینش‌های عملی

برای متخصصان NLP: بلافاصله تأخیر توکن‌سازی خود را پروفایل کنید. اگر بیش از ۱-۲٪ از کل زمان استنتاج شما باشد، به ویژه برای برنامه‌های استریم یا موبایل، اتخاذ الگوریتمی مانند LinMaxMatch یک بهینه‌سازی با بازده سرمایه بالا است. برای پژوهشگران: این کار درها را می‌گشاید. آیا رویکردهای مشابه مبتنی بر اتوماتا می‌توانند Byte-Pair Encoding (BPE) یا SentencePiece را بهینه کنند؟ ایده اصلی—جایگزینی بازگشت به عقب با انتقال حالت پیش‌محاسبه‌شده—به طور گسترده‌ای برای سایر الگوریتم‌های تقسیم‌بندی حریصانه در NLP قابل اعمال است.

7. جزئیات فنی و فرمول‌بندی ریاضی

هسته LinMaxMatch را می‌توان صوری کرد. فرض کنید:

• $V$ = واژگان، مجموعه‌ای از رشته‌ها.
• $T$ = درخت پیشوندی ساخته شده از $V$.
• برای یک گره درخت $u$، $L(u)$ رشته تشکیل شده از نویسه‌های ریشه تا $u$ باشد.
• تابع شکست $f(u)$: گره $v$ به گونه‌ای که $L(v)$ طولانی‌ترین پسوند صحیح $L(u)$ باشد که $v$ نیز یک گره در $T$ است.
• پاپ شکست $P(u)$: مجموعه توکن‌های واژگان $t \in V$ که $t$ یک پسوند $L(u)$ است و یک گره $w$ در مسیر از ریشه به $f(u)$ (یا خود $u$) وجود دارد که $L(w) = t$. این برای همه گره‌ها پیش‌محاسبه می‌شود.

توکن‌سازی رشته ورودی $S[1..n]$ با حفظ یک گره جاری $u$ (در ابتدا ریشه) و یک اندیس $i$ پیش می‌رود. در حالی که $i \leq n$:

1. اگر یک فرزند $v$ از $u$ با برچسب یال $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. چارچوب تحلیل: یک مطالعه موردی

سناریو: بهینه‌سازی توکن‌سازی برای یک دستیار صوتی بلادرنگ روی یک تلفن هوشمند. خط لوله فعلی از یک توکن‌ساز استاندارد WordPiece از یک کتابخانه محبوب استفاده می‌کند.

اعمال چارچوب:

1. اندازه‌گیری پایه: پروفایل نشان می‌دهد توکن‌سازی حدود ۱۵ میلی‌ثانیه در هر پرس‌وجو مصرف می‌کند که ۱۲٪ از کل تأخیر خط لوله (۱۲۵ میلی‌ثانیه) است. هدف کمتر از ۱۰۰ میلی‌ثانیه است.
2. تحلیل گلوگاه: پرس‌وجوها اغلب طولانی هستند (جملات گفتاری). عامل $O(nk)$ قابل توجه است زیرا واژگان شامل کلمات مرکب فنی هستند.
3. طراحی راه‌حل: جایگزینی توکن‌ساز با LinMaxMatch. هزینه یک‌باره ساخت درخت پیشوندی تقویت‌شده با پیوندها/پاپ‌های شکست در طول استقرار مدل قابل قبول است.
4. نتیجه مورد انتظار: بر اساس افزایش سرعت ۵-۸ برابری مقاله، زمان توکن‌سازی باید به حدود ۲-۳ میلی‌ثانیه کاهش یابد و کل تأخیر را به حدود ۱۱۲ میلی‌ثانیه برساند، گامی محکم به سوی هدف. تضمین زمان ثابت نیز پیش‌بینی‌پذیری تأخیر را بهبود می‌بخشد.

این مطالعه موردی نشان می‌دهد که چگونه ویژگی‌های نظری الگوریتم مستقیماً به محدودیت‌های عملی در سیستم‌های هوش مصنوعی مدرن می‌پردازد.

9. چشم‌انداز کاربرد و جهت‌های آینده

پیامدهای توکن‌سازی کارآمد و خطی‌زمان فراتر از BERT است:

• هوش مصنوعی روی دستگاه و لبه: همان‌طور که مدل‌هایی مانند معماری‌های شبیه GPT برای تلفن‌ها تقطیر می‌شوند، هر میلی‌ثانیه ذخیره شده در پیش‌پردازش تشدید می‌شود. این کار برای نسل بعدی برنامه‌های NLP پاسخگو و قادر به کار آفلاین، بنیادین است.
• توکن‌سازی استریم: برای ترجمه بلادرنگ یا زیرنویس زنده، پیچیدگی $O(n)$ عملکرد قابل پیش‌بینی را تضمین می‌کند. کار آینده می‌تواند توکن‌سازی افزایشی برای جریان‌های بی‌نهایت را بررسی کند.
• واژگان چندزبانه و بزرگ: مقیاس‌پذیری به واژگان با بیش از ۱ میلیون توکن در بیش از ۱۰۰ زبان. پژوهش برای بهینه‌سازی ردپای حافظه ساختارهای پیش‌محاسبه‌شده مورد نیاز است، شاید با استفاده از درخت‌های پیشوندی فشرده یا روش‌های تقریبی.
• ادغام با معماری مدل: آیا توکن‌سازی می‌تواند تا حدی یاد گرفته شود یا با لایه اول یک ترانسفورمر ادغام شود؟ «توکن‌سازی پویا» مبتنی بر زمینه همچنان یک چالش باز است، اما الگوریتم‌های پایه کارآمد مانند این، پیش‌نیازی برای چنین اکتشافاتی هستند.

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. (به عنوان نمونه‌ای از بازتعریف تغییردهنده پارادایم ذکر شده است).