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

بگینگ (تجمیع بوت‌استرپ)

معرفی‌شده توسط
Breiman, L.
سال
1996
نوع
Ensemble meta-algorithm (variance reduction via bootstrap aggregation)

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

اندازه قلم

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

بگینگ، مخفف تجمیع بوت‌استرپ، یک فراالگوریتم تجمیعی است که در سال ۱۹۹۶ توسط لئو بریمَن معرفی شد و چندین نسخه از یک یادگیرنده پایه را بر روی نمونه‌های بوت‌استرپ که به طور مستقل از داده‌های آموزشی کشیده شده‌اند، آموزش می‌دهد و پیش‌بینی‌های آن‌ها را ترکیب می‌کند — با میانگین‌گیری برای رگرسیون یا رأی اکثریت برای طبقه‌بندی — تا یک پیش‌بینی‌کننده نهایی با واریانس به طور قابل توجهی کمتر از هر یادگیرنده پایه واحد تولید کند.

شهود پشت روش

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

تاریخ

لئو بریمَن در سال ۱۹۹۶ مقاله‌ای با عنوان «پیش‌بینی‌کننده‌های بگینگ در یادگیری ماشین» منتشر کرد که با مشاهده اینکه یادگیرنده‌های ناپایدار — آن‌هایی که خروجی آن‌ها تحت اغتشاشات کوچک داده به طور قابل توجهی تغییر می‌کند — می‌توانند با میانگین‌گیری بر روی تکرارهای بوت‌استرپ مجموعه آموزشی پایدار شوند، انگیزه گرفت. توجیه نظری بر تجزیه بایاس-واریانس استوار است: میانگین‌گیری واریانس را کاهش می‌دهد در حالی که بایاس را بدون تغییر باقی می‌گذارد. بریمَن بهبودهای دقت مداومی را نسبت به درختان تصمیم واحد در مجموعه‌ای از معیارهای طبقه‌بندی و رگرسیون نشان داد. بگینگ به سرعت به یک تکنیک تجمیعی بنیادی تبدیل شد و مستقیماً الهام‌بخش جنگل تصادفی (بریمَن، ۲۰۰۱) شد که زیرنمونه‌گیری تصادفی ویژگی‌ها را در هر شکاف برای کاهش بیشتر همبستگی درختان و دستیابی به کاهش واریانس بیشتر اضافه می‌کند. امروزه، بگینگ به عنوان ستون فقرات مفهومی برای طیف گسترده‌ای از روش‌های تجمیعی عمل می‌کند و یک موضوع استاندارد در برنامه‌های درسی یادگیری ماشین در سطح تحصیلات تکمیلی است.

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

بگینگ زمانی مناسب است که الگوریتم یادگیری پایه دارای واریانس بالا باشد — یعنی به اغتشاشات کوچک در داده‌های آموزشی حساس باشد — و کاهش این واریانس منبع اصلی خطا باشد. درختان تصمیم کاملاً رشد کرده و بدون هرس، مثال متعارف هستند. بگینگ برای طبقه‌بندی و رگرسیون بر روی داده‌های جدولی مناسب است، هیچ فرضی در مورد توزیع داده‌ها ندارد و انواع ویژگی‌های ترکیبی را مدیریت می‌کند. زمانی بیشترین سود را دارد که مجموعه داده به اندازه کافی بزرگ باشد تا از B نمونه بوت‌استرپ مستقل با کیفیت پشتیبانی کند (حداقل حدود ۳۰ مشاهده یک حد پایین عملی است، اگرچه صدها مورد ترجیح داده می‌شوند). بگینگ زمانی مفید نیست که یادگیرنده پایه از قبل پایدار باشد (مانند رگرسیون خطی در مسائل به خوبی مشخص شده) یا زمانی که منبع خطای غالب، بایاس است نه واریانس — در چنین مواردی روش‌های بوستینگ مناسب‌تر هستند.

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

  • بایاس را کاهش نمی‌دهد: اگر یادگیرنده پایه کم‌برازش باشد، بگینگ نمی‌تواند آن را اصلاح کند.
  • پیش‌بینی‌های تجمیعی دشوارتر از یک مدل واحد قابل تفسیر هستند؛ هیچ آنالوگی از ساختار بصری یک درخت تصمیم واحد وجود ندارد.
  • حافظه و ذخیره‌سازی به صورت خطی با B مقیاس می‌شوند: نگهداری صدها مدل بزرگ در حافظه می‌تواند مانع باشد.
  • افزایش‌ها به سرعت با رشد B کاهش می‌یابند؛ عملکرد معمولاً قبل از B = ۵۰۰ تثبیت می‌شود.
  • بر روی یادگیرنده‌های پایه پایدار (مانند رگرسیون خطی با مشخصات صحیح) بگینگ بهبود ناچیزی ایجاد می‌کند.

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

نقاط قوت

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

کاربردها

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

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

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

1

تعداد B نمونه بوت‌استرپ مستقل از مجموعه داده آموزشی اصلی با اندازه n کشیده می‌شوند. هر نمونه با کشیدن n مشاهده با جایگزینی از داده‌های اصلی تولید می‌شود، بنابراین به طور متوسط هر نمونه حاوی حدود ۶۳.۲٪ از نمونه‌های آموزشی منحصربه‌فرد است؛ باقی‌مانده ~۳۶.۸٪ باقی می‌مانند و مجموعه خارج از کیسه (OOB) را برای آن تکرار تشکیل می‌دهند.

فرمول
\mathcal{D}_b = \{(\mathbf{x}_i^*, y_i^*)\}_{i=1}^{n}, \quad (\mathbf{x}_i^*, y_i^*) \overset{\text{i.i.d.}}{\sim} \hat{F}_n, \quad b = 1, \dots, B
2

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

فرمول
\hat{f}_b = \mathcal{A}(\mathcal{D}_b)
3

برای وظایف رگرسیون، خروجی‌های B مدل میانگین‌گیری می‌شوند. این مرحله میانگین‌گیری مکانیسم اصلی برای کاهش واریانس است: تحت مفروضات استقلال، واریانس میانگین B مدل توزیع‌شده یکسان، ۱/B واریانس یک مدل واحد است، و حتی تحت همبستگی مثبت، کاهش قابل توجه است.

فرمول
\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(\mathbf{x})
4

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

فرمول
\hat{y}(\mathbf{x}) = \underset{k}{\operatorname{arg\,max}} \sum_{b=1}^{B} \mathbf{1}\!\left[\hat{f}_b(\mathbf{x}) = k\right]
5

از آنجایی که هر یادگیرنده پایه بر روی تقریباً ۶۳.۲٪ از داده‌ها آموزش می‌بیند، مشاهدات باقی‌مانده می‌توانند به عنوان یک مجموعه آزمون صادقانه نگه‌داشته شده برای آن یادگیرنده عمل کنند. میانگین‌گیری این پیش‌بینی‌های OOB در سراسر تمام یادگیرندگانی که هر مشاهده را ندیده‌اند، تخمین تقریباً بدون اریب از خطای تعمیم را بدون نیاز به یک بخش اعتبارسنجی جداگانه یا اعتبارسنجی متقابل ارائه می‌دهد.

فرمول
\widehat{\text{Err}}_{\text{OOB}} = \frac{1}{n} \sum_{i=1}^{n} L\!\left(y_i,\; \frac{1}{|\mathcal{B}_i^c|} \sum_{b \in \mathcal{B}_i^c} \hat{f}_b(\mathbf{x}_i)\right)

دام‌های رایج

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

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

چند نمونه بوت‌استرپ B باید استفاده کنم؟

بریمَن (۱۹۹۶) دریافت که عملکرد نسبتاً سریع تثبیت می‌شود؛ B = ۵۰ تا ۱۰۰ اغلب برای درختان تصمیم کافی است. افزایش B فراتر از چند صد، بازده کاهشی دارد. خطای OOB را با رشد B نظارت کنید و زمانی که تثبیت شد، متوقف شوید.

تفاوت بین بگینگ و جنگل تصادفی چیست؟

جنگل تصادفی بگینگ را با افزودن زیرنمونه‌گیری تصادفی ویژگی در هر شکاف از هر درخت، گسترش می‌دهد. این تصادفی‌سازی اضافی، یادگیرنده‌های پایه را بیشتر از همبسته می‌کند و واریانس را فراتر از آنچه بگینگ به تنهایی به دست می‌آورد، کاهش می‌دهد. بنابراین، بگینگ با درختان کاملاً رشد کرده، یک مورد خاص از جنگل تصادفی است که در آن همه ویژگی‌ها در هر شکاف در نظر گرفته می‌شوند.

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

بله. هر یادگیرنده‌ای که ناپایدار است — پیش‌بینی‌های آن با تغییر جزئی داده‌های آموزشی به طور قابل توجهی تغییر می‌کند — می‌تواند از بگینگ سود ببرد. شبکه‌های عصبی، k-نزدیک‌ترین همسایگان، و درختان رگرسیون بدون هرس همگی واجد شرایط هستند. یادگیرنده‌های پایدار مانند رگرسیون خطی با یک مدل به خوبی مشخص شده، سود کمی می‌برند زیرا واریانس کمی برای کاهش وجود دارد.

آیا خطای OOB جایگزین قابل اعتمادی برای اعتبارسنجی متقابل است؟

برای مجموعه داده‌های متوسط تا بزرگ، خطای OOB یک تخمین تقریباً بدون اریب از خطای تعمیم است و از نظر محاسباتی رایگان است زیرا هیچ برازش مدل اضافی لازم نیست. در مجموعه داده‌های بسیار کوچک (n کمتر از حدود ۵۰)، تخمین‌های OOB می‌توانند خوش‌بینانه باشند و اعتبارسنجی متقابل ترجیح داده می‌شود.

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

منابع

  1. Breiman, L. (1996). Bagging Predictors. Machine Learning, 24(2), 123–140.

    باز کردن مرجع DOI
    کپی شد.
  2. Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 8.7). Springer.

    شابک: 978-0-387-84857-0
    کپی شد.
  3. James, G., Witten, D., Hastie, T. & Tibshirani, R. (2013). An Introduction to Statistical Learning (Ch. 8.2). Springer.

    شابک: 978-1-4614-7138-7
    کپی شد.