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

در بسیاری از کاربردهای مدل‌های پنهان مارکف، متغیرهای پنهان تفسیر معناداری دارند و در نتیجه یکی از مهم‌ترین مسائل در این حیطه، پیدا کردن محتمل‌ترین توالی از متغیرهای پنهان با داشتن یک توالی از مشاهدات است. به‌عنوان مثال، در حوزهٔ بازشناسی گفتار، می‌خواهیم یک توالی از واج‌ها با استفاده از توالی‌ای از آواها داشته باشیم.

این مسئله نباید با مسئلهٔ پیدا کردن محتمل‌ترین مجموعه از حالت‌های پنهان اشتباه گرفته شود. مسئلهٔ دوم می‌تواند با استفاده از الگوریتم پس‌رو-پیش‌رو حل شود. بدین صورت که ابتدا توزیع حاشیه‌ای برای هر متغیر نهان را به‌دست آورده و سپس جداگانه آن‌ها را بیشینه می‌کنیم. اما در حالت کلی، مسئلهٔ پیدا کردن محتمل‌ترین توالی پراهمیت‌تر بوده و الگوریتم بهینهٔ ارائه‌شده برای آن، الگوریتم جمع-بیشینه که در حیطهٔ مدل‌های پنهان مارکف، به آن الگوریتم ویتربی گفته می‌شود استفاده کرد.

در مسائل طبیعی مانند در، همیشه واقعیت منطبق بر محتمل‌ترین مسیر نیست. اما بسیاری اوقات محتمل‌ترین مسیر نیز اطلاعات خوبی در اختیار می‌گذارد.

مدل‌های پنهان مارکف برای جزایز سی‌پی‌جی

در این بخش، به بررسی یکی از کاربردهای این مسئله در بیوانفورماتیک می‌پردازیم. مسئله جزایر سی‌پی‌جی (CpG islands) -پیدا کردن ناحیه‌ای از ژنوم که فرکانس بالایی از مکان‌های CG در آن وجود دارد- است. این مسئله را می‌توان با استفاده از دو مدل مخفی مارکف مدل کرد. کافی است حالت‌های مخفی را دو حالتِ ${\displaystyle mode{l}_{+}}$

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

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

پیچیدگی زمانی این راه‌حل از اندازهٔ نمایی (${\displaystyle O(a^n)}$

همان‌طور که در بخش قبل توضیح داده‌شد، تعداد حالت‌های ممکن برای متغیرهای پنهان یا معادلاً تعداد مسیرها نسبت به طول توالی از اندازهٔ نمایی است. شکل زیر، حالت‌های متغیرهای نهان یک مدل پنهان مارکف را به‌صورت یک شبکه نشان داده‌است که در آن، حالت‌های مختلف برای هر متغیر نهان با رنگ‌های متفاوت مشخص شده‌اند و متغیرهای نهان به‌صورت افقی از چپ به راست نمایش داده شده‌اند. با استفاده از الگوریتم ویتربی، می‌خواهیم محتمل‌ترین مسیر را در این شبکه بیابیم به‌طوری که هزینهٔ محاسباتی به‌صورت خطی با طول توالی افزایش یابد.

تعریف مسئله

با توجه به توضیحات داده‌شده، می‌دانیم می‌توان مسئله را به‌صورت زیر بازنویسی کرد:

می‌خواهیم مسیر بهینه‌ای مانند ${\displaystyle {\pi }^{\ast }}$

می‌دانیم برای محاسبهٔ احتمال بالا داریم: ${\displaystyle \mathbb{P}(x,\pi )=p_{0,{\pi }_1}{\mathrm{\Pi }}_{i=1}^L{e}_{{\pi }_i}(x_i)p_{{\pi }_i,{\pi }_{i+1}}}$

ایدهٔ الگوریتم

اگر گره‌های گراف روبرو را با استفاده از دوتایی‌هایی که به‌ترتیب از شمارهٔ متغیر نهان و شمارهٔ حالت‌های ممکن برای آن‌ها تشکیل‌شده باشند، نمایش دهیم، می‌توان وزن بین دو گرهٔ ${\displaystyle (k,i)}$

حال کافی است متغیر ${\displaystyle v_k(i)}$

شبه‌کد الگوریتم

ورودی:

مدل ${\displaystyle M=(\mathrm{\Sigma },Q,P,e)}$

${\displaystyle \mathrm{\Sigma }}$

: الفبای مشاهدات

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

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

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

و توالی ${\displaystyle X=x_1{x}_2\dots x_L}$

خروجی: محتمل‌ترین مسیر ${\displaystyle {\pi }^{\ast }}$

محاسبات آغازین: (i=۰) قرار بده ${\displaystyle V_0(0)=1}$

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

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

قرار بده ${\displaystyle pt{r}_i(l)=argma{x}_{k\in Q}(v_k(i-1)p_{kl})}$

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

و محتمل‌ترین مسیر ${\displaystyle {\pi }_L^{\ast }=argma{x}_{k\in Q}(v_k(L)p_{k0})}$

بازگشت:

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

قرار بده ${\displaystyle {\pi }_{i-1}^{\ast }=pt{r}_i({\pi }_i^{\ast })}$