We present a novel, domain-agnostic, model-independent, unsupervised, and universally applicable Machine Learning approach for dimensionality reduction based on the principles of algorithmic complexity. Specifically, but without loss of generality, we focus on addressing the challenge of reducing certain dimensionality aspects, such as the number of edges in a network, while retaining essential features of interest. These features include preserving crucial network properties like degree distribution, clustering coefficient, edge betweenness, and degree and eigenvector centralities but can also go beyond edges to nodes and weights for network pruning and trimming. Our approach outperforms classical statistical Machine Learning techniques and state-of-the-art dimensionality reduction algorithms by preserving a greater number of data features that statistical algorithms would miss, particularly nonlinear patterns stemming from deterministic recursive processes that may look statistically random but are not. Moreover, previous approaches heavily rely on a priori feature selection, which requires constant supervision. Our findings demonstrate the effectiveness of the algorithms in overcoming some of these limitations while maintaining a time-efficient computational profile. Our approach not only matches, but also exceeds, the performance of established and state-of-the-art dimensionality reduction algorithms. We extend the applicability of our method to lossy compression tasks involving images and any multi-dimensional data. This highlights the versatility and broad utility of the approach in multiple domains.

In communication systems, the circumstances and capabilities of senders and receivers cannot be known/assumed beforehand so as to design optimal semantic transference strategies. Regardless of the recipient (plants, insects, or even life forms unknown on Earth), the spatio-temporal scale of a message could be inappropriate and may never be decoded due to incompatibilities at both ends. We devise a new method to encode messages that is agnostic vis-a-vis space and time scales. We propose the use of fractal functions as self-executable carriers for sending messages, given their properties of structural self-similarity and scale invariance. We call this ‘fractal messaging’. Starting from a spatial embedding, we introduce a framework for a space-time scale-free messaging approach. In creating a space and time agnostic framework for message transmission, encoding a message that could be decoded at several spatio-temporal scales is the objective. Our core idea is to encode a binary message as waves along infinitely many frequencies (in power-like distributions) and amplitudes, transmit such a message, and then decode and reproduce it. To do so, the components/cycles of the Weierstrass function, a known fractal, are used as carriers of the message. Each component will have its amplitude modulated to embed the binary stream, allowing for a space-time agnostic approach to messaging.

Motivated by algorithmic information theory, the problem of program discovery can help find candidates of underlying generative mechanisms of natural and artificial phenomena. The uncomputability of such inverse problem, however, significantly restricts a wider application of exhaustive methods. Here we present a proof of concept of an approach based on IMP, a high-level imperative programming language. Its main advantage is that conceptually complex computational routines are more succinctly expressed, unlike lower-level models such as Turing machines or cellular automata. We investigate if a more expressive higher-level programming language can be more efficient at generating approximations to algorithmic complexity of recursive functions.

NeuroEvolution is one of the most competitive evolutionary learning strategies for designing novel neural networks for use in specific tasks, such as logic circuit design and digital gaming. However, the application of benchmark methods such as the NeuroEvolution of Augmenting Topologies (NEAT) remains a challenge, in terms of their computational cost and search time inefficiency. This paper advances a method which incorporates a type of topological edge coding, named Reverse Encoding Tree (RET), for evolving scalable neural networks efficiently. Using RET, two types of approaches - NEAT with Binary search encoding (Bi-NEAT) and NEAT with Golden-Section search encoding (GS-NEAT) - have been designed to solve problems in benchmark continuous learning environments such as logic gates, Cartpole, and Lunar Lander, and tested against classical NEAT and FS-NEAT as baselines. Additionally, we conduct a robustness test to evaluate the resilience of the proposed NEAT approaches. The results show that the two proposed approaches deliver improved performance, characterized by (1) a higher accumulated reward within a finite number of time steps; (2) using fewer episodes to solve problems in targeted environments, and (3) maintaining adaptive robustness under noisy perturbations, which outperform the baselines in all tested cases. Our analysis also demonstrates that RET expends potential future research directions in dynamic environments. Code is available from https://github.com/HaolingZHANG/ReverseEncodingTree.

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.

MOTIVATION: The use of differential equations (ODE) is one of the most promising approaches to network inference. The success of ODE-based approaches has, however, been limited, due to the difficulty in estimating parameters and by their lack of scalability. Here, we introduce a novel method and pipeline to reverse engineer gene regulatory networks from gene expression of time series and perturbation data based upon an improvement on the calculation scheme of the derivatives and a pre-filtration step to reduce the number of possible links. The method introduces a linear differential equation model with adaptive numerical differentiation that is scalable to extremely large regulatory networks. RESULTS: We demonstrate the ability of this method to outperform current state-of-the-art methods applied to experimental and synthetic data using test data from the DREAM4 and DREAM5 challenges. Our method displays greater accuracy and scalability. We benchmark the performance of the pipeline with respect to dataset size and levels of noise. We show that the computation time is linear over various network sizes. AVAILABILITY AND IMPLEMENTATION: The Matlab code of the HiDi implementation is available at: www.complexitycalculator.com/HiDiScript.zip. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

Is undecidability a requirement for open-ended evolution (OEE)? Using algorithmic complexity theory methods, we propose robust computational definitions for open-ended evolution and adaptability of computable dynamical systems. Within this framework, we show that decidability imposes absolute limits to the growth of complexity on computable dynamical systems up to a logarithm of a logarithmic term. Conversely, systems that exhibit 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. We conjecture that, for similar complexity measures that assign low complexity values, decidability imposes comparable limits to the stable growth of complexity and such behaviour is necessary for non-trivial evolutionary systems. Finally, we show that undecidability of adapted states imposes novel and unpredictable behaviour on the individuals or population being modelled. Such behaviour is irreducible.

Despite extensive attempts to characterize systems and networks based upon metrics drawn from traditional statistics, Shannon entropy, and graph theory to understand systems and networks to reveal their causal mechanisms without making too many unjustified assumptions remains still as one of the greatest challenges in complexity science and science in general, specially beyond traditional statistics and so-called machine learning. Knowing the causal mechanisms that govern a system allows not only the prediction of the system's behavior but the manipulation and controlled reprogramming of the system. Here we introduce a formal interventional calculus based upon universal principles drawn from the theory of computability and algorithmic probability, thereby enabling better approaches to the question of causal discovery. By performing sequences of fully controlled perturbations, changes in the algorithmic content of a system can be classified into the effects they have according to their shift towards or away from algorithmic randomness, thereby inducing a ranking of system's elements. This spectral dimension unmasks an algorithmic separation between components conditioned upon the perturbations and endowing us with a suite of powerful parameter-free algorithms to reprogram the system's underlying program. The predictive and explanatory power of these novel conceptual tools are introduced and numerical experiments are illustrated on various types of networks. We show how the algorithmic content of a network is connected to its possible dynamics and how the instant variation of the sensitivity, depth, and the number of attractors in a network is accessible by an analysis of its algorithmic information landscape. The results demonstrate how to unveil causal mechanisms to infer essential properties, including the dynamics of evolving networks. We introduce measures and methods for system reprogrammability even with no, or limited, access to the system kinetic equations or probability distributions. We expect this interventional calculus to be broadly applicable for predictive causal interventions and we anticipate it to be instrumental in the challenge of causality discovery in science from complex data.

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.

In a previous article, I suggested a method for testing the algorithmicity of a natural/physical process using the concept of Levin's universal distribution. Here, I explain this method in the context of the problem formulated by L. Floridi concerning the testability of pancomputationalism. Then, I will introduce a behavioural battery of programmability tests for natural computation, as an example of a computational philosophy approach. That is to tackle a simplified version of a complex philosophical question with a computer experiment. I go on to demonstrate the application of this novel approach in a case study featuring Conway's Game of Life. In this context, I also briefly discuss another question raised by Floridi, concerning a grand unified theory of information, which I think is deeply connected to the grand unification of physics.

Representing biological systems as networks has proved to be very powerful. For example, local graph analysis of substructures such as subgraph over representation (or motifs) has elucidated different sub-types of networks. Here we report that using numerical approximations of Kolmogorov complexity, by means of algorithmic probability, clusters different classes of networks. For this, we numerically estimate the algorithmic probability of the sub-matrices from the adjacency matrix of the original network (hence including motifs). We conclude that algorithmic information theory is a powerful tool supplementing other network analysis techniques.