الگوریتم Viterbiبا برنامه‌ریزی پویا، محتمل‌ترین مسیرِ کاملِ وضعیت‌ها را برای یک دنبالهٔ مشاهده پیدا می‌کند. بهترین انتخابِ همین لحظه لزوماً بهترین مسیر تا پایان نیست. مثال این صفحه دقیقاً همین اختلاف را با دو وضعیت و سه مشاهده و بازگردانیِ مسیر نشان می‌دهد.
پرسشِ مسیر با پرسشِ احتمالِ مشاهده فرق دارد
در راهنمای HMMوForward سهمِ همهٔ مسیرها جمع می‌شود. اینجا در هر خانه بهترین مسیرِ منتهی به همان وضعیت را نگه می‌داریم. بیشینهٔ احتمالِ مشترک P(path,O)برای مشاهدهٔ ثابت و دارای احتمال مثبت، همان مسیری را برمی‌گزیند که P(path|O)را بیشینه می‌کند؛ خودِ عددِ مشترک هنوز احتمالِ شرطیِ نرمال‌شده نیست.
پارامترهای یک مثالِ تازه
شروع درAاحتمال۰٫۹و درBاحتمال۰٫۱دارد. سطرِ انتقالAبرابر[۰٫۹،۰٫۱]و سطرBبرابر[۰٫۰۱،۰٫۹۹]است. احتمال مشاهدهٔRدرAبرابر۰٫۴و درBبرابر۰٫۹است؛ احتمالِ نمادِ دیگرBمکملِ هرکدام و Gدر هر دو صفر است. دنبالهٔ مشاهده R,R,Rاست. این اعداد از مثالِ Forwardیا یک مدلِ واقعی گرفته نشده‌اند؛ برای این مسئله ساخته شده‌اند.
انتخابِ حریصانه چه می‌کند؟
در شروع،۰٫۹×۰٫۴=۰٫۳۶از۰٫۱×۰٫۹=۰٫۰۹بیشتر است، پس روشِ حریصانهAرا برمی‌دارد. ازAهم در هر گام، ماندن درAو دیدنRامتیاز۰٫۹×۰٫۴=۰٫۳۶دارد؛ رفتن بهBو دیدنRفقط۰٫۱×۰٫۹=۰٫۰۹است. نتیجهٔ این قاعده A,A,Aبا احتمالِ مشترک۰٫۰۴۶۶۵۶می‌شود.
اما مسیرB,B,Bبا شروعِ ضعیف‌تر، دو بار از ماندگاری۰٫۹۹و انتشار۰٫۹استفاده می‌کند و احتمالِ مشترکش۰٫۰۷۱۴۴۹۲۹است. کد تمام هشت مسیر را جدا می‌شمارد و تأیید می‌کند همین مسیر برنده است. حریصانه برای هر گام تعهدِ برگشت‌ناپذیر می‌سازد؛ Viterbiدو حالتِ پایان را هم‌زمان نگه می‌دارد.
دلتا و backpointerرا با هم نگه داریم
برای رسیدن به وضعیتj، امتیازِ هر پایانِ قبلی را در انتقال بهjضرب می‌کنیم و بزرگ‌ترین را انتخاب می‌کنیم؛ سپس احتمالِ مشاهدهٔ جدید درjضرب می‌شود. این مقدارِ دلتا، امتیازِ بهترین پیشوندِ همان پایان است. backpointerهم شمارهٔ وضعیتی را نگه می‌دارد که این بهترین سهم از آن آمده است.
پس از آخرین مشاهده، پایانِ دارای بزرگ‌ترین دلتا انتخاب می‌شود. از آخر به اول با backpointerها برمی‌گردیم؛ برداشتنِ بزرگ‌ترین خانهٔ هر سطر بدون دنبال‌کردنِ پیوندها می‌تواند مسیرِ ناسازگار بسازد. فایل، همهٔ دلتاها، اشاره‌گرها، مسیرِ برگشتی و احتمالِ هشت مسیر را چاپ می‌کند.
تساوی، مشاهدهٔ ناممکن و عددهای کوچک
در تساویِ دقیق، این کد در هر انتخاب شمارهٔ کوچک‌ترِ وضعیت را می‌گیرد. این سیاستِ محلی را تضمینِ عمومیِ کوچک‌ترین مسیرِ واژه‌نامه‌ای نمی‌نامیم. یک ورودیِ متقارنِ جدا برای کنترل همین تساوی داریم. برای مشاهدهٔ Gهمهٔ امتیازها صفر می‌شوند؛ خروجی مسیر Noneو امتیاز صفر است تا یک مسیرِ ظاهراً معتبر به مشاهدهٔ ناممکن نسبت داده نشود.
دنبالهٔ خالی و نمادِ ناشناخته با خطا رد می‌شوند. محاسبه با Fractionبرای سه گام است؛ هیچ نسخهٔ log-space، کتابخانهٔ HMMیا آموزشِ پارامتر اجرا نشده است. در دنباله‌های بلند، روشِ عددی و حافظهٔ اشاره‌گرها باید جدا طراحی شوند. انتخابِ مسیرِ بیشینه، انتخابِ مستقلِ وضعیت با بیشترین احتمالِ حاشیه‌ای در هر گام هم نیست.
این خروجی برای چه تصمیمی مناسب است؟
اگر خروجیِ موردنیاز یک مسیرِ سازگار تحت مدلِ مشخص باشد، جدول و قراردادِ مسیر مفیدند؛ اگر احتمالِ کل مشاهده را می‌خواهید، باید سراغ جمعِ Forwardبروید. هیچ‌کدام بدون ارزیابیِ مدل، صحتِ وضعیتِ واقعی را تضمین نمی‌کنند. ادامهٔ مفاهیم در مبانی هوش مصنوعی است؛ کاربردِ این الگوریتم در فناوری‌های گفتاری، شاهدِ استفادهٔ آن در معماریِ اپرانگار نیست.
فایل تمرین و منبع
جدولِ max، بازگشت مسیر و شاهدِ شکستِ انتخاب حریصانه · پارامترهای مسئلهٔ decodingو قراردادِ تساوی
- درس اصلی Texas A&M؛ اسلایدهای الگوریتم Viterbiو بازگردانی مسیر
- JurafskyوMartin؛ نسخهٔ۲۹دسامبر۲۰۲۱، بخشA.4
منابع در ۳ نوامبر ۲۰۲۶ خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.