AdaBoost Multiclass Classifier¶

AdaBoost (short for “Adaptive Boosting”) is a popular boosting classification algorithm. The AdaBoost algorithm performs well on a variety of data sets except some noisy data ([Friedman98], [Zhu2005]). The library supports two methods for the algorithms:

SAMME, or Stagewise Additive Modeling using a Multi-class Exponential loss function [Zhu2005]
SAMME.R, which is a modification of SAMME method for Real-valued returned probabilities from weak learner

Details¶

Given \(n\) feature vectors \(x_1 = (x_{11}, \ldots, x_{1p}), \ldots x_n = (x_{n1}, \ldots, x_{np})\) of size \(p\), a vector of class labels \(y = (y_1, \ldots, y_n)\) where \(y_i \in K = \{-1, 1\}\) in case of binary classification and \(y_i \in K = \{ 0, \ldots, C-1 \}\), where \(C\) is a number of classes, describes the class \(t\) the feature vector \(x_i\) belongs to, and \(h_t\) is a weak learner algorithm, the problem is to build an AdaBoost classifier.

Training Stage¶

The following scheme shows the major steps of the SAMME algorithm:

Initialize weights \(D_1(i) = \frac{1}{n}\) for \(i = 1, \ldots, n\)
For \(t = 1, \ldots, T\):
- Train the weak learner \(h_t(i)\) using weights \(D_t\).
- Choose a confidence value \(\alpha_t = \log \frac{1 - \mathrm{err}_t}{\mathrm{err}_t} + \log(C-1)\), where \(\mathrm{err}_t = \frac{\sum_{i=1}{n} D_t(i) I(y_i \neq h_t(i))}{\sum_{i=1}{n} D_t(i)}\)
- Update \(D_{t+1}(i) = \frac{D_t{i} \mathrm{exp}(-\alpha_t I(y_i \neq h_t(i)))}{Z_t}\), where \(Z_t\) is a normalization factor.
Output the final hypothesis:

\[H(x) = \underset{k} {\mathrm{argmax}} \sum_{t=1}^{T} \alpha_t I(h_t{x} = k)\]

Note

SAMME algorithm in case of binary classification is equal to the AdaBoost algorithm from [Friedman98].

Prediction Stage¶

Given the AdaBoost classifier and \(r\) feature vectors \(x_1, \ldots, x_r\), the problem is to calculate the final class \(H(x)\):

\[H(x) = \underset{k} {\mathrm{argmax}} \sum_{t=1}^{T} \alpha_t I(h_t{x} = k)\]

Batch Processing¶

AdaBoost classifier follows the general workflow described in Classification Usage Model.

Training¶

For a description of the input and output, refer to Classification Usage Model. At the training stage, an AdaBoost classifier has the following parameters:

Training Parameters for AdaBoost Multiclass Classifier (Batch Processing)¶
Parameter	Default Value	Description
`algorithmFPType`	`float`	The floating-point type that the algorithm uses for intermediate computations. Can be `float` or `double`.
`method`	`defaultDense`	Available methods for computation of the AdaBoost algorithm: `samme` - uses the classifier that returns labels as weak learner `sammeR` - uses the classifier that returns probabilities of belonging to class as weak learner `defaultDense` is equal to `samme` method
`weakLearnerTraining`	Pointer to an object of the classification stump training class	Pointer to the training algorithm of the weak learner. By default, a classification stump weak learner is used.
`weakLearnerPrediction`	Pointer to an object of the classification stump prediction class	Pointer to the prediction algorithm of the weak learner. By default, a classification stump weak learner is used.
`accuracyThreshold`	\(0.01\)	AdaBoost training accuracy.
`maxIterations`	\(100\)	The maximal number of iterations for the algorithm.
`learningRate`	\(1.0\)	Multiplier for each classifier to shrink its contribution.
`nClasses`	\(2\)	The number of classes.
`resultsToCompute`	\(0\)	The 64-bit integer flag that specifies which extra characteristics of AdaBoost to compute. Current version of the library only provides the following option: `computeWeakLearnersErrors`

Output¶

In addition to classifier output, AdaBoost calculates the result described below. Pass the Result ID as a parameter to the methods that access the result of your algorithm. For more details, see Algorithms.

Training Output for AdaBoost Multiclass Classifier (Batch Processing)¶
Result ID	Result
`weakLearnersErrors`	A numeric table \(1 \times \mathrm{maxIterations}\) containing weak learner’s classification errors computed when the `computeWeakLearnersErrors` option is on. Note By default, this result is an object of the `HomogenNumericTable` class, but you can define the result as an object of any class derived from `NumericTable`.

Prediction¶

For a description of the input and output, refer to Classification Usage Model. At the prediction stage, an AdaBoost classifier has the following parameters:

Prediction Parameters for AdaBoost Multiclass Classifier (Batch Processing)¶
Parameter	Default Value	Description
`algorithmFPType`	`float`	The floating-point type that the algorithm uses for intermediate computations. Can be `float` or `double`.
`method`	`defaultDense`	Performance-oriented computation method, the only method supported by the AdaBoost classifier at the prediction stage.
`weakLearnerPrediction`	Pointer to an object of the classification stump prediction class	Pointer to the prediction algorithm of the weak learner. By default, a classification stump weak learner is used.
`nClasses`	\(2\)	The number of classes.

Examples¶

Batch Processing:

oneDAL documentation