جدول المحتويات
1. المقدمة
تعتبر التجزئة (Tokenization) الخطوة التمهيدية الأساسية لجميع مهام معالجة اللغة الطبيعية تقريبًا، من تحليل المشاعر إلى الترجمة الآلية. تعتمد النماذج الحديثة مثل BERT وGPT-3 وXLNet على تجزئة الكلمات الفرعية، وتحديدًا خوارزميات مثل WordPiece، لتقسيم النص إلى وحدات ذات معنى مع التعامل مع الكلمات خارج المفردات. تتناول هذه الورقة البحثية عنق زجاجة حاسمًا: كفاءة خوارزمية تجزئة WordPiece نفسها.
يحدد المؤلفون أن استراتيجية المطابقة الأطول أولاً الجشعة القياسية (MaxMatch) المستخدمة في WordPiece لها تعقيد زمني دون الأمثل — $O(n^2)$ أو $O(nk)$، حيث $n$ هو طول الإدخال و $k$ هو أطول طول للوحدة المعجمية. يقترحون LinMaxMatch، وهي خوارزمية جديدة تحقق تعقيدًا زمنيًا خطيًا صارمًا $O(n)$ لتجزئة الكلمة الواحدة، وخوارزمية WordPiece الشاملة (من البداية إلى النهاية) متكاملة للنص العام.
2. الخلفية والأعمال ذات الصلة
تتضمن تجزئة WordPiece، كما تُستخدم في BERT، خطوتين: (1) تجزئة النص مسبقًا إلى كلمات بناءً على المسافات البيضاء وعلامات الترقيم، و (2) تطبيق خوارزمية MaxMatch على كل كلمة مقابل مفردات ثابتة. MaxMatch، المستخدمة أيضًا في تجزئة الكلمات الصينية، تختار بشكل تكراري أطول بادئة للسلسلة المتبقية التي تطابق وحدة معجمية من المفردات.
كانت الخوارزميات الفعالة السابقة محدودة بـ $O(n^2)$ أو $O(nk)$. عامل $k$ هذا يمثل مشكلة حيث يمكن أن تحتوي المفردات على وحدات معجمية طويلة (مثل "supercalifragilisticexpialidocious"). يكمن إسهام هذه الورقة في التخلص من هذا العامل المعتمد على المفردات تمامًا.
3. خوارزمية LinMaxMatch
3.1 الفكرة الأساسية والإلهام
مستوحاة خوارزمية LinMaxMatch من خوارزمية مطابقة السلاسل Aho-Corasick. الفكرة الرئيسية هي معاملة المفردات كمجموعة من الأنماط والكلمة المدخلة كنص. من خلال حساب هياكل البيانات المساعدة مسبقًا على شجرة البادئات (Trie) للمفردات، يمكن للخوارزمية تجنب التراجع أثناء المطابقة، وهو مصدر التعقيد التربيعي في خوارزمية MaxMatch الساذجة.
3.2 هياكل البيانات: Trie، وصلات الفشل، وقوائم الفشل
تستخدم الخوارزمية ثلاث هياكل بيانات أساسية تُبنى من المفردات خلال مرحلة معالجة مسبقة غير متصلة:
- Trie (شجرة البادئات): شجرة بادئات قياسية حيث تمثل كل عقدة حرفًا وتمثل المسارات من الجذر الوحدات المعجمية.
- رابط الفشل (مشابه لـ Aho-Corasick): بالنسبة لعقدة تمثل السلسلة $s$، يشير رابط الفشل الخاص بها إلى العقدة التي تمثل أطول لاحقة صحيحة لـ $s$ وهي أيضًا بادئة لوحدة معجمية ما. هذا يسمح للخوارزمية بـ "الانتقال الفعال" عند الفشل.
- قائمة الفشل (Failure Pop): إضافة جديدة. عند الانتقال من عقدة عبر رابط الفشل الخاص بها، قد "تستخرج" الخوارزمية وحدة معجمية واحدة أو أكثر تمت مطابقتها وتنتهي عند تلك العقدة. يتم حساب هذه القائمة مسبقًا وتخزينها.
3.3 شرح تفصيلي للخوارزمية
لكلمة مدخلة طولها $n$، تعالج الخوارزمية الأحرف من اليسار إلى اليمين في جولة واحدة. تحتفظ بالعقدة الحالية في شجرة البادئات. لكل حرف جديد:
- محاولة اتباع الحافة المطابقة من العقدة الحالية.
- إذا نجحت، الانتقال إلى العقدة الفرعية. إذا كانت هذه العقدة تمثل نهاية وحدة معجمية، تسجيلها كمطابقة محتملة.
- إذا لم توجد حافة مطابقة، اتبع رابط الفشل للعقدة الحالية. اجمع أي وحدات معجمية مخزنة في قائمة "الفشل" المرتبطة. ثم، أعد محاولة مطابقة نفس حرف الإدخال من العقدة الجديدة.
تضمن هذه العملية معالجة كل حرف مرة واحدة بالضبط، مما يضمن زمن $O(n)$.
4. تجزئة WordPiece الشاملة (من البداية إلى النهاية)
لتجزئة الجمل أو المستندات الكاملة، يقترح المؤلفون دمج خطوة التجزئة المسبقة (التقسيم على أساس المسافات البيضاء/علامات الترقيم) مع خوارزمية LinMaxMatch في خوارزمية موحدة واحدة. تعمل خوارزمية WordPiece الشاملة هذه أيضًا في زمن خطي بالنسبة للطول الإجمالي للنص، متجنبةً النفقات العامة للمراحل المنفصلة. إنها تدمج بذكاء اكتشاف الحدود مع مطابقة الكلمات الفرعية ضمن نفس إطار اجتياز شجرة البادئات.
5. النتائج التجريبية والأداء
تقدم الورقة معايير مقنعة تقارن تنفيذها بمكتبتين مستخدمتين على نطاق واسع: HuggingFace Tokenizers وTensorFlow Text.
مقارنة الأداء
متوسط التسريع:
- أسرع بـ 8.2 مرة من HuggingFace Tokenizers.
- أسرع بـ 5.1 مرة من TensorFlow Text.
تم الاختبار على مهام تجزئة النص العام.
تظهر النتائج أن الميزة النظرية $O(n)$ تترجم إلى مكاسب أداء كبيرة في العالم الحقيقي، خاصةً للنصوص الأطول أو في البيئات الحساسة للزمن مثل الاستدلال على الأجهزة المحمولة.
6. الرؤى الأساسية والتحليل
الرؤية الأساسية
الاختراق الأساسي للورقة ليس مجرد أداة تجزئة أسرع؛ بل هو الاعتراف الرسمي بالتجزئة كـ مشكلة مطابقة سلاسل قابلة للحل بواسطة نظرية الأوتوماتا الكلاسيكية. من خلال إعادة صياغة MaxMatch لـ WordPiece من بحث جشع ساذج إلى متغير من Aho-Corasick، يجسر المؤلفون فجوة عمرها عقود بين علوم الكمبيوتر النظرية وهندسة معالجة اللغة الطبيعية التطبيقية. هذا يذكرنا بكيفية إعادة ورقة CycleGAN صياغة ترجمة الصور كمشكلة تعلم خصومي متسقة دوريًا، مما خلق نموذجًا جديدًا.
التدفق المنطقي
الحجة منطقية ومحكمة: 1) تحديد عنق الزجاجة (تعقيد $O(n^2)$/$O(nk)$). 2) الاستلهام من خوارزمية مثبتة وأمثل (Aho-Corasick). 3) تكييفها مع القيود المحددة لـ MaxMatch (الحاجة إلى إخراج جميع الوحدات المعجمية المطابقة، وليس مجرد الوجود). 4) تقديم هياكل بيانات جديدة (قوائم الفشل) للتعامل مع هذه القيود. 5) توسيع الحل ليشمل خط الأنابيب الكامل (من البداية إلى النهاية). التدفق من المشكلة إلى الإلهام إلى التكيف إلى التعميم هو بحث تطبيقي نموذجي.
نقاط القوة والضعف
نقاط القوة: ضمان $O(n)$ أنيق نظريًا ومثبت عمليًا. تكلفة المعالجة المسبقة هي نفقات لمرة واحدة. يمكن أن يكون التأثير على معالجة اللغة الطبيعية على الأجهزة المحمولة/الطرفية كبيرًا، كما أشار المؤلفون ويدعمه اتجاهات البحث في الذكاء الاصطناعي على الجهاز من مؤسسات مثل Google AI.
نقاط ضعف/إغفالات محتملة: تلمس الورقة بشكل خفيف ولكنها لا تحلل بعمق النفقات العامة للذاكرة لشجرة البادئات المعززة (وصلات الفشل وقوائمه). بالنسبة للمفردات الضخمة (مثل النماذج متعددة اللغات)، قد يكون هذا غير تافه. علاوة على ذلك، فإن المعيار، على الرغم من إقناعه، هو ضد تنفيذات محددة. ستقوي المقارنة مع متغيرات MaxMatch الأخرى المحسنة (مثل استخدام مصفوفات اللواحق) الادعاء.
رؤى قابلة للتنفيذ
لممارسي معالجة اللغة الطبيعية: قم بتحليل زمن التأخير في التجزئة لديك على الفور. إذا كان أكثر من 1-2٪ من إجمالي وقت الاستدلال الخاص بك، خاصةً للتطبيقات المتدفقة أو على الأجهزة المحمولة، فإن اعتماد خوارزمية مثل LinMaxMatch هو تحسين ذو عائد مرتفع على الاستثمار. للباحثين: يفتح هذا العمل الباب. هل يمكن لنهج مماثل قائم على الأوتوماتا تحسين ترميز Byte-Pair (BPE) أو SentencePiece؟ الفكرة الأساسية — استبدال التراجع بانتقالات حالة محسوبة مسبقًا — قابلة للتطبيق على نطاق واسع على خوارزميات التجزئة الجشعة الأخرى في معالجة اللغة الطبيعية.
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$:
- إذا كان هناك طفل $v$ لـ $u$ يحمل تسمية الحافة $S[i]$، اضبط $u = v$، $i = i+1$. إذا كانت $u$ تشير إلى نهاية وحدة معجمية، قم بتسجيلها.
- وإلا، أخرج جميع الوحدات المعجمية في $P(u)$. اضبط $u = f(u)$. لا تزيد $i$. إذا كانت $u$ هي الجذر ولا يوجد طفل يطابق $S[i]$، إذن $i = i+1$ (للتعامل مع الأحرف غير المعروفة).
تعقيد $O(n)$ لهذه الحلقة واضح، حيث أن $i$ إما تزيد أو أن $u$ تتبع روابط الفشل، والتي يمكن تحويلها إلى وقت ثابت لكل خطوة.
8. إطار التحليل: دراسة حالة
السيناريو: تحسين التجزئة لمساعد صوتي فوري على هاتف ذكي. يستخدم خط الأنابيب الحالي أداة تجزئة WordPiece قياسية من مكتبة شائعة.
تطبيق الإطار:
- قياس الأساس: يظهر التحليل أن التجزئة تستهلك ~15 مللي ثانية لكل استعلام، وهو ما يمثل 12٪ من إجمالي زمن التأخير في خط الأنابيب (125 مللي ثانية). الهدف هو <100 مللي ثانية.
- تحليل عنق الزجاجة: غالبًا ما تكون الاستعلامات طويلة (جمل منطوقة). عامل $O(nk)$ كبير لأن المفردات تحتوي على كلمات مركبة تقنية.
- تصميم الحل: استبدال أداة التجزئة بـ LinMaxMatch. تكلفة بناء شجرة البادئات المعززة مع وصلات الفشل/قوائمه لمرة واحدة مقبولة أثناء نشر النموذج.
- النتيجة المتوقعة: بناءً على تسريع الورقة البحثية بمقدار 5-8 مرات، يجب أن ينخفض وقت التجزئة إلى ~2-3 مللي ثانية، مما يقلل إجمالي زمن التأخير إلى ~112 مللي ثانية، وهي خطوة قوية نحو الهدف. يضمن الضمان الزمني الثابت أيضًا تحسين قابلية التنبؤ بزمن التأخير.
توضح دراسة الحالة هذه كيف تعالج خصائص الخوارزمية النظرية القيود العملية في أنظمة الذكاء الاصطناعي الحديثة مباشرة.
9. آفاق التطبيق والاتجاهات المستقبلية
تتجاوز آثار التجزئة الفعالة ذات الزمن الخطي نطاق BERT:
- الذكاء الاصطناعي على الجهاز والطرف: مع تقطير نماذج مثل هياكل شبيهة بـ GPT للهواتف، فإن كل جزء من الألف من الثانية يتم توفيره في المعالجة المسبقة يتراكم. هذا العمل أساسي للجيل القادم من تطبيقات معالجة اللغة الطبيعية المستجيبة والقادرة على العمل دون اتصال.
- تجزئة التدفق: للترجمة الفورية أو التسميات التوضيحية المباشرة، يضمن تعقيد $O(n)$ أداءً يمكن التنبؤ به. يمكن للعمل المستقبلي استكشاف التجزئة التدريجية للتدفقات اللانهائية.
- المفردات متعددة اللغات والكبيرة: التوسع إلى مفردات تحتوي على 1 مليون+ وحدة معجمية عبر 100+ لغة. هناك حاجة للبحث لتحسين البصمة الذاكرة للهياكل المحسوبة مسبقًا، ربما باستخدام أشجار البادئات المضغوطة أو الطرق التقريبية.
- التكامل مع بنية النموذج: هل يمكن تعلم التجزئة جزئيًا أو دمجها مع الطبقة الأولى من المحول (transformer)؟ لا تزال "التجزئة الديناميكية" القائمة على السياق تحديًا مفتوحًا، ولكن الخوارزميات الأساسية الفعالة مثل هذه هي شرط أساسي لمثل هذا الاستكشاف.
10. المراجع
- Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. NAACL-HLT.
- Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Communications of the ACM.
- Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL.
- Wolf, T., et al. (2020). HuggingFace's Transformers: State-of-the-art Natural Language Processing. arXiv preprint arXiv:1910.03771.
- Google. (2020). TensorFlow Text. https://www.tensorflow.org/text
- Brown, T. B., et al. (2020). Language Models are Few-Shot Learners. NeurIPS.
- Zhu, J.-Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. ICCV. (مذكور كمثال لإعادة الصياغة التي تغير النموذج).