Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

Winter 1991, Vol. 3, No. 4, Pages 604-616
(doi: 10.1162/neco.1991.3.4.604)
© 1991 Massachusetts Institute of Technology
Learning the Unlearnable
Article PDF (496.14 KB)
Abstract

We present a local perceptron learning rule that either converges to a solution, or establishes linear nonseparability. We prove that when no solution exists, the algorithm detects this in a finite time (number of learning steps). This time is polynomial in typical cases and exponential in the worst case, when the set of patterns is nonstrictly linearly separable. The algorithm is local and has no arbitrary parameters.