The Stochastic Complexity of Spin Models: Are Pairwise Models Really Simple?
Open Access
Abstract
Models can be simple for different reasons: because they yield a simple and computationally efficient interpretation of a generic dataset (e.g., in terms of pairwise dependencies)—as in statistical learning—or because they capture the laws of a specific phenomenon—as e.g., in physics—leading to non-trivial falsifiable predictions. In information theory, the simplicity of a model is quantified by the stochastic complexity, which measures the number of bits needed to encode its parameters. In order to understand how simple models look like, we study the stochastic complexity of spin models with interactions of arbitrary order. We show that bijections within the space of possible interactions preserve the stochastic complexity, which allows to partition the space of all models into equivalence classes. We thus found that the simplicity of a model is not determined by the order of the interactions, but rather by their mutual arrangements. Models where statistical dependencies are localized on non-overlapping groups of few variables are simple, affording predictions on independencies that are easy to falsify. On the contrary, fully connected pairwise models, which are often used in statistical learning, appear to be highly complex, because of their extended set of interactions, and they are hard to falsify.Keywords
All Related Versions
Funding Information
- Kavli Foundation and the Norwegian Research Council's Center of Excellence scheme (223262)
This publication has 32 references indexed in Scilit:
- Sparse model selection in the highly under-sampled regimeJournal of Statistical Mechanics: Theory and Experiment, 2016
- On the Sufficiency of Pairwise Interactions in Maximum Entropy Models of NetworksJournal of Statistical Physics, 2016
- Multivariate dependence and genetic networks inferenceIET Systems Biology, 2010
- High-dimensional Ising model selection using ℓ1-regularized logistic regressionThe Annals of Statistics, 2010
- Are we there yet?Neural Networks, 2010
- Top 10 algorithms in data miningKnowledge and Information Systems, 2007
- Stochastic Complexity in LearningJournal of Computer and System Sciences, 1997
- Statistical Inference, Occam's Razor, and Statistical Mechanics on the Space of Probability DistributionsNeural Computation, 1997
- Modeling by shortest data descriptionAutomatica, 1978
- Information Theory and Statistical MechanicsPhysical Review B, 1957