Neural Computation
“Sudden” transition to perfect generalization in binary perceptrons is investigated. Building on recent theoretical works of Gardner and Derrida (1989) and Baum and Lyuu (1991), we show the following: for α > αc = 1.44797 …, if α n examples are drawn from the uniform distribution on {+1, −1}n and classified according to a target perceptron wt ∈ {+1, −1}n as positive if wt · x ≥ 0 and negative otherwise, then the expected number of nontarget perceptrons consistent with the examples is 2−⊖(√n); the same number, however, grows exponentially 2⊖(n) if α < αc. Numerical calculations for n up to 1,000,002 are reported.