بوستینگ

بوستینگ یک فرا الگوریتم ترکیبی در حوزه یادگیری ماشین است که برای کاهش عدم توازن و همچنین واریانس به کار می‌رود. این روش در یادگیری با نظارت مورد استفاده قرار گرفته و از خانواده الگوریتم‌های یادگیری ماشین گروهی به شمار می‌رود. این تکنیک، روشی برای تبدیل سیستمهای یادگیری ضعیف به قوی بر اساس ترکیب نتایج طبقه بندهای مختلف است. ایده اولیه این روش بر اساس سؤال مطرح شده توسط کیرنس و شجاع (۱۹۸۸، ۱۹۸۹) به وجود آمده است: آیا می‌توان با ترکیب مجموعه‌ای از سیستم‌های یادگیری ضعیف یک سیستم یادگیری قوی ایجاد نمود؟

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

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

در تصویر سمت چپ صفحه می‌توانید شکل کلی الگوریتم‌ بوستینگ را مشاهده کنید.

مراحل الگوریتم:

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

تاکنون الگوریتم‌های بوستینگ زیادی به وجود آمده‌اند ولی نسخه اصلی این الگوریتم‌ها توسط Robert Schapire و Yoav Freund ارائه شده است که Adaptive نبوده و امکان استفاده کامل از مزایای یادگیرنده‌های ضعیف را ندارد. بعدها این دو نفر الگوریتم AdaBoost که یک الگوریتم بوستینگ سازگار (Adaptive) بود را ارائه نموده و جایزه معتبر گودل را برنده شدند. روش‌های مختلف موجود بوستینگ در نحوه ساخت و تجمیع یادگیرنده‌های ضعیف در پروسه آموزش سریالی با هم تفاوت دارند. از دیگر انواع روش‌های مشهور بوستینگ می‌توان به تقویت گرادیان و XGBoost‌ اشاره کرد.

مزیت‌ها و چالش‌های روش بوستینگ 
مزیت‌های اصلی استفاده از روش‌های بوستینگ به صورت زیر هستند:

 پیاده‌سازی آسان: الگوریتم بوستینگ می‌تواند در کنار گزینه‌های متعدد بهینه‌سازی ابرپارامترها استفاده شود و میزان تطابق مدل با داده‌ها بهتر شود. همچنین نیاز به آماده‌سازی اولیه داده‌ها نیست و همچنین الگوریتم‌های بوستینگ معمولا توابعی برای برطرف کردن مشکل داده‌های گم‌شده در پیاده‌سازی داخلی خود دارند. کتابخانه‌های آماده موجود در زبان‌های برنامه‌نویسی مختلف مانند کتابخانه scikit-learn در python شامل مجموعه‌ای از پیاده‌سازی‌های روش‌های بوستینگ شامل آدابوست، XGBoost، تقویت گرادیان و ... می‌شود که باعث آسان شدن پیاده‌سازی متد‌های روش‌های مختلف بوستینگ می‌شود.
 کاهش بایاس: الگوریتم‌های بوستینگ با ترکیب چندین یادگیرنده ضعیف به صورت سریالی، باعث بهبود عملکرد مدل می‌شود و بایاس مدل را کاهش می‌دهد.

چالش‌های اصلی هنگام استفاده از روش‌های بوستینگ:

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

جستار‌های وابسته 

 یادگیری ماشین
 یادگیری با نظارت
 AdaBoost 
 تقویت گرادیان
 XGBoost
 ماشین بردار‌ پشتیبانی
 شبکه‌ عصبی

منابع 

الگوریتم‌های دسته‌بندی
یادگیری در بینایی رایانه‌ای
یادگیری گروهی