آدابوست

آدابوست الگو:به انگلیسی تطبیقی بوده و یک الگوریتم یادگیری ماشین است که توسط یاو فروند و رابرت شاپیر اختراع شد. تطبیقی بودن آدابوست به این معناست که مدلها یکی پس از دیگری ساخته شده و عملکرد مدل‌های قبلی بر روند مدل‌سازی مدل‌های پس از آن تأثیر می‌گذارد. در واقع آدابوست یک متا الگوریتم است که به منظور ارتقاء عملکرد، و رفع مشکل رده‌های نامتوازن همراه دیگر الگوریتم‌های یادگیری استفاده می‌شود. در این الگوریتم، طبقه‌بندی هر مرحله جدید به نفع نمونه‌های غلط طبقه‌بندی شده در مراحل قبل تنظیم می‌گردد. آدابوست نسبت به داده‌های نویزی و پرت حساس است؛ ولی نسبت به مشکل بیش برازش از بیشتر الگوریتم‌های یادگیری برتری دارد. طبقه‌بندی پایه که در اینجا استفاده می‌شود فقط کافیست از طبقه‌بندی تصادفی (۵۰٪) بهتر باشد و به این ترتیب عملکرد الگوریتم در تکرارهای بیشتر بهبود می‌یابد. حتی طبقه‌بندهای با خطای بالاتر از تصادفی با گرفتن ضریب منفی عملکرد کلی را بهبود می‌بخشند. در الگوریتم آدابوست در هر دور $t=1,\dots ,T$ یک طبقه‌بند ضعیف اضافه می‌شود. در هر فراخوانی بر اساس اهمیت نمونه‌ها، وزن‌ها $D_t$ بروز می‌شود. در هر دور وزن نمونه‌های غلط طبقه‌بندی شده افزایش و وزن نمونه‌های درست طبقه‌بندی شده کاهش داده می‌شود؛ بنابراین طبقه‌بند جدید تمرکز بر نمونه‌هایی که سخت‌تر یادگرفته می‌شوند، خواهند داشت. پس به‌طور خلاصه این الگوریتم منطبق بر یادگیری گروهی می‌باشد. به بیان ساده‌تر طرز کار این الگوریتم به این صورت است که عملکرد مدلهایی که به تنهایی ضعیف عمل می‌کنند را با یکدیگر ترکیب کرده و باعث بهبود عملکرد آنها می‌شود. پس در نظرگرفتن پیش‌بینی که مجموع چند الگوریتم یادگیری ضعیف ارائه می‌دهد می‌تواند در نهایت به اندازهٔ عملکرد یک الگوریتم قوی قابل اتکا باشد.

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

داده شده‌ها:

• مجموعه یادگیری: $(x_1,y_1),\dots ,(x_N,y_N)$ که $x_i\in X,y_i\in Y=\{-1,+1\}$
• تعداد تکرارها: $T$

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

• برای خانواده طبقه‌بندهای ضعیف ℋ طبقه‌بند $h_t$ را پیدا کن که میزان خطا نسبت به توزیع $D_t$ کمینه شود، در این معادله $I$ یک تابع نشانگر است:

الگو:وسط‌چین $h_t=\underset{h\in \mathscr{H}}{\mathrm{argmin}}\sum _{i=1}^N{D}_t(i)I(y_i\ne h(x_i))$ الگو:پایان وسط‌چین خطای $h_t$ را با ${ϵ}_t$ نمایش می‌دهیم: الگو:وسط‌چین ${ϵ}_t=\sum _{i=1}^N{D}_t(i)I(y_i\ne h_t(x_i))$ الگو:پایان وسط‌چین

• اگر $|0.5-{ϵ}_t|\le \beta$ که $\beta$ یک آستانه تعیین شده قبلی است، توقف انجام شود.
• معمولاً مقدار ${\alpha }_t=\frac{1}{2}\text{ln}\frac{1-{ϵ}_t}{{ϵ}_t}$ برای ${\alpha }_t\in ℝ$ در نظر گرفته می‌شود.
• بروز رسانی:

الگو:وسط‌چین $D_{t+1}(i)=\frac{D_t(i)\exp ({\alpha }_{t}I(y_i\ne h_t(x_i)))}{Z_t}$ الگو:پایان وسط‌چین

که $Z_t$ یک عامل نرمال‌سازی با مقدار $\sum _i{D}_t(i)\exp (-{\alpha }_t{y}_i{h}_t(x_i))$ است که موجب می‌شود $D_{t+1}$ یک توزیع احتمالاتی مجاز را نشان دهد (مجموع روی همه $x$‌ها یک شود)

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

الگو:وسط‌چین $H(x)=\text{sign}(\sum _{t=1}^T{\alpha }_t{h}_t(x))$ الگو:پایان وسط‌چین

توجه شود که معادله بروز رسانی توزیع $D_t$ بگونه‌ای بروز می‌شود که

$-{\alpha }_t{y}_i{h}_t(x_i)\{\begin{array}{cc}<0,& y(i)=h_t(x_i)\\ >0,& y(i)\ne h_t(x_i)\end{array}$

الگو:پایان وسط‌چین بنابراین بعد از انتخاب بهینه طبقه‌بند $h_t$ برای توزیع $D_t$ آندسته از نمونه‌ها $x_i$ که طبقه‌بند $h_t$ آن‌ها را غلط طبقه‌بندی می‌کند وزن بیشتری نسبت به بقیه داده می‌شود؛ بنابراین وقتی الگوریتم طبقه‌بندها را براساس توزیع $D_{t+1}$ تست می‌کند، طبقه‌بندی انتخاب می‌شود که نمونه‌های غلط طبقه‌بندی شده را بهتر تشخیص دهد.

مراحل الگوریتم آدابوست

الگوریتم آدابوست مطابق مراحل زیر به صورت مکرر کار می‌کند

• در ابتدا برای این الگوریتم الزامی است یک زیرمجموعه آموزشی انتخاب شود.
• با استفاده از مجموعه آموزشی که بر اساس پیش‌بینی صحیح آخرین آموزش ایجاد شده به صورت مکرر مدل یادگیری‌ماشینی آدابوست را آموزش می‌دهیم.
• تمام نمونه‌های آموزشی در فرایند آموزش دارای وزنی خواهند بود که براساس خطای ناشی از مدل یادگیری‌ماشین به‌دست می‌آید. این الگوریتم وزن بالاتری را به مشاهداتی که به صورت اشتباه طبقه‌بندی شده‌اند اختصاص می‌دهد تا در تکرارهای بعدی این مشاهدات برای فرایند طبقه‌بندی احتمال بالاتری را به‌دست آورند.
• در مرحله بعد طبقه‌بندهایی که آموزش دیده شده‌اند وزن‌دهی می‌شوند. هرچه طبقه‌بندی دقیق‌تر باشد وزن بالاتری خواهد داشت.
• این مراحل تا زمانی تکرار می‌شوند که داده‌های آموزشی کامل و بدون هیچ خطایی توسط مدل آموزش ببیند.
• برای انجام طبقه‌بندی کافی است یک رای به ازای هر الگوریتم یادگیری ساخته‌شده در نظر گرفته شود.

ایجاد مدل در پایتون

در این مرحله مطابق کد زیر کتابخانه‌های مورد نیاز را وارد می‌کنیم.

# Load libraries
from sklearn.ensemble import AdaBoostClassifier
from sklearn import datasets
# Import train_test_split function
from sklearn.model_selection import train_test_split
# Import scikit-learn metrics module for accuracy calculation
from sklearn import metrics

در مرحله بعد از یک مجموعه‌داده برای بررسی مدل روی آن استفاده می‌کنیم.

# Load data
iris = datasets.load_iris()
X = iris.data
y = iris.target

سپس مجموعه‌داده را به دو قسمت آموزش و تست تقسیم می‌کنیم.

# Split dataset into training set and test set
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3) # 70% training and 30% test

در نهایت یک مدل آدابوست روی مجموعه‌داده اجرا می‌کنیم.

# Create adaboost classifer object
abc = AdaBoostClassifier(n_estimators=۵۰,
  learning_rate=۱)
# Train Adaboost Classifer
model = abc.fit(X_train, y_train)
# Predict the response for test dataset
y_pred = model.predict(X_test)

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

عمل تقویت کردن را می‌توان به صورت حداقل کردن یک تابع هزینه محدب روی یک مجموعه محدب از توابع در نظر گرفت. به‌طور خاص تابعی که حداقل می‌شود نمایی است: الگو:وسط‌چین $E=\sum _{i=1}^N\text{exp}(-y_i\times f_m(x_i))$ الگو:پایان وسط‌چین و ما به‌دنبال تابعی به شکل زیر هستیم: الگو:وسط‌چین $f_m(x)=\frac{1}{2}\sum _{t=1}^m{\alpha }_t{h}_t(x)$ الگو:پایان وسط‌چین مجهولِ تابع هزینه $E$، $f_m(\cdot )$ است که خود به ${\alpha }_1,\cdots ,{\alpha }_m,h_1,\cdots ,{\alpha }_m$ بستگی دارد. در نتیجه بهینه‌سازی تابع هزینه در نهایت باید نسبت به ${\alpha }_1,\cdots ,{\alpha }_m,h_1,\cdots ,h_m$ صورت بگیرد.

حال برای راحتتر شدن کار فرض می‌کنیم که مقادیر ${\alpha }_1,\cdots ,{\alpha }_{m-1},h_1,\cdots ,h_{m-1}$ ثابت هستند و هدف ما پیدا کردن ${\alpha }_m$ و $h_m$ است. با این اوصاف تابع $E$را می‌توان به شکل پایین نوشت: الگو:وسط‌چین $E=\sum _{i=1}^N\text{exp}\left(-y_i\times (f_{m-1}(x_i)+\frac{1}{2}{\alpha }_m{h}_m(x_i))\right)=\sum _{i=1}^N\text{exp}\left(-y_i\times f_{m-1}(x_i)\right)\text{exp}\left(-\frac{1}{2}{y}_i\times {\alpha }_m{h}_m(x_i)\right)$ الگو:پایان وسط‌چین اگر $\text{exp}(-y_i\times f_{m-1}(x_i))$ را با $w_i^{(m)}$ نمایش دهیم، تابع هزینه ما به شکل پایین تغییر شکل خواهد داد: الگو:وسط‌چین $E=\sum _{i=1}^N{w}_i^{(m)}{e}^{-\frac{1}{2}{y}_i\times {\alpha }_m{h}_m(x_i)}$ الگو:پایان وسط‌چین اگر مجموعه تمام داده‌هایی که توسط $h_m(\cdot )$ به درستی پیش‌بینی می‌شوند را با ${\mathrm{T}}_m$ و مجموعه تمام داده‌هایی که توسط $h_m(\cdot )$ نادرست پیش‌بینی می‌شوند را با $M_m$ نمایش دهیم. تابع هزینه به شکل پایین تغییر خواهد کرد: الگو:وسط‌چین $\begin{array}{cc}E& =\text{exp}\left(-\frac{{\alpha }_m}{2}\right)\sum _{i\in {\mathrm{T}}_m}{w}_i^{(m)}+\text{exp}\left(\frac{{\alpha }_m}{2}\right)\sum _{i\in M_m}{w}_i^{(m)}\\ & =(\text{exp}\left(\frac{{\alpha }_m}{2}\right)-\text{exp}\left(-\frac{{\alpha }_m}{2}\right))\sum _{i=1}^N{w}_i^{(m)}I(h_m(x_i)\ne y_i)+\text{exp}\left(-\frac{{\alpha }_m}{2}\right)\sum _{i=1}^N{w}_i^{(m)}\end{array}$ الگو:پایان وسط‌چین حال اگر $E$ را نسبت به $h_m$ بهینه کنیم، از آنجا که$\text{exp}\left(-\frac{{\alpha }_m}{2}\right)\sum _{i=1}^N{w}_i^{(m)}$ و $(\text{exp}\left(\frac{{\alpha }_m}{2}\right)-\text{exp}\left(-\frac{{\alpha }_m}{2}\right))$ نسبت به $h_m$ ثابت هستند، فقط باید $\sum _{i=1}^N{w}_i^{(m)}I(h_m(x_i)\ne y_i)$ را نسبت به $h_m$ کمینه کنیم؛ یعنی $h_m=\underset{h\in \mathscr{H}}{\mathrm{argmin}}\sum _{i=1}^N{w}_i^{(m)}I(h(x_i)\ne y_i)$

بعد از پیدا کردن $h_m$ باید ${\alpha }_m$ را پیدا کنیم اگر $\frac{\sum _{i=1}^N{w}_i^{(m)}I(h(x_i)\ne y_i)}{\sum _{i=1}^N{w}_i^{(m)}}$ را ${ϵ}_m$ بنامیم تابع هزینه ما تبدیل می‌شود به $((\text{exp}\left(\frac{{\alpha }_m}{2}\right)-\text{exp}\left(-\frac{{\alpha }_m}{2}\right)){ϵ}_m+\text{exp}\left(-\frac{{\alpha }_m}{2}\right))\sum _{i=1}^N{w}_i^{(m)}$که اگر از آن نسبت به ${\alpha }_m$ مشتق بگیریم و جواب را در نقطه صفر به‌دست بیاوریم به این جواب می‌رسیم: ${\alpha }_m=\frac{1}{2}\text{ln}\frac{1-{ϵ}_m}{{ϵ}_m}$.

حال که ${\alpha }_m$ و $h_m$ را پیدا کردیم باید ببینیم که $w_i^{(m+1)}$ به چه شکل نسبت به $w_i^{(m)}$ بروز می‌شود. $w_i^{(m+1)}$ همان $\text{exp}\left(-y_i\times f_m(x_i)\right)$ است یعنی الگو:وسط‌چین $\begin{array}{cc}{w}_i^{(m+1)}& =\text{exp}\left(-y_i\times f_m(x_i)\right)\\ & =\text{exp}\left(-y_i\times (f_{m-1}(x_i)+\frac{1}{2}{\alpha }_m{h}_m(x_i))\right)\\ & =\text{exp}\left(-y_i{f}_{m-1}(x_i)\right)\text{exp}\left(-\frac{1}{2}{y}_i{\alpha }_m{h}_m(x_i)\right)\\ & =w_i^{(m)}\text{exp}\left(-\frac{1}{2}{y}_i{\alpha }_m{h}_m(x_i)\right)\end{array}$ الگو:پایان وسط‌چین پس ارتباط $w_i^{(m+1)}$ با $w_i^{(m)}$ به این شکل خواهد بود: الگو:وسط‌چین $w_i^{(m+1)}=w_i^{(m)}\text{exp}\left(-\frac{1}{2}{y}_i{\alpha }_m{h}_m(x_i)\right)$ الگو:پایان وسط‌چین از آنجا که $y_i{h}_m(x_i)=1-2I(h(x_i)\ne y_i)$ به‌روز کردن $w_i^{(m+1)}$ به این شکل تغییر خواهد کرد: الگو:وسط‌چین $w_i^{(m+1)}=w_i^{(m)}\text{exp}\left(-\frac{{\alpha }_m}{2}\right)\text{exp}\left({\alpha }_{m}I(h_m(x_i)\ne y_i)\right)$ الگو:پایان وسط‌چین اگر تمام $w_i^{(m+1)}$‌ها را در یک مقدار ثابتی ضرب کنیم تأثیری در جواب نهایی ${ϵ}_{m+1}$ و ${\alpha }_{m+1}$ و $h_{m+1}$ نخواهد داشت. ازین رو همیشه می‌توان مقدار آن‌ها را نرمال‌سازی کرد. با نرمال‌سازی $w_i^{(m+1)}$ به معادله بازگشتی پایین می‌رسیم، در این معادله $Z_m=\sum _i{w}_i^{(m)}$ : الگو:وسط‌چین $w_i^{(m+1)}=\frac{w_i^{(m)}\text{exp}\left({\alpha }_{m}I(h_m(x_i)\ne y_i)\right)}{Z_m}$ الگو:پایان وسط‌چین $w_i^{(m+1)}$ همان $D_{m+1}(i)$است، و از آنجا که $\frac{1}{2}$در جواب $sign(f_m(x))$ تأثیری ندارد، می‌توان آن را حذف کرد. حال اگر $m$ را همان $T$ بگیریم به الگوریتم آدابوست خواهیم رسید.

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

• تقویت گرادیان
• ال پی بوست

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

• 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 الگو:Webarchive for Python implements AdaBoost.
• MPBoost++, a C++ implementation of the original AdaBoost.MH algorithm and of an improved variant, the MPBoost algorithm.
• NPatternRecognizer الگو:Webarchive, 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