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

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

مقدمه

مانند دیگر روش‌های تقویتی (بوستینگ)، تقویت گرادیان (گرادیان بوستینگ) ترکیبی خطی از یک سری از مدل‌های ضعیف برای ایجاد یک مدل قوی و کارآمد است.[4] ساده‌ترین مثال برای توضیح تقویت گرادیان، مثال کمترین مربعات در مسئله رگرسیون است که در آن هدف، یادگیری یک مدل به اسم ${\displaystyle F}$ برای کمینه کردن ${\displaystyle {\frac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}}$ یا میانگین مربعات خطا است. در اینجا ${\displaystyle {\hat {y_{i}}}=F(x_{i})}$، ${\displaystyle n}$ تعداد داده‌های ماست و ${\displaystyle (x_{i},y_{i})}$ داده ${\displaystyle i}$ام است.[4]

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

الگوریتم

فرض کنید داده‌هایکه مدل برای یادگیری از آن‌ها استفاده می‌کند ${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ باشد و هدف از یادگیری، کمینه کردن یک تابع ضرر به اسم ${\displaystyle L}$ باشد. یعنی ${\displaystyle {\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]}$

در مدل تقویت گرادیان این کار به صورت متناوب انجام می‌شود[2][5] و مدل نهایی برابر خواهد بود با ${\displaystyle {\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+F_{0}}$.

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

اولین مدل یک عدد ثابت است به اسم ${\displaystyle F_{0}}$ که به صورت ذیل انتخاب می‌شود: ${\displaystyle F_{0}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$

بقیه مدل‌ها به این صورت ساخته و فراگرفته می‌شوند:${\displaystyle 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 {\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 {\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)}}}}$

به عبارت دیگر ما بدنبال مدلسازی منفی گرادیان تابع ضرر در هر مرحله هستیم یعنی یک مدل به اسم ${\displaystyle h_{m}}$ از ${\displaystyle {\mathcal {H}}}$ که بتواند با داده پایین تابع ضرر را کمینه کند:[5]

${\displaystyle \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\}}$

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

• ${\displaystyle F_{0}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}}$
• برای ${\displaystyle m}$ از ${\displaystyle 1}$ تا ${\displaystyle M}$:
  • برای ${\displaystyle i}$ از ${\displaystyle 1}$ تا ${\displaystyle n}$:
    • ${\displaystyle r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}}$
  • برای داده‌های ${\displaystyle \{(x_{i},r_{im})\}_{i=1}^{n}}$ یک مدل به اسم ${\displaystyle h_{m}}$ از ${\displaystyle {\mathcal {H}}}$ انتخاب کن که تابع ضرر را به حداقل برساند، به عبارت دیگر ${\displaystyle h_{m}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,L\left(r_{im},h(x_{i})\right)}$
  • ${\displaystyle \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)}$
  • ${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x)}$
• مدل نهایی ${\displaystyle F_{M}}$است.

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

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

${\displaystyle h_{m}(x)}$ در ضریبی به اسم ${\displaystyle \gamma _{m}}$ ضرب می‌شود که تابع ضرر را کمینه کند، به عبارت دیگر ${\displaystyle \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i}))}$ و مدل در این مرحله به این شکل به‌روز می‌شود: ${\displaystyle F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x)}$

به پیشنهاد فریدمن به جای اینکه در هر مرحله یک ضریب کلی به اسم ${\displaystyle \gamma _{m}}$ فراگرفته شود، بهتر است ${\displaystyle J_{m}}$ ضریب به تعداد تمام زیرفضاهای ایجاد شده توسط ${\displaystyle h_{m}}$ فراگرفته شود و الگوریتم به این شکل تغییر کند):[5]

${\displaystyle 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 )}$

مشخصات درخت

اگر ${\displaystyle J}$ را اندازه تعداد برگهای درخت یا همان تعداد زیرفضاهای ${\displaystyle {\mathcal {X}}}$ بگیریم معمولاً ${\displaystyle 4\leq J\leq 8}$ مدل خوبی ایجاد می‌کند.[5]

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

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

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

• آدابوست
• جنگل تصادفی

منابع

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.
2. Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF).
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. Check date values in: |date= (help)
4. 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.
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&ndash, 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 ${\displaystyle b_{jm}}$ for the region ${\displaystyle R_{jm}}$ is equal to just the value of output variable, averaged over all training instances in ${\displaystyle R_{jm}}$.