سؤال مصاحبه

بگینگ برای درخت‌های عمیق یا بوستینگ برای استامپ‌ها

Bag the deep trees or boost the stumps

  • سطح ۳: ارشد
  • بده‌بستان
  • ۱۲ دقیقه

یک مجموعه‌داده‌ی جدولی دارید و دو یادگیرنده‌ی پایه‌ی کاندید: درخت‌های تصمیم (decision trees) عمیق که تقریباً داده‌های آموزش را بی‌نقص برازش می‌کنند، و استامپ‌های تصمیم (decision stumps) که عملکردشان به‌زحمت از یک پیش‌بینی ثابت بهتر است. برای هر کدام فقط می‌توانید از یک روش آنسامبل (ensemble methods) استفاده کنید. کدام‌یک را به بگینگ (bagging) می‌سپارید و کدام‌یک را به بوستینگ (boosting)، و چرا؟

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

درخت‌های عمیق را بگینگ کنید و استامپ‌ها را بوستینگ. درخت‌های عمیق، بایاس (bias) کم و واریانس (variance) زیادی دارند؛ میانگین‌گیری از تعداد زیادی از آن‌ها که روی نمونه‌های بوت‌استرپ (bootstrap) آموزش دیده‌اند، بدون افزایش بایاس، واریانس را خنثی می‌کند. در مقابل، استامپ‌ها بایاس زیاد و واریانس کمی دارند؛ بوستینگ آن‌ها را به‌صورت متوالی می‌سازد تا هر مدل جدید خطاهای آنسامبل تا آن مرحله را اصلاح کند و بایاس کاهش یابد.

پاسخ کامل

تطبیق روش با مؤلفه‌ی خطا

خطای مورد انتظار به سه مؤلفه تجزیه می‌شود: مجذور بایاس، واریانس و نویز تقلیل‌ناپذیر. این دو روش به مؤلفه‌های متفاوتی حمله می‌کنند.

روش کاهش می‌دهد بایاس واریانس مراقب چه چیزی باشید
بگینگ، جنگل تصادفی واریانس بدون تغییر کاهش می‌یابد کاری برای بایاس انجام نمی‌دهد
بوستینگ بایاس کاهش می‌یابد می‌تواند افزایش یابد با دورهای بیش از حد دچار بیش‌برازش می‌شود

چرا بگینگ برای درخت‌های عمیق مناسب است

هر درخت روی یک نمونه‌ی بوت‌استرپ آموزش می‌بیند؛ یعنی نمونه‌گیری با جایگذاری هم‌اندازه با کل داده‌ها، که حدود 63.2 درصد از ردیف‌های یکتا را در بر می‌گیرد. بقیه، یعنی حدود 36.8 درصد، خارج از کیسه (out-of-bag) می‌مانند و یک مجموعه‌ی اعتبارسنجی رایگان در اختیارتان می‌گذارند. میانگینِ N پیش‌بینی مستقل با واریانس سیگما به توان 2، واریانسی برابر با سیگما به توان 2 تقسیم بر N دارد. درخت‌ها کاملاً مستقل نیستند، چون داده‌های مشابهی را می‌بینند؛ بنابراین بهبود حاصل از این مقدار کمتر است. جنگل تصادفی (random forest) برای اینکه درخت‌ها اختلاف بیشتری با هم پیدا کنند، در هر انشعاب (split) یک زیرمجموعه‌ی تصادفی از ویژگی‌ها را در نظر می‌گیرد (جذر تعداد کل ویژگی‌ها برای مسائل دسته‌بندی). افزودن درخت‌ها واریانس را کم می‌کند و هرگز بایاس اضافه نمی‌کند؛ به همین دلیل، دقت روی داده‌های آزمون به حالت یکنواخت (plateau) می‌رسد و افت نمی‌کند.

چرا بوستینگ برای استامپ‌ها مناسب است

بوستینگ یادگیرنده‌ها را به‌صورت متوالی آموزش می‌دهد. الگوریتم AdaBoost وزن ردیف‌هایی را که آنسامبل در آن‌ها اشتباه کرده بالا می‌برد تا استامپ بعدی روی همان‌ها تمرکز کند. گرادیان بوستینگ (gradient boosting) هر درخت جدید را روی منفیِ گرادیان (gradient) تابع زیان (loss) برازش می‌کند؛ که در مورد خطای مجذور، همان باقی‌مانده (residual) است. هر دور مقداری از خطای سیستماتیک، یعنی همان بایاس، را برطرف می‌کند. نرخ یادگیری (learning rate) سهم هر درخت را مقیاس‌بندی می‌کند؛ در این درس دامنه‌ی 0.01 تا 0.3 مطرح شده است، و مقادیر کوچک‌تر به درخت‌های بیشتری نیاز دارند اما تعمیم‌پذیری بهتری به همراه می‌آورند. از آنجا که دورهای پایانی سراغ سخت‌ترین ردیف‌ها می‌روند، بوستینگ ممکن است نویزها را هم برازش کند؛ بنابراین، به توقف زودهنگام (early stopping) بر اساس تابع زیان اعتبارسنجی نیاز دارد.

چرا برعکس این جواب نمی‌دهد

بوستینگ درخت‌های عمیق، بایاسِ باقی‌مانده‌ی ناچیزی برای حذف دارد و یادگیرنده‌هایی با واریانس بالا را روی هم می‌چیند؛ در نتیجه خیلی سریع دچار بیش‌برازش می‌شود. بگینگ استامپ‌ها نیز میانگین‌گیری از مدل‌های متعددی است که همگی یک الگوی مشترک را جا می‌اندازند؛ بنابراین میانگین آن‌ها هم آن الگو را جا می‌اندازد. در هر دو حالت، تنوع شرط لازم است: در درس دیدیم که رأی‌گیری اکثریتیِ 21 دسته‌بند مستقل با دقت 60 درصد به حدود 74 درصد دقت می‌رسد، و 101 مورد از آن‌ها به حدود 84 درصد دقت می‌رسند؛ و این دقیقاً به این دلیل رخ می‌دهد که خطاهایشان با هم متفاوت است.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 3: چرا بگینگ درخت‌های عمیق بایاس را اصلاح نمی‌کند؟ پاسخ مورد انتظار: میانگینِ مدل‌های زیادی که همگی یک الگو را جا می‌اندازند باز هم آن الگو را از دست می‌دهد؛ میانگین‌گیری فقط اختلاف نظر میان آن‌ها را حذف می‌کند.
  • سطح 3: نرخ یادگیری در گرادیان بوستینگ چه نقشی دارد؟ پاسخ مورد انتظار: سهم هر درخت را مقیاس‌بندی می‌کند؛ نرخ کوچک‌تر نیازمند درخت‌های بیشتری است و مدل بهتر تعمیم پیدا می‌کند.
  • سطح 4: در بوستینگ، خطای آموزش مدام افت می‌کند اما خطای اعتبارسنجی بالا می‌رود. چه اتفاقی افتاده و چه باید کرد؟ پاسخ مورد انتظار: دورهای پایانی داده‌های نویزی یا دارای برچسب اشتباه را برازش می‌کنند؛ باید با توقف زودهنگام روی تابع زیان اعتبارسنجی فرآیند را متوقف کرد، یا نرخ یادگیری و عمق درخت‌ها را کاهش داد.
  • سطح 4: چرا با اضافه‌شدن درخت‌ها، دقت آزمون جنگل تصادفی به حالت یکنواخت می‌رسد اما افت نمی‌کند؟ پاسخ مورد انتظار: هر درخت واریانس را کاهش می‌دهد و هیچ درختی بایاس اضافه نمی‌کند؛ بنابراین بر خلاف دورهای متوالی بوستینگ، درخت‌های بیشتر نمی‌توانند باعث بیش‌برازش شوند.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «درخت‌های عمیق را بوست کنید، چون بوستینگ روش قدرتمندتری است.» یادگیرنده‌ای با بایاس کم و واریانس زیاد، بایاس ناچیزی برای حذف دارد و بوستینگ فقط واریانس آن را تشدید می‌کند.
  • «استامپ‌ها را بگینگ کنید تا قوی شوند.» میانگین‌گیری از استامپ‌هایی که همگی دچار کم‌برازشی هستند، باز هم نتیجه‌ای دچار کم‌برازشی تحویل می‌دهد؛ بگینگ دست به بایاس نمی‌زند.
  • «هر آنسامبلی با تعداد مدل کافی، مدل تکی را شکست می‌دهد.» سود حاصل از آنسامبل نیازمند خطاهای متنوع است؛ مدل‌هایی که خطاهای یکسانی مرتکب می‌شوند، نمی‌توانند همدیگر را جبران کنند.

کجای دوره آموزش داده می‌شود

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