Viterbi, beam search и LLM-reranking: как алгоритм выбирает один смысл из многих

يبني مؤلفٌ على منصة Habr في عام 2026 سلسلةً تمتد من خوارزميات NLP الكلاسيكية إلى 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 توازناً معقولاً في أنظمة الترجمة الآلية الكلاسيكية، بما فيها Google Translate قبل التحول إلى المحوِّلات.

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

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

Habr الفكرةَ الجوهرية.

أين تندرج LLMs في هذه السلسلة

لا تستخدم المحوِّلات Viterbi مباشرةً: يُولَّد النص بصورة انحدارية ذاتية، رمزاً رمزاً؛ وطريقة الفك القياسية هي beam search أو أسلوب الأخذ بالعينات (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 في LLMs الحديثة؟

لا تُستخدم Viterbi مباشرةً في المحوِّلات: يتطلب التوليد الانحداري الذاتي beam search أو أسلوب الأخذ بالعينات. تظل Viterbi ذات صلة في طبقات CRF فوق المُشفِّرات — على سبيل المثال، في مهام NER ووسم أجزاء الكلام المستندة إلى معماريات مشابهة لـ BERT.