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

**تقویت گرادیان** یا **گرادیان بوستینگ**  یک روش یادگیری ماشین برای مسائل رگرسیون و طبقه‌بندی است. مدل تقویت گرادیان ترکیبی خطی از یک سری مدل‌های ضعیف است که به صورت تناوبی برای ایجاد یک مدل نهائیِ قوی ساخته شده‌است. این روش به خانواده الگوریتم‌های یادگیری گروهی تعلق دارد و عملکرد آن همواره از الگوریتم‌های اساسی یا ضعیف (مثلا درخت تصمیم) یا روش‌های براساس کیسه‌گذاری (مانند جنگل تصادفی) بهتر است. اما صحت این گزاره تا حدی از مشخصات داده‌های ورودی تأثیر می‌پذیرد.

## مقدمه
مانند دیگر روش‌های تقویتی (بوستینگ)، تقویت گرادیان (گرادیان بوستینگ) ترکیبی خطی از یک سری از مدل‌های ضعیف برای ایجاد یک مدل قوی و کارآمد است. ساده‌ترین مثال برای توضیح تقویت گرادیان، مثال کمترین مربعات در مسئله رگرسیون است که در آن هدف، یادگیری یک مدل به اسم F برای کمینه کردن \frac{1}{n}\sum_i(\hat{y}_i - y_i)^2 یا میانگین مربعات خطا است. در اینجا \hat {y_i}=F(x_i) ، n  تعداد داده‌های ماست و (x_i, y_i)  داده i ام است.

برای پیدا کردن F به صورت مرحله‌ای عمل می‌کنیم. در مرحله m به مدل F_m که تا به حال ساخته‌ایم یک مدل دیگر اضافه می‌کنیم به اسم h و مدل F_{m+1} را می‌سازیم، به عبارت دیگر F_{m+1}(x) = F_m(x) + h(x). مدل h را به گونه‌ای انتخاب می‌کنیم که بتواند تفاضل y با پیش‌بینی مدلِ مرحله قبلی را پیش‌بینی کند یعنی 
y - F_m(x)
 را، در اینجا پیش‌بینی مرحله قبلی 
F_m(x)
 است. به عبارت دیگر هدف پیش‌بینی **باقیمانده‌ها**ست، یعنی 
y - F_m(x)
. باقیمانده‌ها را از یک منظر دیگر نیز می‌توان دید، آن‌ها در واقع منفی گرادیان مربع خطا هستند، یعنی منفی گرادیان تابع \frac{1}{2}\left(F(x)-y\right)^2.

## الگوریتم
فرض کنید داده‌هایی که مدل برای یادگیری از آن‌ها استفاده می‌کند \{ (x_1,y_1), \dots , (x_n,y_n) \}  باشد و هدف از یادگیری، کمینه کردن یک تابع ضرر به اسم L  باشد؛ یعنی \hat{F} = \underset{F}{\arg\min} \, \mathbb{E}_{x,y}[L(y, F(x))]

در مدل تقویت گرادیان این کار به صورت متناوب انجام می‌شود و مدل نهایی برابر خواهد بود با \hat{F}(x) = \sum_{i=1}^M \gamma_i h_i(x) + F_0.

در اینجا h_i‌ها مدل‌هایی هستند که از یک گروه از مدل‌های به اسم \mathcal{H}  انتخاب می‌شوند، به عنوان مثال \mathcal{H} می‌تواند مجموعه درخت‌های تصمیم‌گیری با عمق ۱۰ یا کمتر باشد.

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

F_0 = \underset{\gamma}{\arg\min} {\sum_{i=1}^n {L(y_i, \gamma)}}

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

F_m(x) = F_{m-1}(x) + \underset{h_m \in \mathcal{H}}{\operatorname{arg\,min}} \left[{\sum_{i=1}^n {L(y_i, F_{m-1}(x_i) + h_m(x_i))}}\right]

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

{\displaystyle F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}},

{\displaystyle \gamma _{m}={\underset {\gamma }{\arg \min}}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}}}


به عبارت دیگر ما بدنبال مدلسازی منفی گرادیان تابع ضرر در هر مرحله هستیم یعنی یک مدل به اسم h_m  از \mathcal{H}  که بتواند با داده پایین تابع ضرر را کمینه کند:

\left\{\left(x_1, -\nabla _{F_{m-1}}L(y_{1},F_{m-1}(x_{1}))\right), \cdots, \left(x_n, -\nabla _{F_{m-1}}L(y_{n},F_{m-1}(x_{n}))\right)\right\}

الگوریتم کلی را می‌توان به شکل پایین خلاصه کرد:
* F_0 = \underset{\gamma}{\arg\min} {\sum_{i=1}^n {L(y_i, \gamma)}}
* برای m از 1 تا M:
** برای i از 1 تا n:
*** r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)}
** برای داده‌های \{(x_i, r_{im})\}_{i=1}^n  یک مدل به اسم h_m  از \mathcal{H}   انتخاب کن که تابع ضرر را به حداقل برساند، به عبارت دیگر h_m = \underset{h \in \mathcal{H}}{\operatorname{arg\,min}} \, L\left(r_{im}, h(x_i)\right) 
** \gamma_m = \underset{\gamma}{\operatorname{arg\,min}} \sum_{i=1}^n L\left(y_i, F_{m-1}(x_i) + \gamma h_m(x_i)\right) 
** F_m(x) = F_{m-1}(x) + \gamma_m h_m(x) 
* مدل نهایی F_M است.

## درختِ تقویت گرادیان
در این مدل \mathcal{H}  یا مجوعه مدل‌های ما درخت‌های تصمیم‌گیری هستند. در مرحله m، مدل فراگرفته شده یک درخت است به اسم h_m(x) که توانسته منفی گرادیانها را مدلسازی کند. این درخت اگر J_{m} برگ داشته باشد، فضای برداری \mathcal{X} را به J_{m}زیرفضای تجزیه می‌کند، این زیرفضاها با هم اشتراکی ندارند و اجتماعشان کل \mathcal{X} را تشکیل می‌دهد. این زیرفضاها را R_{1m}, \ldots, R_{J_{m}m} می‌نامیم. h_m(x) برای هر کدام از این زیرفضاها یک پیش‌بینی جداگانه دارد به اسم b_{jm}. b_{jm} یا میانگین داده‌های خروجی، اگر مسئله رگرسیون باشد، یا مُدِ دسته (دسته‌ای که از همه بیشتر اتفاق افتاده باشد:h_m(x) = \sum_{j=1}^{J_{m}} b_{jm} \mathbf {1}_{R_{jm}}(x)

h_m(x) در ضریبی به اسم \gamma_m ضرب می‌شود که تابع ضرر را کمینه کند، به عبارت دیگر 
\gamma_m = \underset{\gamma}{\operatorname{arg\,min}} \sum_{i=1}^n L(y_i, F_{m-1}(x_i) + \gamma h_m(x_i))  و مدل در این مرحله به این شکل به‌روز می‌شود:  
F_m(x) = F_{m-1}(x) + \gamma_m h_m(x) 

به پیشنهاد فریدمن به جای اینکه در هر مرحله یک ضریب کلی به اسم \gamma_m فراگرفته شود، بهتر است J_{m} ضریب به تعداد تمام زیرفضاهای ایجاد شده توسط h_m فراگرفته شود و الگوریتم به این شکل تغییر کند):


    F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_{m}} \gamma_{jm} \mathbf {1}_{R_{jm}}(x), \quad
    \gamma_{jm} = \underset{\gamma}{\operatorname{arg\,min}} \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma)
  

### مشخصات درخت
اگر J را اندازه تعداد برگهای درخت یا همان تعداد زیرفضاهای \mathcal{X} بگیریم معمولاً 4 \leq J \leq 8 مدل خوبی ایجاد می‌کند.

### اهمیت متغیرها
این الگوریتم می‌تواند، مانند درخت تصمیم یا جنگل تصادفی، برای رتبه‌بندی اهمیت متغیرها به کار رود. فرمول اهمیت متغیرها در الگوریتم تقویت گرادیان با همان درخت تصمیم یکی است، اما در این الگوریتم امتیاز تمام یادگیرنده‌های ضعیف (یعنی درخت‌های تصمیم) میانگین‌گیری می‌شود.

## جستارهای وابسته
* آدابوست
* جنگل تصادفی

## منابع

رده:درخت تصمیم
رده:یادگیری گروهی