On the classification capability of sign-constrained perceptrons.
The perceptron (also referred to as McCulloch-Pitts neuron, or linear threshold gate) is commonly used as a simplified model for the discrimination and learning capability of a biological neuron. Criteria that tell us when a perceptron can implement (or learn to implement) all possible dichotomies over a given set of input patterns are well known, but only for the idealized case, where one assumes that the sign of a synaptic weight can be switched during learning. We present in this letter an analysis of the classification capability of the biologically more realistic model of a sign-constrained perceptron, where the signs of synaptic weights remain fixed during learning (which is the case for most types of biological synapses). In particular, the VC-dimension of sign-constrained perceptrons is determined, and a necessary and sufficient criterion is provided that tells us when all 2(m) dichotomies over a given set of m patterns can be learned by a sign-constrained perceptron. We also show that uniformity of L(1) norms of input patterns is a sufficient condition for full representation power in the case where all weights are required to be nonnegative. Finally, we exhibit cases where the sign constraint of a perceptron drastically reduces its classification capability. Our theoretical analysis is complemented by computer simulations, which demonstrate in particular that sparse input patterns improve the classification capability of sign-constrained perceptrons.
Legenstein
Robert
R
Institute for Theoretical Computer Science, Technische Universitaet Graz, A-8010 Graz, Austria. legi@igi.tugraz.at
Maass
Wolfgang
W
D000200:Action Potentials / Q000502:physiology; D000465:Algorithms; D001185:Artificial Intelligence; D001921:Brain / Q000502:physiology*; D003198:Computer Simulation; D007858:Learning / Q000502:physiology*; D009415:Nerve Net / Q000502:physiology*; D016571:Neural Networks, Computer; D009434:Neural Pathways / Q000502:physiology; D009474:Neurons / Q000502:physiology*; D009435:Synaptic Transmission / Q000502:physiology