Cargando…
Generic predictions of output probability based on complexities of inputs and outputs
For a broad class of input-output maps, arguments based on the coding theorem from algorithmic information theory (AIT) predict that simple (low Kolmogorov complexity) outputs are exponentially more likely to occur upon uniform random sampling of inputs than complex outputs are. Here, we derive prob...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group UK
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7064605/ https://www.ncbi.nlm.nih.gov/pubmed/32157160 http://dx.doi.org/10.1038/s41598-020-61135-7 |
_version_ | 1783504906545528832 |
---|---|
author | Dingle, Kamaludin Pérez, Guillermo Valle Louis, Ard A. |
author_facet | Dingle, Kamaludin Pérez, Guillermo Valle Louis, Ard A. |
author_sort | Dingle, Kamaludin |
collection | PubMed |
description | For a broad class of input-output maps, arguments based on the coding theorem from algorithmic information theory (AIT) predict that simple (low Kolmogorov complexity) outputs are exponentially more likely to occur upon uniform random sampling of inputs than complex outputs are. Here, we derive probability bounds that are based on the complexities of the inputs as well as the outputs, rather than just on the complexities of the outputs. The more that outputs deviate from the coding theorem bound, the lower the complexity of their inputs. Since the number of low complexity inputs is limited, this behaviour leads to an effective lower bound on the probability. Our new bounds are tested for an RNA sequence to structure map, a finite state transducer and a perceptron. The success of these new methods opens avenues for AIT to be more widely used. |
format | Online Article Text |
id | pubmed-7064605 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
publisher | Nature Publishing Group UK |
record_format | MEDLINE/PubMed |
spelling | pubmed-70646052020-03-19 Generic predictions of output probability based on complexities of inputs and outputs Dingle, Kamaludin Pérez, Guillermo Valle Louis, Ard A. Sci Rep Article For a broad class of input-output maps, arguments based on the coding theorem from algorithmic information theory (AIT) predict that simple (low Kolmogorov complexity) outputs are exponentially more likely to occur upon uniform random sampling of inputs than complex outputs are. Here, we derive probability bounds that are based on the complexities of the inputs as well as the outputs, rather than just on the complexities of the outputs. The more that outputs deviate from the coding theorem bound, the lower the complexity of their inputs. Since the number of low complexity inputs is limited, this behaviour leads to an effective lower bound on the probability. Our new bounds are tested for an RNA sequence to structure map, a finite state transducer and a perceptron. The success of these new methods opens avenues for AIT to be more widely used. Nature Publishing Group UK 2020-03-10 /pmc/articles/PMC7064605/ /pubmed/32157160 http://dx.doi.org/10.1038/s41598-020-61135-7 Text en © The Author(s) 2020 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/. |
spellingShingle | Article Dingle, Kamaludin Pérez, Guillermo Valle Louis, Ard A. Generic predictions of output probability based on complexities of inputs and outputs |
title | Generic predictions of output probability based on complexities of inputs and outputs |
title_full | Generic predictions of output probability based on complexities of inputs and outputs |
title_fullStr | Generic predictions of output probability based on complexities of inputs and outputs |
title_full_unstemmed | Generic predictions of output probability based on complexities of inputs and outputs |
title_short | Generic predictions of output probability based on complexities of inputs and outputs |
title_sort | generic predictions of output probability based on complexities of inputs and outputs |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7064605/ https://www.ncbi.nlm.nih.gov/pubmed/32157160 http://dx.doi.org/10.1038/s41598-020-61135-7 |
work_keys_str_mv | AT dinglekamaludin genericpredictionsofoutputprobabilitybasedoncomplexitiesofinputsandoutputs AT perezguillermovalle genericpredictionsofoutputprobabilitybasedoncomplexitiesofinputsandoutputs AT louisarda genericpredictionsofoutputprobabilitybasedoncomplexitiesofinputsandoutputs |