الگوریتم Bucket Brigade

 مسئله تخصیص اعتبار

الگوریتم Bucket Brigade برای حل مسئله تخصیص اعتبار استفاده می‌شود. این الگوریتم برای حل مسئله کمک می­ کند اصلاح قدرت دسته‌بندی‌ها به چه مقدار باشد. با توجه به این الگوریتم:

·       دسته‌بندی‌هایی که بر پیغام ورودی فعلی منطبق شود، برای انجام عمل مربوطه پیشنهاد می‌شود که پیشنهاد براساس تناسب قدرت آن می­ باشد.

·       وقتی پاداشی از محیط دریافت می‌شود یا وقتی یک دوره[1] گذرانده می‌شود.  

دوره براساس تعداد دسته‌بندی‌های منطبق شده تعریف می‌شود:

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

2.      دسته‌بندی‌هایی که پیشنهاد آن‌ها در پایان هر دوره فعال می‌شود مالیات[2] پرداخت می‌کنند. مالیات پرداختی دسته ­بندهای فعال به‌وسیله توزیع کردنِ بازگشتِ آن‌ها به دسته‌بندی‌های قبلیِ فعال‌شده در طول دوره می ­باشد.

یادگیری

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

·       درک فرایندی که موجودات زنده در طی آن اقدام به یادگیری می‌کنند.

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

هدف از یادگیری

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

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

 انواع روش‌های یادگیری

روش‌های یادگیری بر سه نوع است:

·       یادگیری بدون ناظر[3]

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

·       یادگیری نظارت‌شده[4]

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

·       یادگیری تقویتی[5]

در یک مسئله یادگیری تقویتی عامل از طریق سعی و خطا با محیط تعامل کرده و یاد می‌گیرد با توجه به شناختی که از محیط دارد و بر اساس نتایجِ تعاملاتی که با محیط داشته است سودها و زیان‌هایی که درنتیجه انجامِ عمل‌های مختلف به دست آورده استراتژی را پیدا می‌کند که با عمل به آن در بلندمدت مطلوبیت خود را بیشینه کند. در این نوع از یادگیری بازخوردی به‌صورت عبارات کمکی مثبت (پاداش) یا منفی (جریمه) به عامل یادگیرنده داده می‌شود. غالباً پاداش‌ها مقادیر اسکالری همچون 1 - برای یک کار بد و 1+ برای یک کار خوب هستند.

مشخصه‌های اصلی یادگیری تقویتی:

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

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

·       پاداش از نوع تأخیری است ازاین‌رو دستاوردهای کوتاه‌مدت فدای مزایای بلندمدت‌تر می‌شوند.

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

·       مسئله را به‌صورت یک عامل هدفمند که با یک محیط نامعین در ارتباط است می‌بیند.

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

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

عامل و محیط به‌صورت متوالی در طی گام‌های زمانی t= 0,1,2,3,…. با یکدیگر تعامل می‌کنند. در هر گام مثلاً در گام t، عامل حالت جدیدی از محیط را دریافت می‌کند، s_t ∈S که S مجموعه حالت‌های ممکن برای محیط است و بر مبنای این حالت عمل a_t ∈ A(s_t) را انجام می‌دهد که A(s_t) مجموعه عمل‌های ممکنی است که عامل می‌تواند در حالت s_t انجام دهد. یک گام بعد یعنی در t+1، محیط یک پاداش عددی[6] r_t+1 ∈R برحسب عمل او در گام قبل به وی می‌دهد و عامل نیز خود را در حالت جدیدی s_t+1 می‌یابد.

سیاست یا استراتژی عامل، π_t، تابع احتمالی است که احتمال انتخاب شدن هر عمل را در هر حالت و با توجه به گام زمانی می‌دهد. به‌طور مثال π_t (s,a) = p می‌گوید که اگر عامل در زمان t در حالت s قرارگرفته باشد، با احتمال p عمل a را انتخاب می‌کند.

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

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

1. بدلیل بی­اطلاعی عامل از محیط فرآیند می‌تواند تصادفی باشد.

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

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

4. ممکن است با تعداد تکرار بسیار زیادی روبرو شویم که در آن صورت زمان زیادی را نیز صرف انجام این کار خواهد کرد. پس ممکن است با تعداد تکرار زیادی به هدف برسیم.

---

^[1] Episode

^[2] Tax

^[3] Unsupervised Learning

^[4] Supervised Learning

^[5] Reinforcement Learning

^[6] Numerical Reward