مقایسه الگوریتمهای یادگیری افزوده با تمرکز بر مسائل اجاره اسکی و پوشش راسی برخط

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

کلیدواژه ها:

الگوریتمهای برخط ، مسئله اجاره اسکی ، پوشش راسی برخط ، روش اولیه دوگان ، یادگیری ماشین ، نسبت رقابتی