Using the Perceptron Algorithm to Find Consistent Hypotheses
Martin Anthony, John S. Shawe-Taylor · Combinatorics Probability Computing · 1993
The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.