گرادیان تقویتی

گرادیان تقویتی یا گرادیان بوستینگ (به انگلیسی: Gradient boosting) یک روش یادگیری ماشین برای مسائل رگرسیون و طبقه‌بندی است. مدل گرادیان تقویتی ترکیبی خطی از یک سری مدل‌های ضعیف است که به صورت تناوبی برای ایجاد یک مدل نهائیِ قوی ساخته شده‌است.[۱]

مقدمهویرایش

مانند دیگر روش‌های تقویتی (بوستینگ)، گرادیان تقویتی (گرادیان بوستینگ) ترکیبی خطی از یک سری از مدل‌های ضعیف برای ایجاد یک مدل قوی و کارآمد است.[۲] ساده‌ترین مثال برای توضیح گرادیان تقویتی، مثال کمترین مربعات در مسئله رگرسیون است که در آن هدف، یادگیری یک مدل به اسم   برای کمینه کردن   یا میانگین مربعات خطا است. در اینجا  ،   تعداد داده‌های ماست و   داده  ام است.[۲]

برای پیدا کردن   به صورت مرحله‌ای عمل می‌کنیم. در مرحله   به مدل   که تا به حال ساخته‌ایم یک مدل دیگر اضافه می‌کنیم به اسم   و مدل   را می‌سازیم،[۲] به عبارت دیگر  . مدل   را به گونه‌ای انتخاب می‌کنیم که بتواند تفاضل   با پیش‌بینی مدلِ مرحله قبلی را پیش‌بینی کند یعنی   را، در اینجا پیش‌بینی مرحله قبلی   است. به عبارت دیگر هدف پیش‌بینی باقیمانده‌هاست، یعنی  . باقیمانده‌ها را از یک منظر دیگر نیز می‌توان دید، آن‌ها در واقع منفی گرادیان مربع خطا هستند، یعنی منفی گرادیان تابع  .

الگوریتمویرایش

فرض کنید داده‌هایکه مدل برای یادگیری از آن‌ها استفاده می‌کند   باشد و هدف از یادگیری، کمینه کردن یک تابع ضرر به اسم   باشد. یعنی  

در مدل گرادیان تقویتی این کار به صورت متناوب انجام می‌شود[۱][۳] و مدل نهایی برابر خواهد بود با  .

در اینجا  ‌ها مدل‌هایی هستند که از یک گروه از مدل‌های به اسم   انتخاب می‌شوند، به عنوان مثال   می‌تواند مجموعه درخت‌های تصمیم‌گیری با عمق ۱۰ یا کمتر باشد.[۱]

اولین مدل یک عدد ثابت است به اسم   که به صورت ذیل انتخاب می‌شود:  

بقیه مدل‌ها به این صورت ساخته و فراگرفته می‌شوند: 

برای انجام این مرحله از گرادیان تابع ضرر به این شکل استفاده می‌کنیم:

 

 

به عبارت دیگر ما بدنبال مدلسازی منفی گرادیان تابع ضرر در هر مرحله هستیم یعنی یک مدل به اسم   از   که بتواند با داده پایین تابع ضرر را کمینه کند:[۳]

 

الگوریتم کلی را می‌توان به شکل پایین خلاصه کرد:[۱][۳]

  •  
  • برای   از   تا  :
    • برای   از   تا  :
      •  
    • برای داده‌های  یک مدل به اسم   از   انتخاب کن که تابع ضرر را به حداقل برساند، به عبارت دیگر  
    •  
    •  
  • مدل نهایی  است.

درختِ گرادیانِ تقویتیویرایش

در این مدل   یا مجوعه مدل‌های ما درخت‌های تصمیم‌گیری هستند. در مرحله  ، مدل فراگرفته شده یک درخت است به اسم   که توانسته منفی گرادیانها را مدلسازی کند. این درخت اگر   برگ داشته باشد، فضای برداری   را به  زیرفضای تجزیه می‌کند، این زیرفضاها با هم اشتراکی ندارند و اجتماعشان کل   را تشکیل می‌دهد. این زیرفضاها را   می‌نامیم.   برای هر کدام از این زیرفضاها یک پیش‌بینی جداگانه دارد به اسم  .   یا میانگین داده‌های خروجی، اگر مسئله رگرسیون باشد، یا مُدِ دسته (دسته‌ای که از همه بیشتر اتفاق افتاده باشد:[۴] 

  در ضریبی به اسم   ضرب می‌شود که تابع ضرر را کمینه کند، به عبارت دیگر   و مدل در این مرحله به این شکل به‌روز می‌شود:  

به پیشنهاد فریدمن به جای اینکه در هر مرحله یک ضریب کلی به اسم   فراگرفته شود، بهتر است   ضریب به تعداد تمام زیرفضاهای ایجاد شده توسط   فراگرفته شود و الگوریتم به این شکل تغییر کند):[۳]

 

مشخصات درختویرایش

اگر   را اندازه تعداد برگهای درخت یا همان تعداد زیرفضاهای   بگیریم معمولاً   مدل خوبی ایجاد می‌کند.[۳]

جستارهای وابستهویرایش

منابعویرایش

  1. ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF).
  2. ۲٫۰ ۲٫۱ ۲٫۲ Hastie, Trevor (2009). The Elements of Statistical Learning - Data Mining, Inference, and Prediction, Second Edition (به English). New York: Springer. ISBN 978-0-387-84857-0.
  3. ۳٫۰ ۳٫۱ ۳٫۲ ۳٫۳ ۳٫۴ Hastie, T.; Tibshirani, R.; Friedman, J. H. (2009). "10. Boosting and Additive Trees". The Elements of Statistical Learning (2nd ed.). New York: Springer. pp. 337&ndash, 384. ISBN 0-387-84857-6. Archived from the original on 2009-11-10.
  4. Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient   for the region   is equal to just the value of output variable, averaged over all training instances in  .