Minimum Description Length codes are critical

Abstract

In the Minimum Description Length (MDL) principle, learning from the data is equivalent to an optimal coding problem. We show that the codes that achieve optimal compression in MDL are critical in a very precise sense. First, when they are taken as generative models of samples, they generate samples with broad empirical distributions and with a high value of the relevance, defined as the entropy of the empirical frequencies. These results are derived for different statistical models (Dirichlet model, independent and pairwise dependent spin models, and restricted Boltzmann machines). Second, MDL codes sit precisely at a second order phase transition point where the symmetry between the sampled outcomes is spontaneously broken. The order parameter controlling the phase transition is the coding cost of the samples. The phase transition is a manifestation of the optimality of MDL codes, and it arises because codes that achieve a higher compression do not exist. These results suggest a clear interpretation of the widespread occurrence of statistical criticality as a characterization of samples which are maximally informative on the underlying generative process.

arXiv comment23 pages, 5 figures; Corrected the author name, revised Section 2.2 (Large Deviations of the Universal Codes Exhibit Phase Transitions), corrected Eq. (89)

References in corpus (11)

• Power laws, Pareto distributions and Zipf's law
• A universal model for mobility and migration patterns
• Are biological systems poised at criticality?
• Colloquium: Criticality and dynamical scaling in living systems
• A tutorial introduction to the minimum description length principle
• Zipf's law and criticality in multivariate data without fine-tuning
• Statistical Criticality arises in Most Informative Representations
• Criticality of mostly informative samples: A Bayesian model selection approach
• On the concentration of large deviations for fat tailed distributions, with application to financial data
• The Stochastic complexity of spin models: Are pairwise models really simple?
• Resolution and Relevance Trade-offs in Deep Learning

Cited by in corpus (9)

• Statistical Criticality arises in Most Informative Representations
• Quantifying Relevance in Learning and Inference
• Optimal Work Extraction and the Minimum Description Length Principle
• A random energy approach to deep learning
• The peculiar statistical mechanics of Optimal Learning Machines
• A New Spin on Color Quantization
• Filtering Statistics on Networks
• Maximal Relevance and Optimal Learning Machines
• Complex distributions emerging in filtering and compression