بوستینگ

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

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

الگوریتم بوستینگ

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

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

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

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

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

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

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

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

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

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

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

منابع

↑ Leo Breiman (1996). "BIAS, VARIANCE, AND ARCING CLASSIFIERS" (PDF). TECHNICAL REPORT. Archived from the original (PDF) on 19 January 2015. Retrieved 19 January 2015. Arcing [Boosting] is more successful than bagging in variance reduction
↑ Zhou Zhi-Hua (2012). Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. p. 23. ISBN 978-1439830031. The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners
↑ Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
↑ Michael Kearns; Leslie Valiant (1989). "Crytographic limitations on learning Boolean formulae and finite automata". Symposium on Theory of computing. ACM. 21: 433–444. doi:10.1145/73007.73049. Retrieved 18 January 2015.
↑ Tieu, Kinh; Viola, Paul (2004-01-01). "Boosting Image Retrieval". International Journal of Computer Vision (به انگلیسی). 56 (1): 17–36. doi:10.1023/B:VISI.0000004830.93820.78. ISSN 1573-1405.
↑ Vezhnevets, Alexander; Barinova, Olga (2007). Kok, Joost N.; Koronacki, Jacek; Mantaras, Raomon Lopez de; Matwin, Stan; Mladenič, Dunja; Skowron, Andrzej (eds.). "Avoiding Boosting Overfitting by Removing Confusing Samples". Machine Learning: ECML 2007 (به انگلیسی). Berlin, Heidelberg: Springer: 430–441. doi:10.1007/978-3-540-74958-5_40. ISBN 978-3-540-74958-5.

[1] Leo Breiman (1996). "BIAS, VARIANCE, AND ARCING CLASSIFIERS" (PDF). TECHNICAL REPORT. Archived from the original (PDF) on 19 January 2015. Retrieved 19 January 2015. Arcing [Boosting] is more successful than bagging in variance reduction

[2] Zhou Zhi-Hua (2012). Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. p. 23. ISBN 978-1439830031. The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners

[Kearns88-3] Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)

[4] Michael Kearns; Leslie Valiant (1989). "Crytographic limitations on learning Boolean formulae and finite automata". Symposium on Theory of computing. ACM. 21: 433–444. doi:10.1145/73007.73049. Retrieved 18 January 2015.

[5] Tieu, Kinh; Viola, Paul (2004-01-01). "Boosting Image Retrieval". International Journal of Computer Vision (به انگلیسی). 56 (1): 17–36. doi:10.1023/B:VISI.0000004830.93820.78. ISSN 1573-1405.

[6] Vezhnevets, Alexander; Barinova, Olga (2007). Kok, Joost N.; Koronacki, Jacek; Mantaras, Raomon Lopez de; Matwin, Stan; Mladenič, Dunja; Skowron, Andrzej (eds.). "Avoiding Boosting Overfitting by Removing Confusing Samples". Machine Learning: ECML 2007 (به انگلیسی). Berlin, Heidelberg: Springer: 430–441. doi:10.1007/978-3-540-74958-5_40. ISBN 978-3-540-74958-5.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]