Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 45 / 3 / a

Table of contents
- Solution a

Solution

Use labels

y_{i} \in {- 1, 1}

and base predictions

G_{m} (x) \in {- 1, 1}

. The binary AdaBoost algorithm starts with observation weights

D_{1} (i) = 1/ n

and score

F_{0} (x) = 0

. For rounds

m = 1, \dots, M

Fit the weak learner to the training observations using weights $D_{m} (i)$ , producing $G_{m}$ .
Compute its weighted error $ϵ_{m} = \sum_{i} D_{m} (i) 1_{{G_{m} (x_{i}) \neq = y_{i}}}$ .
For $0 < ϵ_{m} < 1/2$ , choose $α_{m} = \frac{1}{2} lo g [(1 - ϵ_{m}) / ϵ_{m}]$ and update $F_{m} = F_{m - 1} + α_{m} G_{m}$ .
Reweight and normalize: $D_{m + 1} (i) = D_{m} (i) e^{- α_{m} y_{i} G_{m} (x_{i})} / Z_{m}$ , where $Z_{m}$ is the sum of the unnormalized weights.

The final classifier is

G (x) = sign {m = 1 \sum M α_{m} G_{m} (x)} .

(1)

Resolve a zero-score tie by a fixed convention. A classifier with error above

1/2

may be sign-reversed if the base class permits it; otherwise it fails the weak-learning requirement and should be replaced. Error

1/2

gives zero weight and no improvement. Error zero gives the limiting perfect-classifier step with infinite coefficient, so terminate with that classifier rather than computing the undefined finite update. Misclassified observations are multiplied by

e^{α_{m}}

and correctly classified observations by

e^{- α_{m}}

, increasing the relative weight of errors for the next round. The procedure is sequential, and its number of rounds is a tuning parameter.

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 45 / 3 / a

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 45 / 3 / a

Solution

 Ancestors (10)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion