Learning linear threshold functions

This paper surveys recent theoretical results on algorithms for learning linear threshold functions (aka perceptrons, linear discriminants). When the examples are linearly separable, Littlestone has introduced algorithms that are much faster than the perceptron algorithm when there are many irrelevant attributes. When the examples are not linearly separable, Gallant´s Ratchet algorithm will converge to the optimal linear threshold function, albeit slowly, and Bylander´s perceptron-noise algorithm will converge quickly to optimal in the special case of classification noise. Empirical comparisons on some nonlinearly-separable real-world datasets are presented