جزوه دوره یادگیری ماشین دکتر مهدیه سلیمانی - جلسه بیست‌و‌سوم - Reinforcement Learning

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

محتوای این جلسه

در ابتدا نگاهی به یادگیری semi-supervised خواهیم انداخت و در ادامه مقدمات reinforcement learning را خواهیم دید.

یادگیری semi-supervised

فرض در این مسائل به این صورت هست که یک سری از داده‌ها برچسب دارند و یک سری برچسب ندارند. چرا یک سری داده بدون برچسب داریم؟ به این دلیل که برامون هزینه‌بر هست تا برای تمامی داده‌ها برچسب اختصاص بدیم. در ادامه یک مثال رو بررسی می‌کنیم.

فرض کنید یک ویژگی داریم و دو تا نمونه. یکی از نمونه‌ها برای کلاس اول و یکی دیگه از نمونه‌ها برای کلاس دوم. تو این حالت مسئله سوپروایزد هست و دو کلاس رو از هم جدا می‌کنه به سادگی. حالا فرض کنید تو حالت دوم یک سری نمونه بدون برچسب وارد می‌کنیم و می‌خوایم ببینیم که چی میشه. تو این حالت باز هم دو دسته رو از هم جدا می‌کنه ولی جای مرز با حالت قبلی یکم متفاوت میشه. حالا فرض کنید می‌خوایم از روش EM برای حل این مسئله استفاده کنیم. تو این مثال متغیرهای نهانمون چی هستن؟ تو یک مثال دیگه توضیح میدیم.

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

روش کار با EM به این صورت میشه که با استفاده از اون سمپل‌های برچسب دار میایم اول پارامترهای اولیه گاوسی رو تخمین میزنیم که میشه مرحله اول EM. بعد تو گام بعدی مقدار متغیر نهان رو باید با استفاده از اون پارامترها تخمین بزنیم. متغیرهای نهان اینجا چی ان؟ به ازای همه سمپل‌های بدون برچسب شماره گاوسی و شماره کلاس رو نمی‌دونیم. حالا داده‌هایی که برچسب دارن که مشخصن، داده‌هایی که برچسب ندارن با یک احتمالی به هر کدوم از کلاس‌ها تعلق دارن. حالا چجوری پارامترهای کلاسترهارو تخمین بزنیم؟ فرقی نداره مثل قبله. فقط با این تفاوت که وزن داده‌های برچسب خورده برای کلاسی که بهش تعلق دارن 1 میشه و برای کلاسی که بهش تعلق ندارن 0 میشه. همون گام‌های الگوریتم EM رو باید جلو ببریم. منتها اینجا یه مشکلی ممکنه به‌وجود بیاد. اینکه نتونیم دسته‌بند بهینه رو پیدا کنیم. چرا؟ چون داده‌هایی که برچسب خوردن وزن خیلی بشتری می‌گیرن و ممکنه این باعث بشه که مثلا مرزی که به سادگی با یک خط جدا میشه، جواب خیلی پیچیده‌‌تری براش پیدا بشه.

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

روش EM بهینه‌های محلی بیشتری داره که اگه نقطه شروع خوبی نداشته باشیم توش گیر میفتیم. برای مقداردهی اولیه خوب گاهی این پیشنهاد رو میکنن که اول با الگوریتم k-means یک سری مرکز دسته اولیه برای کلاسترها پیدا کنیم و اون رو بعنوان نقطه شروع و مقداردهی اولیه برای EM در نظر بگیریم تا با احتمال کمتری تو بهینه‌های محلی بیفتیم.

یادگیری تقویتی

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

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

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

هدف اینجا چیه؟ اینکه یک دنباله از اکشن‌هارو به‌نحوی انجام بدیم که باعث بشه به بیشترین مقدار reward برسیم.

محیط‌هایی که عامل می‌تواند با آن سر و کار داشته باشد چه محیط‌هایی هستند؟

• محیط‌های قطعی و غیر قطعی

یک سری از محیط‌ها به صورت قطعی هستند. یعنی وقتی عامل یک اکشنی انجام میده نتیجه‌ش کاملا مشخصه. یعنی معلومه که بواسطه انجام اون اکشن به کجا میره و استیتی که داره به صورت قطعی تغییر میکنه و استیت جدید رو می‌گیره. اما یک‌سری از محیط‌ها به‌صورت غیر قطعی هستن. یعنی انجام اکشن در یک استیت ممکنه عامل با یک احتمالی وارد استیت A بشه یا با احتمالی دیگر وارد استیت B بشه. مثلا به یک ربات بگیم جلو برو. ممکنه چرخ ربات به جایی گیر کرده باشه و با احتمال 0.9 جلو بره و با احتمال 0.1 سرجاش بمونه. پس یعنی تو این حالت با انجام یک سری اکشن به استیت‌های مختلفی می‌تونیم بریم.

• محیط‌های شناخته‌شده و شناخته‌نشده

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

• محیط قابل مشاهده و کمی قابل مشاهده

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

در ادامه یک سری مثال رو ببینیم.

مثلا بازی شطرنج رو در نظر بگیرید. تو این بازی وضعیت برد استیت‌هارو مشخص می‌کنه. حرکاتی که بازیکنان انجام میدن اکشن‌ها هست و اخر بازی اگه نتیجه باعث برد بشه reward یک میشه و اگه باعث باخت بشه -1 میشه.

مثال زیر بردی هست که یک خونه‌ش شامل reward منفی 1 و خونه دیگه‌ش مثبت 1 هست که باعث تموم شدن بازی میشه و یکی از خونه‌هارو نمیشه اصلا واردش شد و مسدوده. بقیه خونه‌ها هم به میزان منفی 0.4 reward دریافت میکنن. این reward منفی به این معنی هست که باعث بشه تو زمان کمتری به نتیجه دلخواه برسیم. کامندها هم به این صورته که اگه به ربات تو این برد بگیم برو بالا، با احتمال 0.8 میره بالا و با احتمال 0.1 به چپ و راست ممکنه بره.

خصوصیات یادگیری تقویتی

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

از طرفی این‌جور مسائل معمولا delay reward هستن. یعنی بلافاصله نمی‌تونیم reward رو دریافت کنیم و تاخیر وجود داره. این باعث میشه که متوجه نشیم که آیا اکشنی که الان داریم انجام میدیم خوبه یا بده و بعدا میفهمیم که این باعث سخت شدن این جور مسائل میشه.

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

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

اپلیکیشن‌های RL

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

المان‌های اصلی مسئله RL

• تابع policy

چیزی که نهایتا دنبالش هستیم. یاد بگیریم در هر استیتی چه اکشنی انجام بدیم که در واقع یک تابع از فضای استیت‌ها به اکشن‌ها هست که بهش تابع policy گفته میشه. این تابع لزوما قطعی نیست. یعنی اینجوری نیست که بهش استیت بدیم و حتما بهمون اکشن بده. می‌تونه به‌ازای یک زوج استیت-اکشن بهمون یک عدد بین 0 و 1 بده که به این معنی هست که چقدر انجام اون اکشن رو در اون استیت بهمون توصیه می‌کنه.

• تابع reward

چیزی هست که از طرف محیط بهمون داده میشه و واضح هست.

• تابع value

به ازای هر استیت یک مقداری به‌دست میاره که نشون میده بودن تو اون استیت چقدر باعث reward در آینده خواهد شد. تابع reward به صورت آنی هست اما این تابع مجموع reward رو بهمون نشون میده.

در ادامه یک مثال رو بررسی خواهیم کرد.

یک محیط قطعی رو در نظر بگیرید که عامل می‌تونه توش بالا و پایین و چپ و راست بره. استیت نهایی با G مشخص شده. اگر به خونه G برسه reward دریافت شده 100 هست و در بقیه جاها 0 هست. تو این مثال policy می‌تونه بهمون بگه که چپ یا راست بریم و کلا در هر استیت چه اکشنی رو انجام بدیم.

حالا مثالی که یکم بالاتر دیدیم رو در نظر بگیرید. برای policy بهینه تو این مثال چیزی که تو تصویر اول سمت چپ بالا در نظر گرفته به این صورت هست که به‌جای اینکه از سمت منفی یک بره، بره دور بزنه و بعد به 1 برسه. دلیلش این بوده که اگه با یه احتمالی مجبور شد به راست بره وارد خونه -1 نشه و عددی هم که برای reward داره دریافت می‌کنه -0.04 هست که ناچیزه.

به ازای مقادیر مختلف reward تابع policy بهینه متفاوت میشه که تو تصاویر زیر هم مشخصه.

جزییات یادگیری تقویتی

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

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

در محیط‌های غیرقطعی، ممکنه در یک لحظه اکشن رو در استیتی انجام بدیم و منجر به یک reward بشه، تو لحظه دیگه‌ای همین اکشن رو در همین استیت انجام بدیم و reward دیگه‌ای بگیریم. تو این محیط‌ها به‌جای خود reward امید ریاضی‌شو در نظر می‌گیریم و می‌خوایم این مقدار رو ماکسیمم کنیم.

Markov Decision Process

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

اگه دنبال پیدا کردن policy بهینه باشیم (این policy بهمون می‌گفت تو هر استیتی چه اکشنی رو انجام بدیم)، دنبال این هستیم که policy P رو به صورتی پیدا کنیم که انجام اون در هر کدوم از استیت‌ها منجر به این بشه که اکسپکتیشن reward دریافت‌شده بیشینه بشه.

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

در ادامه یک مثال رو از MDP بررسی خواهیم کرد.

رباتی رو در نظر بگیرید که استیتشو با وضعیت باتری‌ش نشون میدیم که کم یا زیاد هست. یعنی کلا دو تا استیت داریم. اکشن‌ها هم به این ترتیب هستن:

• هیچ کاری انجام نمیده.
• سرچ کنه و دنبال قوطی خالی بگرده.
• برگرده و خودش رو شارژ کنه.

به ازای هر اکشن reward رو هم خودمون مشخص می‌کنیم که چی باشه.

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

تو اسلاید پایین مفهوم value function آورده شده. بهمون میگه که policy P در استیت S چقدر منجر به ارزش برای استیت S میشه. ارزش استیت S هم برابر با مجموع reward هایی هست که با حرکت با policy P دریافت خواهیم کرد. ارزش (value) هر استیت نشون میده که اون استیت چقدر برامون خوب هست اگر با policy P حرکت کنیم. خوب بودن استیت هم برابر با زیاد بودن reward هست.

سه دسته الگوریتم مهم برای این قضیه وجود داره:

• الگوریتم‌های داینامیک
• روش‌های Monto Carlo
• یادگیری Temporal-difference

روش Value Iteration

فرض کنید رابطه value function رو به صورت زیر باز کنیم و بنویسیم. چیزی که به‌دست میاد یک دستگاه معادلات خطی هست که V هر کدوم از استیت‌هارو داره به‌صورت ترکیب خطی V بقیه استیت‌ها بهمون میده.

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

جمع‌بندی مطالب گفته شده

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

اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.

اسلایدهای این جلسه (بخش semi-supervised learning)

اسلایدهای این جلسه (بخش reinforcement learning)

ویدیو این جلسه

جزوه جلسه قبلی (جلسه بیستم‌و‌دوم)