Viterbi وbeam search وإعادة الترتيب بواسطة LLM: كيف تختار الخوارزمية معنى واحدًا من بين معانٍ عدة

يبني كاتب على Habr في عام 2026 سلسلة تمتد من خوارزميات NLP الكلاسيكية إلى إعادة الترتيب بواسطة LLM (LLM-reranking) انطلاقًا من مبدأ واحد: المهم ليس أفضل خطوة في كل دور، بل أفضل مسار عبر التسلسل كله. ويشرح ذلك من خلال مثال تفسير بطاقات التاروت.

لماذا تعطي خوارزمية greedy الجشعة نتيجة خاطئة

تختار خوارزمية greedy الخيار الأعلى احتمالًا في كل خطوة، بمعزل عن السياق اللاحق. وفي مهام NLP، مثل وسم أقسام الكلام (POS-tagging) والتعرّف على الكيانات المسمّاة (NER)، يؤدي ذلك إلى أخطاء منهجية، إذ قد يُفسد الوسم الأفضل محليًا اتساق التسلسل بأكمله.

تحلّ خوارزمية Viterbi المسألة بطريقة البرمجة الديناميكية: فهي تنظر في جميع المسارات عبر الحالات الخفية في آنٍ واحد، وتجد الحل الأمثل عالميًا. التعقيد الحسابي هو O(N × T²) مقابل O(N × T) لدى greedy، حيث N هو طول التسلسل وT هو عدد الحالات. هذا أكثر كلفة، لكنه يضمن الوصول إلى الحل الأمثل.

• Greedy: O(N × T)، سريعة، ولا تضمن الحل الأمثل عالميًا
• Viterbi: O(N × T²)، حل أمثل عالمي دقيق وفق النموذج
• Beam search: تحتفظ بأفضل k فرضية، وهي حل وسط بين الدقة والسرعة (القيم المعتادة k = 4–10)
• CRF (Conditional Random Fields): معاملات انتقال قابلة للتدريب فوق مفكّك Viterbi
• LLM reranking: نموذج لغوي يرتّب مجموعة المرشحين النهائية

ما الذي تضيفه beam search وCRF

تحتل beam search موقعًا وسطًا، فهي تحتفظ بأفضل k فرضية بدل فرضية واحدة. عند k = 1 تتطابق مع greedy، وعند k = ∞ تتطابق مع البحث الشامل الكامل. وقد وفّرت القيم من 4 إلى 10 توازنًا معقولًا في أنظمة الترجمة الآلية (MT) الكلاسيكية، ومنها Google Translate قبل الانتقال إلى المحوّلات (transformers).

تضيف CRF (الحقول العشوائية الشرطية) معاملات انتقال قابلة للتدريب: فبدل الاحتمالات الثابتة، يتعلم النموذج من البيانات أي تسلسلات الوسوم معقولة. ووفق نتائج اختبار CoNLL-2003، تفوّق BiLSTM-CRF على BiLSTM بدون CRF بمقدار 1–2 نقطة مئوية في مقياس F1. وهذه زيادة ثابتة جعلت CRF مكوّنًا قياسيًا في مسارات NER إلى حين ظهور BERT.

«أبيّن بمثال معاكس لماذا يخسر الاختيار الأفضل محليًا أمام الاختيار العالمي، وكذلك أين ينتهي البحث عن البنية وأين يبدأ توليد النص»، هكذا يصوغ كاتب المقالة على

Habr فكرته الأساسية.

أين تدخل LLM في هذه السلسلة

لا تستخدم المحوّلات (transformers) خوارزمية Viterbi مباشرة: فالنص يُولَّد بأسلوب انحداري ذاتي (autoregressive)، رمزًا بعد رمز، وطريقة فك الترميز القياسية هي beam search أو العيّنات (sampling، مثل nucleus وtemperature). أما LLM reranking فيسدّ الفجوة على المستوى التالي: يولّد النموذج 10–20 صيغة للإجابة، ثم يرتّبها نموذج LLM منفصل (أو النموذج نفسه بتعليمات prompt مختلفة) وفق معايير الجودة، وهي الترابط والدقة الواقعية والتوافق مع التعليمات.

وكما يشير الكاتب، فإن الحدّ الفاصل بين البحث عن البنية وتوليد النص يمرّ من هنا. وفهم هذا الحدّ يفسّر لماذا لا تزال إعادة الترتيب (reranking) في مسارات LLM الإنتاجية تمنح تحسنًا قابلًا للقياس في الجودة وفق المقاييس الآلية.

ماذا يعني ذلك

سلسلة greedy ← Viterbi ← beam search ← CRF ← LLM reranking هي تطوّر لمبدأ واحد: البحث عن أفضل مسار عالميًا عبر فضاء المعاني الممكنة. وفهم هذا التسلسل الهرمي يساعد على اختيار طريقة فك الترميز المناسبة لمهمة NLP محددة، ويفسّر القرارات المعمارية في النماذج اللغوية الحديثة.

الأسئلة الشائعة

ما الفرق بين خوارزمية Viterbi وbeam search؟

تضمن Viterbi إيجاد المسار الأمثل عالميًا عبر جميع الحالات، وهي خوارزمية دقيقة بتغطية كاملة لكل المسارات. أما beam search فتحتفظ بأفضل k فرضية فقط في كل خطوة: هي أسرع، لكنها لا تضمن الحل الأمثل.

هل تُستخدم Viterbi في نماذج LLM الحديثة؟

لا تُطبَّق Viterbi مباشرة في المحوّلات (transformers): فالتوليد الانحداري الذاتي يتطلب beam search أو العيّنات (sampling). وتبقى Viterbi مناسبة في طبقات CRF فوق المشفّرات (encoders)، مثلًا في مهام NER وPOS-tagging المبنية على معماريات شبيهة بـ BERT.