Counting the learnable functions of structured data

Abstract

Cover's function counting theorem is a milestone in the theory of artificial neural networks. It provides an answer to the fundamental question of determining how many binary assignments (dichotomies) of $p$ points in $n$ dimensions can be linearly realized. Regrettably, it has proved hard to extend the same approach to more advanced problems than the classification of points. In particular, an emerging necessity is to find methods to deal with structured data, and specifically with non-pointlike patterns. A prominent case is that of invariant recognition, whereby identification of a stimulus is insensitive to irrelevant transformations on the inputs (such as rotations or changes in perspective in an image). An object is therefore represented by an extended perceptual manifold, consisting of inputs that are classified similarly. Here, we develop a function counting theory for structured data of this kind, by extending Cover's combinatorial technique, and we derive analytical expressions for the average number of dichotomies of generically correlated sets of patterns. As an application, we obtain a closed formula for the capacity of a binary classifier trained to distinguish general polytopes of any dimension. These results may help extend our theoretical understanding of generalization, feature extraction, and invariant object recognition by neural networks.

References in corpus (12)

• Estimating the intrinsic dimension of datasets by a minimal neighborhood information
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Classification and Geometry of General Perceptual Manifolds
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Linear Readout of Object Manifolds
• Intrinsic dimension estimation for locally undersampled data
• Statistical Physics and Representations in Real and Artificial Neural Networks
• Exploring the Function Space of Deep-Learning Machines
• Statistics of shared components in complex component systems
• Storage of correlated patterns in a perceptron
• Generalization from correlated sets of patterns in the perceptron

Cited by in corpus (16)

• Modelling the influence of data structure on learning in neural networks: the hidden manifold model
• The Gaussian equivalence of generative models for learning with shallow neural networks
• A statistical mechanics framework for Bayesian deep neural networks beyond the infinite-width limit
• Statistical learning theory of structured data
• Quantifying Relevance in Learning and Inference
• Beyond the storage capacity: data driven satisfiability transition
• Gaussian Universality of Perceptrons with Random Labels
• Linear Classification of Neural Manifolds with Correlated Variability
• Random geometric graphs in high dimension
• Random features and polynomial rules
• Inversion dynamics of class manifolds in deep learning reveals tradeoffs underlying generalisation
• Ray-based classification framework for high-dimensional data
• Optimal Learning with Excitatory and Inhibitory synapses
• Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
• Maximal Relevance and Optimal Learning Machines