Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Boosting

Aliases: Ensemble learning

Keywords: boosting, classification, ensemble

Categories: Learning


Author(s): Chris Jeffery

A useful technique in binary classification, the separation of data into two classes. Boosting is a method of learning that builds an ensemble of weighted hypotheses generated by some weak learner that together form a more accurate hypothesis space.

Consider a problem where a collection of data has to be separated into two classes A and B, where some unknown function exists that maps each object of the data to it's classification.

Given a sample set and number of iterations k
Initially every object in the sample space is assigned a weighting to form a uniform distribution.
loop for i = 1 ... k

  1. A weak learner builds a hypothesis H(i) based on the weighted sample set
  2. A training error E(i) is calculated for H(i) over the data and the algorithm terminates if the error E(i) exceeds 0.5
  3. A weighting W(i) is assigned to H(i) as to minimise some loss function which is intended to relate to the expected misclassification of data not covered in the sample space.
  4. Each object of the sample space is then assigned a new weighting. The weighting of those which were misclassified being increased the most, while those which were furthest from the decision boundary are decreased. Weightings are then scaled as a distribution.

The final hypothesis is the average of all weighted hypotheses W(1)H(1) ... W(k)H(k)


Wikipedia: An entry on the boosting algorithm AdoBoost with psuedocode
www.boosting.org A large collection of information on boosting.


References:


Comments:

Add Comment

No comments.