Monthly
288 pp. per issue
6 x 9, illustrated
ISSN
0899-7667
E-ISSN
1530-888X
2014 Impact factor:
2.21

Neural Computation

November 1992, Vol. 4, No. 6, Pages 854-862
(doi: 10.1162/neco.1992.4.6.854)
© 1992 Massachusetts Institute of Technology
Tight Bounds on Transition to Perfect Generalization in Perceptrons
Article PDF (320.52 KB)
Abstract

“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.