On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm

摘要: In this paper we analyze the PAC learning abilities of several simple iterative algorithms for linear threshold functions, obtaining both positive and negative results. We show that Littlestone’s Winnow algorithm is not an efficient class functions. also prove Perceptron cannot efficiently learn unrestricted functions even under uniform distribution on boolean examples. However, can nested (a concept known to be hard arbitrary distributions) Finally, give a very Perceptron-like origin-centered halfspaces unit sphere in Unlike algorithm, which presence classification noise, new monotonic noise generalization noise). The significantly faster than previous settings.