•Let X be a set of objects (eg., vectors in a high-dimensional space).
•Let C be a class of possible classifying functions (eg.,
hyperplanes).
–f in C: X-> {0,1}
–One of these correctly classifies all data.
•The learner is asked to classify an item in X, then told
the correct class.
•Eventually, learner determines correct f.
–Measure number of mistakes made.
–Worst case bound for learning strategy.
•