مدل-زنجیره-تصمیم گیری مارکوف

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

یک مدل مارکوف آماری است که در آن سیستم مدل شده به‌صورت یک فرایند مارکوف باحالت‌های مشاهده نشده (پنهان) فرض می‌شود. یک مدل پنهان مارکوف می‌تواند به‌عنوان ساده‌ترین شبکه بیزی پویا در نظر گرفته شود.  

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

مدل‌های پنهان مارکوف بیشتر به دلیل کاربردشان در بازشناخت الگو، مانند تشخیص صدا و دست‌خط، تشخیص اشاره و حرکت، برچسب‌گذاری اجزای سخن، بیوانفورماتیک و … شناخته‌شده هستند.

زنجیره مارکوف مدلی تصادفی برای توصیف یک توالی از رویدادهای احتمالی است که در آن احتمال هر رویداد فقط به حالت رویداد قبلی بستگی دارد. زنجیره مارکوف که به‌افتخار آندری مارکوف ریاضی‌دان اهل روسیه این‌گونه نام‌گذاری شده یک سیستم ریاضی است که در آن انتقال میان حالات شمارا، از حالتی به حالت دیگر صورت می‌گیرد. زنجیره مارکوف یک فرایند تصادفی بدون حافظه است بدین معنی که توزیع احتمال شرطی حالت بعد تنها به حالت فعلی بستگی دارد و مستقل از گذشته آن است. این نوع بدون حافظه بودن خاصیت مارکوف نام دارد. زنجیره مارکوف در مدل‌سازی دنیای واقعی کاربردهای زیادی دارد.

زنجیره مارکوف

یک فرایند تصادفی گسسته در زمان با خاصیت مارکوف است. اگرچه برخی از نویسندگان در مورد فرایندهای پیوسته در زمان هم از اصطلاح زنجیره مارکوف استفاده می‌کنند. یک فرایند تصادفی گسسته در زمان شامل سیستمی است که در هر مرحله در حالت خاص و مشخصی قرار دارد و به‌صورت تصادفی در هر مرحله تغییر حالت می‌دهد. مراحل اغلب به‌عنوان لحظه‌های زمانی در نظر گرفته می‌شوند ولی می‌توان آن‌ها را فاصله فیزیکی یا هر متغیر گسسته دیگری در نظر گرفت. خاصیت مارکوف بیان می‌کند که توزیع احتمال شرطی برای سیستم در مرحله بعد فقط به حالت فعلی سیستم بستگی دارد و به حالت‌های قبل بستگی ندارد. چون سیستم به‌صورت تصادفی تغییر می‌کند به‌طورکلی پیش‌بینی حالت زنجیره مارکوف در نقطه‌ای خاص در آینده غیرممکن است. بااین‌حال ویژگی‌های آماری سیستم در آینده قابل پیش‌بینی است که در بسیاری از کاربردها همین ویژگی‌های آماری بسیار حائز اهمیت است.

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

یکی از معروف‌ترین زنجیره‌های مارکوف که موسوم به «پیاده‌روی می خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به‌اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی (۱+) و یکی به عدد صحیح قبلی (۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هردوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.

مثالی دیگر عادات غذایی موجودی است که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

·       او فقط یک‌بار در روز غذا می‌خورد.

·       اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.

·       اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.

·       اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.

عادات غذایی این موجود را می‌توان با یک زنجیره مارکوف مدل‌سازی کرد به دلیل این‌که چیزی که فردا می‌خورد (حالت بعدی) تنها به چیزی که امروز خورده است (حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی درصد روزهایی است که انگور خورده است (در یک دوره طولانی).

فرایندهای تصمیم‌گیری مارکوف

 یک چارچوب ریاضی است برای مدل‌سازی تصمیم‌گیری در شرایطی که نتایج تا حدودی تصادفی و تا حدودی تحت کنترل یک تصمیم گیر است. برای مطالعه طیف گسترده‌ای از مسائل بهینه‌سازی که از طریق برنامه‌نویسی پویا و تقویت یادگیری حل می‌شوند مفید است. حداقل از اوایل ۱۹۵۰ میلادی فرایندهای تصمیم‌گیری مارکوف  شناخته‌شده است. هسته اصلی پژوهش در فرایندهای تصمیم‌گیری مارکوف حاصل کتاب رونالد هوارد است که در سال ۱۹۶۰ تحت عنوان «برنامه‌نویسی پویا و فرایندهای مارکف» منتشر شد. فرایندهای تصمیم‌گیری مارکوف در طیف گسترده‌ای از رشته‌ها ازجمله رباتیک، اقتصاد و تولید استفاده می‌شود. به‌طور دقیق‌تر، فرایندهای تصمیم‌گیری مارکوف، فرایندهای کنترل تصادفی زمان گسسته است.