آدابوست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

آدابوست مخفف بوستینگ تطبیقی بوده و یک الگوریتم یادگیری ماشین است که توسط یاو فروند و رابرت شاپیر ابداع شد.[۱] در واقع آدابوست یک متا الگوریتم است که بمظور ارتقاء عملکرد، و رفع مشکل رده های نامتوزان[۲] همراه دیگر الگوریتم های یادگیری استفاده می شود. در این الگوریتم، طبقه بند هر مرحله جدید به نفع نمونه های غلط طبقه بندی شده در مراحل قبل تنظیم می گردد. آدابوست نسبت به داده های نویزی و پرت حساس است. ولی نسبت به مشکل بیش برازش از بیشتر الگوریتم های یادگیری برتری دارد. طبقه بند پایه که در اینجا استفاده می شود فقط کافیست از طبقه بند نصادفی(50%) بهتر باشد و به این ترتیب بهبود عملکرد الگوریتم با تکرارهای بیشتر بهبود می یابد. حتی طبقه بندهای با خطای بالاتر از تصادفی با گرفتن ضریب منفی عملکرد کلی را بهبود می بخشند. در الگوریتم آدابوست در هر دور  t = 1,\ldots,T یک طبقه بند ضعیف اضافه می شود. در هر فراخوانی بر اساس اهمیت نمونه ها، وزن ها D_{t} بروز می شود. در هر دور وزن نمونه های غلط طبقه بندی شده افزایش و وزن نمونه های درست طبقه بندی شده کاهش داده می شود. بنابراین طبقه بند جدید تمرکز بر نمونه هایی که سخت تر یادگرفته می شوند، خواهند داشت.

الگوریتم طبقه بندی دوگانه[ویرایش]

داده شده ها:

  • مجموعه یادگیری: (x_{1},y_{1}),\ldots,(x_{m},y_{m}) که x_{i} \in X,\, y_{i} \in Y = \{-1, +1\}
  • تعداد تکرارها: T

مقداردهی اولیه: \textstyle D_{1}(i) = \frac{1}{m}, i=1,\ldots,m. برای t = 1,\ldots,T

  • برای خانواده طبقه بندهای ضعیف ℋ طبقه بند h_{t}\,\! را پیدا کن که قدر مطلق اختلاف نرخ خطای وزن دهی شده متناظر \epsilon_{t}\,\! از 0.5 نسبت به توزیع D_{t} حداکثر شود :

h_{t} = \underset{h_{t} \in \mathcal{H}}{\operatorname{argmax}} \; \left\vert 0.5 - \epsilon_{t}\right\vert که  \epsilon_{t} = \sum_{i=1}^{m} D_{t}(i)I(y_i \ne h_{t}(x_{i})) . I یک تابع نشانگر است

  • اگر \left\vert 0.5 - \epsilon_{t}\right\vert \leq \beta که \beta یک آستانه تعین شده قبلی است، توقف انجام شود.
  • معمولا مفدار \alpha_{t}=\frac{1}{2}\textrm{ln}\frac{1-\epsilon_{t}}{\epsilon_{t}} برای \alpha_{t} \in \mathbb{R} در نظر گرفته می شود.
  • بروز رسانی :
D_{t+1}(i) = \frac{ D_t(i) \exp(-\alpha_t y_i h_t(x_i)) }{ Z_t }
که Z_{t} یک عامل نرمالیزاسیون با مقدار \sum_{i} D_{t}(i)\exp(-\alpha_t y_i h_t(x_i))\,\! است که موجب می شود D_{t+1} یک توزیع احتمالاتی مجاز را نشان دهد(مجموع روی همه x ها یک شود)
خروجی نهایی طبقه بند
H(x) = \textrm{sign}\left( \sum_{t=1}^{T} \alpha_{t}h_{t}(x)\right)
توجه شود که معادله بروز رسانی توزیع D_{t} بگونه ای بروز می شود که
- \alpha_{t} y_{i} h_{t}(x_{i}) \begin{cases} <0, & y(i)=h_{t}(x_{i}) \\ >0, & y(i) \ne h_{t}(x_{i}) \end{cases}

بنابراین بعد از انتخاب بهینه طبقه بند h_{t} \, برای توزیع D_{t} \, آندسته از نمونه ها x_{i} \, که طبقه بند h_{t} \, آنها را غلط طبقه بندی می کند وزن بیشتری نسبت به بقیه داده می شود. بنابراین وقتی الگوریتم طبقه بندها را براساس توزیع D_{t+1} \, تست می کند، طبقه بندی انتخاب می شود که نمونه های غلط طبقه بندی شده را بهتر تشخیص دهد.

درک آماری تقویت کردن[ویرایش]

عمل تقویت کردن را می توان بصورت حداقل کردن یک تابع هزینه محدب روی یک مجموعه محدب از توابع درنظر گرفت.[۳] بطور خاص تابعی که حداقل می شود نمایی است :

\sum_i e^{-y_i f(x_i)}

و ما بدنبال تابعی به شکل زیر هستیم :

f(x) = \sum_t \alpha_t h_t(x)\,\!

مطالب مرتبط[ویرایش]

  • * * == منابع ==
  1. Yoav Freund, Robert E. Schapire. "A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting", 1995
  2. مهسا المعی نژاد. «روش‌های Bagging و Boosting به منظور رفع مشکل کلاس‌های نامتوازن». گروه داده کاوی ایران. بازبینی‌شده در 26 فبریه 2014. 
  3. T. Zhang, "Statistical behavior and consistency of classification methods based on convex risk minimization", Annals of Statistics 32 (1), pp. 56-85, 2004.

پیاده سازی ها[ویرایش]

پیوند به بیرون[ویرایش]