Vapnik-Chervonenkis dimension of neural networks with binary weights
Authors:
- 1 April 1997
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 55 (4) , 4478-4488
Abstract
We investigate the Vapnik-Chervonenkis (VC) dimension of the perceptron and simple two-layer networks such as the committee and the parity machine with weights restricted to values ±1. For binary inputs, the VC dimension is determined by atypical pattern sets, i.e., it cannot be found by replica analysis or numerical Monte Carlo sampling. For small systems, exhaustive enumerations yield exact results. For systems that are too large for enumerations, number theoretic arguments give lower bounds for the VC dimension. For the Ising perceptron, the VC dimension is probably larger than N/2.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Statistical physics estimates for the complexity of feedforward neural networksPhysical Review E, 1995
- UNIFORM CONVERGENCE BOUNDS FOR LEARNING FROM EXAMPLESModern Physics Letters B, 1994
- Systems that can learn from examples: Replica calculation of uniform convergence bounds for perceptronsPhysical Review Letters, 1993
- Vapnik-Chervonenkis bounds for generalizationJournal of Physics A: General Physics, 1993
- Capacity of neural networks with discrete synaptic couplingsJournal of Physics A: General Physics, 1990
- Critical storage capacity of the J = ± 1 neural networkJournal of Physics A: General Physics, 1989
- What Size Net Gives Valid Generalization?Neural Computation, 1989
- On the density of families of setsJournal of Combinatorial Theory, Series A, 1972
- On the Uniform Convergence of Relative Frequencies of Events to Their ProbabilitiesTheory of Probability & Its Applications, 1971
- Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern RecognitionIEEE Transactions on Electronic Computers, 1965