موضوع مقاله: الگوریتم ویتربی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم ویتربی | مقدمه: به عبارت دیگر ما دنبال محتمل‌ترین مسیر به‌وجودآورندهٔ مشاهدات در یک مدل پنهان مارکف هستیم. | ## بخش 1: الگوریتم ویتربی | الگوریتم ویتربی از نام اندرو ویتربی گرفته شده است که در سال ۱۹۶۷ آن را به عنوان الگوریتمی رمزگشا برای کدهای کانولوشنال از طریق پیوندهای ارتباطی دیجیتالی نویزی ارائه کرد.29 Apr 2005, G. به‌عنوان مثال، در حوزهٔ بازشناسی گفتار، می‌خواهیم یک توالی از واج‌ها با استفاده از توالی‌ای از آواها داشته باشیم. این مسئله نباید با مسئلهٔ پیدا کردن محتمل‌ترین مجموعه از حالت‌های پنهان اشتباه گرفته شود. بدین صورت که ابتدا توزیع حاشیه‌ای برای هر متغیر نهان را به‌دست آورده و سپس جداگانه آن‌ها را بیشینه می‌کنیم. اما در حالت کلی، مسئلهٔ پیدا کردن محتمل‌ترین توالی پراهمیت‌تر بوده و الگوریتم بهینهٔ ارائه‌شده برای آن، الگوریتم جمع-بیشینه که در حیطهٔ مدل‌های پنهان مارکف، به آن الگوریتم ویتربی گفته می‌شود استفاده کرد. مدل‌های پنهان مارکف برای جزایز سی‌پی‌جی در این بخش، به بررسی یکی از کاربردهای این مسئله در بیوانفورماتیک می‌پردازیم. | ## بخش 2: الگوریتم ویتربی | کافی است حالت‌های مخفی را دو حالتِ و در نظر گیریم به‌طوری که زمانی که در ناحیهٔ سی‌جی‌پی قرار داریم یا زمانی که در این ناحیه قرار نداریم؛ و حالت‌هایمان نیز حروف A, C، G و T که در واقع نوکلئوتیدهای روی رشته‌اند در نظر گیریم. جستجوی کامل فضای مسئله می‌توانیم تمامی مسیرهای ممکن را که مشاهده ما را تولید می‌کنند را پیدا کنیم، سپس با محاسبه احتمال آنها، محتمل‌ترین مسیر را بدست آوریم. به عنوان نمونه در مسئله آب و هوا (می‌توانید در مثال‌هایی برای مدل پنهان مارکف ببینید) مشاهدی ما به صورت خشک، نم‌دار، مرطوب است. برای به‌دست آوردن محتمل‌ترین مسیر باید احتمال زیر بیشینه شود: Pr(توالی مشاهده شده | انتخابی از حالت‌های مخفی) برای جستجوی تمامی فضای جواب باید این احتمال را برای تمامی مسیرها بدست بیاوریم: Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، آفتابی)، Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، ابری)، Pr(خشک، نم‌دار، مرطوب | آفتابی، آفتابی، بارانی)، . Pr(خشک، نم‌دار، مرطوب | بارانی، بارانی، بارانی) پیچیدگی زمانی این راه‌حل از اندازهٔ نمایی بوده و بهینه نیست. برای سرعت بخشیدن به الگوریتم می‌توان از تکنیک شاخه و حد استفاده کرد اما یک راه حل در زمان چندجمله‌ای برای این مسئله وجود دارد که الگوریتم ویتربی است. | ## بخش 3: الگوریتم ویتربی | الگوریتم ویتربی همان‌طور که در بخش قبل توضیح داده‌شد، تعداد حالت‌های ممکن برای متغیرهای پنهان یا معادلاً تعداد مسیرها نسبت به طول توالی از اندازهٔ نمایی است. شکل زیر، حالت‌های متغیرهای نهان یک مدل پنهان مارکف را به‌صورت یک شبکه نشان داده‌است که در آن، حالت‌های مختلف برای هر متغیر نهان با رنگ‌های متفاوت مشخص شده‌اند و متغیرهای نهان به‌صورت افقی از چپ به راست نمایش داده شده‌اند. با استفاده از الگوریتم ویتربی، می‌خواهیم محتمل‌ترین مسیر را در این شبکه بیابیم به‌طوری که هزینهٔ محاسباتی به‌صورت خطی با طول توالی افزایش یابد. برای هر مسیر داده‌شده، احتمال متناظر با استفاده از ضرب مقادیر ماتریس انتقال احتمال‌ها برای هر قسمت از مسیر با استفاده از احتمال‌های انتشار متناظر با هر گره در مسیر به‌دست می‌آید.|339x339پیکسل تعریف مسئله با توجه به توضیحات داده‌شده، می‌دانیم می‌توان مسئله را به‌صورت زیر بازنویسی کرد: می‌خواهیم مسیر بهینه‌ای مانند پیدا کنیم به‌گونه‌ای که داشته باشیم: . | ## جمع‌بندی | Dieterich, February 6, 2007 اگر گره‌های گراف روبرو را با استفاده از دوتایی‌هایی که به‌ترتیب از شمارهٔ متغیر نهان و شمارهٔ حالت‌های ممکن برای آن‌ها تشکیل‌شده باشند، نمایش دهیم، می‌توان وزن بین دو گرهٔ و را برابر با مقدار تعریف کرد.