بوستینگ

بوستینگ یک فرا الگوریتم ترکیبی در حوزه یادگیری ماشین است که برای کاهش عدم توازن و همچنین واریانسبه کار می‌رود.^[۱] این روش در یادگیری با نظارت مورد استفاده قرار گرفته و از خانواده الگوریتم‌های یادگیری ماشین به شمار می‌رود. این تکنیک، روشی برای تبدیل سیستمهای یادگیری ضعیف به قوی بر اساس ترکیب نتایج طبقه بندهای مختلف است.^[۲] ایده اولیه این روش بر اساس سؤال مطرح شده توسط کیرنس و شجاع (۱۹۸۸, ۱۹۸۹) به وجود آمده است:^[۳][۴] آیا می‌توان با ترکیب مجموعه‌ای از سیستم‌های یادگیری ضعیف یک سیستم یادگیری قوی ایجاد نمود؟

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

تقویت الگوریتم‌های

هرچند که بوستینگ در قالب الگوریتک قرار ندارد ولی اکثر الگوریتم‌هایی که بر پایه بوستینگ طراحی شده‌اند، یادگیرنده‌های ضعیف را در به صورت تکرار شونده آموزش داده و به مجموعه قبلی اضافه می‌نماید تا در نهایت به یک طبقه بند قوی درست یابد. یادگیرنده‌های ضعیف در حین اضافه شدن به مجموعه، وزن دهی می‌شوند که این وزن دهی معمولاً بر اساس میزان دقت در طبقه‌بندی نمونه هاست. پس از اضافه شدن هر طبقه بند، نمونه‌های موجود (داده‌ها) نیز وزن دهی می‌گردند (وزنشان اصلاح می‌گردد). وزن دهی نمونه‌ها به صورتی است که در هر مرحله، وزن نمونه‌هایی که به صورت صحیح طبقه‌بندی می‌شوند کاهش یافته و وزن نمونه‌هایی که به درستی طبقه‌بندی نشده‌اند، بیشتر می‌شود تا در مراحل بعدی (توسط یادگیرنده‌های جدید) بیشتر مورد توجه بوده و با دقت بیشتری طبقه‌بندی گردند؛ بنابراین تمرکز یادگیرنده‌های ضعیف جدید، بیشتر بر روی داده‌های خواهد بود که سیستم در مراحل قبلی قادر به طبقه‌بندی صحیح آنها نبوده است.

تاکنون الگوریتم‌های بوستینگ زیادی به وجود آمده‌اند ولی نسخه اصلی این الگوریتم‌ها توسط Robert Schapire و Yoav Freund ارائه شده است که Adaptive نبودهو امکان استفاده کامل از مزایای یادگیرنده‌های ضعیف را ندارد. بعدها این دو نفر الگوریتم AdaBoost که یک الگوریتم بوستینگ سازگار (Adaptive) بود را ارائه نموده و جایزه معتبر گودل را برنده شدند.

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

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

داده شده‌ها:

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

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

• برای خانواده طبقه بندهای ضعیف ℋ طبقه بند h t {\displaystyle h_{t}\,\!} را پیدا کن که قدر مطلق اختلاف نرخ خطای وزن دهی شده متناظر ϵ t {\displaystyle \epsilon _{t}\,\!} از ۰٫۵ نسبت به توزیع D t {\displaystyle D_{t)) حداکثر شود:

h t = argmax h t ∈ H | 0.5 − ϵ t | {\displaystyle h_{t}={\underset {h_{t}\in {\mathcal {H))}{\operatorname {argmax} ))\;\left\vert 0.5-\epsilon _{t}\right\vert } که ϵ t = ∑ i = 1 m D t ( i ) I ( y i ≠ h t ( x i ) ) {\displaystyle \epsilon _{t}=\sum _{i=1}^{m}D_{t}(i)I(y_{i}\neq h_{t}(x_{i}))} . I یک تابع نشانگر است

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

D t + 1 ( i ) = D t ( i ) exp ⁡ ( − α t y i h t ( x i ) ) Z t {\displaystyle D_{t+1}(i)={\frac {D_{t}(i)\exp(-\alpha _{t}y_{i}h_{t}(x_{i}))}{Z_{t))))

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

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

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

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

− α t y i h t ( x i ) { < 0 , y ( i ) = h t ( x i ) > 0 , y ( i ) ≠ h t ( x i ) {\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))}

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

درک آماری تقویت کردن

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

∑ i e − y i f ( x i ) {\displaystyle \sum _{i}e^{-y_{i}f(x_{i})))

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

f ( x ) = ∑ t α t h t ( x ) {\displaystyle f(x)=\sum _{t}\alpha _{t}h_{t}(x)\,\!}

مطالب مرتبط

منابع

1. ↑ Yoav Freund, Robert E. Schapire. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting”, 1995
2. ↑ مهسا المعی نژاد. «روش‌های Bagging و Boosting به منظور رفع مشکل کلاس‌های نامتوازن». گروه داده کاوی ایران. بازبینی‌شده در ۲۶ فبریه ۲۰۱۴.
3. ↑ Zhang, “Statistical behavior and consistency of classification methods based on convex risk minimization”, Annals of Statistics 32 (1), pp. 56-85, 2004.

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

• 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.

از ویکی‌پدیا، دانشنامهٔ آزاد