| |
Abstract:
We describe a method for proving relative loss bounds for
on-line learning algorithms that use linear threshold functions for
classifying the examples. For instance the Perceptron algorithm and
Winnow are such learning algorithms. For classification problems
the discrete loss is used, i.e., the total number of prediction
mistakes. We introduce a continuous loss function called the linear
loss. Our method consists of first proving bounds w.r.t. the linear
loss and then converting these bounds to the discrete loss.
|
