گرادیان بوستینگ چیست ؟

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

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

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

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

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

حال اگر تمایل به ادامه دادن درخت داشته باشیم که مانند روشهاي درخت تصمیم باشد بر روي خصوصیت تمایل به کلاه و بازيهاي ویدیویی درخت را ادامه میدهیم. به صورت زیر :

در درختی که حاصل شده است تصمیم نهایی بخشی بر اساس تمایل به پوشیدن کلاه و بخشی بر اساس تمایل به بازیهای ویدیویی گرفته می شود که خود نشان‌دهنده overfitting مدل (برازش بیش از حد مدل با داده‌های آزمایشی  که در محیط‌ های واقعی خطا را بالا می برد) می‌شود.

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

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

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

درخت دوم مقدار خطاهاي درخت اول را پیش‌بینی می‌کند و به مقدار باقی مانده خطا‌ها برای درخت دوم را ارایه می‌کند.براي مقادیري که در سمت راست مدل یادگیرنده دوم قرار گرفته اند مقدار۳٫۵۶۷- و براي مقادیري که در سمت چپ قرار گرفته اند مقدار۷٫۳۳۳ در نظر گرفته شده است که این مقدار مقدار میانگین همه داده در سمت چپ و راست است.در مدلCART بدین صورت انجام می‌شود که میانگین از تمامی داده در برگها گرفته شده و به عنوان مقدار آن در نهایت در نظر می‌گیرد. حال این مقدار را با مقداري که توسط درخت اول پیشگویی شده جمع میکنیم که به مقدار مجموع پیشگویی‌ها می‌رسیم و پس از آن مقدار به دست آمده را با مقدار واقعی مقایسه کرده و خطاي بدست آمده را در خطای نهایی قرار میدهیم به صورت زیر:

پیشنویس اول از گرادیان بوستینگ

با توجه به ایده‌هاي که در بالا مطرح شد مدل ساده‌ای از گرادیان بوستینگ مطرح شد و به صورت شبه کد زیر عنوان می‌شود :

در نهایت به معادله زیر برای مدل نهایی می‌رسیم

در جدول بالا برای مربع خطا ٣ مرحله از این الگوریتم به صورت کامل نشان داده شده است. با توجه به معادله نهایی یادگیرنده که در بالا ذکر شد مشخص است که در هر مرحله به مقدار واقعی نزدیک می‌شویم. با استفاده از دو مدل یادگیرنده ساده که در بالا ذکر شده است مقدار h0 و مقدار h1 محاسبه می‌شود.

امیدوارم که مفید واقع شده باشد.