تقویت گرادیان
تقویت گرادیان یا گرادیان بوستینگ یک روش یادگیری ماشین برای مسائل رگرسیون و طبقه‌بندی است. مدل تقویت گرادیان ترکیبی خطی از یک سری مدل‌های ضعیف است که به صورت تناوبی برای ایجاد یک مدل نهائیِ قوی ساخته شده‌است. این روش به خانواده الگوریتم‌های یادگیری گروهی تعلق دارد و عملکرد آن همواره از الگوریتم‌های اساسی یا ضعیف (مثلا درخت تصمیم) یا روش‌های براساس کیسه‌گذاری (مانند جنگل تصادفی) بهتر است. اما صحت این گزاره تا حدی از مشخصات داده‌های ورودی تأثیر می‌پذیرد.
مانند دیگر روش‌های تقویتی (بوستینگ)، تقویت گرادیان (گرادیان بوستینگ) ترکیبی خطی از یک سری از مدل‌های ضعیف برای ایجاد یک مدل قوی و کارآمد است. ساده‌ترین مثال برای توضیح تقویت گرادیان، مثال کمترین مربعات در مسئله رگرسیون است که در آن هدف، یادگیری یک مدل به اسم formula_1 برای کمینه کردن formula_2 یا میانگین مربعات خطا است. در اینجا formula_3، formula_4 تعداد داده‌های ماست و formula_5 داده formula_6ام است.
برای پیدا کردن formula_1 به صورت مرحله‌ای عمل می‌کنیم. در مرحله formula_8 به مدل formula_9 که تا به حال ساخته‌ایم یک مدل دیگر اضافه می‌کنیم به اسم formula_10 و مدل formula_11 را می‌سازیم، به عبارت دیگر formula_12. مدل formula_10 را به گونه‌ای انتخاب می‌کنیم که بتواند تفاضل formula_14 با پیش‌بینی مدلِ مرحله قبلی را پیش‌بینی کند یعنی formula_15 را، در اینجا پیش‌بینی مرحله قبلی formula_16 است. به عبارت دیگر هدف پیش‌بینی باقیمانده‌هاست، یعنی formula_15. باقیمانده‌ها را از یک منظر دیگر نیز می‌توان دید، آن‌ها در واقع منفی گرادیان مربع خطا هستند، یعنی منفی گرادیان تابع formula_18.
فرض کنید داده‌هایکه مدل برای یادگیری از آن‌ها استفاده می‌کند formula_19 باشد و هدف از یادگیری، کمینه کردن یک تابع ضرر به اسم formula_20 باشد؛ یعنی formula_21
در مدل تقویت گرادیان این کار به صورت متناوب انجام می‌شود و مدل نهایی برابر خواهد بود با formula_22.
در اینجا formula_23‌ها مدل‌هایی هستند که از یک گروه از مدل‌های به اسم formula_24 انتخاب می‌شوند، به عنوان مثال formula_24 می‌تواند مجموعه درخت‌های تصمیم‌گیری با عمق ۱۰ یا کمتر باشد.
اولین مدل یک عدد ثابت است به اسم formula_26 که به صورت ذیل انتخاب می‌شود: formula_27
بقیه مدل‌ها به این صورت ساخته و فراگرفته می‌شوند:formula_28
برای انجام این مرحله از گرادیان تابع ضرر به این شکل استفاده می‌کنیم:
formula_29 formula_30
به عبارت دیگر ما بدنبال مدلسازی منفی گرادیان تابع ضرر در هر مرحله هستیم یعنی یک مدل به اسم formula_31 از formula_32 که بتواند با داده پایین تابع ضرر را کمینه کند:
formula_33
الگوریتم کلی را می‌توان به شکل پایین خلاصه کرد:
در این مدل formula_32 یا مجوعه مدل‌های ما درخت‌های تصمیم‌گیری هستند. در مرحله formula_8، مدل فراگرفته شده یک درخت است به اسم formula_51 که توانسته منفی گرادیانها را مدلسازی کند. این درخت اگر formula_52 برگ داشته باشد، فضای برداری formula_53 را به formula_52زیرفضای تجزیه می‌کند، این زیرفضاها با هم اشتراکی ندارند و اجتماعشان کل formula_53 را تشکیل می‌دهد. این زیرفضاها را formula_56 می‌نامیم. formula_51 برای هر کدام از این زیرفضاها یک پیش‌بینی جداگانه دارد به اسم formula_58. formula_58 یا میانگین داده‌های خروجی، اگر مسئله رگرسیون باشد، یا مُدِ دسته (دسته‌ای که از همه بیشتر اتفاق افتاده باشد:formula_60
formula_51 در ضریبی به اسم formula_62 ضرب می‌شود که تابع ضرر را کمینه کند، به عبارت دیگر formula_63 و مدل در این مرحله به این شکل به‌روز می‌شود: formula_64
به پیشنهاد فریدمن به جای اینکه در هر مرحله یک ضریب کلی به اسم formula_62 فراگرفته شود، بهتر است formula_52 ضریب به تعداد تمام زیرفضاهای ایجاد شده توسط formula_67 فراگرفته شود و الگوریتم به این شکل تغییر کند):
formula_68 اگر formula_69 را اندازه تعداد برگهای درخت یا همان تعداد زیرفضاهای formula_53 بگیریم معمولاً formula_71 مدل خوبی ایجاد می‌کند.
این الگوریتم می‌تواند، مانند درخت تصمیم یا جنگل تصادفی، برای رتبه‌بندی اهمیت متغیرها به کار رود. فرمول اهمیت متغیرها در الگوریتم تقویت گرادیان با همان درخت تصمیم یکی است، اما در این الگوریتم امتیاز تمام یادگیرنده‌های ضعیف (یعنی درخت‌های تصمیم) میانگین‌گیری می‌شود.