آدابوست

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

آدابوست مخفف بوستینگ تطبیقی بوده و یک الگوریتم یادگیری ماشین است که توسط یاو فروند و رابرت شاپیر ابداع شد.[۱] در واقع آدابوست یک متا الگوریتم است که بمنظور ارتقاء عملکرد، و رفع مشکل رده‌های نامتوازن[۲] همراه دیگر الگوریتم‌های یادگیری استفاده می‌شود. در این الگوریتم، طبقه بند هر مرحله جدید به نفع نمونه‌های غلط طبقه‌بندی شده در مراحل قبل تنظیم می‌گردد. آدابوست نسبت به داده‌های نویزی و پرت حساس است؛ ولی نسبت به مشکل بیش برازش از بیشتر الگوریتم‌های یادگیری برتری دارد. طبقه بند پایه که در اینجا استفاده می‌شود فقط کافیست از طبقه بند تصادفی (۵۰٪) بهتر باشد و به این ترتیب بهبود عملکرد الگوریتم با تکرارهای بیشتر بهبود می‌یابد. حتی طبقه بندهای با خطای بالاتر از تصادفی با گرفتن ضریب منفی عملکرد کلی را بهبود می‌بخشند. در الگوریتم آدابوست در هر دور یک طبقه بند ضعیف اضافه می‌شود. در هر فراخوانی بر اساس اهمیت نمونه‌ها، وزن‌ها بروز می‌شود. در هر دور وزن نمونه‌های غلط طبقه‌بندی شده افزایش و وزن نمونه‌های درست طبقه‌بندی شده کاهش داده می‌شود؛ بنابراین طبقه بند جدید تمرکز بر نمونه‌هایی که سخت تر یادگرفته می‌شوند، خواهند داشت.

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

داده شده‌ها:

  • مجموعه یادگیری: که
  • تعداد تکرارها:

مقداردهی اولیه: برای

  • برای خانواده طبقه‌بندهای ضعیف ℋ طبقه‌بند را پیدا کن که میزان خطا نسبت به توزیع کمینه شود، در این معادله یک تابع نشانگر است:

خطای را با نمایش میدهیم:

  • اگر که یک آستانه تعیین شده قبلی است، توقف انجام شود.
  • معمولاً مقدار برای در نظر گرفته می‌شود.
  • بروز رسانی:
که یک عامل نرمالیزاسیون با مقدار است که موجب می‌شود یک توزیع احتمالاتی مجاز را نشان دهد (مجموع روی همه ها یک شود)
خروجی نهایی طبقه بند
توجه شود که معادله بروز رسانی توزیع بگونه‌ای بروز می‌شود که

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

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

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

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

مجهولِ تابع هزینه ، است که خود به بستگی دارد. در نتیجه بهینه سازی تابع هزینه در نهایت باید نسبت به صورت بگیرد.

حال برای راحتتر شدن کار فرض میکنیم که مقادیر ثابت هستند و هدف ما پیدا کردن و است. با این اوصاف تابع را می‌توان به شکل پایین نوشت:

اگر را با نمایش دهیم، تابع هزینه ما به شکل پایین تغییر شکل خواهد داد[۴]:

اگر مجموعه تمام داده‌هایی که توسط به درستی پیش‌بینی می‌شوند را با و مجموعه تمام داده‌هایی که توسط نادرست پیش‌بینی میشوند را با نمایش دهیم. تابع هزینه به شکل پایین تغییر خواهد کرد:‌

حال اگر را نسبت بهینه کنیم، ازآنجا که و نسبت به ثابت هستند، فقط باید را نسبت به کمینه کنیم. یعنی

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

حال که و را پیدا کردیم باید ببینیم که به چه شکل نسبت به بروز می شود. همان است یعنی

پس ارتباط با به این شکل خواهد بود[۴]:

از آنجا که به‌روز کردن به این شکل تغییر خواهد کرد:

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

همان است، و از آنجا که در جواب تاثیری ندارد، می توان آنرا حذف کرد. حال اگر را همان بگیریم به الگوریتم آدابوست خواهیم رسید[۴].

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

منابع[ویرایش]

  1. Yoav Freund, Robert E. Schapire. "A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting", 1995
  2. مهسا المعی نژاد. «روش‌های Bagging و Boosting به منظور رفع مشکل کلاس‌های نامتوازن». گروه داده کاوی ایران. بازبینی‌شده در ۲۶ فبریه ۲۰۱۴. 
  3. T. Zhang, "Statistical behavior and consistency of classification methods based on convex risk minimization", Annals of Statistics 32 (1), pp. 56-85, 2004.
  4. ۴٫۰ ۴٫۱ ۴٫۲ ۴٫۳ Bishop, Christopher. Pattern Recognition and Machine Learning. New York: Springer, 2006. 658-661. ISBN ‎978-0-387-31073-2. 

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

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