الگوریتم ویتربی ( به انگلیسی: Viterbi algorithm ) الگوریتمی پویا برای پیدا کردن محتمل ترین مسیر از حالت های پنهان، با داشتن یک توالی از مشاهدات است. [ ۱] [ ۲] [ ۳] [ ۴]
این الگوریتم اغلب در مواردی بکار می رود که با داشتن یک مدل پنهان مارکف و توالی ای از مشاهدات، می خواهیم بدانیم چه توالی ای از حالت ها ( مسیر ) این مشاهدات را تولید کرده اند. به عبارت دیگر ما دنبال محتمل ترین مسیر به وجودآورندهٔ مشاهدات در یک مدل پنهان مارکف هستیم.
الگوریتم ویتربی از نام اندرو ویتربی گرفته شده است که در سال ۱۹۶۷ آن را به عنوان الگوریتمی رمزگشا برای کدهای کانولوشنال از طریق پیوندهای ارتباطی دیجیتالی نویزی ارائه کرد. [ ۵]
در بسیاری از کاربردهای مدل های پنهان مارکف، متغیرهای پنهان تفسیر معناداری دارند و در نتیجه یکی از مهم ترین مسائل در این حیطه، پیدا کردن محتمل ترین توالی از متغیرهای پنهان با داشتن یک توالی از مشاهدات است. به عنوان مثال، در حوزهٔ بازشناسی گفتار، می خواهیم یک توالی از واج ها با استفاده از توالی ای از آواها داشته باشیم.
این مسئله نباید با مسئلهٔ پیدا کردن محتمل ترین مجموعه از حالت های پنهان اشتباه گرفته شود. مسئلهٔ دوم می تواند با استفاده از الگوریتم پس رو - پیش رو حل شود. بدین صورت که ابتدا توزیع حاشیه ای برای هر متغیر نهان را به دست آورده و سپس جداگانه آن ها را بیشینه می کنیم. [ ۶] اما در حالت کلی، مسئلهٔ پیدا کردن محتمل ترین توالی پراهمیت تر بوده و الگوریتم بهینهٔ ارائه شده برای آن، الگوریتم جمع - بیشینه که در حیطهٔ مدل های پنهان مارکف، به آن الگوریتم ویتربی گفته می شود استفاده کرد. [ ۷]
در مسائل طبیعی مانند در، همیشه واقعیت منطبق بر محتمل ترین مسیر نیست. اما بسیاری اوقات محتمل ترین مسیر نیز اطلاعات خوبی در اختیار می گذارد.
در این بخش، به بررسی یکی از کاربردهای این مسئله در بیوانفورماتیک می پردازیم. مسئله جزایر سی پی جی ( CpG islands ) - پیدا کردن ناحیه ای از ژنوم که فرکانس بالایی از مکان های CG در آن وجود دارد - است. این مسئله را می توان با استفاده از دو مدل مخفی مارکف مدل کرد. کافی است حالت های مخفی را دو حالتِ m o d e l + و m o d e l − در نظر گیریم به طوری که زمانی که در ناحیهٔ سی جی پی قرار داریم یا زمانی که در این ناحیه قرار نداریم؛ و حالت هایمان نیز حروف A, C، G و T که در واقع نوکلئوتیدهای روی رشته اند در نظر گیریم. پس مجموعاً ۸ حالت مخفی که در شکل زیر نمایش داده شده اند را داریم. [ ۸]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین الگوریتم اغلب در مواردی بکار می رود که با داشتن یک مدل پنهان مارکف و توالی ای از مشاهدات، می خواهیم بدانیم چه توالی ای از حالت ها ( مسیر ) این مشاهدات را تولید کرده اند. به عبارت دیگر ما دنبال محتمل ترین مسیر به وجودآورندهٔ مشاهدات در یک مدل پنهان مارکف هستیم.
الگوریتم ویتربی از نام اندرو ویتربی گرفته شده است که در سال ۱۹۶۷ آن را به عنوان الگوریتمی رمزگشا برای کدهای کانولوشنال از طریق پیوندهای ارتباطی دیجیتالی نویزی ارائه کرد. [ ۵]
در بسیاری از کاربردهای مدل های پنهان مارکف، متغیرهای پنهان تفسیر معناداری دارند و در نتیجه یکی از مهم ترین مسائل در این حیطه، پیدا کردن محتمل ترین توالی از متغیرهای پنهان با داشتن یک توالی از مشاهدات است. به عنوان مثال، در حوزهٔ بازشناسی گفتار، می خواهیم یک توالی از واج ها با استفاده از توالی ای از آواها داشته باشیم.
این مسئله نباید با مسئلهٔ پیدا کردن محتمل ترین مجموعه از حالت های پنهان اشتباه گرفته شود. مسئلهٔ دوم می تواند با استفاده از الگوریتم پس رو - پیش رو حل شود. بدین صورت که ابتدا توزیع حاشیه ای برای هر متغیر نهان را به دست آورده و سپس جداگانه آن ها را بیشینه می کنیم. [ ۶] اما در حالت کلی، مسئلهٔ پیدا کردن محتمل ترین توالی پراهمیت تر بوده و الگوریتم بهینهٔ ارائه شده برای آن، الگوریتم جمع - بیشینه که در حیطهٔ مدل های پنهان مارکف، به آن الگوریتم ویتربی گفته می شود استفاده کرد. [ ۷]
در مسائل طبیعی مانند در، همیشه واقعیت منطبق بر محتمل ترین مسیر نیست. اما بسیاری اوقات محتمل ترین مسیر نیز اطلاعات خوبی در اختیار می گذارد.
در این بخش، به بررسی یکی از کاربردهای این مسئله در بیوانفورماتیک می پردازیم. مسئله جزایر سی پی جی ( CpG islands ) - پیدا کردن ناحیه ای از ژنوم که فرکانس بالایی از مکان های CG در آن وجود دارد - است. این مسئله را می توان با استفاده از دو مدل مخفی مارکف مدل کرد. کافی است حالت های مخفی را دو حالتِ m o d e l + و m o d e l − در نظر گیریم به طوری که زمانی که در ناحیهٔ سی جی پی قرار داریم یا زمانی که در این ناحیه قرار نداریم؛ و حالت هایمان نیز حروف A, C، G و T که در واقع نوکلئوتیدهای روی رشته اند در نظر گیریم. پس مجموعاً ۸ حالت مخفی که در شکل زیر نمایش داده شده اند را داریم. [ ۸]
wiki: الگوریتم ویتربی