Skip to content
بازگشت به نتایج جست‌وجو

AdaBoost

معرفی‌شده توسط
Freund, Y. & Schapire, R.E.
سال
1997
نوع
Ensemble (sequential boosting of weak learners)

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

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

شهود پشت روش

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

تاریخ

AdaBoost در سال ۱۹۹۷ توسط Yoav Freund و Robert Schapire به عنوان تعمیم نظریه تصمیم‌گیری یادگیری آنلاین به بوستینگ معرفی شد. این اولین الگوریتم بوستینگ عملی بود و نشان داد که بسیاری از یادگیرنده‌های ضعیف می‌توانند با هم ترکیب شده و یک یادگیرنده قوی را تشکیل دهند، کاری که برای کل خانواده بوستینگ بنیادی شد. این الگوریتم پیشگام مستقیم بوستینگ گرادیان و ابزارهای مدرن مانند XGBoost است.

چه زمانی استفاده شود

برای طبقه‌بندی و پیش‌بینی بر روی داده‌های جدولی مقطعی با ویژگی‌های پیوسته، دسته‌ای یا دودویی و حداقل حدود ۵۰ مشاهده مناسب است، زمانی که یک خط پایه بوستینگ ساده و قابل تفسیر می‌خواهید. AdaBoost هیچ فرض نرمالیتی ندارد، اما به داده‌های نویزی و نقاط پرت حساس است، بنابراین ابتدا نقاط پرت را غربالگری کنید. تعداد تخمین‌گرها را برای مدیریت ریسک بیش‌برازش کم اما غیرصفر کنترل کنید. در نمونه‌های کوچک، رگرسیون لجستیک ساده‌تر یا Random Forest مقاوم‌تر، گزینه‌های ایمن‌تری هستند.

محدودیت‌ها و ملاحظات

  • به دلیل تابع زیان نمایی خود به داده‌های نویزی و نقاط پرت حساس است؛ غربالگری نقاط پرت لازم است.
  • ریسک بیش‌برازش کم اما غیرصفر است و باید از طریق تعداد تخمین‌گرها کنترل شود.
  • در نمونه‌های کوچک (n کمتر از حدود ۵۰) مشاهدات نویزی بیش از حد وزن‌دهی می‌شوند و هر تکرار می‌تواند عملکرد را بدتر کند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • ساده و قابل تفسیر، با پارامترهای کمی برای تنظیم.
  • یادگیرنده‌های ضعیف با عمق ۱ را به یک طبقه‌بند قوی تبدیل می‌کند، یک خط پایه آماده و قوی.
  • فرض نرمالیتی ندارد؛ با ویژگی‌های پیوسته، دسته‌ای و دودویی کار می‌کند.
  • پیشگام بوستینگ گرادیان، با یک مکانیزم وزن‌دهی تطبیقی واضح.

کاربردها

  • خطوط پایه طبقه‌بندی بر روی داده‌های جدولی مقطعی.
  • وظایف پیش‌بینی که در آن‌ها یک مدل بوست شده ساده و قابل تفسیر ترجیح داده می‌شود.
  • آموزش و نمایش ایده بوستینگ قبل از رفتن به سراغ بوستینگ گرادیان.
  • ترکیب بسیاری از decision stumpهای کم‌عمق در یک طبقه‌بند قوی واحد.

چگونه کار می‌کند

چگونه کار می‌کند

1

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

2

یک یادگیرنده ضعیف — معمولاً یک decision stump، درختی با عمق ۱ — بر روی داده‌های وزن‌دار برازش می‌شود. به دلیل سادگی، به تنهایی تنها کمی بهتر از شانس عمل می‌کند.

3

دقت کلی یادگیرنده، میزان تأثیر آن را در رأی نهایی تعیین می‌کند و وزن مشاهداتی که اشتباه طبقه‌بندی کرده است افزایش می‌یابد تا یادگیرنده بعدی بر آن‌ها تمرکز کند. تابع زیان نمایی این به‌روزرسانی را هدایت می‌کند: این تابع جریمه‌ای با نرخ افزایشی شدید برای طبقه‌بندی اشتباه اعمال می‌کند، که همچنین باعث می‌شود AdaBoost به نقاط پرت و داده‌های نویزی حساس باشد.

فرمول
w_i \leftarrow w_i \exp(\alpha \, \mathbb{1}[y_i \neq h(x_i)])
4

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

فرمول
H(x) = \text{sign}\left(\sum_t \alpha_t h_t(x)\right)

دام‌های رایج

  • اجرای AdaBoost بر روی داده‌های پر از نقاط پرت بدون غربالگری اولیه آن‌ها.
  • اجازه دادن به رشد نامحدود تعداد تخمین‌گرها به جای تنظیم آن.
  • استفاده از آن بر روی نمونه‌ای با کمتر از حدود ۵۰ مشاهده، که در آن نقاط نویزی بر وزن‌دهی غالب می‌شوند.
  • انتخاب AdaBoost زمانی که یک مجموعه داده مقاوم‌تر مانند Random Forest داده‌های نویزی را بهتر برازش می‌دهد.

پرسش‌های متداول

AdaBoost چگونه با Random Forest تفاوت دارد؟

Random Forest بسیاری از درختان مستقل را به صورت موازی ساخته و آن‌ها را میانگین‌گیری می‌کند (bagging)؛ AdaBoost یادگیرنده‌های ضعیف را به صورت متوالی می‌سازد، که هر کدام بر مواردی که موارد قبلی اشتباه انجام داده‌اند تمرکز می‌کنند (boosting). به دلیل تابع زیان نمایی خود، AdaBoost به نویز و نقاط پرت حساس‌تر است، در حالی که Random Forest مقاوم‌تر است.

چرا AdaBoost به نقاط پرت حساس است؟

این الگوریتم از تابع زیان نمایی استفاده می‌کند که جریمه طبقه‌بندی اشتباه را با نرخ افزایشی شدید اعمال می‌کند. نقاطی که به طور مداوم اشتباه طبقه‌بندی می‌شوند — اغلب نقاط پرت یا مشاهدات نویزی — وزن بیشتری کسب می‌کنند، بنابراین می‌توانند تکرارهای بعدی را تحت تأثیر قرار داده و مدل را تخریب کنند.

چند تخمین‌گر باید استفاده کنم؟

تعداد تخمین‌گرها (یادگیرنده‌های ضعیف) ریسک بیش‌برازش کم اما واقعی AdaBoost را کنترل می‌کند. آن را افزایش دهید تا زمانی که عملکرد اعتبارسنجی بهبود یابد و زمانی که ثابت شد یا شروع به بدتر شدن کرد، متوقف شوید.

یادگیرنده ضعیف در اینجا چیست؟

معمولاً یک decision stump — یک درخت تصمیم با عمق ۱. به تنهایی تنها کمی بهتر از شانس عمل می‌کند، اما AdaBoost بسیاری از آن‌ها را ترکیب می‌کند، که هر کدام با دقت خود وزن‌دهی می‌شوند، تا یک طبقه‌بند قوی واحد را تشکیل دهند.

روش‌های مرتبط

منابع

  1. Freund, Y. & Schapire, R.E. (1997). A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1), 119–139.

    باز کردن مرجع DOI
    کپی شد.