|
NeuroCOLT
Technical Report NC-TR-96-024
Lower Bounds on
Identification Criteria for Perceptron-like Learning Rules
Michael
Schmitt
Institute for Theoretical Computer Science
Technische Universitaet Graz
Austria
Abstract
Topic of this paper is the computational complexity of identifying
neural weights using Perceptron-like learning rules. By Perceptron-like
rules we understand instructions to modify weight vectors by adding
or subtracting constant values after occurrence of an error. By computational
complexity we mean worst-case bounds on the number of correction steps.
The training examples are taken from Boolean functions computable
by McCulloch-Pitts neurons. Exact identification by the Perceptron
rule is known to take exponential time in the worst case. Therefore,
we define identification criteria that do not require that the learning
process exactly identifies the function being learned: PAC identification,
order identification, and sign identification. Our results show that
Perceptron-like learning rules cannot satisfy any of these criteria
when the number of correction steps is to be bounded by a polynomial.
This indicates that even by considerably lowering one's demands on
the learning process one cannot prevent Perceptron rules from being
computationally infeasible.
Download Compressed
Postscript
|