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

Online Boosting

معرفی‌شده توسط
Oza, N. C. & Russell, S.
سال
2001
نوع
Online ensemble (incremental boosting)
خانواده
Machine learning

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

اندازه قلم

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

Online Boosting چارچوب کلاسیک بوستینگ را با جریان‌های داده تطبیق می‌دهد و مجموعه‌ای از یادگیرنده‌های ضعیف را با پردازش یک نمونه در هر زمان، بدون نیاز به ذخیره کل مجموعه داده، به‌روزرسانی می‌کند. فرمول‌بندی Oza-Russell بازوزنی AdaBoost را با استفاده از شمارش نمونه‌های نمونه‌برداری شده پواسون تقریب می‌زند و طبقه‌بندی دقیق و تطبیقی را در محیط‌های بی‌درنگ یا با محدودیت منابع امکان‌پذیر می‌سازد.

شهود پشت روش

بوستینگ دسته‌ای (Batch boosting) وزن نمونه‌های آموزشی را تغییر می‌دهد تا یادگیرنده‌های متوالی را مجبور کند خطاهای یکدیگر را اصلاح کنند، اما این امر مستلزم دیدن تمام داده‌ها به صورت یکجا است. Online Boosting بازوزنی صریح را با ترفند نمونه‌برداری پواسون جایگزین می‌کند: هر نمونه ورودی به زنجیره‌ای از یادگیرنده‌های ضعیف ارسال می‌شود و تعداد دفعاتی که هر یادگیرنده آن را می‌بیند (وزن مؤثر آن) از توزیع پواسون که نرخ آن هنگام اشتباه بودن یادگیرنده قبلی افزایش و هنگام درست بودن آن کاهش می‌یابد، نمونه‌برداری می‌شود. نتیجه به طور نزدیک دینامیک اصلاحی AdaBoost را بدون نیاز به بازپخش داده‌های گذشته تقلید می‌کند.

تاریخ

Online Boosting توسط Nikunj Oza و Stuart Russell در مقاله سال ۲۰۰۱ آنها با عنوان 'Online Bagging و Boosting' فرموله شد، که نشان داد ترفند نمونه‌برداری پواسون یک تقریب آماری معتبر به AdaBoost دسته‌ای در محیط جریان ارائه می‌دهد. این کار بر اساس AdaBoost (1997) از Freund و Schapire و نمونه‌برداری دسته‌ای (1996) از Breiman بنا شد. تحقیقات بعدی این رویکرد را برای مدیریت انحراف مفهوم، مسائل چندکلاسه و یادگیری حساس به هزینه گسترش داد و Online Boosting را به عنوان یک ابزار استاندارد در ادبیات داده‌کاوی جریانی تثبیت کرد.

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

هنگامی که داده‌ها به صورت یک جریان پیوسته وارد می‌شوند و مدل باید به صورت افزایشی و بدون بازبینی نمونه‌های گذشته به‌روز شود، از Online Boosting استفاده کنید — به عنوان مثال در تشخیص تقلب بی‌درنگ، نظارت بر نفوذ شبکه، طبقه‌بندی مبتنی بر حسگر، یا هر وضعیتی که ذخیره کل مجموعه داده غیرممکن است. این روش در مواردی که جریان دارای انحراف مفهوم (concept drift) است که از بازوزنی تطبیقی سود می‌برد، از یادگیرنده‌های آنلاین منفرد و نمونه‌برداری آنلاین بهتر عمل می‌کند. زمانی که مجموعه داده ایستا است و در حافظه جا می‌شود، از آن استفاده نکنید — بوستینگ گرادیان دسته‌ای (XGBoost, LightGBM) تقریباً همیشه دقت بالاتری تولید خواهد کرد. همچنین از آن در مواردی که جریان دارای انحراف مفهوم شدید و ناگهانی است، اجتناب کنید، زیرا ممکن است به مکانیزم‌های بازنشانی صریح تشخیص انحراف که در Online Boosting پایه ساخته نشده‌اند، نیاز داشته باشد.

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

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

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

نقاط قوت

  • هر نمونه را دقیقاً یک بار پردازش می‌کند و آن را برای جریان‌های داده با سرعت بالا یا محدود از نظر حافظه مناسب می‌سازد.
  • خاصیت کاهش بایاس قوی بوستینگ را به ارث می‌برد و اغلب در وظایف طبقه‌بندی دشوار از نمونه‌برداری آنلاین بهتر عمل می‌کند.
  • بازوزنی تطبیقی به نمونه‌های بعدی اجازه می‌دهد تا خطاهای معرفی شده توسط بخش‌های قبلی جریان را اصلاح کنند.
  • نیازی به تنظیم ابرپارامتر وزن نمونه نیست؛ تقریب پواسون خودتنظیم است.
  • با هر یادگیرنده ضعیف قابل به‌روزرسانی افزایشی سازگار است و انعطاف‌پذیری در انتخاب مدل را فراهم می‌کند.

کاربردها

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

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

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

1

یک دنباله مرتب از M یادگیرنده ضعیف — معمولاً درخت‌های تصمیم کم‌عمق یا ساقه‌ها — با نرخ‌های پواسون برابر مقداردهی اولیه می‌شوند. هر یادگیرنده با وزن آلفا و شمارش جاری پیش‌بینی‌های وزنی صحیح و نادرست که برای تخمین سهم آن استفاده می‌شود، مرتبط است.

2

یک نمونه برچسب‌دار جدید از جریان وارد می‌شود. هیچ داده تاریخی ذخیره نمی‌شود؛ الگوریتم آن را یک بار پردازش کرده و به سراغ بعدی می‌رود. این محدودیت تک‌گذر، ویژگی تعیین‌کننده‌ای است که بوستینگ آنلاین را از همتای دسته‌ای آن متمایز می‌کند.

3

برای یادگیرنده اول، نمونه k بار تکرار می‌شود که k از پواسون(1) نمونه‌برداری شده است. این امر نمونه‌برداری با جایگذاری را مانند نمونه‌برداری دسته‌ای تقریب می‌زند. نرخ پواسون لامبدا در طول زنجیره منتشر می‌شود و به عنوان وزن مؤثر نمونه برای هر یادگیرنده بعدی عمل می‌کند.

فرمول
k \sim \text{Poisson}(\lambda),\; \lambda = 1 \text{ initially}
4

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

5

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

فرمول
\lambda_{m+1} = \lambda_m \cdot \frac{e^{\pm \alpha_m}}{Z_m}
6

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

فرمول
\hat{y} = \operatorname{sign}\!\left(\sum_{m=1}^{M} \alpha_m h_m(x)\right)

دام‌های رایج

  • اشتباه گرفتن Online Boosting با Batch Boosting و انتظار دقت یکسان در مجموعه داده‌های ایستا — در صورت امکان از روش‌های دسته‌ای استفاده کنید.
  • نادیده گرفتن نویز برچسب: یک جریان نویزی سریع‌تر از Online Bagging به Online Boosting آسیب می‌زند زیرا بوستینگ تأثیر نمونه‌های دشوار (احتمالاً با برچسب اشتباه) را تشدید می‌کند.
  • انتخاب M (تعداد یادگیرنده‌های ضعیف) بسیار کوچک و پذیرش عملکرد ضعیف بدون تنظیم.
  • عدم نظارت بر انحراف مفهوم و ادامه اتکا به مدلی که مفروضات توزیع آن تغییر کرده است.
  • گزارش فقط دقت لحظه‌ای به جای ارزیابی پیش‌گویانه (آزمون-سپس-آموزش)، که می‌تواند افت عملکرد را پنهان کند.

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

Online Boosting چگونه با AdaBoost دسته‌ای تفاوت دارد؟

AdaBoost دسته‌ای با مقیاس‌بندی مجدد احتمالات نمونه‌برداری آنها در طول چندین گذر، وزن نمونه‌های آموزشی را تغییر می‌دهد. Online Boosting با عبور دادن هر نمونه ورودی از طریق زنجیره‌ای از یادگیرنده‌های ضعیف و تنظیم نرخ پواسون که کنترل می‌کند هر یادگیرنده چند بار نمونه را می‌بیند، بدون ذخیره یا بازپخش داده‌های تاریخی، این را تقریب می‌زند.

باید از چند یادگیرنده ضعیف M استفاده کنم؟

مقدار M بین 10 تا 50 برای ساقه‌های کم‌عمق یا درخت‌های کوچک معمول است. یادگیرنده‌های بیشتر بایاس را کاهش می‌دهند اما تأخیر استنتاج را افزایش می‌دهند. M را با استفاده از ارزیابی پیش‌گویانه بر روی بخشی از داده‌های نماینده قبل از استقرار، تنظیم کنید.

آیا Online Boosting نسبت به انحراف مفهوم مقاوم است؟

Online Boosting پایه به طور صریح انحراف مفهوم را تشخیص نمی‌دهد یا به آن پاسخ نمی‌دهد. برای جریان‌های منحرف، آن را با یک الگوریتم تشخیص انحراف مانند ADWIN یا DDM که هنگام تشخیص انحراف، بازنشانی جزئی یا کامل مجموعه را فعال می‌کند، جفت کنید.

چه زمانی باید Online Bagging را به Online Boosting ترجیح دهم؟

هنگامی که جریان حاوی نویز برچسب قابل توجهی است، Online Bagging مقاوم‌تر است زیرا تأثیر نمونه‌های دشوار (احتمالاً با برچسب اشتباه) را مانند بوستینگ تشدید نمی‌کند. Online Boosting زمانی ترجیح داده می‌شود که جریان نسبتاً تمیز باشد و شما به حداکثر دقت نیاز دارید.

آیا می‌توانم یک مدل جریانی را بدون مجموعه آزمون جداگانه ارزیابی کنم؟

بله. از ارزیابی پیش‌گویانه (آزمون-سپس-آموزش) استفاده کنید: هر نمونه ورودی را قبل از به‌روزرسانی مدل پیش‌بینی کنید و این پیش‌بینی‌ها را در یک دقت یا F1 در حال اجرا جمع‌آوری کنید. این امر یک تخمین عملکرد بدون بایاس و بدون نیاز به داده‌های نگه‌داشته شده ارائه می‌دهد.

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

منابع

  1. Oza, N. C., & Russell, S. (2001). Online Bagging and Boosting. In Artificial Intelligence and Statistics 2001 (pp. 105–112). Morgan Kaufmann.

    باز کردن مرجع انتشار
    کپی شد.
  2. Online machine learning. Wikipedia.

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