On the VC-dimension of neural networks with binary weights

Abstract

We investigate the VC-dimension of the perceptron and simple two-layer networks like the committee- and the parity-machine with weights restricted to values $\pm 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$.

12 pages, LaTeX2e, 7 figures (eps)

References in corpus (5)

• Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
• Analytical and Numerical Study of Internal Representations in Multilayer Neural Networks with Binary Weights
• Multifractal Analysis of the Coupling Space of Feed-Forward Neural Networks
• Multifractality and percolation in the coupling space of perceptrons
• On the Vapnik-Chervonenkis dimension of the Ising-perceptron

Cited by in corpus (1)

• On the Vapnik-Chervonenkis dimension of the Ising-perceptron