Generalization from correlated sets of patterns in the perceptron

Abstract

Generalization is a central aspect of learning theory. Here, we propose a framework that explores an auxiliary task-dependent notion of generalization, and attempts to quantitatively answer the following question: given two sets of patterns with a given degree of dissimilarity, how easily will a network be able to "unify" their interpretation? This is quantified by the volume of the configurations of synaptic weights that classify the two sets in a similar manner. To show the applicability of our idea in a concrete setting, we compute this quantity for the perceptron, a simple binary classifier, using the classical statistical physics approach in the replica-symmetric ansatz. In this case, we show how an analytical expression measures the "distance-based capacity", the maximum load of patterns sustainable by the network, at fixed dissimilarity between patterns and fixed allowed number of errors. This curve indicates that generalization is possible at any distance, but with decreasing capacity. We propose that a distance-based definition of generalization may be useful in numerical experiments with real-world neural networks, and to explore computationally sub-dominant sets of synaptic solutions.

References in corpus (12)

• A high-bias, low-variance introduction to Machine Learning for physicists
• Classification and Geometry of General Perceptual Manifolds
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
• Origin of the computational hardness for learning with binary synapses
• Linear Readout of Object Manifolds
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Zipf and Heaps laws from dependency structures in component systems
• Statistics of shared components in complex component systems
• Learning of correlated patterns by simple perceptrons
• Storage of correlated patterns in a perceptron

Cited by in corpus (7)

• Statistical learning theory of structured data
• Counting the learnable functions of structured data
• Beyond the storage capacity: data driven satisfiability transition
• Random geometric graphs in high dimension
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Random features and polynomial rules
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data