فهم خوارزميّة فيتربي
الترشيح والتنعيم يجيبان عن أسئلة تخصّ خطوة زمنيّة واحدة في كلّ مرّة. أمّا طلب الحكاية كلّها التي تفسّر المشاهدات خير تفسير فسؤال آخر، والإجابة عنه بأخذ أرجح حالة عند كلّ خطوة على حدة خطأ: فالفائزون خطوةً خطوة لا يؤلّفون بالضرورة متتالية ممكنة، فضلًا عن أن تكون راجحة.
وتُصلح خوارزميّة فيتربي ذلك بتغيير واحد في العلاقة الأماميّة. فحيث يجمع الترشيح على سبل بلوغ حالة، يأخذ فيتربي الأعظم، حاملًا احتمال أفضل مسار إلى كلّ حالة بدل الاحتمال الكلّيّ لكلّ المسارات. وتسجيل السلف الذي حقّق ذلك الأعظم يعطي مؤشّرًا خلفيًّا، وتتبّع المؤشّرات رجوعًا من أفضل حالة نهائيّة يعيد بناء المتتالية.
والتوفير هو التوفير الذي تشتريه البرمجة الدينامية دائمًا. فهناك 2^t حكاية على t من الحالات الثنائيّة، والعلاقة تمسّ كلّ حالة مرّةً في كلّ خطوة، فالكلفة خطّيّة في t وتربيعيّة في عدد الحالات. ولا شيء يُقرَّب: فالجواب هو المعظِّم الدقيق.
وأيّ السؤالين يُطرَح قرارُ نمذجةٍ لا تفصيلٌ تقنيّ. فالهوامش خطوةً خطوة هي الصواب حين يُعمَل بكلّ خطوة على حدة؛ وفيتربي هو الصواب حين يجب أن تتماسك الحالات، كفكّ ترميز رسالة، أو محاذاة متتالية، أو إعادة بناء مسار، حيث يكون انتقال مستحيل فيزيائيًّا في وسط الجواب أسوأ من جواب أقلّ رجحانًا قليلًا.
كيفية الحساب
m_{1:t+1} = P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{\mathbf{x}_t} \big( P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)\, m_{1:t} \big)
حيث
- m_{1:t}
- احتمال أفضل مسار ينتهي عند كلّ حالة في اللحظة t
- P(\mathbf{X}_{t+1} \mid \mathbf{x}_t)
- نموذج الانتقال
- P(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1})
- نموذج المجسّ
مثال على خوارزميّة فيتربي
في عالم المظلّة - يستمرّ المطر باحتمال 0.7، وتظهر المظلّة في تسعين في المئة من الأيّام الماطرة وعشرين في المئة من الجافّة - خذ المشاهدات الثلاث: بلا مظلّة، مظلّة، بلا مظلّة.
تنعيم اليوم الثاني وحده يعطي احتمال مطر قدره 0.554، فالجواب خطوةً خطوة يقول إنّها أمطرت. أمّا أرجح حكاية لثلاثة أيّام، وقد وجدها فيتربي وأكّدها تعداد الحكايات الثماني، فهي الجفاف في الأيّام الثلاثة، باحتمال 0.402.
ولا تناقض في ذلك. فالمطر في اليوم الثاني هو أرجح قيمة لذلك اليوم حين يُتوسَّط على بقيّة الأيّام؛ والحكاية الجافّة كلّها هي أرجح تركيبة حين لا يُتوسَّط عليها. فللسؤالين جوابان مختلفان لأنّ الأيّام غير مستقلّة.
الأسئلة الشائعة
هل مسار فيتربي هو مسار العظائم المنعَّمة؟
ليس عمومًا، ومثال المظلّة أعلاه مثالٌ مضادّ وُجد بالتعداد لا بالدعوى. بل قد تؤلّف العظائم المنعَّمة متتالية احتمالها صفر إن كان أحد الانتقالات مستحيلًا.
هل تعمل في فضاء لوغاريتميّ؟
تُشغَّل فيه عادةً. فالعلاقة تضرب احتمالات، وذلك يهبط دون حدّ التمثيل على متتالية طويلة؛ وأخذ اللوغاريتمات يحوّل الجداءات إلى مجاميع، ولا يتأثّر الأعظم لأنّ اللوغاريتم متزايد.
الخلاصة
استبدل بالمجموع في العلاقة الأماميّة أعظمَ قيمة، واحتفظ بمؤشّر خلفيّ، تحصل على أرجح حكاية في زمن خطّيّ. ولكن اعلم أنّها تجيب عن سؤال غير الذي يجيب عنه التنعيم، وأنّ الاثنين قد يختلفان حقًّا.