Statistical learning theory of structured data

Abstract

The traditional approach of statistical physics to supervised learning routinely assumes unrealistic generative models for the data: usually inputs are independent random variables, uncorrelated with their labels. Only recently, statistical physicists started to explore more complex forms of data, such as equally-labelled points lying on (possibly low dimensional) object manifolds. Here we provide a bridge between this recently-established research area and the framework of statistical learning theory, a branch of mathematics devoted to inference in machine learning. The overarching motivation is the inadequacy of the classic rigorous results in explaining the remarkable generalization properties of deep learning. We propose a way to integrate physical models of data into statistical learning theory, and address, with both combinatorial and statistical mechanics methods, the computation of the Vapnik-Chervonenkis entropy, which counts the number of different binary classifications compatible with the loss class. As a proof of concept, we focus on kernel machines and on two simple realizations of data structure introduced in recent physics literature: $k$-dimensional simplexes with prescribed geometric relations and spherical manifolds (equivalent to margin classification). Entropy, contrary to what happens for unstructured data, is nonmonotonic in the sample size, in contrast with the rigorous bounds. Moreover, data structure induces a novel transition beyond the storage capacity, which we advocate as a proxy of the nonmonotonicity, and ultimately a cue of low generalization error. The identification of a synaptic volume vanishing at the transition allows a quantification of the impact of data structure within replica theory, applicable in cases where combinatorial methods are not available, as we demonstrate for margin learning.

arXiv comment19 pages, 3 figures

References in corpus (19)

• A high-bias, low-variance introduction to Machine Learning for physicists
• Estimating the intrinsic dimension of datasets by a minimal neighborhood information
• Intrinsic dimension of data representations in deep neural networks
• 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
• Phase coexistence and finite-size scaling in random combinatorial problems
• Linear Readout of Object Manifolds
• Zipf and Heaps laws from dependency structures in component systems
• Intrinsic dimension estimation for locally undersampled data
• Devil's staircase phase diagram of the fractional quantum Hall effect in the thin-torus limit
• Statistics of shared components in complex component systems
• Counting the learnable functions of structured data
• Beyond the storage capacity: data driven satisfiability transition
• Random geometric graphs in high dimension
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• Generalization from correlated sets of patterns in the perceptron
• An exactly solvable random satisfiability problem
• Rademacher complexity and spin glasses: A link between the replica and statistical theories of learning

Cited by in corpus (16)

• A statistical mechanics framework for Bayesian deep neural networks beyond the infinite-width limit
• Probing transfer learning with a model of synthetic correlated datasets
• Activation function dependence of the storage capacity of treelike neural networks
• 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
• Space of Functions Computed by Deep-Layered Machines
• Inversion dynamics of class manifolds in deep learning reveals tradeoffs underlying generalisation
• 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?
• Satisfiability transition in asymmetric neural networks
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation