Cargando…

Minimum Description Length Codes Are Critical

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Cubero, Ryan John, Marsili, Matteo, Roudi, Yasser
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7512318/
https://www.ncbi.nlm.nih.gov/pubmed/33265844
http://dx.doi.org/10.3390/e20100755
_version_ 1783586130396971008
author Cubero, Ryan John
Marsili, Matteo
Roudi, Yasser
author_facet Cubero, Ryan John
Marsili, Matteo
Roudi, Yasser
author_sort Cubero, Ryan John
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7512318
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-75123182020-11-09 Minimum Description Length Codes Are Critical Cubero, Ryan John Marsili, Matteo Roudi, Yasser Entropy (Basel) Article 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. MDPI 2018-10-01 /pmc/articles/PMC7512318/ /pubmed/33265844 http://dx.doi.org/10.3390/e20100755 Text en © 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Cubero, Ryan John
Marsili, Matteo
Roudi, Yasser
Minimum Description Length Codes Are Critical
title Minimum Description Length Codes Are Critical
title_full Minimum Description Length Codes Are Critical
title_fullStr Minimum Description Length Codes Are Critical
title_full_unstemmed Minimum Description Length Codes Are Critical
title_short Minimum Description Length Codes Are Critical
title_sort minimum description length codes are critical
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7512318/
https://www.ncbi.nlm.nih.gov/pubmed/33265844
http://dx.doi.org/10.3390/e20100755
work_keys_str_mv AT cuberoryanjohn minimumdescriptionlengthcodesarecritical
AT marsilimatteo minimumdescriptionlengthcodesarecritical
AT roudiyasser minimumdescriptionlengthcodesarecritical