LETTER Communicated by Peter Latham On the Classification Capability of Sign-Constrained

The perceptron (also referred to as McCulloch-Pitts neuron, or linear threshold gate) is commonly used as a simplified model for the discrimi-nation and learning capability of a biological neuron. Criteria that tell us when a perceptron can implement (or learn to implement) all possible di-chotomies 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 re-main fixed during learning (which is the case for most types of biological synapses). In particular, the VC-dimension of sign-constrained percep-trons is determined, and a necessary and sufficient criterion is provided that tells us when all 2m dichotomies over a given set ofm patterns can be learned by a sign-constrained perceptron. We also show that uniformity of L1 norms of input patterns is a sufficient condition for full represen-tation power in the case where all weights are required to be nonnega-tive. 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 par-ticular that sparse input patterns improve the classification capability of sign-constrained perceptrons.