Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
arXiv:2109.08502 · doi:10.1088/1742-5468/ac312b
Abstract
The classification problem of structured data can be solved with different strategies: a supervised learning approach, starting from a labeled training set, and an unsupervised learning one, where only the structure of the patterns in the dataset is used to find a classification compatible with it. The two strategies can be interpreted as extreme cases of a semi-supervised approach to learn multi-view data, relevant for applications. In this paper I study the critical properties of the two storage problems associated with these tasks, in the case of the linear binary classification of doublets of points sharing the same label, within replica theory. While the first approach presents a SAT/UNSAT transition in a (marginally) stable replica-symmetric phase, in the second one the satisfiability line lies in a full replica-symmetry-broken phase. A similar behavior in the problem of learning with a margin is also pointed out.
arXiv comment20 pages + appendices, 8 figures
References in corpus (16)
- Universal Spectrum of Normal Modes in Low-Temperature Glasses: an Exact Solution
- Stability at Random Close Packing
- Classification and Geometry of General Perceptual Manifolds
- The simplest model of jamming
- Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
- Modelling the influence of data structure on learning in neural networks: the hidden manifold model
- Jamming in multilayer supervised learning models
- Critical jammed phase of the linear perceptron
- Intrinsic dimension estimation for locally undersampled data
- Statistical learning theory of structured data
- Techniques of replica symmetry breaking and the storage problem of the McCulloch-Pitts neuron
- Counting the learnable functions of structured data
- Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
- Beyond the storage capacity: data driven satisfiability transition
- Storage of correlated patterns in a perceptron
- Generalization from correlated sets of patterns in the perceptron