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

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

مقدمه

مانند دیگر روش‌های تقویتی (بوستینگ)، تقویت گرادیان (گرادیان بوستینگ) ترکیبی خطی از یک سری از مدل‌های ضعیف برای ایجاد یک مدل قوی و کارآمد است. ساده‌ترین مثال برای توضیح تقویت گرادیان، مثال کمترین مربعات در مسئله رگرسیون است که در آن هدف، یادگیری یک مدل به اسم $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

مدل خوبی ایجاد می‌کند.

اهمیت متغیرها

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

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

منابع

↑ Piryonesi, S. M.; El-Diraby, T. E. (2020) [Published online: December 21, 2019]. "Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index". Journal of Infrastructure Systems. 26 (1). doi:10.1061/(ASCE)IS.1943-555X.0000512.
↑ Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF).
↑ Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-06). "Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems". Journal of Transportation Engineering, Part B: Pavements. 146 (2): 04020022. doi:10.1061/jpeodx.0000175. ISSN 2573-5438.
↑ Hastie, Trevor (2009). The Elements of Statistical Learning - Data Mining, Inference, and Prediction, Second Edition (به انگلیسی). New York: Springer.
↑ 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–384. ISBN 0-387-84857-6. Archived from the original on 2009-11-10.
↑ Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient $b_{jm}$ for the region $R_{jm}$ is equal to just the value of output variable, averaged over all training instances in $R_{jm}$ .

[:12-1] Piryonesi, S. M.; El-Diraby, T. E. (2020) [Published online: December 21, 2019]. "Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index". Journal of Infrastructure Systems. 26 (1). doi:10.1061/(ASCE)IS.1943-555X.0000512.

[Friedman1999a-2] Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF).

[:1-3] Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-06). "Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems". Journal of Transportation Engineering, Part B: Pavements. 146 (2): 04020022. doi:10.1061/jpeodx.0000175. ISSN 2573-5438.

[:0-4] Hastie, Trevor (2009). The Elements of Statistical Learning - Data Mining, Inference, and Prediction, Second Edition (به انگلیسی). New York: Springer.

[hastie3-5] 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–384. ISBN 0-387-84857-6. Archived from the original on 2009-11-10.

[6] Note: in case of usual CART trees, the trees are fitted using least-squares loss, and so the coefficient $b_{jm}$ for the region $R_{jm}$ is equal to just the value of output variable, averaged over all training instances in $R_{jm}$ .