یادگیری تقویتی
یادگیری تقویتی یکی از گرایشهای یادگیری ماشینی است که از روانشناسی رفتارگرایی الهام میگیرد. این روش بر رفتارهایی تمرکز دارد که ماشین باید برای بیشینه کردن پاداشش انجام دهد. این مسئله، با توجه به گستردگیاش، در زمینههای گوناگونی بررسی میشود. مانند: نظریه بازیها، نظریه کنترل، تحقیق در عملیات، نظریه اطلاعات، سامانه چندعامله، هوش ازدحامی، آمار، الگوریتم ژنتیک، بهینهسازی بر مبنای شبیهسازی. در مبحث تحقیق در عملیات و در ادبیات کنترل، حوزهای که در آن روش یادگیری تقویتی مطالعه میشود برنامهنویسی تخمینی پویای (approximate dynamic programming) خوانده میشود. این مسئله در تئوری کنترل بهینه نیز مطالعه شدهاست. البته دغدغه اصلی بیشتر مطالعات در این زمینه، اثبات وجود پاسخ بهینه و یافتن ویژگیهای آن است و به دنبال جزئیات یادگیری یا تخمین نیست. یادگیری تقویتی در اقتصاد و نظریه بازیها بیشتر به بررسی تعادلهای ایجاد شده تحت عقلانیت محدود میپردازد.
در یادگیری ماشینی با توجه به این که بسیاری از الگوریتمهای یادگیری تقویتی از تکنیکهای برنامهنویسی پویا استفاده میکنند معمولاً مسئله تحت عنوان یک فرایند تصمیمگیری مارکف مدل میشود. تفاوت اصلی بین روشهای سنتی و الگوریتمهای یادگیری تقویتی این است که در یادگیری تقویتی نیازی به داشتن اطلاعات راجع به فرایند تصمیمگیری ندارد و این که این روش روی فرایندهای مارکف بسیار بزرگی کار میکند که روشهای سنتی در آنجا ناکارآمدند.
یادگیری تقویتی با یادگیری با نظارت معمول دو تفاوت عمده دارد، نخست اینکه در آن زوجهای صحیح ورودی و خروجی در کار نیست و رفتارهای ناکارامد نیز از بیرون اصلاح نمیشوند، و دیگر آنکه تمرکز زیادی روی کارایی زنده وجود دارد که نیازمند پیدا کردن یک تعادل مناسب بین اکتشاف چیزهای جدید و بهرهبرداری از دانش اندوخته شده دارد. این سبک-سنگین کردن بین بهرهبرداری و اکتشاف در یادگیری تقویتی برای فرایندهای مارکف متناهی، تقریباً بهطور کامل در مسئلهٔ راهزن چند دست (Multi-armed bandit) بررسی شده.
مقدمه
یک مدل ابتدایی یادگیری تقویتی از:
- یک مجموعه از حالات مختلف مسئله.
- یک مجموعه از تصمیمات قابل اتخاذ.
- قوانینی برای گذار از حالات مختلف به یکدیگر.
- قوانینی برای میزان پاداش به ازای هر تغییر وضعیت.
- قوانینی برای توصیف آنچه که ماشین میتواند مشاهده کند.
معمولاً مقدار پاداش به آخرین گذار مربوط است. در بسیاری از کارها ماشین میتواند وضعیت فعلی مسئله را نیز بهطور کامل (یا ناقص) مشاهده کند. گاهی نیز مجموعه فعالیتهای ممکن محدود است (مثلاً این که ماشین نتواند بیشتر از مقدار پولی که دارد خرج کند)
در یادگیری تقویتی ماشین میتواند در گامهای زمانی گسسته با محیط تعامل کند. در هر لحظهٔ مفروض ، ماشین یک مجموعه مشاهدات را دریافت میکند که معمولاً شامل پاداش نیز میشود و پس از آن یک واکنش از بین واکنشهای ممکن از خود نشان میدهد که به محیط ارسال میشود. سپس وضعیت به حالت گذار میکند و پاداش نیز مشخص میشود که مربوط به گذار حاصل از است؛ و این پاداش قبل از انجام حرکت بعدی ماشین همراه با به ماشین داده میشود تا بر اساس آن را انتخاب کند. هدف ماشین هم طبیعتاً این است که بیشترین پاداش ممکن را کسب کند. ماشین میتواند هر تصمیماتش را به صورت تابعی از روند تغییر بازی تا وضعیت حاضر یا حتی به صورت تصادفی انتخاب کند.
نکتهٔ مهمی که در اینجا وجود دارد این است که یادگیری تقویتی برای مسائلی که در آنها بیشترین سود در کوتاه مدت تضمین کنندهٔ بیشترین سود در دراز مدت نیست بسیار مناسب است. مثلاً من برای اینکه در بزرگسالی درآمد بیشتری داشته باشیم بهتر است که به دانشگاه بروم و درس بخوانم در حالی که این امر در حال حاضر از نظر مالی برای من بهینه نیست. دلیل وجود این برتری در روش یادگیری تقویتی نیز این است که ماشین در هر مرحله لزوماً بهترین راه را انتخاب نمیکند و در نهایت هم سعی دارد مجموع پاداش. این روش به شکل موفقیتآمیزی بر روی مسائل مختلفی نظیر: کنترل رباتها، برنامهریزی آسانسورها، مخابرات، تخته نرد، چکرز(Sutton and Barto 1998, Chapter 11) و بازی گو (آلفاگو) استفاده شدهاست.
دو عامل مهم هستند که باعث برتری این روش میشوند: استفاده از نمونهها برای بهینهسازی کارایی و استفاده از تخمین توابع برای تعامل با محیطهای پیچیده در هریک از حالات زیر:
- برای مسئله یک مدل وجود دارد اما راه حل تحلیلیای وجود ندارد.
- فقط یک محیط شبیهسازی شده از مسئله در دسترس است (موضوع بحث بهینهسازی بر مبنای شبیهسازی)[1]
- هنگامی که تنها راه برای به دست آوردن اطلاعات از محیط تعامل با آن باشد.
دو حالت اول را میتوان تحت عنوان مسائل برنامهریزی بررسی کرد. (با توجه به این که مدلهایی از مسئله موجود است)، در حالی که سومی را باید به عنوان یک مسئلهٔ یادگیری صرف در نظر گرفت. در هر حال در چهارچوب یادگیری تقویتی هر سه مسئله به یک مسئلهٔ یادگیری ماشین تبدیل میشوند.
اکتشاف
مسئلهٔ یادگیری تقویتی همانطور که توصیف شد، نیازمند یک راهکار هوشمندانه برای اکتشاف است. تصمیمگیریهای تصادفی بدون استفاده از یک توزیع احتمال برآورد شده، معمولاً کارای بسیار ضعیفی دارد. برای فرایندهای مارکف کوچک و محدود مسئله در حال حاضر تا حدود خوبی حل شدهاست. اما با توجه به این که بیشتر الگوریتمها به درستی با زیاد شدن تعداد حالات کارایی خود را حفظ نمیکنند (مخصوصا برای تعداد حالات نامتناهی)، در دنیای واقعی افراد به همان راههای ساده اکتشاف بسنده میکنند. یکی از این راهها الگوریتم -حریصانه نام دارد که در آن ماشین تصمیمی را که به اعتقاد او بیشترین سود را در درازمدت به همراه خواهد داشت به احتمال انتخاب میکند و با احتمال یکنواخت نیست یکی از کارهای دیگر را انجام میدهد. در اینجا یک متغیر برای تنظیم کردن میزان اکتشاف است و بعضاً چه به دلیل وجود یک برنامهٔ زمانبندی مشخص (کم کردن مقدار اکتشاف با گذشت زمان) و چه به دلایل ابتکاری تغییر میکند.
الگوریتمهای یادگیری کنترلی
اگر مشکل اکتشاف را نادیده بگیریم و فرض کنیم که حالت فعلی کاملاً قابل مشاهده است (که این موضوع از اینجا به بعد مفروض است)، مسئله به این تبدیل میشود که چه اعمالی با توجه به تجربیات گذشته بهتر هستند.
معیار بهینگی
برای سادگی، فرض کنید مسئله به صورت دنبالهای از قسمتهای مستقل باشد، که هر کدام از این قسمتها با رسیدن به یک حالت انتهایی به پایان میرسد، (برای مثال اگر قرار باشد ماشین خروج از اتاق را یاد بگیرد، به محض خروج یک قسمت تمام میشود و ماشین پاداش را دریافت میکند[2] همچنین، فرض کنید مستقل از این که ماشین چه تصمیماتی را به چه ترتیبی اتخاذ کند، رسیدن به این حالت انتهایی اجتناب ناپذیر باشد. تحت چند شرط دیگر برای تعادل و نظم مسئله انتظار ما از پاداش نهایی به ازای هر رویکرد انتخاب شده توسط ماشین و هر شرایط اولیهای تعریف شده خواهد بود. در اینجا یک رویکرد یعنی یک توزیع احتمال بر روی تمام تصمیمات ممکن ماشین بسته به روند طی شده برای رسیدن به حالت حاضر.
اگر توزیع احتمال در نظر گرفته شده باشد، ما میتوانیم را به عنوان امید ریاضی پاداش مربوط به رویکرد انتخابی در نظر بگیریم:
- ،
که در اینجا متغیر تصادفی نشاندهندهٔ مقدار خروجی است و به این صورت تعریف میشود:
- ،
که در اینجا پاداش دریافتی بعد از گذار ام است حالت اولیه در ، و تصمیمات گرفته شده با توجه به رویکرد در نمود پیدا کردهاند. در اینجا، نشان دهندهٔ زمان تصادفیای است که حالت انتهایی فرا میرسد و قسمت یادگیری حاضر به پایان میرسد.
در مسئلههایی که به این شکل از قسمتهای مستقل تشکیل نشدهاند، معمولاً از خروجی کاسته میشود.
در اینجا اصطلاحاً ضریب نزول خوانده میشود.
جستجوی جامع
روش جستجوی جامع از دو مرحلهٔ زیر تشکیل شدهاست:
- به ازای همهٔ رویکردهای ممکن، در حین دنبال کردن آنها از پاداشها نمونه برداری کن.
- رویکردی را که بیشترین مجموع پاداش را دارد انتخاب کن.
مشکل اصلی این روش این است که تعداد حالات ممکن است بسیار زیاد یا حتی نامتناهی باشد؛ و دیگر اینکه ممکن است خروجیها بسیار متنوع باشند که این حالت نیازمند نمونه برداری بسیار گستردهای برای تخمین خروجی نهایی هر رویکرد است.
نظریه
نظریه برای فرایندهای مارکف کوچک و محدود کامل است؛ و هر دو رفتار تقریبی و نمونه برداری محدود بیشتر الگوریتمها به خوبی فهمیده شدهاست. همانطور که پیشتر گفته شد، الگوریتمهایی شناخته شدهای که به صورت اثبات شده کارایی بالایی دارند (راجع به مسئلهٔ اکتشاف) وجود دارند. اما برای فرایندهای مارکف بزرگ همچنان کار لازم است. تقریباً الگوریتمی برای اکتشاف کردن بهینه وجود ندارد (به غیر از مسئلهٔ راهزن). اگرچه کرانهای محدودی برای زمان اجرای برخی الگوریتمها در سالهای اخیر به دست آمده، اما به نظر میرسد که این کرانها فعلاً ضعیف هستند و بدین ترتیب کار بیشتری لازم است تا بتوانیم برتریهای نسبی این الگوریتمها و محدودیتهایشان لازم است.
تحقیقات جاری
تحقیقات جاری شامل:
- پیدا کردن راهکارهای قابل انطباق با تعداد کمتر (یا هیچ) پارامتری تحت شرطهای بسیار زیاد.
- تخمینهای تجربی بزرگ
- یادگیری و تصمیمگیری تحت اطلاعات محدود.
- یادگیری تقویتی سلسله مراتبی
- بهینهسازی راهکارهای «تابع-مقدار» و «جستجوی راهبرد» حاضر
- الگوریتمهایی که برای مجموعهٔ بزرگ و حتی پیوستهٔ تصمیمات ممکن کار کنند
- یادگیریهای برای تمام عمر
- برنامهریزی بهینهٔ بر پایهٔ نمونه (بر اساس درخت جستجوی مونت کارلو)
- یادگیری توزیع شده یا چند ماشینی
- استفاده از یادگیری تقویتی در زندگی واقعی
پیشرفتهای اتفاق افتاده در زمینهٔ یادگیری تقویتی در اینجا و همچنین اینجا جمعآوری میشوند.
بر روی الگوریتمهای یادگیری تقویتی نظیر یادگیری تفاوت زمانی هم به عنوان یک مدل برای یادگیری بر پایهٔ دوپامین در مغز تحقیقاتی در حال انجام است. در این مدل راههای دوپامینی(Dopaminergic pathways) از توده سیاه به عقدههای قاعدهای به عنوان خطای پیشبینی عمل میکنند. یادگیری تقویتی همچنین به عنوان بخشی از مدل مهارتآموزی انسان مورد استفاده قرار گرفتهاست. به خصوص در رابطه با تعامل بین یادگیری ضمنی و صریح در اکتساب مهارتها. (اولین انتشار در این رابطه به سال ۱۹۹۵–۱۹۹۶ بازمیگردد و در ادامه تحقیقات بسیاری هم در این رابطه انجام شد). برای اطلاعات بیشتر راجع به جزئیات این تحقیقات میتوانید به اینجا مراجعه کنید.
پیادهسازی
- RL-Glue یک رابط(Interface) استاندارد ارائه میدهد که با کمک آن میتوان ماشینها - محیطها و برنامههای تجربی را به هم متصل کرد، حتی اگر به زبانهای مختلف نوشته شده باشند.
- Maja Machine Learning Framework یک چارچوب(framework) برای مسئلههای حوزهٔ یادگیری تقویتی است که به زبان پایتون نوشته شدهاست.
- ابزارهای برنامهنویسی برای زبانهای متلب و پایتون
- (PyBrain(Python
- TeachingBox یک چارچوب برنامهنویسی به زبان جاوا برای یادگیری تقویتی است که امکانات زیادی را از جمله RBF networks, gradient descent learning methods, … پشتیبانی میکند.
- پیادهسازیهای پایتون و سی++ برای یافتن پیادهسازی تعداد زیادی از الگوریتمهای یادگیری تقویتی معروف.
- Orange، یک برنامهٔ مربوط به دادهکاوی(data mining)
- Policy Gradient Toolbox
- BURLAP یک کتابخانهٔ متن-باز به زبان جاوا است که راهکارهای گستردهای برای برنامهریزی و یادگیری یک یا چند ماشین ارائه میدهد.
یادگیری تقویتی تقلیدی
در یادگیری تقویتی معکوس، هیچ تابع پاداشی وجود ندارد. در عوض، ماشین با مشاهدهٔ یک رفتار که معمولاً به رفتار بهینه نزدیک است سعی میکند آن را تقلید کند. اگر ماشینی که از روش یادگیری معکوس استفاده میکند از دنبال کردن رفتاری که باید مشاهده کند منحرف شود، معمولاً مدتی طول میکشد تا بتواند ثبات رفتار خود را حفظ کند. خیلی وقتها بهتر است که رفتار ایدهآل چندین بار با ایرادات کوچک به ماشین نشان داده شود.
در یادگیری شاگردی(apprenticeship learning)یک ماشین فرض میکند که موجود متخصصی که در حال انجام دادن یک رفتار است سعی میکند یک تابع پاداش را بیشینه کند، و هدف ماشین این است که به گونهای این تابع پاداش را کشف کند.
همچنین نگاه کنید به
- یادگیری تفاوت زمانی
- کیو-یادگیری
- حالت-عمل-پاداش-حالت-عمل(State-Action-Reward-State-Action)
- بازی ساختگی(fictitious play)
- سیستم طبقهبندی کنندهٔ یادگیری learning classifier system)
- کنترل بهینه
- رژیم رفتار پویا(dynamic treatment regime)
- یادگیری بر پایهٔ خطا(error-driven learning)
- سامانه چندعامله
- هوش مصنوعی توزیع شده distributed artificial intelligence)
منابع
- Gosavi, Abhijit (2003). Simulation-based Optimization: Parametric Optimization Techniques and Reinforcement. Springer. ISBN 1-4020-7454-9.
- جزوه کلاس یادگیری ماشین دکتر شیری - دانشگاه صنعتی امیرکبیر
ویکیپدیای انگلیسی