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

کیسه‌بندی آنلاین (Online Bagging)

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

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

اندازه قلم

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

کیسه‌بندی آنلاین (Online Bagging) یک روش گروهی جریانی است که در سال ۲۰۰۱ توسط اوزا و راسل معرفی شد و چارچوب کلاسیک تجمیع بوت‌استرپ (Bagging) را برای محیط یادگیری آنلاین تطبیق می‌دهد. به جای نمونه‌برداری مجدد از یک مجموعه داده ثابت، هر نمونه ورودی به تعداد دفعاتی که از توزیع پواسون (Poisson(1)) نمونه‌برداری شده است، به هر یادگیرنده پایه داده می‌شود و به طور دقیق نمونه‌برداری بوت‌استرپ را با تکامل جریان تقریب می‌زند. نتیجه یک گروهی قوی و به‌روزرسانی شونده افزایشی است که می‌تواند رانش مفهوم (concept drift) و ورود مداوم داده‌ها را بدون ذخیره کل مجموعه داده مدیریت کند.

شهود پشت روش

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

تاریخ

کیسه‌بندی آنلاین توسط نیتش اوزا و استوارت راسل در AISTATS 2001 به عنوان یک توسعه نظری و عملی از الگوریتم کیسه‌بندی سال ۱۹۹۶ برمن به محیط آنلاین معرفی شد. بینش کلیدی - جایگزینی نمونه‌برداری مجدد بوت‌استرپ با وزن‌دهی پواسون (Poisson(1)) در هر نمونه - تقریب را از نظر ریاضی دقیق کرد. این الگوریتم به یک الگوریتم پایه‌ای در ادبیات یادگیری ماشین جریانی تبدیل شد و گروهی پایه در پلتفرم‌هایی مانند MOA (Massive Online Analysis) است که از سال ۲۰۱۰ اکثر ارزیابی‌های تجربی طبقه‌بندهای جریانی را هدایت کرده است.

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

هنگامی که داده‌ها به صورت یک جریان پیوسته وارد می‌شوند و ذخیره کل مجموعه داده غیرممکن یا ممنوع است (به عنوان مثال، گزارش‌های حسگر، جریان‌های کلیک، داده‌های تیک مالی، نظارت در زمان واقعی)، از کیسه‌بندی آنلاین استفاده کنید. این روش زمانی مناسب است که به طبقه‌بندی یا رگرسیونی نیاز دارید که با هر مشاهده جدید به‌روزرسانی شود، رانش مفهوم خفیف را تحمل کند و از نظر حافظه کارآمد باقی بماند. از کیسه‌بندی آنلاین به عنوان جایگزین مستقیم برای جنگل تصادفی دسته‌ای (Random Forest) در یک مجموعه داده ثابت، کوچک تا متوسط استفاده نکنید - در آنجا، گروه‌های دسته‌ای با اعتبارسنجی متقابل (cross-validation) عملکرد بهتری خواهند داشت. همچنین زمانی که جریان داده رانش شدید ناگهانی را بدون افزودن یک مکانیزم تشخیص رانش صریح نشان می‌دهد، از آن اجتناب کنید.

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

  • در مجموعه داده‌های ایستا، روش‌های دسته‌ای مانند جنگل تصادفی یا XGBoost به طور مداوم از کیسه‌بندی آنلاین بهتر عمل می‌کنند زیرا می‌توانند از اعتبارسنجی متقابل کامل و تقسیم‌های بهینه استفاده کنند.
  • کیسه‌بندی آنلاین پایه، انعطاف‌پذیری محدودی در برابر رانش مفهوم شدید ارائه می‌دهد؛ باید به صورت خارجی، آشکارسازهای رانش اختصاصی (مانند ADWIN) اضافه شوند.
  • وزن‌دهی پواسون واریانس اضافی در هر نمونه ایجاد می‌کند که می‌تواند همگرایی را در جریان‌های کوتاه کند کند.
  • قابلیت تفسیر پایین است: بررسی گروهی از درختان رشد یافته افزایشی نسبت به یک درخت تصمیم منفرد دشوارتر است.

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

نقاط قوت

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

کاربردها

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

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

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

1

برای هر نمونه ورودی، یک وزن k به طور مستقل از توزیع پواسون (Poisson(1)) برای هر یادگیرنده پایه نمونه‌برداری می‌شود. وزن ۰ به این معنی است که یادگیرنده این نمونه را کاملاً نادیده می‌گیرد؛ وزن ۲ به این معنی است که دو بار از نمونه یاد می‌گیرد. این وزن‌دهی تصادفی، معادل آنلاین نمونه‌برداری مجدد بوت‌استرپ است و هسته ریاضی الگوریتم محسوب می‌شود.

فرمول
k \sim \text{Poisson}(1)
2

هر یادگیرنده پایه - که معمولاً یک درخت تصمیم افزایشی مانند درخت هوفینگ (Hoeffding Tree) است - نمونه فعلی را با وزن اختصاص داده شده دریافت کرده و مدل داخلی خود را بلافاصله به‌روزرسانی می‌کند. هیچ نمونه‌ای پس از پردازش ذخیره نمی‌شود. این ویژگی تک‌گذر، حافظه را محدود نگه می‌دارد و به گروهی اجازه می‌دهد تا به جریان‌های دلخواه طولانی مقیاس‌پذیر شود.

3

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

فرمول
\hat{y} = \text{mode/mean of } M \text{ base learners}

دام‌های رایج

  • ارزیابی کیسه‌بندی آنلاین با یک مجموعه آزمون نگه‌داشته شده که قبل از شروع آموزش ایجاد شده است - به جای آن از ارزیابی پیش‌گویانه (test-then-train) استفاده کنید، که در یادگیری ماشین جریانی استاندارد است.
  • فرض کردن اینکه تعداد پیش‌فرض یادگیرنده‌های پایه (اغلب ۱۰) کافی است؛ معمولاً برای پیش‌بینی‌های پایدار به گروه‌هایی با حداقل ۵۰ تا ۱۰۰ یادگیرنده نیاز است.
  • نادیده گرفتن رانش مفهوم: استقرار کیسه‌بندی آنلاین بر روی یک جریان در حال رانش بدون تشخیص رانش منجر به تخریب خاموش دقت می‌شود.
  • مقایسه دقت بر روی یک معیار ایستا با روش‌های دسته‌ای و نتیجه‌گیری اینکه کیسه‌بندی آنلاین ضعیف‌تر است - مقایسه صحیح، دقت به ازای هر نمونه دیده شده در یک معیار جریانی است.
  • استفاده از یادگیرنده‌های پایه‌ای که واقعاً افزایشی نیستند (مانند درختان دسته‌ای بازآموزی شده)، که مزایای حافظه و سرعت چارچوب آنلاین را نفی می‌کند.

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

توزیع پواسون با میانگین ۱، تعداد دفعاتی که یک مشاهده در یک نمونه بوت‌استرپ به اندازه n ظاهر می‌شود را هنگامی که n به سمت بی‌نهایت میل می‌کند، تقریب می‌زند. استفاده از پواسون (۱) در هر نمونه برای هر یادگیرنده، این رفتار حدی را دقیقاً تکرار می‌کند و تقریب آنلاین را از نظر تئوری صحیح می‌سازد.

کیسه‌بندی آنلاین چگونه با جنگل تصادفی تطبیقی (Adaptive Random Forest) متفاوت است؟

جنگل تصادفی تطبیقی (Gomes et al., 2017) کیسه‌بندی آنلاین را با افزودن نمونه‌برداری تصادفی ویژگی در هر تقسیم (مانند جنگل تصادفی دسته‌ای) و ادغام آشکارسازهای رانش در هر درخت که یادگیرنده‌های منفرد را هنگام تشخیص رانش مفهوم بازنشانی می‌کنند، گسترش می‌دهد. کیسه‌بندی آنلاین پایه ساده‌تر است؛ جنگل تصادفی تطبیقی، گروهی جریانی پیشرفته مبتنی بر آن است.

از کدام یادگیرنده پایه باید استفاده کنم؟

رایج‌ترین انتخاب، درخت هوفینگ (که VFDT نیز نامیده می‌شود) است که درخت تصمیم افزایشی متعارف است. این درخت از کران‌های هوفینگ برای تصمیم‌گیری در مورد اینکه چه زمانی داده‌های کافی در یک گره دیده شده است تا تقسیم شود، استفاده می‌کند و درخت را بدون ذخیره نمونه‌های گذشته قابل به‌روزرسانی نگه می‌دارد.

به چند یادگیرنده پایه نیاز دارم؟

معیارهای تجربی در چارچوب MOA، ۵۰ تا ۱۰۰ یادگیرنده پایه را برای عملکرد پایدار گروهی در اکثر وظایف جریانی پیشنهاد می‌کنند. تعداد کمتر یادگیرنده‌ها هزینه محاسباتی را کاهش می‌دهد اما واریانس پیش‌بینی را افزایش می‌دهد، به خصوص در اوایل جریان.

چگونه باید یک طبقه‌بند کیسه‌بندی آنلاین را ارزیابی کنم؟

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

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

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

منابع

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    باز کردن مرجع انتشار
    کپی شد.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

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