Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks

DOI10.1006/jcss.1997.1477zbMath0869.68088OpenAlexW2006698588WikidataQ56214754 ScholiaQ56214754MaRDI QIDQ676431

Marek Karpinski, Angus J. Macintyre

Publication date: 18 March 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:a14465ce-11d9-4f89-aeec-fcf0bea603ed

zbMATH Keywords

VC dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (31)

Deep learning: a statistical viewpoint ⋮ On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations ⋮ Descartes' Rule of Signs for Radial Basis Function Neural Networks ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ The Vapnik-Chervonenkis dimension of graph and recursive neural networks ⋮ On multivariate randomized classification trees: \(l_0\)-based sparsity, VC dimension and decomposition methods ⋮ Neural Networks with Local Receptive Fields and Superlinear VC Dimension ⋮ Theory of graph neural networks: representation and learning ⋮ Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations ⋮ A statistical learning theory approach for uncertain linear and bilinear matrix inequalities ⋮ Negative results for approximation using single layer and multilayer feedforward neural networks ⋮ CONVERGENCE OF A LEAST‐SQUARES MONTE CARLO ALGORITHM FOR AMERICAN OPTION PRICING WITH DEPENDENT SAMPLE DATA ⋮ Pfaffian Sets and O-minimality ⋮ On the stability and generalization of neural networks with VC dimension and fuzzy feature encoders ⋮ A tight upper bound on the generalization error of feedforward neural networks ⋮ Multiscale topology optimization using neural network surrogate models ⋮ Model Theory: Geometrical and Set-Theoretic Aspects and Prospects ⋮ Aspects of discrete mathematics and probability in the theory of machine learning ⋮ On the Capabilities of Higher-Order Neurons: A Radial Basis Function Approach ⋮ On the Complexity of Computing and Learning with Multiplicative Neural Networks ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory ⋮ Probabilistic solutions to some NP-hard matrix problems ⋮ Research on probabilistic methods for control system design ⋮ Randomized algorithms for the synthesis of cautious adaptive controllers ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ Vapnik-Chervonenkis dimension of recurrent neural networks ⋮ Partitioning points by parallel planes ⋮ On sharpness of error bounds for univariate approximation by single hidden layer feedforward neural networks ⋮ Transfer theorems via sign conditions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the computation of Boolean functions by analog circuits of bounded fan-in
• On the decidability of sparse univariate polynomial interpolation
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Feedforward nets for interpolation and classification
• A result of Vapnik with applications
• The elementary theory of restricted analytic fields with exponentiation
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Definable Sets in Ordered Structures. II
• Vapnik-Chervonenkis Classes of Definable Sets
• VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions
• Neural Nets with Superlinear VC-Dimension
• Finiteness results for sigmoidal “neural” networks
• Bounds for the computational power and learning complexity of analog neural nets
• Lower Bounds for Approximation by Nonlinear Manifolds
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
• An exact sequence in differential topology
• On the Betti Numbers of Real Varieties
• The measure of the critical values of differentiable maps

This page was built for publication: Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks