The Transition to Perfect Generalization in Perceptrons

Several recent papers (Gardner and Derrida 1989; Gyiirgyi 1990; Sompolinsky et al. 1990) have found, using methods of statistical physics, that a transition to perfect generalization occurs in training a simple perceptron whose weights can only take values +/- 1. We give a rigorous proof of such a phenomena. That is, we show, for alpha = 2.0821, that if at least alpha n examples are drawn from the uniform distribution on {+1, -1}(n) and classified according to a target perceptron w(t) is an element of {+1, -1}(n) as positive or negative according to whether w(t). is nonnegative or negative, then the probability is 2(-(root n)) that there is any other such perceptron consistent with the examples. Numerical results indicate further that perfect generalization holds for alpha as low as 1.5.