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

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

مهسا مظفر1 مهدی یعقوبی2

1) دانشجوی کارشناسی ارشد، دانشکده فنی و مهندسی گرگان، گروه مهندسی کامپیوتر، دانشگاه گلستان
2) استادیار دانشکده فنی و مهندسی گرگان، گروه مهندسی کامپیوتر، دانشگاه گلستان

کد IOI مقاله : AAHD-ACZZCG
محل انتشار : کنفرانس ملی فناوری اطلاعات، نانوتکنولوژی، هوش مصنوعی و آینده پژوهی فناوری (itnaf.ir)
چکیده :
    الگوریتم‌های برخط و تقریبی کلاسیک عموماً بر پایه تحلیل بدترین حالت طراحی شده‌اند؛ رویکردی که اگرچه تضمین‌های نظری قابل اتکایی فراهم می‌کند، اما در بسیاری از کاربردهای عملی از بهره‌گیری مؤثر از الگوهای موجود در داده‌های واقعی بازمی‌ماند. در مقابل، مدل‌های یادگیری ماشین قادرند با استفاده از داده‌های گذشته، پیش‌بینی‌هایی با دقت قابل قبول ارائه دهند، ولی عملکرد آن‌ها در شرایط تغییر توزیع داده‌ها یا پیش‌بینی‌های نادرست فاقد تضمین‌های نظری است. ظهور چارچوب الگوریتم‌های یادگیری‌افزوده تلاشی برای تلفیق این دو رویکرد محسوب می‌شود؛ به‌گونه‌ای که اطلاعات حاصل از مدل‌های یادگیری ماشین در طراحی الگوریتم به کار گرفته شود، بدون آنکه تضمین‌های عملکرد در بدترین حالت از بین برود. در این مقاله، ابتدا مبانی نظری الگوریتم‌های یادگیری‌افزوده شامل مفاهیم سازگاری، استحکام و همواری بررسی می‌شود. سپس دو مسئله شاخص این حوزه، یعنی مسئله اجاره اسکی و مسئله پوشش رأسی برخط، از منظر ساختار الگوریتمی، نوع پیش‌بینی، معیارهای ارزیابی و کران‌های نظری مورد مطالعه قرار می‌گیرند. همچنین توسعه‌های جدید این حوزه، از جمله پیش‌بینی‌های کالیبره‌شده، روش‌های اولیه–دوگان یادگیری‌افزوده و پیش‌بینی متغیرهای دوگان، معرفی و تحلیل می‌شوند. نتایج این بررسی نشان می‌دهد که بهره‌گیری هدفمند از پیش‌بینی‌های یادگیری ماشین می‌تواند نسبت رقابتی یا نسبت تقریب الگوریتم‌ها را در شرایط وجود پیش‌بینی‌های دقیق به طور محسوسی بهبود بخشد، در حالی که در صورت نادرست بودن پیش‌بینی‌ها، تضمین‌های نظری کلاسیک همچنان حفظ می‌شوند. علاوه بر این، شباهت ساختاری میان مسئله اجاره اسکی و مسئله پوشش رأسی نشان می‌دهد که بسیاری از روش‌های توسعه‌یافته برای یکی از این مسائل قابلیت تعمیم به دیگری را نیز دارند. در پایان، روندهای نوین پژوهشی و چالش‌های آینده در زمینه الگوریتم‌های یادگیری‌افزوده مورد بحث قرار می‌گیرد.

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