AdaBoost System

An AdaBoost System is an iterative boosting system that implements an AdaBoost algorithm to solve an AdaBoost Task.

• Context:
  • It can range from being a AdaBoost Regression System to being a AdaBoost Classification System.
  • …
• Example(s):
  • sklearn.ensemble.AdaBoostClassifier, Scikit-Learn AdaBoost algorithm implementation for solving Classification Tasks.
  • sklearn.ensemble.AdaBoostRegressor, Scikit-Learn AdaBoost algorithm implementation for solving Regression Tasks.
  • bonzaiboost[1] a C++ implementation of multi-class Adaboost.MH.
  • MultiBoost[2] a C++ implementation of multi-class Adaboost.MH.
  • adabag[3], a R package for binary and multiclass Boosting and Bagging.
  • ada, a R package within rpart System.
  • JBoost[4], a Java implementation of the AdaBoost algorithm.
  • …
• Counter-Example(s)
  • A Gradient Tree Boosting System.
  • A Random Forests System.
  • A Bagged Trees System.
  • A Rotation Forests System.
  • An Extremely Randomized Trees System.
  • A Totally Random Trees Embedding System.
  • An Isolation Forest System.
• See: Boosting System.

---

---

References

2017a

• (Wikipedia, 2017A) ⇒ https://en.wikipedia.org/wiki/AdaBoost Retrieved:2017-10-22.
  • AdaBoost, short for "Adaptive Boosting", is a machine learning meta-algorithm formulated by Yoav Freund and Robert Schapire who won the Gödel Prize in 2003 for their work. It can be used in conjunction with many other types of learning algorithms to improve their performance. The output of the other learning algorithms ('weak learners') is combined into a weighted sum that represents the final output of the boosted classifier. AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers. AdaBoost is sensitive to noisy data and outliers. In some problems it can be less susceptible to the overfitting problem than other learning algorithms. The individual learners can be weak, but as long as the performance of each one is slightly better than random guessing (e.g., their error rate is smaller than 0.5 for binary classification), the final model can be proven to converge to a strong learner.

    Every learning algorithm will tend to suit some problem types better than others, and will typically have many different parameters and configurations to be adjusted before achieving optimal performance on a dataset, AdaBoost (with decision trees as the weak learners) is often referred to as the best out-of-the-box classifier. When used with decision tree learning, information gathered at each stage of the AdaBoost algorithm about the relative 'hardness' of each training sample is fed into the tree growing algorithm such that later trees tend to focus on harder-to-classify examples.

2017b

• (Scikit Learn, 2017B) ⇒ http://scikit-learn.org/stable/modules/ensemble.html#AdaBoost Retrieved: 2017-10-22.
  • QUOTE: The module sklearn.ensemble includes the popular boosting algorithm AdaBoost, introduced in 1995 by Freund and Schapire [FS1995] .

    The core principle of AdaBoost is to fit a sequence of weak learners (i.e., models that are only slightly better than random guessing, such as small decision trees) on repeatedly modified versions of the data. The predictions from all of them are then combined through a weighted majority vote (or sum) to produce the final prediction. The data modifications at each so-called boosting iteration consist of applying weights [math]\displaystyle{ w_1, w_2,\cdots, w_N }[/math] to each of the training samples. Initially, those weights are all set to [math]\displaystyle{ w_i = 1/N }[/math], so that the first step simply trains a weak learner on the original data. For each successive iteration, the sample weights are individually modified and the learning algorithm is reapplied to the reweighted data. At a given step, those training examples that were incorrectly predicted by the boosted model induced at the previous step have their weights increased, whereas the weights are decreased for those that were predicted correctly. As iterations proceed, examples that are difficult to predict receive ever-increasing influence. Each subsequent weak learner is thereby forced to concentrate on the examples that are missed by the previous ones in the sequence [HTF].

     AdaBoost can be used both for classification and regression problems:

    • For multi-class classification, AdaBoostClassifier implements AdaBoost-SAMME and AdaBoost-SAMME.R [ZZRH2009].
    • For regression, AdaBoostRegressor implements AdaBoost.R2 [D1997].

2017c

• (Brown, 2017) ⇒ Gavin Brown. (2017). "Ensemble Learning." In: "Encyclopedia of Machine Learning and Data Mining"(Editors: Claude Sammut, Geoffrey I. Webb) pp 393-402
  • QUOTE: Adaboost (Freund and Schapire 1996) is the most well known of the Boosting family of algorithms (Schapire 2003). The algorithm trains models sequentially, with a new model trained at each round. At the end of each round, mis-classified examples are identified and have their emphasis increased in a new training set which is then fed back into the start of the next round, and a new model is trained. The idea is that subsequent models should be able to compensate for errors made by earlier models.

    Adaboost occupies somewhat of a special place in the history of ensemble methods. Though the procedure seems heuristic, the algorithm is in fact grounded in a rich learning-theoretic body of literature. (Schapire 1990) addressed a question posed by Kearns and Valiant (1988) on the nature of two complexity classes of learning problems. The two classes are strongly learnable and weakly learnable problems. Schapire showed that these classes were equivalent; this had the corollary that a weak model, performing only slightly better than random guessing, could be “boosted” into an arbitrarily accurate strong model. The original Boosting algorithm was a proof by construction of this equivalence, though had a number of impractical assumptions built-in. The Adaboost algorithm (Freund and Schapire 1996) was the first practical Boosting method. The authoritative historical account of the development can be found in Schapire (1999), including discussion of numerous variants and interpretations of the algorithm. The procedure is shown in Algorithm 2. Some similarities with Bagging are evident; a key differences is that at each round t, Bagging has a uniform distribution D t , while Adaboost adapts a nonuniform distribution.

2014

• http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Classification/adaboost#Implementation
  • Adaboost is part of ada package. In this section you find more information about installing and using it on R Environment. Type the following commands in R console to install and load the ada package:
install.packages("ada")
library("rpart")
library("ada")

    The function used to execute the algorithm adaboost is:
ada(x, y,test.x,test.y=NULL, loss=c("exponential","logistic"), type=c("discrete", "real", "gentle"), iter=50, nu=0.1, bag.frac=model.coef=TRUE, bag.shift=FALSE, max.iter=20, delta=10^(-10), verbose=...,na.action=na.rpart)

---