A decision-theoretic generalization of on-line learning and an application to boosting

Inside the paper

The problem

Online decision making requires allocating weight among alternatives before seeing each round's losses. In boosting, a related problem is how to combine weak classifiers without assuming their advantage is known in advance.

The idea

Update weights multiplicatively in response to observed losses, and adapt that idea to repeatedly focus a weak learner on difficult examples. Combine the resulting classifiers in a weighted vote.

How it works

• Start with a distribution of weights over the training examples and give it to a weak learning procedure.
• Measure the classifier's weighted error and assign its contribution to the final vote according to that error.
• Adjust the example weights so that examples the classifier got wrong receive more emphasis relative to those it classified correctly.
• Normalize the weights, train another classifier on the revised distribution, and repeat before taking the weighted vote.

What it showed

The paper bounds the training error of the combined classifier in terms of the errors of its components. It also develops extensions for multiclass classification and regression and analyzes a more general online allocation problem.

Read it for

Read Section 2 for the allocation setting and Section 4.1 for the boosting procedure; Section 4.2 explains its training-error guarantee. The extensions in Section 5 can be skimmed until you need a multiclass or regression setting.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.