Despite its age, the Perceptron algorithm is a simple and efficient learning
rule for margin classifiers. We present a generalization of the Perceptron
algorithm that can accommodate instance noise. The new algorithm performs a
Perceptron-style update whenever the margin of an example is smaller than a
predefined value. We derive worst case mistake bounds for our algorithm. As
a byproduct we obtain a new mistake bound for the Perceptron algorithm in the
inseparable case. To conclude, we demonstrate a usage of the algorithm for
finding a maximal margin separating hyperplane.
Short Course: Information Theory &
Statistics Bin Yu & Mark Hansen June 1, 2005
Colorado State University Campus
Fort Collins, CO 80523
Graybill Conference June 2-3, 2005
Hilton Fort Collins (Formerly: University Park Holiday- Inn)
Fort Collins, CO 80526
