بوستینگ
بوستینگ یک فرا الگوریتم ترکیبی در حوزه یادگیری ماشین است که برای کاهش عدم توازن و همچنین واریانس به کار میرود.[1] این روش در یادگیری با نظارت مورد استفاده قرار گرفته و از خانواده الگوریتمهای یادگیری ماشین به شمار میرود. این تکنیک، روشی برای تبدیل سیستمهای یادگیری ضعیف به قوی بر اساس ترکیب نتایج طبقه بندهای مختلف است.[2] ایده اولیه این روش بر اساس سؤال مطرح شده توسط کیرنس و شجاع (۱۹۸۸، ۱۹۸۹) به وجود آمده است:[3][4] آیا میتوان با ترکیب مجموعهای از سیستمهای یادگیری ضعیف یک سیستم یادگیری قوی ایجاد نمود؟
سیستم یادگیری ضعیف، یادگیرندهای است که به عنوان یک طبقه بند، تنها کمی بهتر از حالت تصادفی عمل مینماید (برچسب نمونهها را بهتر از تصادفی حدس میزند). در مقابل یادگیرنده قوی طبقهبندی است که به تنهایی میتواند برچسب نمونهها را خوبی پیش بینی نماید.
الگوریتم بوستینگ
هرچند که بوستینگ در قالب الگوریتمیک قرار ندارد ولی اکثر الگوریتمهایی که بر پایه بوستینگ طراحی شدهاند، یادگیرندههای ضعیف را به صورت تکرار شونده آموزش داده و به مجموعه قبلی اضافه مینماید تا در نهایت به یک طبقه بند قوی دست یابد. یادگیرندههای ضعیف در حین اضافه شدن به مجموعه، وزن دهی میشوند که این وزن دهی معمولاً بر اساس میزان دقت در طبقهبندی نمونه هاست. پس از اضافه شدن هر طبقه بند، نمونههای موجود (دادهها) نیز وزن دهی میگردند (وزنشان اصلاح میگردد). وزن دهی نمونهها به صورتی است که در هر مرحله، وزن نمونههایی که به صورت صحیح طبقهبندی میشوند کاهش یافته و وزن نمونههایی که به درستی طبقهبندی نشدهاند، بیشتر میشود تا در مراحل بعدی (توسط یادگیرندههای جدید) بیشتر مورد توجه بوده و با دقت بیشتری طبقهبندی گردند؛ بنابراین تمرکز یادگیرندههای ضعیف جدید، بیشتر بر روی دادههای خواهد بود که سیستم در مراحل قبلی قادر به طبقهبندی صحیح آنها نبوده است.
تاکنون الگوریتمهای بوستینگ زیادی به وجود آمدهاند ولی نسخه اصلی این الگوریتمها توسط Robert Schapire و Yoav Freund ارائه شده است که Adaptive نبوده و امکان استفاده کامل از مزایای یادگیرندههای ضعیف را ندارد. بعدها این دو نفر الگوریتم AdaBoost که یک الگوریتم بوستینگ سازگار (Adaptive) بود را ارائه نموده و جایزه معتبر گودل را برنده شدند.
منابع
- 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.