آدابوست

آدابوست (به انگلیسی: AdaBoost) تطبیقی بوده و یک الگوریتم یادگیری ماشین است که توسط یاو فروند و رابرت شاپیر ابداع شد.[1] در واقع آدابوست یک متا الگوریتم است که به منظور ارتقاء عملکرد، و رفع مشکل رده‌های نامتوازن[2] همراه دیگر الگوریتم‌های یادگیری استفاده می‌شود. در این الگوریتم، طبقه‌بند هر مرحله جدید به نفع نمونه‌های غلط طبقه‌بندی شده در مراحل قبل تنظیم می‌گردد. آدابوست نسبت به داده‌های نویزی و پرت حساس است؛ ولی نسبت به مشکل بیش برازش از بیشتر الگوریتم‌های یادگیری برتری دارد. طبقه‌بند پایه که در اینجا استفاده می‌شود فقط کافیست از طبقه‌بند تصادفی (۵۰٪) بهتر باشد و به این ترتیب بهبود عملکرد الگوریتم با تکرارهای بیشتر بهبود می‌یابد. حتی طبقه‌بندهای با خطای بالاتر از تصادفی با گرفتن ضریب منفی عملکرد کلی را بهبود می‌بخشند.[1] در الگوریتم آدابوست در هر دور ${\displaystyle t=1,\ldots ,T}$ یک طبقه‌بند ضعیف اضافه می‌شود. در هر فراخوانی بر اساس اهمیت نمونه‌ها، وزن‌ها ${\displaystyle D_{t}}$ بروز می‌شود. در هر دور وزن نمونه‌های غلط طبقه‌بندی شده افزایش و وزن نمونه‌های درست طبقه‌بندی شده کاهش داده می‌شود؛ بنابراین طبقه‌بند جدید تمرکز بر نمونه‌هایی که سخت‌تر یادگرفته می‌شوند، خواهند داشت.[1]

الگوریتم طبقه‌بندی دوگانه

داده شده‌ها:

• مجموعه یادگیری: ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{N},y_{N})}$ که ${\displaystyle x_{i}\in X,\,y_{i}\in Y=\{-1,+1\}}$
• تعداد تکرارها: ${\displaystyle T}$

مقداردهی اولیه: ${\displaystyle \textstyle D_{1}(i)={\frac {1}{N}},i=1,\ldots ,N.}$ برای ${\displaystyle t=1,\ldots ,T}$

• برای خانواده طبقه‌بندهای ضعیف ℋ طبقه‌بند ${\displaystyle h_{t}\,\!}$ را پیدا کن که میزان خطا نسبت به توزیع ${\displaystyle D_{t}}$ کمینه شود، در این معادله ${\displaystyle I}$ یک تابع نشانگر است:

${\displaystyle h_{t}={\underset {h\in {\mathcal {H}}}{\operatorname {argmin} }}\;\sum _{i=1}^{N}D_{t}(i)I(y_{i}\neq h(x_{i}))}$

خطای ${\displaystyle h_{t}}$ را با ${\displaystyle \epsilon _{t}}$ نمایش می‌دهیم:

${\displaystyle \epsilon _{t}=\sum _{i=1}^{N}D_{t}(i)I(y_{i}\neq h_{t}(x_{i}))}$

• اگر ${\displaystyle \left\vert 0.5-\epsilon _{t}\right\vert \leq \beta }$ که ${\displaystyle \beta }$ یک آستانه تعیین شده قبلی است، توقف انجام شود.
• معمولاً مقدار ${\displaystyle \alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{t}}{\epsilon _{t}}}}$ برای ${\displaystyle \alpha _{t}\in \mathbb {R} }$ در نظر گرفته می‌شود.
• بروز رسانی:

${\displaystyle D_{t+1}(i)={\frac {D_{t}(i)\exp \left(\alpha _{t}I(y_{i}\neq h_{t}(x_{i}))\right)}{Z_{t}}}}$

که ${\displaystyle Z_{t}}$ یک عامل نرمال‌سازی با مقدار ${\displaystyle \sum _{i}D_{t}(i)\exp(-\alpha _{t}y_{i}h_{t}(x_{i}))\,\!}$ است که موجب می‌شود ${\displaystyle D_{t+1}}$ یک توزیع احتمالاتی مجاز را نشان دهد (مجموع روی همه ${\displaystyle x}$‌ها یک شود)

خروجی نهایی طبقه‌بند

${\displaystyle H(x)={\textrm {sign}}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\right)}$

توجه شود که معادله بروز رسانی توزیع ${\displaystyle D_{t}}$ بگونه‌ای بروز می‌شود که

${\displaystyle -\alpha _{t}y_{i}h_{t}(x_{i}){\begin{cases}<0,&y(i)=h_{t}(x_{i})\\>0,&y(i)\neq h_{t}(x_{i})\end{cases}}}$

بنابراین بعد از انتخاب بهینه طبقه‌بند ${\displaystyle h_{t}\,}$ برای توزیع ${\displaystyle D_{t}\,}$ آندسته از نمونه‌ها ${\displaystyle x_{i}\,}$ که طبقه‌بند ${\displaystyle h_{t}\,}$ آن‌ها را غلط طبقه‌بندی می‌کند وزن بیشتری نسبت به بقیه داده می‌شود؛ بنابراین وقتی الگوریتم طبقه‌بندها را براساس توزیع ${\displaystyle D_{t+1}\,}$ تست می‌کند، طبقه‌بندی انتخاب می‌شود که نمونه‌های غلط طبقه‌بندی شده را بهتر تشخیص دهد.

اثبات و فهم ریاضی آدابوست

عمل تقویت کردن را می‌توان به صورت حداقل کردن یک تابع هزینه محدب روی یک مجموعه محدب از توابع در نظر گرفت.[3] به‌طور خاص تابعی که حداقل می‌شود نمایی است:

${\displaystyle E=\sum _{i=1}^{N}{\mbox{exp}}({-y_{i}\times f_{m}(x_{i})})}$

و ما بدنبال تابعی به شکل زیر هستیم:[4]

${\displaystyle f_{m}(x)={\frac {1}{2}}\sum _{t=1}^{m}\alpha _{t}h_{t}(x)\,\!}$

مجهولِ تابع هزینه ${\displaystyle E}$، ${\displaystyle f_{m}(\cdot )}$ است که خود به ${\displaystyle \alpha _{1},\cdots ,\alpha _{m},h_{1},\cdots ,\alpha _{m}}$ بستگی دارد. در نتیجه بهینه‌سازی تابع هزینه در نهایت باید نسبت به ${\displaystyle \alpha _{1},\cdots ,\alpha _{m},h_{1},\cdots ,h_{m}}$ صورت بگیرد.

حال برای راحتتر شدن کار فرض می‌کنیم که مقادیر ${\displaystyle \alpha _{1},\cdots ,\alpha _{m-1},h_{1},\cdots ,h_{m-1}}$ ثابت هستند و هدف ما پیدا کردن ${\displaystyle \alpha _{m}}$و ${\displaystyle h_{m}}$ است. با این اوصاف تابع ${\displaystyle E}$را می‌توان به شکل پایین نوشت:

${\displaystyle E=\sum _{i=1}^{N}{\mbox{exp}}\left({-y_{i}\times \left(f_{m-1}(x_{i})+{\frac {1}{2}}\alpha _{m}h_{m}(x_{i})\right)}\right)=\sum _{i=1}^{N}{\mbox{exp}}\left({-y_{i}\times f_{m-1}(x_{i})}\right){\mbox{exp}}\left({-{\frac {1}{2}}y_{i}\times \alpha _{m}h_{m}(x_{i})}\right)}$

اگر ${\displaystyle {\mbox{exp}}({-y_{i}\times f_{m-1}(x_{i})})}$را با ${\displaystyle w_{i}^{(m)}}$ نمایش دهیم، تابع هزینه ما به شکل پایین تغییر شکل خواهد داد:[4]

${\displaystyle E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-{\frac {1}{2}}y_{i}\times \alpha _{m}h_{m}(x_{i})}}$

اگر مجموعه تمام داده‌هایی که توسط ${\displaystyle h_{m}(\cdot )}$به درستی پیش‌بینی می‌شوند را با ${\displaystyle \mathrm {T} _{m}}$ و مجموعه تمام داده‌هایی که توسط ${\displaystyle h_{m}(\cdot )}$ نادرست پیش‌بینی می‌شوند را با ${\displaystyle M_{m}}$ نمایش دهیم. تابع هزینه به شکل پایین تغییر خواهد کرد:

${\displaystyle {\begin{aligned}E&={\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\sum _{i\in \mathrm {T} _{m}}w_{i}^{(m)}+{\mbox{exp}}\left({\frac {\alpha _{m}}{2}}\right)\sum _{i\in M_{m}}w_{i}^{(m)}\\&=\left({\mbox{exp}}\left({\frac {\alpha _{m}}{2}}\right)-{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\right)\sum _{i=1}^{N}w_{i}^{(m)}I\left(h_{m}(x_{i})\neq y_{i}\right)+{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\sum _{i=1}^{N}w_{i}^{(m)}\end{aligned}}}$

حال اگر ${\displaystyle E}$را نسبت ${\displaystyle h_{m}}$ بهینه کنیم، از آنجا که${\displaystyle {\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\sum _{i=1}^{N}w_{i}^{(m)}}$ و ${\displaystyle \left({\mbox{exp}}\left({\frac {\alpha _{m}}{2}}\right)-{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\right)}$ نسبت به ${\displaystyle h_{m}}$ ثابت هستند، فقط باید ${\displaystyle \sum _{i=1}^{N}w_{i}^{(m)}I\left(h_{m}(x_{i})\neq y_{i}\right)}$ را نسبت به ${\displaystyle h_{m}}$ کمینه کنیم. یعنی ${\displaystyle h_{m}={\underset {h\in {\mathcal {H}}}{\operatorname {argmin} }}\;\sum _{i=1}^{N}w_{i}^{(m)}I(h(x_{i})\neq y_{i})}$

بعد از پیدا کردن ${\displaystyle h_{m}}$ باید ${\displaystyle \alpha _{m}}$ را پیدا کنیم اگر ${\displaystyle {\frac {\sum _{i=1}^{N}w_{i}^{(m)}I(h(x_{i})\neq y_{i})}{\sum _{i=1}^{N}w_{i}^{(m)}}}}$ را ${\displaystyle \epsilon _{m}}$ بنامیم تابع هزینه ما تبدیل می‌شود به ${\displaystyle \left(\left({\mbox{exp}}\left({\frac {\alpha _{m}}{2}}\right)-{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\right)\epsilon _{m}+{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right)\right)\sum _{i=1}^{N}w_{i}^{(m)}}$که اگر از آن نسبت به ${\displaystyle \alpha _{m}}$ مشتق بگیریم و جواب را در نقطه صفر بدست بیاوریم به این جواب می‌رسیم: ${\displaystyle \alpha _{m}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{m}}{\epsilon _{m}}}}$.

حال که ${\displaystyle \alpha _{m}}$ و ${\displaystyle h_{m}}$ را پیدا کردیم باید ببینیم که ${\displaystyle w_{i}^{(m+1)}}$ به چه شکل نسبت به ${\displaystyle w_{i}^{(m)}}$ بروز می‌شود. ${\displaystyle w_{i}^{(m+1)}}$ همان ${\displaystyle {\mbox{exp}}\left({-y_{i}\times f_{m}(x_{i})}\right)}$ است یعنی

${\displaystyle {\begin{aligned}w_{i}^{(m+1)}&={\mbox{exp}}\left({-y_{i}\times f_{m}(x_{i})}\right)\\&={\mbox{exp}}\left({-y_{i}\times \left(f_{m-1}(x_{i})+{\frac {1}{2}}\alpha _{m}h_{m}(x_{i})\right)}\right)\\&={\mbox{exp}}\left({-y_{i}f_{m-1}(x_{i})}\right){\mbox{exp}}\left({-{\frac {1}{2}}y_{i}\alpha _{m}h_{m}(x_{i})}\right)\\&=w_{i}^{(m)}{\mbox{exp}}\left({-{\frac {1}{2}}y_{i}\alpha _{m}h_{m}(x_{i})}\right)\end{aligned}}}$

پس ارتباط ${\displaystyle w_{i}^{(m+1)}}$ با ${\displaystyle w_{i}^{(m)}}$ به این شکل خواهد بود:[4]

${\displaystyle w_{i}^{(m+1)}=w_{i}^{(m)}{\mbox{exp}}\left({-{\frac {1}{2}}y_{i}\alpha _{m}h_{m}(x_{i})}\right)}$

از آنجا که ${\displaystyle y_{i}h_{m}(x_{i})=1-2I(h(x_{i})\neq y_{i})}$ به‌روز کردن ${\displaystyle w_{i}^{(m+1)}}$ به این شکل تغییر خواهد کرد:

${\displaystyle w_{i}^{(m+1)}=w_{i}^{(m)}{\mbox{exp}}\left({-{\frac {\alpha _{m}}{2}}}\right){\mbox{exp}}\left({\alpha _{m}I\left(h_{m}(x_{i})\neq y_{i}\right)}\right)}$

اگر تمام ${\displaystyle w_{i}^{(m+1)}}$‌ها را در یک مقدار ثابتی ضرب کنیم تأثیری در جواب نهایی ${\displaystyle \epsilon _{m+1}}$ و ${\displaystyle \alpha _{m+1}}$ و ${\displaystyle h_{m+1}}$ نخواهد داشت. ازین رو همیشه می‌توان مقدار آن‌ها را نرمال‌سازی کرد. با نرمال‌سازی ${\displaystyle w_{i}^{(m+1)}}$ به معادله بازگشتی پایین می‌رسیم، در این معادله ${\displaystyle Z_{m}=\sum _{i}w_{i}^{(m)}}$ :

${\displaystyle w_{i}^{(m+1)}={\frac {w_{i}^{(m)}{\mbox{exp}}\left({\alpha _{m}I\left(h_{m}(x_{i})\neq y_{i}\right)}\right)}{Z_{m}}}}$

${\displaystyle w_{i}^{(m+1)}}$ همان ${\displaystyle D_{m+1}(i)}$است، و از آنجا که ${\displaystyle {\frac {1}{2}}}$در جواب ${\displaystyle sign(f_{m}(x))}$ تأثیری ندارد، می‌توان آن را حذف کرد. حال اگر ${\displaystyle m}$ را همان ${\displaystyle T}$ بگیریم به الگوریتم آدابوست خواهیم رسید.[4]

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

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

منابع

1. Yoav Freund, Robert E. Schapire. "A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting", 1995
2. مهسا المعی نژاد. «روش‌های Bagging و Boosting به منظور رفع مشکل کلاس‌های نامتوازن». گروه داده کاوی ایران. بایگانی‌شده از اصلی در ۳۱ مارس ۲۰۱۴. دریافت‌شده در ۲۶ فوریه ۲۰۱۴.
3. T. Zhang, "Statistical behavior and consistency of classification methods based on convex risk minimization", Annals of Statistics 32 (1), pp. 56-85, 2004.
4. Bishop, Christopher (2006). Pattern Recognition and Machine Learning (به English). New York: Springer. pp. 658–661. ISBN 978-0-387-31073-2.

پیاده‌سازی‌ها

• AdaBoost and the Super Bowl of Classifiers - A Tutorial on AdaBoost.
• Adaboost in C++, an implementation of Adaboost in C++ and boost by Antonio Gulli
• icsiboost, an open source implementation of Boostexter
• JBoost, a site offering a classification and visualization package, implementing AdaBoost among other boosting algorithms.
• MATLAB AdaBoost toolbox. Includes Real AdaBoost, Gentle AdaBoost and Modest AdaBoost implementations.
• A Matlab Implementation of AdaBoost
• milk for Python implements AdaBoost.
• MPBoost++, a C++ implementation of the original AdaBoost.MH algorithm and of an improved variant, the MPBoost algorithm.
• NPatternRecognizer, a fast machine learning algorithm library written in C#. It contains support vector machine, neural networks, bayes, boost, k-nearest neighbor, decision tree, … , etc.
• OpenCV implementation of several boosting variants
• Into contains open source implementations of many AdaBoost and FloatBoost variants in C++.

پیوند به بیرون

• Boosting.org, a site on boosting and related ensemble learning methods
• AdaBoost Presentation summarizing Adaboost (see page 4 for an illustrated example of performance)
• A Short Introduction to Boosting Introduction to Adaboost by Freund and Schapire from 1999
• A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 (Original paper of Yoav Freund and Robert E.Schapire where Adaboost is first introduced.)
• An applet demonstrating AdaBoost
• Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, no.3, pp. 21–45, 2006. A tutorial article on ensemble systems including pseudocode, block diagrams and implementation issues for AdaBoost and other ensemble learning algorithms.
• Additive logistic regression: a statistical view of boosting by Jerome Friedman, Trevor Hastie, Robert Tibshirani. Paper introducing probabilistic theory for AdaBoost, and introducing GentleBoost