Boosting و AdaBoost

ایده‌ی Boosting و الگوریتم AdaBoost

برخلاف Bagging که مدل‌ها را موازی و مستقل می‌سازد، Boosting آن‌ها را پشت سر هم می‌سازد و هر مدل روی اشتباه‌های قبلی تمرکز می‌کند. هدف اصلی‌اش کاهش بایاس است.

AdaBoost با برچسب‌های $y_i \in \{-1, +1\}$:

1. وزن‌ها را یکسان شروع کن: $w_i = 1/n$
2. برای $t = 1, \dots, T$:
   • یادگیرنده‌ی ضعیف $h_t$ را با وزن‌های $w_i$ آموزش بده
   • خطای وزن‌دار $\varepsilon_t = \sum_i w_i\,\mathbb{1}[h_t(x_i) \ne y_i]$ را حساب کن
   • ضریب مدل: $\alpha_t = \tfrac12 \ln\dfrac{1-\varepsilon_t}{\varepsilon_t}$
   • وزن‌ها را به‌روز کن: $w_i \leftarrow w_i\,e^{-\alpha_t y_i h_t(x_i)}$ و نرمال کن
3. خروجی نهایی: $H(x) = \operatorname{sign}\big(\sum_t \alpha_t h_t(x)\big)$

نمونه‌های اشتباه ($y_i h_t(x_i) = -1$) وزنشان در $e^{\alpha_t}$ ضرب می‌شود و بزرگ‌تر می‌شود.

AdaBoost از نگاه تابع زیان

Friedman، Hastie و Tibshirani (۲۰۰۰) نشان دادند AdaBoost همان مدل‌سازی جمعی گام‌به‌گام با زیان نمایی است:

این دید دو نتیجه دارد:

• زیان نمایی برای نمونه‌هایی که با حاشیه‌ی زیاد اشتباه دسته‌بندی شده‌اند، بسیار سریع رشد می‌کند. پس AdaBoost به نویز برچسب و داده‌ی پرت حساس است.
• با عوض کردن تابع زیان می‌شود الگوریتم‌های Boosting دیگری ساخت. این همان ایده‌ی Gradient Boosting در درس بعد است.