الگوریتم ویتربی

الگوریتم ویتربی برای پیدا کردن محتمل‌ترین مسیر از حالت‌های پنهان کاربرد دارد.

این الگوریتم اغلب در مواردی بکار می‌رود که ما یک مدل پنهان مارکوف داریم و یک توالی از مشاهدات. می‌خواهیم بدانیم چه ترتیبی از حالت‌ها(مسیر) این مشاهدات را تولید کرده. به عبارت دیگر ما دنبال محتمل‌ترین مسیر تولید کننده مشاهدات هستیم.

در مسائل طبیعی مانند مسئله جزایر سی‌پی‌جی (CpG islands) در بیوانفورماتیک، همیشه واقعیت منطبق بر محتمل‌ترین مسیر نیست. اما بسیاری اوقات محتمل‌ترین مسیر نیز اطلاعات خوبی در اختیار می‌گذارد.

جستجوی کامل فضای مساله

می‌توانیم تمامی مسیرهای ممکن را که مشاهده ما را تولید می‌کنند را پیدا کنیم، سپس با محاسبه احتمال آنها، محتمل‌ترینشان را بدست آوریم. به عنوان نمونه در مساله آب و هوا (می‌توانید در مثال‌هایی برای مدل پنهان مارکوف ببینید) مشاهدی ما به صورت dry,damp,soggy است. برای بدست آوردن محتمل‌ترین مسیر باید احتمال زیر بیشینه شود:

Pr(observed sequence | hidden state combination)

برای جستجوی تمامی فضای جواب باید این احتمال را برای تمامی مسیرها بدست بیاوریم:

Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,rainy)

پیچیدگی زمانی این راه‌حل بالا است ($O(a^n)$). برای سرعت بخشیدن به الگوریتم می‌توان از تکنیک شاخه و حد استفاده کرد اما یک راه حل در زمان چندجمله‌ای برای این مساله وجود دارد که الگوریتم ویتربی است.

الگوریتم ویتربی

ورودی: مدل $M=(\Sigma,Q,P,e)$ که:

$\Sigma$: الفبای مشاهدات

Q: مجموعه حالات

P: ماتریس احتمال انتقال بین حالات

e: ماتریس احتمال تولید الفبا در هر حالت

و توالی $X=x_1x_2\dots x_L$

خروجی: محتمل‌ترین مسیر $\pi^*$

محاسبات آغازین: ( i=0 ) قرار بده $V_0(0)=1$ وبرای تمام kهای بزرگتر از صفر قرار بده $V_K(0)=0$

برای i از ۱ تا L و تمامی l‌ها عضو Q

قرار بده $v_l(i)=e_l(x_i)\max_{k\in Q}(v_k(i-1)p_{kl})$

قرار بده $ptr_i(l)=argmax_{k \in Q}(v_k(i-1)p_{kl})$

خاتمه: $P(X,\pi^*)=\max_{k \in Q}(v_k(L)p_{k0})$

و محتمل‌ترین مسیر $\pi^*_L=argmax_{k\in Q}(v_k(L)p_{k0})$

Traceback:

برای i از L تا 1 :

قرار بده $\pi_{i-1}^*=ptr_i(\pi_i^*)$