کاربردهای زنجیره مارکوف در الگوریتم‌ها

1.الگوریتم Viterbi

2.الگوریتم Forward-Backward

3.الگوریتم PageRank

4.الگوریتم Monte Carlo

5.الگوریتم Q-learning

6.الگوریتم POMDP (Partially Observable Markov Decision Process)

7.الگوریتم Hidden Markov Model (HMM)

8.الگوریتم Reinforcement Learning

9.الگوریتم Dynamic Programming

1.الگوریتم Viterbi

کاربرد زنجیره مارکوف:

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

مثال: فرض کنید در حال تحلیل گفتار یک فرد هستید. هر بار که فرد صحبت می‌کند، ممکن است او در یکی از چند حالت قرار داشته باشد: خواب، کار یا تفریح. با استفاده از الگوریتم Viterbi، می‌توانید به بهترین نحو تعیین کنید که فرد در هر لحظه کدام وضعیت را تجربه می‌کند، بر اساس نشانه‌هایی که از او دریافت می‌کنید (مانند اینکه او چه کلماتی می‌گوید).

2.الگوریتم Forward-Backward

کاربرد زنجیره مارکوف:

این الگوریتم به‌منظور محاسبه احتمال یک دنباله از نشانه‌ها در یک مدل مارکوف پنهان (HMM) استفاده می‌شود. با استفاده از این الگوریتم، می‌توانیم بفهمیم که چگونه یک مدل به مشاهدات رسیده است و چه احتمالی برای هر حالت وجود دارد.

مثال: فرض کنید شما در حال تشخیص احساسات یک شخص هستید. با گوش دادن به صداهای او (نشانه‌ها) و استفاده از Forward-Backward، می‌توانید محاسبه کنید که چه احساسی (شادی، غم و …) احتمال بیشتری دارد با توجه به نشانه‌های خاصی که شنیده‌اید.

3.الگوریتم PageRank گوگل:

کاربرد زنجیره مارکوف:

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

این تصویر الگوریتم PageRank گوگل را به‌صورت شبکه‌ای از گره‌ها و اتصالات نمایش می‌دهد که سایت‌ها و ارتباطات بین آن‌ها را از نظر اهمیت رتبه‌بندی نشان می‌دهد.

مثال: تصور کنید وب‌سایتی دارید که به چندین وب‌سایت دیگر لینک داده است. با استفاده از PageRank، می‌توانید بفهمید که آیا وب‌سایت شما به اندازه کافی مهم است یا خیر، بر اساس اینکه چه تعداد صفحه به آن لینک داده‌اند و این صفحات چقدر معتبر هستند.

4.الگوریتم Monte Carlo

کاربرد زنجیره مارکوف:

روش‌های Monte Carlo از زنجیره‌های مارکوف برای تولید نمونه‌های تصادفی از یک توزیع استفاده می‌کنند. این روش‌ها می‌توانند برای برآورد مقادیر مورد نیاز در مسائل پیچیده و در شرایط عدم قطعیت استفاده شوند.

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

5.الگوریتم Q-learning

کاربرد زنجیره مارکوف:

Q-learning یک روش یادگیری تقویتی است که به ماشین‌ها یاد می‌دهد چگونه بهترین تصمیمات را در یک محیط مشخص بگیرند. این الگوریتم بر اساس فرایند تصمیم‌گیری مارکوف (MDP) کار می‌کند و به ماشین‌ها اجازه می‌دهد از تجربیاتشان بیاموزند.

مثال: فرض کنید یک ربات در حال یادگیری نحوه پیمایش در یک اتاق است. این ربات با استفاده از Q-learning یاد می‌گیرد که هر بار که حرکتی انجام می‌دهد، چه پاداشی دریافت می‌کند و می‌تواند بهترین راه را برای رسیدن به هدفش پیدا کند. به این ترتیب، ربات به تدریج بهتر و بهتر می‌شود.

6.الگوریتم POMDP (Partially Observable Markov Decision Process)

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

فرض کنید شما در یک هزارتوی تاریک هستید و نمی‌توانید به‌طور دقیق ببینید در کدام اتاق هستید، اما از طریق نشانه‌های محیطی (مثل صدا یا دما) به‌طور تقریبی می‌توانید بفهمید در کدام اتاق هستید. اینجا یک “تابع باور” وجود دارد که احتمالات حضور شما در هر اتاق را به‌روز می‌کند.

کاربرد زنجیره مارکوف:

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

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

7.الگوریتم Hidden Markov Model (HMM)

کاربرد زنجیره مارکوف:

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

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

8.الگوریتم Reinforcement Learning

کاربرد زنجیره مارکوف:

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

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

9.الگوریتم Dynamic Programming

کاربرد زنجیره مارکوف:

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

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

زمان‌بندی و  فرایند تصمیم گیری مارکوف با زمان گسسته یا پیوسته

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

در MDPهای محدود، علاوه بر تلاش برای بهینه‌سازی پاداش، باید به محدودیت‌هایی مثل منابع انرژی یا زمان نیز توجه کنید.

مثال: فرض کنید یک ربات دارید که باید وظایف مختلفی را انجام دهد، اما تنها باتری محدودی دارد. در اینجا علاوه بر اینکه می‌خواهید وظایف را به بهترین نحو انجام دهید، باید مطمئن شوید که ربات قبل از خالی شدن باتری به اتمام کارهایش می‌رسد.

چگونه به مرحله همگرا شدن می‌رسیم ؟

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

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

1.نوشتن ماتریس انتقال احتمالات :

 

ابتدا باید ماتریس انتقال احتمالات را تعریف کنیم. فرض کنید که دو حالت داریم:

• حالت آفتابی (S)
• حالت ابری (C)
• ماتریس انتقال احتمالات P به صورت روبرو است :

• SSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز آفتابی باشد.
• SCP یعنی احتمال اینکه فردا ابری باشد ، اگر امروز آفتابی باشد.
• CSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز ابری باشد.
• CCP یعنی احتمال اینکه ابری آفتابی باشد ، اگر امروز ابری باشد.

2.یافتن توزیع پایدار :

• توزیع پایدار، توزیعی است که با گذر زمان تغییر نمی‌کند. برای یافتن این توزیع، باید برداری را پیدا کنیم که وقتی با ماتریس انتقال P ضرب می‌شود، خودش را تولید کند:
• این معادله به این معناست که توزیع جدید  همانند توزیع قبلی است و هیچ تغییر معنی‌داری در توزیع ایجاد نمی‌شود.

3.نوشتن معادلات :

• از معادله فوق، معادلات زیر به دست می‌آید:

 

 

4.شرط نرمالسازی :

• چون مجموع احتمالات باید برابر با 1 باشد، یک شرط نرمال‌سازی داریم:

5.حل دستگاه معادلات :

• حالا این معادلات را حل می‌کنیم تا مقادیر و  (توزیع پایدار) را به دست آوریم.

مثال عملی :

فرض کنید که ماتریس انتقال به شکل زیر باشد:

1.نوشتن معادلات توزیع پایدار :

• معادلات زیر را داریم:

2.حل معادله اول :

• از معادله اول می‌نویسیم:

• این را حل می‌کنیم :

3.استفاده از شرط نرمالسازی :

• با استفاده از شرط نرمال‌سازی:

 

نتیجه‌گیری

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

0.75 =(احتمال آفتابی)

0.25 = (احتمال ابری)

---

ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA

نمونه‌ای از زنجیره مارکوف چیست ؟

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

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

برای اهداف تجسم، شبکه‌ی بالا تنها تعداد محدودی کلمه در مجموعه خود دارد. اما هنگامی که با حجم بالایی از متن مانند مجموعه “هری پاتر” مواجه می‌شوید، این شبکه بسیار بزرگ و پیچیده‌تر خواهد شد. به عنوان مثال، اگر به کلمه ابتدایی “سلام” (Hello) نگاه کنیم، سه کلمه یا نماد دیگر وجود دارند که می‌توانند پس از آن بیایند: “همه” (Everyone) و “در آنجا” (There) با احتمالات مربوطه. ساده‌ترین راه برای محاسبه این احتمالات، استفاده از فراوانی وقوع کلمات در مجموعه متن است.

Hello = [ “Everyone” , “” , “Everyone” , “There” , “There” , “There” , “There” , “There” ,…]

 اگر در لیست بالا ۲۰ کلمه وجود داشته باشد که هر کدام پس از کلمه “سلام” (Hello) آمده باشد، آنگاه احتمال وقوع هر کلمه طبق فرمول زیر محاسبه می‌شود:

P(word) = Frequency of word / total Number of Words in List

P(Everyone) = 9/20

P(,) = 1/20

P(There) = 10/20

بردار حالت اولیه نشان‌دهنده احتمال شروع جمله با هر یک از کلمات ممکن است. در مثال بالا، از آنجا که “سلام” (Hello) تنها کلمه‌ای است که می‌توانید با آن شروع کنید، بردار حالت اولیه یک بردار Nx1 خواهد بود که ۱۰۰ درصد احتمال به کلمه “سلام” اختصاص داده شده است. با استفاده از این بردار، می‌توانید حالت‌های آینده را از طریق این مدل مارکوف پیش‌بینی کنید.

کاربردهای زنجیره مارکوف و نحوه کارکرد

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

1.هواشناسی:

یکی از معروف‌ترین کاربردهای زنجیره مارکوف در پیش‌بینی آب و هوا است. با استفاده از وضعیت آب و هوای امروز (مثلاً آفتابی یا ابری)، می‌توانیم حدس بزنیم که فردا هوا چطور خواهد بود.

چطور کاربرد دارد؟ فرض کن هواشناسی می‌خواهد پیش‌بینی کند فردا هوا چطور خواهد بود. با استفاده از زنجیره مارکوف، یک سری حالت داریم (مثلاً: آفتابی، ابری، بارونی). با بررسی وضعیت امروز، هواشناسی با استفاده از یک جدول احتمال تصمیم می‌گیرد که فردا احتمال آفتابی بودن یا بارونی بودن چقدر است.

مثال: اگر امروز هوا آفتابی است ، زنجیره مارکوف می‌گوید ۸۰٪ احتمال است که فردا هم آفتابی باشد، و ۲۰٪ احتمال دارد بارانی باشد.

 

 

2.تشخیص صدا و گفتار:

در گوشی‌های موبایل، وقتی از سیری یا google assistant سؤال می‌پرسید، این سیستم‌ها از زنجیره مارکوف استفاده می‌کنند تا بفهمند هر کلمه‌ای که می‌گویید به چه کلمه‌ی بعدی ممکن است مربوط باشد. به عبارت دیگر، صدای شما را با استفاده از مدل مارکوف تجزیه و تحلیل می‌کنند.

چطور کاربرد دارد؟ وقتی با موبایل خود صحبت می‌کنید و آن می‌خواهد بفهمد چه کلمه‌ای گفته‌اید، زنجیره مارکوف به آن کمک می‌کند که از بین کلمات مختلف حدس بزند. به عنوان مثال، وقتی می‌گویید “سلام”، موبایل باید تصمیم بگیرد که چه کلمه‌ای بعد از “سلام” بیاید. با کمک زنجیره مارکوف، گوشی بررسی می‌کند که چه کلمات دیگری بیشتر با “سلام” همراه می‌شوند.

• مثال: اگر گفتید “سلام”، احتمال زیادی دارد که کلمه بعدی “خوبی” باشه، نه “موبایل”.

3.بازاریابی و تحلیل رفتار مشتری:

• 

• شرکت‌ها با استفاده از زنجیره مارکوف، رفتار مشتری‌ها رو پیش‌بینی می‌کنند. مثلاً وقتی شما محصولی را خریداری می‌کنید، زنجیره مارکوف می‌گوید بعد از آن ممکن است که چه محصول دیگری را خریداری کنید.
• چطور کاربرد دارد؟ شرکت‌ها از زنجیره مارکوف استفاده می‌کنند تا بفهمند بعد از خرید یک محصول، مشتری چه چیزی را ممکن است بعد از آن خریداری کند . این کار با ساختن مدل مارکوف برای رفتار مشتری‌ها انجام می‌شود. برای هر محصول، احتمال خرید محصول بعدی بر اساس محصول قبلی مشخص می‌شود.
• مثال: اگر مشتری کتابی درباره “آموزش پایتون” خرید، زنجیره مارکوف می‌تواند پیش‌بینی کند احتمال اینکه بعدش کتاب “پروژه‌های پایتون” رو خریداری کند بیشتر است.

 

4.مالی و بورس:

• 

• در بازار بورس، از زنجیره مارکوف استفاده می‌شود تا قیمت سهام یا ارزها رو پیش‌بینی کنند. یعنی مثلاً اگر قیمت سهام امروز بالا رفته باشد، می‌توانند احتمال دهند که فردا قیمت بالا می‌ماند یا خیر.
• چطور کاربرد دارد؟ در بازار بورس، قیمت سهام به وضعیت فعلی بازار بستگی دارد. زنجیره مارکوف کمک می‌کند که پیش‌بینی کنیم فردا قیمت سهام چطوری تغییر می‌کند. مثلاً اگر امروز سهام بالا رفته است، زنجیره مارکوف با استفاده از احتمالات می‌تواند پیش‌بینی کند که فردا چقدر احتمال دارد قیمت بیشتر بره بالا یا پایین بیاید.
• مثال: اگر امروز قیمت سهام زیاد شده است، زنجیره مارکوف می‌گوید ۶۰٪ احتمال دارد فردا هم بالا برود، ولی ۴۰٪ احتمال داره پایین بیاد.

 

5.مدیریت صف‌ها:

• در بانک‌ها یا بیمارستان‌ها، زنجیره مارکوف می‌تواند پیش‌بینی کند که در چه ساعاتی صف طولانی‌تر میشود. مثلاً اگر الان صف کوتاه است، یک ساعت بعد صف احتمال دارد چقدر طولانی شود؟
• چطور کاربرد دارد؟ در بانک یا بیمارستان، با استفاده از زنجیره مارکوف می‌توانند پیش‌بینی کنند که در چه زمانی صف طولانی‌تر می‌شود. مثلاً اگر الان تعداد مراجعین کم است، زنجیره مارکوف می‌تواند پی‌بینی کند در یک ساعت آینده صف شلوغ‌تر میشود یا خیر.
• مثال: اگر الان در بانک فقط ۵ نفر در صف قرار دارند، زنجیره مارکوف می‌گوید ۷۰٪ احتمال دارد که در ۳۰ دقیقه آینده تعداد افراد بیشتر شود.

6.مهندسی ژنتیک و بیولوژی:

• زنجیره مارکوف در تحلیل ژن‌ها هم کاربرد دارد. با استفاده از این مدل می‌توانند الگوهای تکراری در DNA را پیدا کنند و حدس بزنند که بعد از یک رشته ژنتیکی خاص، چه چیزی قرار دارد.
• مثال کاربردی: بررسی ترتیب ژن‌ها در رشته DNA برای کشف بیماری‌ها.

7.تشخیص چهره و تصویر

• چطور کاربرد دارد؟ وقتی می‌خوایم عکسی بگیریم و موبایل می‌خواهد صورت شما را تشخیص دهد، زنجیره مارکوف کمک می‌کند که اول از روی وضعیت فعلی تصویر (مثلاً روشنایی یا زاویه) حدس بزند چهره‌ شما کجا است و بعد به دنبال الگوهای صورت بگردد.
• مثال: زنجیره مارکوف مش‌گوید که اگر بخشی از چهره دیده شد (مثلاً چشم)، احتمال زیادی وجود دارد که بینی در موقعیت مشخصی باشد.

8.الگوریتم PageRank گوگل

• چطور کاربرد دارد؟ گوگل از زنجیره مارکوف استفاده می‌کند تا صفحات وب را بر اساس لینک‌هایی که بین آن‌ها است، رتبه‌بندی کند. وقتی یک صفحه به صفحه دیگر لینک می‌دهد، زنجیره مارکوف احتمال می‌دهد که چه صفحاتی بیشتر کلیک می‌شند.
• مثال: اگر صفحه‌ای به یک سایت دیگری لینک داده است، زنجیره مارکوف کمک می‌کند بفهمیم که چقدر احتمال دارد کاربر روی این لینک کلیک کند و وارد سایت جدید بشود.

9.فیلتر کالمن (Kalman Filter)

• چطور کاربرد دارد؟ در سیستم‌های کنترلی مثل هواپیماها یا ماهواره‌ها، زنجیره مارکوف کمک می‌کند که وضعیت آینده سیستم (مثل سرعت یا مسیر حرکت) پیش‌بینی شود. برای هر لحظه، زنجیره مارکوف بر اساس وضعیت فعلی حدس می‌زند که سیستم در لحظه بعدی کجا خواهد بود.
• مثال: وقتی ماهواره‌ای در حال حرکت توی فضا است، زنجیره مارکوف می‌گوید که در ثانیه بعد احتمال دارد ماهواره کجا باشد و با چه سرعتی حرکت کند.

10.پردازش زبان طبیعی (NLP) :

• در تحلیل و پردازش متن و زبان هم از زنجیره مارکوف استفاده می‌کنند. مثلاً وقتی جمله‌ای را می‌نویسید، این مدل کمک می‌کند حدس بزنند چه کلمه‌ای بعدی باید باشد.
• مثال کاربردی: تصحیح خودکار جمله‌هایی که تایپ می‌کنید یا ترجمه ماشینی.

---

ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA

روش‌های حل زنجیره مارکوف

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

1.حل تحلیلی (Analytical Solution)

2.روش ماتریس انتقال (Transition Matrix Method)

3.شبیه‌سازی مونت کارلو (Monte Carlo Simulation)

4.روش مقدار ویژه (Eigenvalue Method)

5.روش گاوس-سایدل (Gauss-Seidel Method)

6.روش تکراری (Iterative Methods)

7.الگوریتم ول‌من (Value Iteration Algorithm)

8. روش برنامه ریزی پویا (Dynamic Programming – DP)

9.روش بلمن-فورد(Bellman-Ford Algorithm)

10.ارزش گذاری(Value Iteration)

11.سیاست گذاری تکراری (Policy Iteration)

12.الگوریتم سیاست ثابت (Policy Iteration Algorithm)

13.روش شبیه سازی و بهینه سازی (Simulation and Optimization)

14.روش های یادگیری تقویتی (Reinforcement Learning Methods)

15.روش زنجیره مارکوف پنهان (Hidden Markov Models – HMM)

1.حل تحلیلی(Analytical Solution)

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

 

 

مثال:

فرض کنید ماتریس انتقال وضعیت آب و هوا به صورت روبرو است:

 

 

 

 

با استفاده از حل تحلیلی، می‌توانیم محاسبه کنیم که در بلندمدت چه درصد از روزها آفتابی، ابری، یا بارانی خواهد بود.

2.روش ماتریس انتقال (Transition Matrix Method)

این روش با استفاده از ماتریس انتقال احتمالات بین حالت‌ها حل می‌شود. هر ورودی ماتریس نشان می‌دهد که با چه احتمالی از یک حالت به حالت دیگر تغییر می‌کنیم.

به عنوان مثال، فرض کنید امروز آفتابی است. با استفاده از ماتریس انتقال مذکور، می‌توانیم بفهمیم فردا چه احتمالاتی برای وضعیت هوا وجود دارد. با تکرار این فرآیند، می‌توانیم وضعیت چند روز آینده را پیش‌بینی کنیم.

3.شبیه سازی مونت کارلو (Monte Carlo Simulation)

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

به عنوان مثال، اگر بخواهیم بدانیم در طول ۱۰۰ روز وضعیت هوا چگونه خواهد بود، می‌توانیم چندین بار وضعیت‌ها را به‌صورت تصادفی شبیه‌سازی کنیم و ببینیم که مثلا، چه درصدی از روزها آفتابی، ابری یا بارانی بوده است.

4.روش مقدار ویژه (Eigenvalue Method)

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

به عنوان مثال، اگر بخواهیم بدانیم در یک سیستم پیچیده، پس از تعداد زیادی انتقال، وضعیت‌ها به چه حالتی می‌رسند، از این روش استفاده می‌کنیم.

5.روش گاوس-سایدل (Gauss-Seidel Method)

این روش عددی برای حل زنجیره مارکوف است که حالت‌های مختلف را تکرار می‌کند تا به پاسخ نهایی برسد. این روش معمولاً سریع‌تر از برخی روش‌های دیگر به جواب می‌رسد.

به عنوان مثال، در محاسبات پیچیده، اگر بخواهیم به‌سرعت‌تر به پاسخ برسیم، این روش به ما کمک می‌کند تا وضعیت‌های آینده را پیش‌بینی کنیم.

6.روش تکراری (Iterative Methods)

در این روش، وضعیت‌های سیستم را به‌صورت تکراری محاسبه می‌کنیم و هر بار نتایج قبلی را به‌عنوان ورودی برای دفعه بعدی استفاده می‌کنیم تا در نهایت به یک جواب پایدار برسیم.

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

7.الگوریتم ول من (Value Iteration Algorithm)

این روش برای حل مسائل تصمیم‌گیری مارکوف (MDP) استفاده می‌شود. هدف این الگوریتم، یافتن بهترین سیاست (Policy) برای یک سیستم است که سود یا پاداش بلندمدت را بیشینه کند.

به عنوان مثال، فرض کنید در یک بازی باید تصمیم بگیرید که در هر مرحله چه حرکتی انجام دهید تا بیشترین امتیاز را کسب کنید. الگوریتم ولمن به شما کمک می‌کند تا بهترین تصمیم‌ها را برای هر وضعیت بازی پیدا کنید.

8.روش برنامه ریزی پویا (Dynamic Programming – DP)

این روش‌ها زمانی استفاده می‌شوند که مدل MDP و قوانین انتقال حالت‌ها مشخص باشند.

معادله بلمن (Bellman Equation)

معادله بلمن یکی از اصلی‌ترین روش‌های حل مسائل تصمیم‌گیری مارکوف (MDP) است. در این روش، هدف یافتن تابع ارزش (Value Function) برای هر حالت می‌باشد. این معادله یکی از پایه‌های یادگیری تقویتی (Reinforcement Learning) است و برای درک ارزش یک حالت در محیط استفاده می‌شود.

این تابع نشان می‌دهد که با شروع از یک حالت مشخص، چه ارزشی می‌توان از آن به دست آورد.

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

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

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

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

1.پاداشی که در همان لحظه در آن اتاق دریافت می‌کنید R(s)

2.احتمال این که بعد از رفتن به آن اتاق، به اتاق‌های دیگری هم بروید و از آن‌ها هم پاداش بگیرید. (این همان بخشی است که داریم احتمال رسیدن به اتاق بعدی رو حساب می‌کنیم، که این را با P(s′,s,a) نشان می‌دهیم).

فرمول بلمن به شما می‌گوید که ارزش یک اتاق (یا همان حالت) برابر با جمع این دو چیز است:

1.پاداشی که همون لحظه دریافت میکنید R(s)

2.مجموع ارزش اتاق‌های بعدی که ممکن است به آن‌ها بروید، ضربدر احتمالی که به آنجا می‌روید.

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

V(s) ارزش حالت فعلی است.

R(s,a, s′) پاداش دریافتی برای رفتن از حالت s به حالت s′ با اقدام a.

γ(گاما): ضریب تخفیف که اهمیت پاداش‌های آینده را مشخص می‌کند  . این عدد تعیین می‌کنه که چقدر به پاداش‌های آینده اهمیت دهیم. اگر γ زدیک ۰ باشه، یعنی فقط به پاداش‌های حال اهمیت دهیم؛ اگه نزدیک ۱ باشد، یعنی پاداش‌های آینده‌هم اهیمت دارند.

P(s′,s,a): احتمال رفتن به حالت s′ با انجام عمل a در حالت s

V(s′) ارزش حالت بعدی است.

این معادله را برای همه حالت‌ها حل می‌کنیم تا بهترین سیاست را پیدا کنیم.

مثال :

فرض کنید در هزارتو (Maze) هستید. وقتی در اتاق (حالت s) ایستادید :

• می‌دانید که ۵ سکه در آنجا روی زمین است (این R(s) می‌شود)
• اما از آن اتاق ممکن است به اتاق‌های دیگری بروید که در آن‌ها هم سکه وجود دارد. در این بخش، باید ببینید احتمال رسیدن به اتاق‌های دیگر چقدر است. (این همون P(s′,s,a) می‌شود) و اگر به آن اتاق‌ها برسید، چند سکه دیگر دریافت می‌کنید (این V(s′) است.)

کاربرد معادله بلمن کجاست؟

این معادله در جاهایی استفاده می‌شود که بخواهیم تصمیم بگیریم چگونه بهترین کار (action) را در هر موقعیت انجام دهیم تا به بهترین نتیجه برسیم. به عنوان مثال:

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

 

 

 

• رباتیک: برای اینکه ربات‌ها بتوانند راه‌هایی را انتخاب کنند که سریع‌تر به مقصد برسند و انرژی کمتری مصرف کنند. (همچنین در طراحی ربات‌ها برای یادگیری راه‌های بهینه، مانند پیدا کردن مسیر بهینه در یک محیط پیچیده.)

 

 

 

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

 

 

 

 

• کنترل هوشمند: در سیستم‌های کنترل، مانند هواپیماها یا خودروهای خودران، معادله بلمن کمک می‌کند تا سیستم بهترین تصمیم‌ها را بگیرد و بهینه‌ترین مسیرها را انتخاب کند.

 

 

چرا معادله بلمن خوب است؟

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

کاربرد در الگوریتم‌ها :

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

1.برنامه ریزی پویا (Dynamic Programming)

• الگوریتم Policy Iteration :

این الگوریتم در دو مرحله کار می‌کند:

1.Evaluation: ارزش هر حالت (value) با استفاده از معادله بلمن محاسبه می‌شود.

2.Improvement: با استفاده از این ارزش‌ها، سیاست (policy) بهبود داده می‌شود تا انتخاب عمل‌هایی (actions) که به حالت‌های بهتر منجر می‌شوند، تقویت شوند.

• از معادله بلمن استفاده می‌شود تا بفهمیم در هر مرحله کدام حالت بهتر است و چگونه باید سیاست را تغییر دهیم.
• الگوریتم Value Iteration:

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

معادله بلمن در اینجا برای به‌روزرسانی مکرر ارزش‌ها استفاده می‌شود تا به مجموعه‌ای از ارزش‌های بهینه برسیم.

2.Q-Learning:

معادله بلمن Q

در Q-Learning، به جای اینکه فقط ارزش حالت‌ها را بذانیم ، می‌خواهیم بدانیم هر عمل (action) در هر حالت چقدر خوب است. در اینجا به جای ارزش حالت، ارزش Q  (ا Q-value) داریم که نشان می‌دهد هر حالت و عمل چقدر بهینه است.

فرمول Q-Learning هم از معادله بلمن مشتق شده و به شکل زیر است  :

Q-Learning از معادله بلمن استفاده می‌کند تا با به‌روزرسانی Q-value‌ها بفهمیم کدام عمل بهترین نتیجه را به همراه دارد.

3.SARSA (State-Action-Reward-State-Action):

معادله بلمن برای به‌روزرسانی Q-value :

SARSA هم مثل Q-Learning کار می‌کند ولی به جای اینکه از بیشترین Q-value استفاده کند، از سیاستی که همان لحظه در اختیار دارد پیروی می‌کند ، استفاده می‌کند. معادله SARSA مشابه Q-Learning است اما با استفاده از معادله بلمن به صورت متفاوتی به‌روزرسانی می‌شود.

4.DQN (Deep Q-Networks):

DQN نسخه پیشرفته‌تری از Q-Learning که از شبکه‌های عصبی برای تقریب زدن Q-value‌ها استفاده می‌کند. این الگوریتم هم از معادله بلمن برای به‌روزرسانی Q-value‌ها استفاده می‌کند، با این تفاوت که ارزش Q از طریق شبکه عصبی یاد گرفته می‌شود.

چرا از معادله بلمن استفاده می‌کنند؟

1.مدل‌سازی تصمیم‌گیری بهینه: معادله بلمن به ما کمک می‌کند تا بدانیم چه تصمیمی در هر حالت از یک محیط بهتر است. این موضوع توی خیلی از مسائل کاربرد دارد، مثل بازی‌های کامپیوتری، رباتیک و حتی تصمیم‌گیری‌های اقتصادی.

2.رویکرد بازگشتی (Recursive) : معادله بلمن به شکل بازگشتی کار می‌کند و این باعث می‌شود به راحتی ارزش حالت‌ها را در طول زمان و با تکرار به‌روزرسانی کنیم. این تکرار باعث می‌شود که ارزش بهینه رو پیدا کنیم.

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

در نهایت، معادله بلمن کمک می‌کند که در مسائل پیچیده، بهترین و بهینه‌ترین تصمیم رو بگیریم.

9.روش بلمن-فورد(Bellman-Ford Algorithm)

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

مثال:

فرض کنید در یک شبکه ارتباطی، می‌خواهید کمترین هزینه انتقال داده را پیدا کنید. این الگوریتم به شما کمک می‌کند.

10.ارزش گذاری(Value Iteration)

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

مراحل کار:

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

مثال:

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

11.سیاست گذاری تکراری (Policy Iteration)

در این روش به‌جای تمرکز بر ارزش حالت‌ها، سیاست (Policy) را بهبود می‌دهیم. سیاست یعنی “برای هر حالت چه عملی انجام دهیم؟”. این روش شامل دو مرحله است:

1.ارزیابی سیاست: ابتدا ارزش حالات را با سیاست فعلی محاسبه می‌کنیم.

2.بهبود سیاست: سپس سیاست را طوری تغییر می‌دهیم که پاداش بهتری بگیریم.

این فرآیند تکرار می‌شود تا به یک سیاست بهینه برسیم.

مثال:

در بازی‌ها، سیاست شما می‌تواند این باشد که مثلاً همیشه به جلو بروید. سپس بررسی می‌کنید که این سیاست چقدر خوب است و با تغییر سیاست به “گاهی به جلو و گاهی به عقب بروید”، پاداش بهتری بگیرید.

12.الگوریتم سیاست ثابت (Policy Iteration Algorithm)

این روش مشابه الگوریتم ول‌من است، با این تفاوت که ابتدا یک سیاست اولیه را انتخاب می‌کنیم و سپس آن را تکرار می‌کنیم تا به بهترین سیاست برسیم. این روش برای حل MDP استفاده می‌شود.

مثال:در یک سیستم اتوماتیک، می‌خواهید بدانید در هر وضعیت چه تصمیمی بگیرید تا بیشترین سود را کسب کنید. این الگوریتم کمک می‌کند سیاست‌های مختلف را بررسی و بهینه کنید.

13.روش شبیه سازی و بهینه سازی (Simulation and Optimization)

این روش با شبیه‌سازی وضعیت‌های مختلف سیستم و پیدا کردن بهترین حالت ممکن، بهینه‌سازی می‌کند. این روش معمولاً برای مسائل پیچیده‌ای که تحلیل دقیق آن‌ها سخت است استفاده می‌شود.

مثال:

در یک کارخانه تولید، می‌خواهید بدانید که با چه ترتیبی محصولات تولید شوند تا بیشترین بهره‌وری را داشته باشید. با شبیه‌سازی، می‌توانید وضعیت‌های مختلف را بررسی و بهترین راه‌حل را پیدا کنید.

14.روش های یادگیری تقویتی (Reinforcement Learning Methods)

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

مثال:

یک ربات را در نظر بگیرید که در حال یادگیری است که چگونه از یک مسیر پر از موانع عبور کند. ربات با آزمون و خطا یاد می‌گیرد که بهترین تصمیم‌ها چیست.

15.روش زنجیره مارکوف پنهان (Hidden Markov Models – HMM)

این روش برای مسائلی استفاده می‌شود که حالت واقعی سیستم قابل مشاهده نیست و فقط اطلاعات محدودی از وضعیت داریم. با HMM می‌توانیم پیش‌بینی کنیم که سیستم در چه حالتی است.

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

 

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

 

---

ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA