1
|
Zenil H, Marshall JAR, Tegnér J. Approximations of algorithmic and structural complexity validate cognitive-behavioral experimental results. Front Comput Neurosci 2023; 16:956074. [PMID: 36761393 PMCID: PMC9904762 DOI: 10.3389/fncom.2022.956074] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/29/2022] [Accepted: 11/29/2022] [Indexed: 01/26/2023] Open
Abstract
Being able to objectively characterize the intrinsic complexity of behavioral patterns resulting from human or animal decisions is fundamental for deconvolving cognition and designing autonomous artificial intelligence systems. Yet complexity is difficult in practice, particularly when strings are short. By numerically approximating algorithmic (Kolmogorov) complexity (K), we establish an objective tool to characterize behavioral complexity. Next, we approximate structural (Bennett's Logical Depth) complexity (LD) to assess the amount of computation required for generating a behavioral string. We apply our toolbox to three landmark studies of animal behavior of increasing sophistication and degree of environmental influence, including studies of foraging communication by ants, flight patterns of fruit flies, and tactical deception and competition (e.g., predator-prey) strategies. We find that ants harness the environmental condition in their internal decision process, modulating their behavioral complexity accordingly. Our analysis of flight (fruit flies) invalidated the common hypothesis that animals navigating in an environment devoid of stimuli adopt a random strategy. Fruit flies exposed to a featureless environment deviated the most from Levy flight, suggesting an algorithmic bias in their attempt to devise a useful (navigation) strategy. Similarly, a logical depth analysis of rats revealed that the structural complexity of the rat always ends up matching the structural complexity of the competitor, with the rats' behavior simulating algorithmic randomness. Finally, we discuss how experiments on how humans perceive randomness suggest the existence of an algorithmic bias in our reasoning and decision processes, in line with our analysis of the animal experiments. This contrasts with the view of the mind as performing faulty computations when presented with randomized items. In summary, our formal toolbox objectively characterizes external constraints on putative models of the "internal" decision process in humans and animals.
Collapse
Affiliation(s)
- Hector Zenil
- Machine Learning Group, Department of Chemical Engineering and Biotechnology, University of Cambridge, Cambridge, United Kingdom
- Kellogg College, University of Oxford, Oxford, United Kingdom
- Oxford Immune Algorithmics Ltd., Oxford, United Kingdom
| | - James A. R. Marshall
- Complex Systems Modelling Research Group, Department of Computer Science, University of Sheffield, Sheffield, United Kingdom
| | - Jesper Tegnér
- Living Systems Laboratory, Biological and Environmental Science and Engineering Division, King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
| |
Collapse
|
2
|
Abstract
Cancers are complex adaptive diseases regulated by the nonlinear feedback systems between genetic instabilities, environmental signals, cellular protein flows, and gene regulatory networks. Understanding the cybernetics of cancer requires the integration of information dynamics across multidimensional spatiotemporal scales, including genetic, transcriptional, metabolic, proteomic, epigenetic, and multi-cellular networks. However, the time-series analysis of these complex networks remains vastly absent in cancer research. With longitudinal screening and time-series analysis of cellular dynamics, universally observed causal patterns pertaining to dynamical systems, may self-organize in the signaling or gene expression state-space of cancer triggering processes. A class of these patterns, strange attractors, may be mathematical biomarkers of cancer progression. The emergence of intracellular chaos and chaotic cell population dynamics remains a new paradigm in systems medicine. As such, chaotic and complex dynamics are discussed as mathematical hallmarks of cancer cell fate dynamics herein. Given the assumption that time-resolved single-cell datasets are made available, a survey of interdisciplinary tools and algorithms from complexity theory, are hereby reviewed to investigate critical phenomena and chaotic dynamics in cancer ecosystems. To conclude, the perspective cultivates an intuition for computational systems oncology in terms of nonlinear dynamics, information theory, inverse problems, and complexity. We highlight the limitations we see in the area of statistical machine learning but the opportunity at combining it with the symbolic computational power offered by the mathematical tools explored.
Collapse
Affiliation(s)
| | - Hector Zenil
- Machine Learning Group, Department of Chemical Engineering and Biotechnology, The University of Cambridge, Cambridge, United Kingdom
- The Alan Turing Institute, British Library, London, United Kingdom
- Oxford Immune Algorithmics, Reading, United Kingdom
- Algorithmic Dynamics Lab, Karolinska Institute, Stockholm, Sweden
- Algorithmic Nature Group, LABORES, Paris, France
- *Correspondence: Hector Zenil,
| |
Collapse
|
3
|
Abrahão FS, Zenil H. Emergence and algorithmic information dynamics of systems and observers. Philos Trans A Math Phys Eng Sci 2022; 380:20200429. [PMID: 35599568 PMCID: PMC9125223 DOI: 10.1098/rsta.2020.0429] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/07/2023]
Abstract
One of the challenges of defining emergence is that one observer's prior knowledge may cause a phenomenon to present itself as emergent that to another observer appears reducible. By formalizing the act of observing as mutual perturbations between dynamical systems, we demonstrate that the emergence of algorithmic information does depend on the observer's formal knowledge, while being robust vis-a-vis other subjective factors, particularly: the choice of programming language and method of measurement; errors or distortions during the observation; and the informational cost of processing. This is called observer-dependent emergence (ODE). In addition, we demonstrate that the unbounded and rapid increase of emergent algorithmic information implies asymptotically observer-independent emergence (AOIE). Unlike ODE, AOIE is a type of emergence for which emergent phenomena will be considered emergent no matter what formal theory an observer might bring to bear. We demonstrate the existence of an evolutionary model that displays the diachronic variant of AOIE and a network model that displays the holistic variant of AOIE. Our results show that, restricted to the context of finite discrete deterministic dynamical systems, computable systems and irreducible information content measures, AOIE is the strongest form of emergence that formal theories can attain. This article is part of the theme issue 'Emergent phenomena in complex physical and socio-technical systems: from cells to societies'.
Collapse
Affiliation(s)
- Felipe S. Abrahão
- National Laboratory for Scientific Computing (LNCC), 25651-075 Petropolis, Rio de Janeiro, Brazil
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, 75005 Paris, France
| | - Hector Zenil
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, 75005 Paris, France
- Oxford Immune Algorithmics, RG1 3EU Reading, UK
- The Alan Turing Institute, British Library 2QR, 96 Euston Rd, London NW1 2DB, UK
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Karolinska Institutet, 171 77 Stockholm, Sweden
| |
Collapse
|
4
|
Abstract
One of the challenges of defining emergence is that one observer's prior knowledge may cause a phenomenon to present itself as emergent that to another observer appears reducible. By formalizing the act of observing as mutual perturbations between dynamical systems, we demonstrate that the emergence of algorithmic information does depend on the observer's formal knowledge, while being robust vis-a-vis other subjective factors, particularly: the choice of programming language and method of measurement; errors or distortions during the observation; and the informational cost of processing. This is called observer-dependent emergence (ODE). In addition, we demonstrate that the unbounded and rapid increase of emergent algorithmic information implies asymptotically observer-independent emergence (AOIE). Unlike ODE, AOIE is a type of emergence for which emergent phenomena will be considered emergent no matter what formal theory an observer might bring to bear. We demonstrate the existence of an evolutionary model that displays the diachronic variant of AOIE and a network model that displays the holistic variant of AOIE. Our results show that, restricted to the context of finite discrete deterministic dynamical systems, computable systems and irreducible information content measures, AOIE is the strongest form of emergence that formal theories can attain. This article is part of the theme issue 'Emergent phenomena in complex physical and socio-technical systems: from cells to societies'.
Collapse
Affiliation(s)
- Felipe S Abrahão
- National Laboratory for Scientific Computing (LNCC), 25651-075 Petropolis, Rio de Janeiro, Brazil
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, 75005 Paris, France
| | - Hector Zenil
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, 75005 Paris, France
- Oxford Immune Algorithmics, RG1 3EU Reading, UK
- The Alan Turing Institute, British Library 2QR, 96 Euston Rd, London NW1 2DB, UK
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Karolinska Institute, 171 77 Stockholm, Sweden
| |
Collapse
|
5
|
Zenil H. AIM and Causality for Precision and Value-Based Healthcare. Artif Intell Med 2022. [DOI: 10.1007/978-3-030-64573-1_294] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
|
6
|
Hernández-Orozco S, Zenil H, Riedel J, Uccello A, Kiani NA, Tegnér J. Algorithmic Probability-Guided Machine Learning on Non-Differentiable Spaces. Front Artif Intell 2021; 3:567356. [PMID: 33733213 PMCID: PMC7944352 DOI: 10.3389/frai.2020.567356] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/29/2020] [Accepted: 11/19/2020] [Indexed: 11/20/2022] Open
Abstract
We show how complexity theory can be introduced in machine learning to help bring together apparently disparate areas of current research. We show that this model-driven approach may require less training data and can potentially be more generalizable as it shows greater resilience to random attacks. In an algorithmic space the order of its element is given by its algorithmic probability, which arises naturally from computable processes. We investigate the shape of a discrete algorithmic space when performing regression or classification using a loss function parametrized by algorithmic complexity, demonstrating that the property of differentiation is not required to achieve results similar to those obtained using differentiable programming approaches such as deep learning. In doing so we use examples which enable the two approaches to be compared (small, given the computational power required for estimations of algorithmic complexity). We find and report that 1) machine learning can successfully be performed on a non-smooth surface using algorithmic complexity; 2) that solutions can be found using an algorithmic-probability classifier, establishing a bridge between a fundamentally discrete theory of computability and a fundamentally continuous mathematical theory of optimization methods; 3) a formulation of an algorithmically directed search technique in non-smooth manifolds can be defined and conducted; 4) exploitation techniques and numerical methods for algorithmic search to navigate these discrete non-differentiable spaces can be performed; in application of the (a) identification of generative rules from data observations; (b) solutions to image classification problems more resilient against pixel attacks compared to neural networks; (c) identification of equation parameters from a small data-set in the presence of noise in continuous ODE system problem, (d) classification of Boolean NK networks by (1) network topology, (2) underlying Boolean function, and (3) number of incoming edges.
Collapse
Affiliation(s)
- Santiago Hernández-Orozco
- Facultad de Ciencias, Universidad Nacional Autónoma de México, Mexico City, Mexico.,Oxford Immune Algorithmics, Oxford, United Kingdom
| | - Hector Zenil
- Oxford Immune Algorithmics, Oxford, United Kingdom.,Algorithmic Dynamics Lab, Unit of Computational Medicine, Karolinska Institutet, Solna, Sweden.,Algorithmic Nature Group, LABORES, Paris, France.,King Abdullah University of Science and Technology (KAUST), Computer, Electrical and Mathematical Sciences and Engineering, Thuwal, Saudi Arabia
| | - Jürgen Riedel
- Oxford Immune Algorithmics, Oxford, United Kingdom.,Algorithmic Nature Group, LABORES, Paris, France
| | - Adam Uccello
- Algorithmic Nature Group, LABORES, Paris, France
| | - Narsis A Kiani
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Karolinska Institutet, Solna, Sweden.,Algorithmic Nature Group, LABORES, Paris, France
| | - Jesper Tegnér
- King Abdullah University of Science and Technology (KAUST), Computer, Electrical and Mathematical Sciences and Engineering, Thuwal, Saudi Arabia
| |
Collapse
|
7
|
Zenil H. AIM and Causality for Precision and Value Based Healthcare. Artif Intell Med 2021. [DOI: 10.1007/978-3-030-58080-3_294-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/28/2022]
|
8
|
Zenil H. A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions. Entropy (Basel) 2020; 22:e22060612. [PMID: 33286384 PMCID: PMC7517143 DOI: 10.3390/e22060612] [Citation(s) in RCA: 10] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 04/30/2020] [Revised: 05/17/2020] [Accepted: 05/23/2020] [Indexed: 12/19/2022]
Abstract
Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently co-exist for the first time and are here reviewed, ranging from dominant ones such as statistical lossless compression to newer approaches that advance, complement and also pose new challenges and may exhibit their own limitations. Evidence suggesting that these different methods complement each other for different regimes is presented and despite their many challenges, some of these methods can be better motivated by and better grounded in the principles of algorithmic information theory. It will be explained how different approaches to algorithmic complexity can explore the relaxation of different necessary and sufficient conditions in their pursuit of numerical applicability, with some of these approaches entailing greater risks than others in exchange for greater relevance. We conclude with a discussion of possible directions that may or should be taken into consideration to advance the field and encourage methodological innovation, but more importantly, to contribute to scientific discovery. This paper also serves as a rebuttal of claims made in a previously published minireview by another author, and offers an alternative account.
Collapse
Affiliation(s)
- Hector Zenil
- Algorithmic Dynamics Lab, Karolinska Institute, 171 77 Stockholm, Sweden;
- Oxford Immune Algorithmics, Reading RG1 3EU, UK
- Algorithmic Nature Group, LABORES, 75006 Paris, France
| |
Collapse
|
9
|
|
10
|
Gholami N, Dehshibi MM, Adamatzky A, Rueda-Toicen A, Zenil H, Fazlali M, Masip D. A Novel Method for Reconstructing CT Images in GATE/GEANT4 with Application in Medical Imaging: A Complexity Analysis Approach. ACTA ACUST UNITED AC 2020. [DOI: 10.2197/ipsjjip.28.161] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/05/2022]
Affiliation(s)
| | - Mohammad Mahdi Dehshibi
- Department of Computer Science, Multimedia and Telecommunication, Universitat Oberta de Catalunya
| | - Andrew Adamatzky
- Unconventional Computing Laboratory, University of the West of England
| | | | - Hector Zenil
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Centre for Molecular Medicine, Department of Medicine Solna, Karolinska Institute
- Oxford Immune Algorithmics, Oxford University Innovation
| | | | - David Masip
- Department of Computer Science, Multimedia and Telecommunication, Universitat Oberta de Catalunya
| |
Collapse
|
11
|
Zenil H, Minary P. Training-free measures based on algorithmic probability identify high nucleosome occupancy in DNA sequences. Nucleic Acids Res 2019; 47:e129. [PMID: 31511887 PMCID: PMC6846163 DOI: 10.1093/nar/gkz750] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/10/2019] [Revised: 07/10/2019] [Accepted: 08/27/2019] [Indexed: 01/01/2023] Open
Abstract
We introduce and study a set of training-free methods of an information-theoretic and algorithmic complexity nature that we apply to DNA sequences to identify their potential to identify nucleosomal binding sites. We test the measures on well-studied genomic sequences of different sizes drawn from different sources. The measures reveal the known in vivo versus in vitro predictive discrepancies and uncover their potential to pinpoint high and low nucleosome occupancy. We explore different possible signals within and beyond the nucleosome length and find that the complexity indices are informative of nucleosome occupancy. We found that, while it is clear that the gold standard Kaplan model is driven by GC content (by design) and by k-mer training; for high occupancy, entropy and complexity-based scores are also informative and can complement the Kaplan model.
Collapse
Affiliation(s)
- Hector Zenil
- Oxford Immune Algorithmics, Oxford University Innovation, Oxford, UK
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Center for Molecular Medicine, Karolinska Institute, Stockholm, Sweden
- Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, Paris, France
- Department of Computer Science, University of Oxford, Oxford, UK
| | - Peter Minary
- Department of Computer Science, University of Oxford, Oxford, UK
| |
Collapse
|
12
|
Zenil H, Kiani NA, Marabita F, Deng Y, Elias S, Schmidt A, Ball G, Tegnér J. An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems. iScience 2019; 19:1160-1172. [PMID: 31541920 PMCID: PMC6831824 DOI: 10.1016/j.isci.2019.07.043] [Citation(s) in RCA: 19] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/03/2018] [Revised: 04/27/2019] [Accepted: 07/26/2019] [Indexed: 12/26/2022] Open
Abstract
We introduce and develop a method that demonstrates that the algorithmic information content of a system can be used as a steering handle in the dynamical phase space, thus affording an avenue for controlling and reprogramming systems. The method consists of applying a series of controlled interventions to a networked system while estimating how the algorithmic information content is affected. We demonstrate the method by reconstructing the phase space and their generative rules of some discrete dynamical systems (cellular automata) serving as controlled case studies. Next, the model-based interventional or causal calculus is evaluated and validated using (1) a huge large set of small graphs, (2) a number of larger networks with different topologies, and finally (3) biological networks derived from a widely studied and validated genetic network (E. coli) as well as on a significant number of differentiating (Th17) and differentiated human cells from a curated biological network data.
Collapse
Affiliation(s)
- Hector Zenil
- Algorithmic Dynamics Lab, Center for Molecular Medicine, Karolinska Institutet, Stockholm 171 76, Sweden; Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Oxford Immune Algorithmics, Reading RG1 3EU, UK; Science for Life Laboratory, Solna 171 65, Sweden; Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, Paris 75006, France.
| | - Narsis A Kiani
- Algorithmic Dynamics Lab, Center for Molecular Medicine, Karolinska Institutet, Stockholm 171 76, Sweden; Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden; Algorithmic Nature Group, LABORES for the Natural and Digital Sciences, Paris 75006, France
| | - Francesco Marabita
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden
| | - Yue Deng
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden
| | - Szabolcs Elias
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden
| | - Angelika Schmidt
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden
| | - Gordon Ball
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden
| | - Jesper Tegnér
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Karolinska Institutet, Solna, Stockholm 171 76, Sweden; Science for Life Laboratory, Solna 171 65, Sweden; Biological and Environmental Sciences and Engineering Division, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Kingdom of Saudi Arabia
| |
Collapse
|
13
|
Zenil H, Kiani NA, Tegnér J. The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy. Entropy (Basel) 2019; 21:e21060560. [PMID: 33267274 PMCID: PMC7515049 DOI: 10.3390/e21060560] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 04/09/2019] [Revised: 05/17/2019] [Accepted: 05/20/2019] [Indexed: 12/03/2022]
Abstract
The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent collapses cases confounding all distinct degrees of randomness and pseudo-randomness, here we take into consideration the generative mechanism of the systems considered in the ensemble to separate objects that may comply with the principle under some restriction and whose entropy is maximal but may be generated recursively from those that are actually algorithmically random offering a refinement to classical Maxent. We take advantage of a causal algorithmic calculus to derive a thermodynamic-like result based on how difficult it is to reprogram a computer code. Using the distinction between computable and algorithmic randomness, we quantify the cost in information loss associated with reprogramming. To illustrate this, we apply the algorithmic refinement to Maxent on graphs and introduce a Maximal Algorithmic Randomness Preferential Attachment (MARPA) Algorithm, a generalisation over previous approaches. We discuss practical implications of evaluation of network randomness. Our analysis provides insight in that the reprogrammability asymmetry appears to originate from a non-monotonic relationship to algorithmic probability. Our analysis motivates further analysis of the origin and consequences of the aforementioned asymmetries, reprogrammability, and computation.
Collapse
Affiliation(s)
- Hector Zenil
- Algorithmic Dynamics Lab, Karolinska Institute, 17177 Stockholm, Sweden
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden
- Algorithmic Nature Group, Laboratory of Scientific Research (LABORES) for the Natural and Digital Sciences, 75006 Paris, France
- Oxford Immune Algorithmics, Oxford University Innovation, Reading RG1 7TT, UK
- Biological and Environmental Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
- Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
- Correspondence:
| | - Narsis A. Kiani
- Algorithmic Dynamics Lab, Karolinska Institute, 17177 Stockholm, Sweden
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden
- Algorithmic Nature Group, Laboratory of Scientific Research (LABORES) for the Natural and Digital Sciences, 75006 Paris, France
| | - Jesper Tegnér
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, 17177 Stockholm, Sweden
- Biological and Environmental Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
- Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
| |
Collapse
|
14
|
|
15
|
Zenil H, Hernández-Orozco S, Kiani NA, Soler-Toscano F, Rueda-Toicen A, Tegnér J. A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity. Entropy (Basel) 2018; 20:e20080605. [PMID: 33265694 PMCID: PMC7513128 DOI: 10.3390/e20080605] [Citation(s) in RCA: 23] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 04/28/2018] [Revised: 06/18/2018] [Accepted: 07/31/2018] [Indexed: 12/28/2022]
Abstract
We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff–Levin’s theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages—Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell—and an online algorithmic complexity calculator.
Collapse
Affiliation(s)
- Hector Zenil
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
- Department of Computer Science, University of Oxford, Oxford OX1 3QD, UK
- Correspondence:
| | - Santiago Hernández-Orozco
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM), Mexico City 04510, Mexico
| | - Narsis A. Kiani
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
| | | | - Antonio Rueda-Toicen
- Algorithmic Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute and SciLifeLab, SE-171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
- Instituto Nacional de Bioingeniería, Universidad Central de Venezuela, Caracas 1051, Venezuela
| | - Jesper Tegnér
- Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab and Karolinska Institute, Stockholm SE-171 77, Sweden
- Biological and Environmental Sciences and Engineering Division, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
| |
Collapse
|
16
|
Hernández-Orozco S, Kiani NA, Zenil H. Algorithmically probable mutations reproduce aspects of evolution, such as convergence rate, genetic memory and modularity. R Soc Open Sci 2018; 5:180399. [PMID: 30225028 PMCID: PMC6124114 DOI: 10.1098/rsos.180399] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/16/2018] [Accepted: 07/20/2018] [Indexed: 05/07/2023]
Abstract
Natural selection explains how life has evolved over millions of years from more primitive forms. The speed at which this happens, however, has sometimes defied formal explanations when based on random (uniformly distributed) mutations. Here, we investigate the application of a simplicity bias based on a natural but algorithmic distribution of mutations (no recombination) in various examples, particularly binary matrices, in order to compare evolutionary convergence rates. Results both on synthetic and on small biological examples indicate an accelerated rate when mutations are not statistically uniform but algorithmically uniform. We show that algorithmic distributions can evolve modularity and genetic memory by preservation of structures when they first occur sometimes leading to an accelerated production of diversity but also to population extinctions, possibly explaining naturally occurring phenomena such as diversity explosions (e.g. the Cambrian) and massive extinctions (e.g. the End Triassic) whose causes are currently a cause for debate. The natural approach introduced here appears to be a better approximation to biological evolution than models based exclusively upon random uniform mutations, and it also approaches a formal version of open-ended evolution based on previous formal results. These results validate some suggestions in the direction that computation may be an equally important driver of evolution. We also show that inducing the method on problems of optimization, such as genetic algorithms, has the potential to accelerate convergence of artificial evolutionary algorithms.
Collapse
Affiliation(s)
- Santiago Hernández-Orozco
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM), Mexico
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Department of Medicine Solna, Centre for Molecular Medicine, Stockholm, Sweden
- Algorithmic Nature Group, LABORES, Paris, France
| | - Narsis A. Kiani
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Department of Medicine Solna, Centre for Molecular Medicine, Stockholm, Sweden
- Algorithmic Nature Group, LABORES, Paris, France
| | - Hector Zenil
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Department of Medicine Solna, Centre for Molecular Medicine, Stockholm, Sweden
- Algorithmic Nature Group, LABORES, Paris, France
| |
Collapse
|
17
|
Zenil H, Kiani NA, Tegnér J. A Review of Graph and Network Complexity from an Algorithmic Information Perspective. Entropy (Basel) 2018; 20:e20080551. [PMID: 33265640 PMCID: PMC7513075 DOI: 10.3390/e20080551] [Citation(s) in RCA: 27] [Impact Index Per Article: 4.5] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 06/21/2018] [Revised: 07/18/2018] [Accepted: 07/20/2018] [Indexed: 11/22/2022]
Abstract
Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.
Collapse
Affiliation(s)
- Hector Zenil
- Algorithmic Dynamics Lab, Centre for Molecular Medicine, Karolinska Institute, 171 77 Stockholm, Sweden
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden
- Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
- Biological and Environmental Sciences and Engineering Division (BESE), King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
- Correspondence: or
| | - Narsis A. Kiani
- Algorithmic Dynamics Lab, Centre for Molecular Medicine, Karolinska Institute, 171 77 Stockholm, Sweden
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden
- Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
| | - Jesper Tegnér
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute, 171 77 Stockholm, Sweden
- Science for Life Laboratory (SciLifeLab), 171 77 Stockholm, Sweden
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique (LABORES) for the Natural and Digital Sciences, 75005 Paris, France
- Biological and Environmental Sciences and Engineering Division (BESE), King Abdullah University of Science and Technology (KAUST), Thuwal 23955, Saudi Arabia
| |
Collapse
|
18
|
Vallverdú J, Castro O, Mayne R, Talanov M, Levin M, Baluška F, Gunji Y, Dussutour A, Zenil H, Adamatzky A. Corrigendum to “Slime mould: The fundamental mechanisms of biological cognition” [BioSystems 165 (2018) 57–70]. Biosystems 2018; 166:66. [DOI: 10.1016/j.biosystems.2018.02.002] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/18/2022]
|
19
|
Vallverdú J, Castro O, Mayne R, Talanov M, Levin M, Baluška F, Gunji Y, Dussutour A, Zenil H, Adamatzky A. Slime mould: The fundamental mechanisms of biological cognition. Biosystems 2018; 165:57-70. [DOI: 10.1016/j.biosystems.2017.12.011] [Citation(s) in RCA: 38] [Impact Index Per Article: 6.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/01/2017] [Revised: 12/18/2017] [Accepted: 12/20/2017] [Indexed: 01/27/2023]
|
20
|
Abstract
Is undecidability a requirement for open-ended evolution (OEE)? Using methods derived from algorithmic complexity theory, we propose robust computational definitions of open-ended evolution and the adaptability of computable dynamical systems. Within this framework, we show that decidability imposes absolute limits on the stable growth of complexity in computable dynamical systems. Conversely, systems that exhibit (strong) open-ended evolution must be undecidable, establishing undecidability as a requirement for such systems. Complexity is assessed in terms of three measures: sophistication, coarse sophistication, and busy beaver logical depth. These three complexity measures assign low complexity values to random (incompressible) objects. As time grows, the stated complexity measures allow for the existence of complex states during the evolution of a computable dynamical system. We show, however, that finding these states involves undecidable computations. We conjecture that for similar complexity measures that assign low complexity values, decidability imposes comparable limits on the stable growth of complexity, and that such behavior is necessary for nontrivial evolutionary systems. We show that the undecidability of adapted states imposes novel and unpredictable behavior on the individuals or populations being modeled. Such behavior is irreducible. Finally, we offer an example of a system, first proposed by Chaitin, that exhibits strong OEE.
Collapse
Affiliation(s)
- Santiago Hernández-Orozco
- * Department of Mathematics, Universidad Nacional Autónoma de México, Ciudad Universitaria, Ciudad de México, México 04510. Posgrado en Ciencias e Ingeniería de la Computación, Universidad Nacional Autónoma de México. E-mail:
| | - Francisco Hernández-Quiroz
- Department of Mathematics, Universidad Nacional Autónoma de México, Ciudad Universitaria, Ciudad de México, México 04510. Posgrado en Ciencias e Ingeniería de la Computación, Universidad Nacional Autónoma de México. E-mail:
| | - Hector Zenil
- Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLifeLab, Karolinska Institute, Karolinska Hospital L8:05, SE-171 76, Stockholm, Sweden. E-mail:
| |
Collapse
|
21
|
Adamatzky A, Akl S, Burgin M, Calude CS, Costa JF, Dehshibi MM, Gunji YP, Konkoli Z, MacLennan B, Marchal B, Margenstern M, Martínez GJ, Mayne R, Morita K, Schumann A, Sergeyev YD, Sirakoulis GC, Stepney S, Svozil K, Zenil H. East-West paths to unconventional computing. Prog Biophys Mol Biol 2017; 131:469-493. [PMID: 28818636 DOI: 10.1016/j.pbiomolbio.2017.08.004] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/01/2017] [Revised: 08/04/2017] [Accepted: 08/08/2017] [Indexed: 01/29/2023]
Abstract
Unconventional computing is about breaking boundaries in thinking, acting and computing. Typical topics of this non-typical field include, but are not limited to physics of computation, non-classical logics, new complexity measures, novel hardware, mechanical, chemical and quantum computing. Unconventional computing encourages a new style of thinking while practical applications are obtained from uncovering and exploiting principles and mechanisms of information processing in and functional properties of, physical, chemical and living systems; in particular, efficient algorithms are developed, (almost) optimal architectures are designed and working prototypes of future computing devices are manufactured. This article includes idiosyncratic accounts of 'unconventional computing' scientists reflecting on their personal experiences, what attracted them to the field, their inspirations and discoveries.
Collapse
Affiliation(s)
- Andrew Adamatzky
- Unconventional Computing Centre, University of the West of England, Bristol, UK; Unconventional Computing Ltd, Bristol, UK.
| | - Selim Akl
- School of Computing, Queen's University, Kingston, Ontario, Canada
| | - Mark Burgin
- University of California at Los Angelos, USA
| | - Cristian S Calude
- Department of Computer Science, University of Auckland, Auckland, New Zealand
| | - José Félix Costa
- Departamento de Matemática, Instituto Superior Técnico, Centro de Filosofia das Ciências da Universidade de Lisboa, Portugal
| | | | | | - Zoran Konkoli
- Department of Microtechnology and Nanoscience - MC2, Chalmers University of Technology, Gothenburg, Sweden
| | - Bruce MacLennan
- Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, USA
| | | | - Maurice Margenstern
- Laboratoire d'Informatique Théorique et Appliquée, Université de Lorraine, Metz, France
| | - Genaro J Martínez
- Escuela Superior de Cómputo, Instituto Politécnico Nacional, Mexico; Unconventional Computing Centre, University of the West of England, Bristol, UK
| | - Richard Mayne
- Unconventional Computing Centre, University of the West of England, Bristol, UK
| | | | - Andrew Schumann
- University of Information Technology and Management in Rzeszow, Rzeszow, Poland
| | - Yaroslav D Sergeyev
- University of Calabria, Rende, Italy and Lobachevsky State University, Nizhni Novgorod, Russia
| | - Georgios Ch Sirakoulis
- Department of Electrical and Computer Engineering, Democritus University of Thrace, Xanthi, Greece
| | - Susan Stepney
- Department of Computer Science, University of York, UK
| | - Karl Svozil
- Institute for Theoretical Physics, Vienna University of Technology, Austria
| | - Hector Zenil
- Algorithmic Dynamics Lab, Unit of Computational Medicine SciLifeLab and Center of Molecular Medicine, Karolinska Institute, Stockholm, Sweden
| |
Collapse
|
22
|
Deng Y, Zenil H, Tegnér J, Kiani NA. HiDi: an efficient reverse engineering schema for large-scale dynamic regulatory network reconstruction using adaptive differentiation. Bioinformatics 2017; 33:3964-3972. [DOI: 10.1093/bioinformatics/btx501] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/04/2016] [Accepted: 08/05/2017] [Indexed: 11/14/2022] Open
Affiliation(s)
- Yue Deng
- Algorithmic Dynamics Lab, Karolinska Institute, Stockholm, Sweden
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Solna and Science for Life Laboratory (SciLifeLab), Karolinska Institute, Stockholm, Sweden
| | - Hector Zenil
- Algorithmic Dynamics Lab, Karolinska Institute, Stockholm, Sweden
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Solna and Science for Life Laboratory (SciLifeLab), Karolinska Institute, Stockholm, Sweden
| | - Jesper Tegnér
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Solna and Science for Life Laboratory (SciLifeLab), Karolinska Institute, Stockholm, Sweden
- Biological and Environmental Sciences and Engineering Division, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, Kingdom of Saudi Arabia
| | - Narsis A Kiani
- Algorithmic Dynamics Lab, Karolinska Institute, Stockholm, Sweden
- Unit of Computational Medicine, Center for Molecular Medicine, Department of Medicine, Solna and Science for Life Laboratory (SciLifeLab), Karolinska Institute, Stockholm, Sweden
| |
Collapse
|
23
|
Abstract
In estimating the complexity of objects, in particular, of graphs, it is common practice to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we see that when applying a computable measure such as the Shannon entropy, not only is it necessary to preselect a feature of interest where there is one, and to make an arbitrary selection where there is not, but also more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as the entropy and entropy rate. We introduce recursive and nonrecursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.
Collapse
Affiliation(s)
- Hector Zenil
- Information Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab, Karolinska Institute, Stockholm 171 76, Sweden; Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom; and Algorithmic Nature Group, LABoRES, Paris 75006, France
| | - Narsis A Kiani
- Information Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab, Karolinska Institute, Stockholm 171 76, Sweden and Algorithmic Nature Group, LABoRES, Paris 75006, France
| | - Jesper Tegnér
- Biological and Environmental Sciences and Engineering Division, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955 - 6900, Kingdom of Saudi Arabia and Unit of Computational Medicine, Department of Medicine Solna, Center for Molecular Medicine, SciLifeLab, Karolinska Institute, Stockholm 171 76, Sweden
| |
Collapse
|
24
|
Abstract
Random Item Generation tasks (RIG) are commonly used to assess high cognitive abilities such as inhibition or sustained attention. They also draw upon our approximate sense of complexity. A detrimental effect of aging on pseudo-random productions has been demonstrated for some tasks, but little is as yet known about the developmental curve of cognitive complexity over the lifespan. We investigate the complexity trajectory across the lifespan of human responses to five common RIG tasks, using a large sample (n = 3429). Our main finding is that the developmental curve of the estimated algorithmic complexity of responses is similar to what may be expected of a measure of higher cognitive abilities, with a performance peak around 25 and a decline starting around 60, suggesting that RIG tasks yield good estimates of such cognitive abilities. Our study illustrates that very short strings of, i.e., 10 items, are sufficient to have their complexity reliably estimated and to allow the documentation of an age-dependent decline in the approximate sense of complexity. It has been unclear how this ability evolves over a person’s lifetime and it had not been possible to be assessed with previous classical tools for statistical randomness. To better understand how age impacts behavior, we have assessed more than 3,400 people aged 4 to 91 years old. Each participant performed a series of online tasks that assessed their ability to behave randomly. The five tasks included listing the hypothetical results of a series of 12 coin flips so that they would “look random to somebody else,” guessing which card would appear when selected from a randomly shuffled deck, and listing the hypothetical results of 10 rolls of a die. We analyzed the participants’ choices according to their algorithmic randomness, which is based on the idea that patterns that are more random are harder to encode in a short computer program. After controlling for characteristics such as gender, language, and education. We have found that age was the only factor that affected the ability to behave randomly. This ability peaked at age 25, on average, and declined from then on. We also demonstrate that a relatively short list of choices, say 10 hypothetical coin flips, can be used to reliably gauge randomness of human behavior. A similar approach could be then used to study potential connections between the ability to behave randomly, cognitive decline, neurodegenerative diseases and abilities such as human creativity.
Collapse
Affiliation(s)
- Nicolas Gauvrit
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique LABORES For the Natural and Digital Sciences, Paris, France
- Human and Artificial Cognition Lab, EPHE, Paris, France
| | - Hector Zenil
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique LABORES For the Natural and Digital Sciences, Paris, France
- Department of Computer Science, University of Oxford, Oxford, United Kingdom
- Information Dynamics Lab, Unit of Computational Medicine, Department of Medicine Solna, Centre for Molecular Medicine and Science for Life Laboratory (SciLifeLab), Karolinska Institute, Stockholm, Sweden
- * E-mail:
| | - Fernando Soler-Toscano
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique LABORES For the Natural and Digital Sciences, Paris, France
- Grupo de Lógica, Lenguaje e Información. Universidad de Sevilla, Sevilla, Spain
| | - Jean-Paul Delahaye
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique LABORES For the Natural and Digital Sciences, Paris, France
- Centre de Recherche en Informatique, Signal et Automatique de Lille (CRISTAL), UMR CNRS 9189, University of Lille 1, Lille, France
| | - Peter Brugger
- Algorithmic Nature Group, Laboratoire de Recherche Scientifique LABORES For the Natural and Digital Sciences, Paris, France
- Department of Neurology, Neuropsychology Unit, University Hospital, Zurich, Switzerland
| |
Collapse
|
25
|
Tegnér J, Zenil H, Kiani NA, Ball G, Gomez-Cabrero D. A perspective on bridging scales and design of models using low-dimensional manifolds and data-driven model inference. Philos Trans A Math Phys Eng Sci 2016; 374:rsta.2016.0144. [PMID: 27698038 PMCID: PMC5052728 DOI: 10.1098/rsta.2016.0144] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Accepted: 08/15/2016] [Indexed: 05/06/2023]
Abstract
Systems in nature capable of collective behaviour are nonlinear, operating across several scales. Yet our ability to account for their collective dynamics differs in physics, chemistry and biology. Here, we briefly review the similarities and differences between mathematical modelling of adaptive living systems versus physico-chemical systems. We find that physics-based chemistry modelling and computational neuroscience have a shared interest in developing techniques for model reductions aiming at the identification of a reduced subsystem or slow manifold, capturing the effective dynamics. By contrast, as relations and kinetics between biological molecules are less characterized, current quantitative analysis under the umbrella of bioinformatics focuses on signal extraction, correlation, regression and machine-learning analysis. We argue that model reduction analysis and the ensuing identification of manifolds bridges physics and biology. Furthermore, modelling living systems presents deep challenges as how to reconcile rich molecular data with inherent modelling uncertainties (formalism, variables selection and model parameters). We anticipate a new generative data-driven modelling paradigm constrained by identified governing principles extracted from low-dimensional manifold analysis. The rise of a new generation of models will ultimately connect biology to quantitative mechanistic descriptions, thereby setting the stage for investigating the character of the model language and principles driving living systems.This article is part of the themed issue 'Multiscale modelling at the physics-chemistry-biology interface'.
Collapse
Affiliation(s)
- Jesper Tegnér
- Department of Medicine, Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet, Solna, Sweden Center for Molecular Medicine, Karolinska Institutet, L8:05, 171 76 Stockholm, Sweden Department of Medicine, Unit of Clinical Epidemiology, Karolinska University Hospital L8, 17176 Stockholm, Sweden Science for Life Laboratory, Stockholm, Sweden
| | - Hector Zenil
- Department of Medicine, Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet, Solna, Sweden Center for Molecular Medicine, Karolinska Institutet, L8:05, 171 76 Stockholm, Sweden Department of Medicine, Unit of Clinical Epidemiology, Karolinska University Hospital L8, 17176 Stockholm, Sweden Science for Life Laboratory, Stockholm, Sweden
| | - Narsis A Kiani
- Department of Medicine, Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet, Solna, Sweden Center for Molecular Medicine, Karolinska Institutet, L8:05, 171 76 Stockholm, Sweden Department of Medicine, Unit of Clinical Epidemiology, Karolinska University Hospital L8, 17176 Stockholm, Sweden Science for Life Laboratory, Stockholm, Sweden
| | - Gordon Ball
- Department of Medicine, Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet, Solna, Sweden Center for Molecular Medicine, Karolinska Institutet, L8:05, 171 76 Stockholm, Sweden Department of Medicine, Unit of Clinical Epidemiology, Karolinska University Hospital L8, 17176 Stockholm, Sweden Science for Life Laboratory, Stockholm, Sweden
| | - David Gomez-Cabrero
- Department of Medicine, Unit of Computational Medicine, Center for Molecular Medicine, Karolinska Institutet, Solna, Sweden Center for Molecular Medicine, Karolinska Institutet, L8:05, 171 76 Stockholm, Sweden Department of Medicine, Unit of Clinical Epidemiology, Karolinska University Hospital L8, 17176 Stockholm, Sweden Science for Life Laboratory, Stockholm, Sweden Mucosal and Salivary Biology Division, King's College London Dental Institute, London SE1 9RT, UK
| |
Collapse
|
26
|
Masoudi-Nejad A, Zenil H. Flow of Information in Biological Systems. Semin Cell Dev Biol 2016; 51:1-2. [PMID: 26987578 DOI: 10.1016/j.semcdb.2016.03.004] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/22/2022]
Affiliation(s)
- Ali Masoudi-Nejad
- Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Tehran, Iran.
| | - Hector Zenil
- Unit of Computational Medicine, Science for Life Laboratory (SciLifeLab), Department of Medicine Solna, Center for Molecular Medicine, Karolinska Institute, Stockholm, Sweden.
| |
Collapse
|
27
|
Zenil H, Kiani NA, Tegnér J. Methods of information theory and algorithmic complexity for network biology. Semin Cell Dev Biol 2016; 51:32-43. [PMID: 26802516 DOI: 10.1016/j.semcdb.2016.01.011] [Citation(s) in RCA: 22] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/16/2015] [Accepted: 01/07/2016] [Indexed: 10/22/2022]
Abstract
We survey and introduce concepts and tools located at the intersection of information theory and network biology. We show that Shannon's information entropy, compressibility and algorithmic complexity quantify different local and global aspects of synthetic and biological data. We show examples such as the emergence of giant components in Erdös-Rényi random graphs, and the recovery of topological properties from numerical kinetic properties simulating gene expression data. We provide exact theoretical calculations, numerical approximations and error estimations of entropy, algorithmic probability and Kolmogorov complexity for different types of graphs, characterizing their variant and invariant properties. We introduce formal definitions of complexity for both labeled and unlabeled graphs and prove that the Kolmogorov complexity of a labeled graph is a good approximation of its unlabeled Kolmogorov complexity and thus a robust definition of graph complexity.
Collapse
Affiliation(s)
- Hector Zenil
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute & Center for Molecular Medicine, Karolinska University Hospital, Stockholm, Sweden.
| | - Narsis A Kiani
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute & Center for Molecular Medicine, Karolinska University Hospital, Stockholm, Sweden
| | - Jesper Tegnér
- Unit of Computational Medicine, Department of Medicine, Karolinska Institute & Center for Molecular Medicine, Karolinska University Hospital, Stockholm, Sweden
| |
Collapse
|
28
|
Lui LT, Terrazas G, Zenil H, Alexander C, Krasnogor N. Complexity measurement based on information theory and kolmogorov complexity. Artif Life 2015; 21:205-224. [PMID: 25622014 DOI: 10.1162/artl_a_00157] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/04/2023]
Abstract
In the past decades many definitions of complexity have been proposed. Most of these definitions are based either on Shannon's information theory or on Kolmogorov complexity; these two are often compared, but very few studies integrate the two ideas. In this article we introduce a new measure of complexity that builds on both of these theories. As a demonstration of the concept, the technique is applied to elementary cellular automata and simulations of the self-organization of porphyrin molecules.
Collapse
|
29
|
|
30
|
|
31
|
Soler-Toscano F, Zenil H, Delahaye JP, Gauvrit N. Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines. PLoS One 2014; 9:e96223. [PMID: 24809449 PMCID: PMC4014489 DOI: 10.1371/journal.pone.0096223] [Citation(s) in RCA: 49] [Impact Index Per Article: 4.9] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/30/2014] [Accepted: 04/04/2014] [Indexed: 11/24/2022] Open
Abstract
Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the traditional lossless compression algorithms, which it may complement, the two being serviceable for different string lengths. We provide a thorough analysis for all binary strings of length and for most strings of length by running all Turing machines with 5 states and 2 symbols ( with reduction techniques) using the most standard formalism of Turing machines, used in for example the Busy Beaver problem. We address the question of stability and error estimation, the sensitivity of the continued application of the method for wider coverage and better accuracy, and provide statistical evidence suggesting robustness. As with compression algorithms, this work promises to deliver a range of applications, and to provide insight into the question of complexity calculation of finite (and short) strings. Additional material can be found at the Algorithmic Nature Group website at http://www.algorithmicnature.org. An Online Algorithmic Complexity Calculator implementing this technique and making the data available to the research community is accessible at http://www.complexitycalculator.com.
Collapse
Affiliation(s)
- Fernando Soler-Toscano
- Grupo de Lógica, Lenguaje e Información, Universidad de Sevilla, Sevilla, Spain
- Algorithmic Nature Group, LABORES, Paris, France
| | - Hector Zenil
- Unit of Computational Medicine, Karolinska Institutet, Stockholm, Sweden
- Algorithmic Nature Group, LABORES, Paris, France
- * E-mail:
| | - Jean-Paul Delahaye
- Laboratoire d'Informatique Fondamentale de Lille, Université de Lille I, Lille, France
- Algorithmic Nature Group, LABORES, Paris, France
| | - Nicolas Gauvrit
- École Pratique des Hautes Études, Paris, France
- Algorithmic Nature Group, LABORES, Paris, France
| |
Collapse
|
32
|
Abstract
While evolution has inspired algorithmic methods of heuristic optimization, little has been done in the way of using concepts of computation to advance our understanding of salient aspects of biological phenomena. The authors argue under reasonable assumptions, interesting conclusions can be drawn that are of relevance to behavioral evolution. The authors will focus on two important features of life---robustness and fitness---which, they will argue, are related to algorithmic probability and to the thermodynamics of computation, disciplines that may be capable of modeling key features of living organisms, and which can be used in formulating new algorithms of evolutionary computation.
Collapse
Affiliation(s)
- Hector Zenil
- University of Sheffield and Algorithmic Nature Group
| | | |
Collapse
|
33
|
|