مفاهیم پایه

آشنایی با مفهوم زنجیره مارکوف

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

زنجیره مارکوف بر اصل بدون یادآوری یا بی حافظه بنا شده است به این معنی که حالت بعدی سیستم، به حالت های قبلی آن بستگی ندارد. با این اصل، محاسبه احتمال عملیات مجاز بعدی بسیار ساده تر خواهد بود. البته حالت پیشرفته تری از زنجیره مارکوف با نام Latent MC در کاربردهای دنیای واقعی که وابستگی به عملیات قبلی هم جزء الزامات پیش بینی ها خواهد بود، استفاده میشود که در اینجا به آن نمی پردازیم.

یک مثال عملی

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

شرکت تحلیل گر نتایج زیر را بعد از بررسی بازار ارائه داده است :

P(P->P) = 0.7 – احتمال ماندن مشتریان برند Pepsi بعد از یکماه با برند Pepsi

P(P->C) = 0.3 – احتمال تغییر شرکت مشتریان Pepsi بعد از یکماه به برند Coke

P(C->C) = 0.9 – حتمال ماندن مشتریان برند  Coke بعد از یکماه با برند Coke

P(C->P) = 0.1 – حتمال تغییر شرکت مشتریان Coke بعد از یکماه به برند Pepsi

همانطور که می بینید مشتریان شرکت Coke وفادارترند اما سهم بازار این شرکت در حال حاضر کمتر است . برای تصمیم گیری نهایی بهتر است محاسبات اندکی انجام دهیم و آینده را پیش بینی کنیم که کدام شرکت برنده بازار خواهد بود ؟

نمودار انتقال

چهار حالتی که در بالا به آن رسیده ایم را می توان در نمودار انتقال زیر به تصویر کشید :

transition

این نمودار به سادگی هم سهم بازار هر برند و هم نرخ تغییر کاربران را نشان می دهد. برای اینکه بدانیم در یک ماه آینده این نمودار به چه شکلی در خواهد آمد باید چند تا محاسبه ساده مطابق زیر انجام دهیم :

سهم بازار (t+1) شرکت Pepsi‌ = سهم فعلی بازارPepsi * نرخ ماندگاری مشتریان آن + سهم فعلی بازار Coke‌* نرخ ترک مشتریان Coke

سهم بازار (t+1) شرکت Coke= سهم فعلی بازار Coke * نرخ ماندگاری مشتریان آن + سهم فعلی بازار  Pepsi‌* نرخ ترک مشتریان Pepsi‌

این محاسبات را می توانیم با ضرب ماتریس ها به صورت زیر هم انجام دهیم :

trans1که ماتریس اول ، سهم اولیه بازار دو شرکت مورد مطالعه و ماتریس دوم ، ماتریس انتقال است . بنابراین همانطور که مشاهده می شود شرکت Coke در پایان یکماه ، سهم بازار بیشتری خواهد داشت . این محاسبه ساده ، به نام زنجیره مارکوف معروف است.

اگر این ماتریس انتقال در گذر زمان ثابت بماند، می توانیم سهم بازار شرکتها را در بازه های زمانی طولانیتر هم بررسی کنیم .

مثلا در پایان ماه دوم سهم بازار شرکتها از قرار زیر خواهد بود :

trans2محاسبه حالت پایدار

شرکت Soda‌ می خواهد بداند که در نهایت سهم بازار هر شرکت چقدر خواهد شد. سهم شرکت Pepsi همانطور که در محاسبات بالا مشاهده می کنید روبه نزول است اما نهایتا بازار به یک حالت ثابت و پایدار خواهد رسید که در آن تبادل و تغییر مشتریان دو شرکت در میزان سهم بازار آنها تاثیری نخواهد داشت یعنی مجموع مشتریان جداشده از شرکت اول با میزان مشتریان جداشده از شرکت دوم برابر خواهد شد . به این حالت، حالت پایدار می گوییم (Steady State)

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

۱- میزان سهم بازار شرکت Pepsi * ۳۰٪ = میزان سهم بازار شرکت Coke * ۱۰٪

۲- میزان سهم بازار شرکت Pepsi + سهم بازار شرکت Coke‌ = ۱۰۰ ٪

با محاسبه مقدار سهم بازار شرکت Coke در فرمول اول و جایگزینی آن در فرمول دوم به معادله تک مجهولی زیر می رسیم

۴ * Pepsi = ۱۰۰٪ => سهم شرکت Pepsi = ۲۵٪ و سهم شرکت Coke‌ = ۷۵ ٪

البته این معادله بسیار ساده بود و در مسایل دنیای واقعی پارامترها و تعداد مجهول ها بسیار بیشتر خواهد بود . برای به دست آوردن یک روش کاربردی برای محاسبه حالت پایدار، می توانیم از جبر ماتریسی کمک بگیریم :

ماتریس اولیه * ماتریس انتقال = ماتریس اولیه

که از این معادله ماتریسی می توان مجهولات که همان مقادیر ماتریس اولیه هستند را به کمک دستگاه معادلات خطی که بخشی از جبر خطی است، یافت .

سخن پایانی

در این مقاله با مفاهیم زنجیره مارکوف آشنا شدیم و برای پیش بینی حالات آینده و حالت پایدار از ضرب ماتریسی استفاده کردیم .

در مقالات بعدی به استفاده های عملی از این مفهوم ساده خواهیم پرداخت.

جهت تکمیل بحث و آشنایی بیشتر با زنجیره  مارکوف از دو مقاله زیر هم می توانید کمک بگیرید :

پی نوشت :

این مقاله جدید را که به زیبایی و به کمک اشکال مناسب، همین مفهوم را با مثالی دیگر توضیح داده است را هم از دست ندهید.

مجتبی بنائی

دانشجوی دکترای نرم‌افزار دانشگاه تهران (yun.ir/smbanaie)، مدرس دانشگاه و فعال در حوزه توسعه نرم‌افزار و مهندسی داده که تمرکز کاری خود را در چند سال اخیر بر روی مطالعه و تحقیق در حوزه کلان‌داده و زیرساخت‌های پردازش داده و تولید محتوای تخصصی و کاربردی به زبان فارسی و انتشار آنها در سایت مهندسی داده گذاشته است. مدیریت پروژه‌های نرم‌افزاری و طراحی سامانه‌های مقیاس‌پذیر اطلاعاتی از دیگر فعالیتهای صورت گرفته ایشان در چند سال گذشته است.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

جای خالی در معادله زیر را با کی برد انگلیسی وارد کنید : * Time limit is exhausted. Please reload CAPTCHA.

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.

دکمه بازگشت به بالا