Perceptron learning: the largest version space
Michael L. Biehl, Manfred Opper · 1995
We revisit the learning of a linearly separable rule with a single layer perceptron. The rule is taken to be correlated with a set of random training inputs, such that the concept is located in the largest of all version spaces. We formulate the corresponding statistical mechanics problem and study the model using the replica method. Replica symmetry is found to be broken, but the zero entropy approximation is interpreted as an estimate for the groundstate properties of the system. We investigate the typical overlap and generalization error in the largest version space and compare with the results for a typical random rule. The learning curves differ significantly, but preliminary studies indicate that the asymptotic decay of the generalization error with the number of examples could be the same apart from possible logarithmic corrections. 1. Introduction Feedforward neural networks 1;2 can serve as a tool for classification: an output value is assigned to any possible input of the ...