مدل مارکوف

مدل پنهان مارکوف[1] یک مدل مارکوف آماری است که در آن سیستم مدل شده به صورت یک فرایند مارکوف با حالت‌های مشاهده نشده (پنهان) فرض می‌شود. یک مدل پنهان مارکوف می‌تواند به عنوان ساده‌ترین شبکه بیزی پویا در نظر گرفته شود. در مدل عادی مارکوف، حالت به‌طور مستقیم توسط ناظر قابل مشاهده است و بنابراین احتمال‌های انتقال بین حالت‌ها تنها پارامترهای موجود است. در یک مدل پنهان مارکوف، حالت به‌طور مستقیم قابل مشاهده نیست، اما خروجی بسته به حالت قابل مشاهده است.   هر حالت یک توزیع احتمال روی سمبل‌های خروجی ممکن دارد؛ بنابراین دنباله سمبل‌های تولید شده توسط یک مدل پنهان مارکوف اطلاعاتی درباره دنباله حالت‌ها می‌دهد. توجه داشته باشید که صفت 'پنهان' به دنباله حالت‌هایی که مدل از آن‌ها عبور می‌کند اشاره دارد، نه به پارامترهای مدل؛ حتی اگر پارامترهای مدل به‌طور دقیق مشخص باشند، مدل همچنان 'پنهان' است.

مدل‌های پنهان مارکوف بیشتر به‌دلیل کاربردشان در بازشناخت الگو، مانند تشخیص صدا و دست‌خط، تشخیص اشاره و حرکت، برچسب‌گذاری اجزای سخن، بیوانفورماتیک و … شناخته‌شده هستند. مدل پنهان مارکوف در حالت گسسته جز خانواده مسائل ظرف‌ها قرار می‌گیرد. به‌طور مثال از ربینر ۱۹۸۹ ظروف x1،x2،x3... و توپهای رنگی y1,y2,y3… را در نظر می‌گیریم، که نفر مقابل دنباله‌ای از توپ‌ها را مشاهده کرده ولی اطلاعی از دنباله ظرف‌هایی که توپ‌ها از آن‌ها انتخاب‌شده ندارد. ظرف n­ام با احتمالی وابسته به ظرف n-1­ام انتخاب می‌شود و چون به انتخاب ظرف‌های خیلی قبل‌تر وابسته نیست یک فرایند مارکوف است.

معماری مدل پنهان مارکوف

در معماری کلی مدل پنهان مارکوف را هر شکل بیضی یک متغیر تصادفی است که می‌تواند هر عددی از مقادیر را انتخاب کند. متغیر تصادفی X(t) یک حالت پنهان در زمانtو متغیر تصادفی y(t) مشاهده در زمان t است. فلش‌ها به معنای وابستگی‌های شرطی می‌باشند. از شکل مشخص است که توزیع احتمال شرطی متغیر پنهان x(t)، در همه زمان های t مقداری را برای x ارائه می‌دهد که فقط به مقدار متغیر پنهانx(t-1)وابسته است: مقادیر در زمان‌هایt-2 و قبل‌تر از آن هیچ اثری ندارند. این مشخصه مارکوف نامیده می‌شود. به‌طور مشابه مقدار متغیر مشاهده‌ای y(t) تنها به مقدار متغیر پنهان x(t)(هر دو در زمان خاصt) بستگی دارد. در حالت استاندارد مدل پنهان مارکوف که در اینجا در نظر گرفته شده‌است فضای حالت متغیرهای پنهان گسسته است؛ درحالی‌که متغیرهای مشاهده‌ای می‌توانند گسسته یا پیوسته (از توزیع گوسین) باشند.در مدل پنهان مارکوف دو نوع پارامتر وجود دارد:

    احتمال جابه‌جایی‌ها (بین حالات) و احتمال خروجی‌ها (یا مشاهدات)

   احتمال جابه‌جایی نحوه انتقال از حالتt-1 بهt را کنترل می‌کند.

فضای حالت پنهان شاملN مقدار ممکن برای حالات است. متغیر پنهان در زمان t می‌تواند هر یک از این مقادیر را اختیار کند. احتمال جابجایی این است که در زمانt در حالت k(یکی از حالات ممکن) و در زمانk+1 در حالتk₁ باشیم. بنابراین در کلN² احتمال جابجایی وجود دارد. (مجموع احتمالات جابجایی از یک حالت به تمام حالت­های دیگر ۱ است).

احتمال خروجی، احتمال رخ دادن هر یک از اعضای مجموعه مشاهده‌ای را برای هر حالت پنهان ممکن را مشخص می‌سازد که می‌تواند از یک توزیع احتمال پیروی کند. تعداد اعضای مجموعه مشاهده بستگی به طبیعت متغیر مشاهده‌ای دارد. اگر تعداد اعضای مجموعه متغیرهای مشاهده‌ای برابر M باشد، بنابراین مجموع تعداد احتمالات خروجی NM می‌باشد. با توجه به پارامترهای مدل پنهان مارکوف، می‌توانیم مسایلی به صورت زیر را حل کنیم.

Annotation

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

Classification

 مدل را داریم توالی از مشاهدات داده شده‌است، می‌خواهیم احتمال (کل) تولید شدن این توالی توسط این مدل را (جمع احتمالات تمامی مسیرهایی که این توالی را تولید می‌کنند) حساب کنیم.

الگوریتم forward Consensus

 مدل را داریم، می‌خواهیم بدانیم محتمل‌ترین توالی که توسط این مدل تولید می‌شود (توالی که بیشترین احتمال را داراست) چیست.

 الگوریتم Backward Training

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

 الگوریتم Baum-Welch یادگیری

وظیفه یادگیری در مدل پنهان مارکوف، یافتن بهترین احتمالات جابجایی‌ها و خروجی‌ها بر اساس یک دنباله یا دنباله‌هایی از خروجی هاست. معمولاً این پارامترها به وسیله متد maximum likelihood بر اساس خروجی داده شده تخمین زده می‌شوند. هیچ الگوریتم قطعی برای حل این مسئله وجود ندارد ولی برای پیدا کردن maximum likelihood محلی می‌توان از الگوریتم‌های کارایی مانند Baum-welch algorithm و یا Baldi-chauvin algorithm استفاده کرد. الگوریتم Baum-Welch نمونه‌ای از الگوریتمforward-backward و به صورت خاص موردی از الگوریتم exception-maximization می‌باشد.

---

[1] Hidden Markov Model