الگوریتم ویتربی
الگوریتم ویتربی الگوریتمی پویا برای پیدا کردن محتمل‌ترین مسیر از حالت‌های پنهان، با داشتن یک توالی از مشاهدات است.
این الگوریتم اغلب در مواردی بکار می‌رود که با داشتن یک مدل پنهان مارکف و توالی‌ای از مشاهدات، می‌خواهیم بدانیم چه توالی‌ای از حالت‌ها (مسیر) این مشاهدات را تولید کرده‌اند. به عبارت دیگر ما دنبال محتمل‌ترین مسیر به‌وجودآورندهٔ مشاهدات در یک مدل پنهان مارکف هستیم.
در بسیاری از کاربردهای مدل‌های پنهان مارکف، متغیرهای پنهان تفسیر معناداری دارند و در نتیجه یکی از مهم‌ترین مسائل در این حیطه، پیدا کردن محتمل‌ترین توالی از متغیرهای پنهان با داشتن یک توالی از مشاهدات است. به‌عنوان مثال، در حوزهٔ بازشناسی گفتار، می‌خواهیم یک توالی از واج‌ها با استفاده از توالی‌ای از آواها داشته باشیم.
این مسئله نباید با مسئلهٔ پیدا کردن محتمل‌ترین مجموعه از حالت‌های پنهان اشتباه گرفته شود. مسئلهٔ دوم می‌تواند با استفاده از الگوریتم پس‌رو-پیش‌رو حل شود. بدین صورت که ابتدا توزیع حاشیه‌ای برای هر متغیر نهان را به‌دست آورده و سپس جداگانه آن‌ها را بیشینه می‌کنیم. اما در حالت کلی، مسئلهٔ پیدا کردن محتمل‌ترین "توالی" پراهمیت‌تر بوده و الگوریتم بهینهٔ ارائه‌شده برای آن، الگوریتم جمع-بیشینه که در حیطهٔ مدل‌های پنهان مارکف، به آن الگوریتم "ویتربی" گفته می‌شود استفاده کرد.
در مسائل طبیعی مانند در، همیشه واقعیت منطبق بر محتمل‌ترین مسیر نیست. اما بسیاری اوقات محتمل‌ترین مسیر نیز اطلاعات خوبی در اختیار می‌گذارد.
در این بخش، به بررسی یکی از کاربردهای این مسئله در بیوانفورماتیک می‌پردازیم. مسئله جزایر سی‌پی‌جی (CpG islands) -پیدا کردن ناحیه‌ای از ژنوم که فرکانس بالایی از مکان‌های CG در آن وجود دارد- است. این مسئله را می‌توان با استفاده از دو مدل مخفی مارکف مدل کرد. کافی است حالت‌های مخفی را دو حالتِ formula_1 و formula_2 در نظر گیریم به‌طوری که زمانی که در ناحیهٔ سی‌جی‌پی قرار داریم یا زمانی که در این ناحیه قرار نداریم؛ و حالت‌هایمان نیز حروف A, C، G و T که در واقع نوکلئوتیدهای روی رشته‌اند در نظر گیریم. پس مجموعاً ۸ حالت مخفی که در شکل زیر نمایش داده شده‌اند را داریم.
می‌توانیم تمامی مسیرهای ممکن را که مشاهده ما را تولید می‌کنند را پیدا کنیم، سپس با محاسبه احتمال آنها، محتمل‌ترین مسیر را بدست آوریم. به عنوان نمونه در مسئله آب و هوا (می‌توانید در مثال‌هایی برای مدل پنهان مارکف ببینید) مشاهدی ما به صورت خشک، نم‌دار، مرطوب است. برای به‌دست آوردن محتمل‌ترین مسیر باید احتمال زیر بیشینه شود:
Pr(توالی مشاهده شده | انتخابی از حالت‌های مخفی)
برای جستجوی تمامی فضای جواب باید این احتمال را برای تمامی مسیرها بدست بیاوریم: Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، آفتابی)، Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، ابری)، Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، بارانی)، . . Pr(خشک، نم‌دار، مرطوب | بارانی، بارانی، بارانی) پیچیدگی زمانی این راه‌حل از اندازهٔ نمایی (formula_3) بوده و بهینه نیست. برای سرعت بخشیدن به الگوریتم می‌توان از تکنیک شاخه و حد استفاده کرد اما یک راه حل در زمان چندجمله‌ای برای این مسئله وجود دارد که الگوریتم ویتربی است.
همان‌طور که در بخش قبل توضیح داده‌شد، تعداد حالت‌های ممکن برای متغیرهای پنهان یا معادلاً تعداد مسیرها نسبت به طول توالی از اندازهٔ نمایی است. شکل زیر، حالت‌های متغیرهای نهان یک مدل پنهان مارکف را به‌صورت یک شبکه نشان داده‌است که در آن، حالت‌های مختلف برای هر متغیر نهان با رنگ‌های متفاوت مشخص شده‌اند و متغیرهای نهان به‌صورت افقی از چپ به راست نمایش داده شده‌اند. با استفاده از الگوریتم ویتربی، می‌خواهیم محتمل‌ترین مسیر را در این شبکه بیابیم به‌طوری که هزینهٔ محاسباتی به‌صورت خطی با طول توالی افزایش یابد.
با توجه به توضیحات داده‌شده، می‌دانیم می‌توان مسئله را به‌صورت زیر بازنویسی کرد:
می‌خواهیم مسیر بهینه‌ای مانند formula_4پیدا کنیم به‌گونه‌ای که داشته باشیم: formula_5. که در آن formula_6یک توالی از مشاهدات و formula_7یک توالی از متغیرهای پنهان باشد.
می‌دانیم برای محاسبهٔ احتمال بالا داریم: formula_8. که در آن formula_9 مقادیر احتمال‌های انتقال و formula_10 احتمال انتشار را نشان می‌دهد. برای اطلاعات بیشتر به صفحهٔ مدل پنهان مارکف مراجعه کنید.
اگر گره‌های گراف روبرو را با استفاده از دوتایی‌هایی که به‌ترتیب از شمارهٔ متغیر نهان و شمارهٔ حالت‌های ممکن برای آن‌ها تشکیل‌شده باشند، نمایش دهیم، می‌توان وزن بین دو گرهٔ formula_11و formula_12را برابر با مقدار formula_13تعریف کرد. حال می‌توان احتمال formula_14 برای یک مسیر مانند formula_15 به‌طوری که با یال formula_16 به گرهٔ formula_11ختم شود را به‌صورت زیر محاسبه کرد:
formula_18
حال کافی است متغیر formula_19را به‌طوری تعریف کنیم که احتمال بهترین مسیر تا مکان formula_20باشد، به‌طوری که توالی مشاهدات به formula_21ختم شده‌باشد و متغیر نهان برابر با formula_22باشد؛ بنابراین طبق نتایج بالا داریم:
formula_23
ورودی:
مدل formula_24 که:
و توالی formula_26
خروجی: محتمل‌ترین مسیر formula_4به‌گونه‌ای که formula_28
محاسبات آغازین: (i=۰) قرار بده formula_29 و برای تمام kهای بزرگتر از صفر قرار بده formula_30
خاتمه: formula_33
و محتمل‌ترین مسیر formula_34
بازگشت: