-
Systematizing Modeler Experience (MX) in Model-Driven Engineering Success Stories
Authors:
Reyhaneh Kalantari,
Julian Oertel,
Joeri Exelmans,
Satrio Adi Rukmono,
Vasco Amaral,
Matthias Tichy,
Katharina Juhnke,
Jan-Philipp Steghöfer,
Silvia Abrahão
Abstract:
Modeling is often associated with complex and heavy tooling, leading to a negative perception among practitioners. However, alternative paradigms, such as everything-as-code or low-code, are gaining acceptance due to their perceived ease of use. This paper explores the dichotomy between these perceptions through the lens of ``modeler experience'' (MX). MX includes factors such as user experience,…
▽ More
Modeling is often associated with complex and heavy tooling, leading to a negative perception among practitioners. However, alternative paradigms, such as everything-as-code or low-code, are gaining acceptance due to their perceived ease of use. This paper explores the dichotomy between these perceptions through the lens of ``modeler experience'' (MX). MX includes factors such as user experience, motivation, integration, collaboration \& versioning and language complexity. We examine the relationships between these factors and their impact on different modeling usage scenarios. Our findings highlight the importance of considering MX when understanding how developers interact with modeling tools and the complexities of modeling and associated tooling.
△ Less
Submitted 28 June, 2024;
originally announced June 2024.
-
Reinforcement Learning-Based Framework for the Intelligent Adaptation of User Interfaces
Authors:
Daniel Gaspar-Figueiredo,
Marta Fernández-Diego,
Ruben Nuredini,
Silvia Abrahão,
Emilio Insfrán
Abstract:
Adapting the user interface (UI) of software systems to meet the needs and preferences of users is a complex task. The main challenge is to provide the appropriate adaptations at the appropriate time to offer value to end-users. Recent advances in Machine Learning (ML) techniques may provide effective means to support the adaptation process. In this paper, we instantiate a reference framework for…
▽ More
Adapting the user interface (UI) of software systems to meet the needs and preferences of users is a complex task. The main challenge is to provide the appropriate adaptations at the appropriate time to offer value to end-users. Recent advances in Machine Learning (ML) techniques may provide effective means to support the adaptation process. In this paper, we instantiate a reference framework for Intelligent User Interface Adaptation by using Reinforcement Learning (RL) as the ML component to adapt user interfaces and ultimately improving the overall User Experience (UX). By using RL, the system is able to learn from past adaptations to improve the decision-making capabilities. Moreover, assessing the success of such adaptations remains a challenge. To overcome this issue, we propose to use predictive Human-Computer Interaction (HCI) models to evaluate the outcome of each action (ie adaptations) performed by the RL agent. In addition, we present an implementation of the instantiated framework, which is an extension of OpenAI Gym, that serves as a toolkit for developing and comparing RL algorithms. This Gym environment is highly configurable and extensible to other UI adaptation contexts. The evaluation results show that our RL-based framework can successfully train RL agents able to learn how to adapt UIs in a specific context to maximize the user engagement by using an HCI model as rewards predictor.
△ Less
Submitted 15 May, 2024;
originally announced May 2024.
-
Decoding Geometric Properties in Non-Random Data from First Information-Theoretic Principles
Authors:
Hector Zenil,
Felipe S. Abrahão
Abstract:
Based on the principles of information theory, measure theory, and theoretical computer science, we introduce a univariate signal deconvolution method with a wide range of applications to coding theory, particularly in zero-knowledge one-way communication channels, such as in deciphering messages from unknown generating sources about which no prior knowledge is available and to which no return mes…
▽ More
Based on the principles of information theory, measure theory, and theoretical computer science, we introduce a univariate signal deconvolution method with a wide range of applications to coding theory, particularly in zero-knowledge one-way communication channels, such as in deciphering messages from unknown generating sources about which no prior knowledge is available and to which no return message can be sent. Our multidimensional space reconstruction method from an arbitrary received signal is proven to be agnostic vis-a-vis the encoding-decoding scheme, computation model, programming language, formal theory, the computable (or semi-computable) method of approximation to algorithmic complexity, and any arbitrarily chosen (computable) probability measure of the events. The method derives from the principles of an approach to Artificial General Intelligence capable of building a general-purpose model of models independent of any arbitrarily assumed prior probability distribution. We argue that this optimal and universal method of decoding non-random data has applications to signal processing, causal deconvolution, topological and geometric properties encoding, cryptography, and bio- and technosignature detection.
△ Less
Submitted 17 May, 2024; v1 submitted 13 May, 2024;
originally announced May 2024.
-
Human Factors in Model-Driven Engineering: Future Research Goals and Initiatives for MDE
Authors:
Grischa Liebel,
Jil Klünder,
Regina Hebig,
Christopher Lazik,
Inês Nunes,
Isabella Graßl,
Jan-Philipp Steghöfer,
Joeri Exelmans,
Julian Oertel,
Kai Marquardt,
Katharina Juhnke,
Kurt Schneider,
Lucas Gren,
Lucia Happe,
Marc Herrmann,
Marvin Wyrich,
Matthias Tichy,
Miguel Goulão,
Rebekka Wohlrab,
Reyhaneh Kalantari,
Robert Heinrich,
Sandra Greiner,
Satrio Adi Rukmono,
Shalini Chakraborty,
Silvia Abrahão
, et al. (1 additional authors not shown)
Abstract:
Purpose: Software modelling and Model-Driven Engineering (MDE) is traditionally studied from a technical perspective. However, one of the core motivations behind the use of software models is inherently human-centred. Models aim to enable practitioners to communicate about software designs, make software understandable, or make software easier to write through domain-specific modelling languages.…
▽ More
Purpose: Software modelling and Model-Driven Engineering (MDE) is traditionally studied from a technical perspective. However, one of the core motivations behind the use of software models is inherently human-centred. Models aim to enable practitioners to communicate about software designs, make software understandable, or make software easier to write through domain-specific modelling languages. Several recent studies challenge the idea that these aims can always be reached and indicate that human factors play a role in the success of MDE. However, there is an under-representation of research focusing on human factors in modelling. Methods: During a GI-Dagstuhl seminar, topics related to human factors in modelling were discussed by 26 expert participants from research and industry. Results: In breakout groups, five topics were covered in depth, namely modelling human aspects, factors of modeller experience, diversity and inclusion in MDE, collaboration and MDE, and teaching human-aware MDE. Conclusion: We summarise our insights gained during the discussions on the five topics. We formulate research goals, questions, and propositions that support directing future initiatives towards an MDE community that is aware of and supportive of human factors and values.
△ Less
Submitted 29 April, 2024;
originally announced April 2024.
-
VeGAn-Tool: A Fuzzy-logic Approach for Value-based Goal Model Analysis
Authors:
Carlos Cano-Genoves,
Emilio Insfrán,
Silvia Abrahão
Abstract:
Goal-oriented analysis tools are used to assess goal models and assist analysts in decision-making. We introduce the VeGAn-Tool, which prioritizes goals according to their qualitative importance for the stakeholders and propagates this information in the goal model according to the different types of relationships. The FTOPSIS technique is used to calculate the value of each intentional element by…
▽ More
Goal-oriented analysis tools are used to assess goal models and assist analysts in decision-making. We introduce the VeGAn-Tool, which prioritizes goals according to their qualitative importance for the stakeholders and propagates this information in the goal model according to the different types of relationships. The FTOPSIS technique is used to calculate the value of each intentional element by employing the fuzzified importance (importance level fuzzified and refined by a confidence level) and the impact among the related intentional elements. The result is a prioritized goal model according to the value of each intentional element from the stakeholders' point of view.
△ Less
Submitted 23 April, 2024;
originally announced April 2024.
-
Assembly Theory is an approximation to algorithmic complexity based on LZ compression that does not explain selection or evolution
Authors:
Felipe S. Abrahão,
Santiago Hernández-Orozco,
Narsis A. Kiani,
Jesper Tegnér,
Hector Zenil
Abstract:
We prove the full equivalence between Assembly Theory (AT) and Shannon Entropy via a method based upon the principles of statistical compression renamed `assembly index' that belongs to the LZ family of popular compression algorithms (ZIP, GZIP, JPEG). Such popular algorithms have been shown to empirically reproduce the results of AT, results that have also been reported before in successful appli…
▽ More
We prove the full equivalence between Assembly Theory (AT) and Shannon Entropy via a method based upon the principles of statistical compression renamed `assembly index' that belongs to the LZ family of popular compression algorithms (ZIP, GZIP, JPEG). Such popular algorithms have been shown to empirically reproduce the results of AT, results that have also been reported before in successful applications to separating organic from non-organic molecules and in the context of the study of selection and evolution. We show that the assembly index value is equivalent to the size of a minimal context-free grammar. The statistical compressibility of such a method is bounded by Shannon Entropy and other equivalent traditional LZ compression schemes, such as LZ77, LZ78, or LZW. In addition, we demonstrate that AT, and the algorithms supporting its pathway complexity, assembly index, and assembly number, define compression schemes and methods that are subsumed into the theory of algorithmic (Kolmogorov-Solomonoff-Chaitin) complexity. Due to AT's current lack of logical consistency in defining causality for non-stochastic processes and the lack of empirical evidence that it outperforms other complexity measures found in the literature capable of explaining the same phenomena, we conclude that the assembly index and the assembly number do not lead to an explanation or quantification of biases in generative (physical or biological) processes, including those brought about by (abiotic or Darwinian) selection and evolution, that could not have been arrived at using Shannon Entropy or that have not been reported before using classical information theory or algorithmic complexity.
△ Less
Submitted 1 April, 2024; v1 submitted 11 March, 2024;
originally announced March 2024.
-
A Comparative Study on Reward Models for UI Adaptation with Reinforcement Learning
Authors:
Daniel Gaspar-Figueiredo,
Silvia Abrahão,
Marta Fernández-Diego,
Emilio Insfran
Abstract:
Adapting the User Interface (UI) of software systems to user requirements and the context of use is challenging. The main difficulty consists of suggesting the right adaptation at the right time in the right place in order to make it valuable for end-users. We believe that recent progress in Machine Learning techniques provides useful ways in which to support adaptation more effectively. In partic…
▽ More
Adapting the User Interface (UI) of software systems to user requirements and the context of use is challenging. The main difficulty consists of suggesting the right adaptation at the right time in the right place in order to make it valuable for end-users. We believe that recent progress in Machine Learning techniques provides useful ways in which to support adaptation more effectively. In particular, Reinforcement learning (RL) can be used to personalise interfaces for each context of use in order to improve the user experience (UX). However, determining the reward of each adaptation alternative is a challenge in RL for UI adaptation. Recent research has explored the use of reward models to address this challenge, but there is currently no empirical evidence on this type of model. In this paper, we propose a confirmatory study design that aims to investigate the effectiveness of two different approaches for the generation of reward models in the context of UI adaptation using RL: (1) by employing a reward model derived exclusively from predictive Human-Computer Interaction (HCI) models (HCI), and (2) by employing predictive HCI models augmented by Human Feedback (HCI&HF). The controlled experiment will use an AB/BA crossover design with two treatments: HCI and HCI&HF. We shall determine how the manipulation of these two treatments will affect the UX when interacting with adaptive user interfaces (AUI). The UX will be measured in terms of user engagement and user satisfaction, which will be operationalized by means of predictive HCI models and the Questionnaire for User Interaction Satisfaction (QUIS), respectively. By comparing the performance of two reward models in terms of their ability to adapt to user preferences with the purpose of improving the UX, our study contributes to the understanding of how reward modelling can facilitate UI adaptation using RL.
△ Less
Submitted 15 January, 2024; v1 submitted 26 August, 2023;
originally announced August 2023.
-
The Future of Fundamental Science Led by Generative Closed-Loop Artificial Intelligence
Authors:
Hector Zenil,
Jesper Tegnér,
Felipe S. Abrahão,
Alexander Lavin,
Vipin Kumar,
Jeremy G. Frey,
Adrian Weller,
Larisa Soldatova,
Alan R. Bundy,
Nicholas R. Jennings,
Koichi Takahashi,
Lawrence Hunter,
Saso Dzeroski,
Andrew Briggs,
Frederick D. Gregory,
Carla P. Gomes,
Jon Rowe,
James Evans,
Hiroaki Kitano,
Ross King
Abstract:
Recent advances in machine learning and AI, including Generative AI and LLMs, are disrupting technological innovation, product development, and society as a whole. AI's contribution to technology can come from multiple approaches that require access to large training data sets and clear performance evaluation criteria, ranging from pattern recognition and classification to generative models. Yet,…
▽ More
Recent advances in machine learning and AI, including Generative AI and LLMs, are disrupting technological innovation, product development, and society as a whole. AI's contribution to technology can come from multiple approaches that require access to large training data sets and clear performance evaluation criteria, ranging from pattern recognition and classification to generative models. Yet, AI has contributed less to fundamental science in part because large data sets of high-quality data for scientific practice and model discovery are more difficult to access. Generative AI, in general, and Large Language Models in particular, may represent an opportunity to augment and accelerate the scientific discovery of fundamental deep science with quantitative models. Here we explore and investigate aspects of an AI-driven, automated, closed-loop approach to scientific discovery, including self-driven hypothesis generation and open-ended autonomous exploration of the hypothesis space. Integrating AI-driven automation into the practice of science would mitigate current problems, including the replication of findings, systematic production of data, and ultimately democratisation of the scientific process. Realising these possibilities requires a vision for augmented AI coupled with a diversity of AI approaches able to deal with fundamental aspects of causality analysis and model discovery while enabling unbiased search across the space of putative explanations. These advances hold the promise to unleash AI's potential for searching and discovering the fundamental structure of our world beyond what human scientists have been able to achieve. Such a vision would push the boundaries of new fundamental science rather than automatize current workflows and instead open doors for technological innovation to tackle some of the greatest challenges facing humanity today.
△ Less
Submitted 29 August, 2023; v1 submitted 9 July, 2023;
originally announced July 2023.
-
Measuring User Experience of Adaptive User Interfaces using EEG: A Replication Study
Authors:
Daniel Gaspar-Figueiredo,
Silvia Abrahão,
Emilio Insfrán,
Jean Vanderdonckt
Abstract:
Adaptive user interfaces have the advantage of being able to dynamically change their aspect and/or behaviour depending on the characteristics of the context of use, i.e. to improve user experience(UX). UX is an important quality factor that has been primarily evaluated with classical measures but to a lesser extent with physiological measures, such as emotion recognition, skin response, or brain…
▽ More
Adaptive user interfaces have the advantage of being able to dynamically change their aspect and/or behaviour depending on the characteristics of the context of use, i.e. to improve user experience(UX). UX is an important quality factor that has been primarily evaluated with classical measures but to a lesser extent with physiological measures, such as emotion recognition, skin response, or brain activity.In a previous exploratory experiment involving users with different profiles and a wide range of ages, we analysed user experience in terms of cognitive load, engagement, attraction and memorisation when employing twenty graphical adaptive menus through the use of an Electroencephalogram (EEG) device. The results indicated that there were statistically significant differences for these four variables. However, we considered that it was necessary to confirm or reject these findings using a more homogeneous group of users.We conducted an operational internal replication study with 40 participants. We also investigated the potential correlation between EEG signals and the participants' user experience ratings, such as their preferences.The results of this experiment confirm that there are statistically significant differences between the EEG variables when the participants interact with the different adaptive menus. Moreover, there is a high correlation among the participants' UX ratings and the EEG signals, and a trend regarding performance has emerged from our analysis.These findings suggest that EEG signals could be used to evaluate UX. With regard to the menus studied, our results suggest that graphical menus with different structures and font types produce more differences in users' brain responses, while menus which use colours produce more similarities in users' brain responses. Several insights with which to improve users' experience of graphical adaptive menus are outlined.
△ Less
Submitted 6 June, 2023;
originally announced June 2023.
-
A simplicity bubble problem and zemblanity in digitally intermediated societies
Authors:
Felipe S. Abrahão,
Ricardo P. Cavassane,
Michael Winter,
Mariana Vitti Rodrigues,
Itala M. L. D'Ottaviano
Abstract:
In this article, we discuss the ubiquity of Big Data and machine learning in society and propose that it evinces the need of further investigation of their fundamental limitations. We extend the "too much information tends to behave like very little information" phenomenon to formal knowledge about lawlike universes and arbitrary collections of computably generated datasets. This gives rise to the…
▽ More
In this article, we discuss the ubiquity of Big Data and machine learning in society and propose that it evinces the need of further investigation of their fundamental limitations. We extend the "too much information tends to behave like very little information" phenomenon to formal knowledge about lawlike universes and arbitrary collections of computably generated datasets. This gives rise to the simplicity bubble problem, which refers to a learning algorithm equipped with a formal theory that can be deceived by a dataset to find a locally optimal model which it deems to be the global one. In the context of lawlike (computable) universes and formal learning systems, we show that there is a ceiling above which formal knowledge cannot further decrease the probability of zemblanitous findings, should the randomly generated data made available to the formal learning system be sufficiently large in comparison to their joint complexity. We also argue that this is an epistemological limitation that may generate unpredictable problems in digitally intermediated societies.
△ Less
Submitted 13 January, 2024; v1 submitted 20 April, 2023;
originally announced April 2023.
-
An Optimal, Universal and Agnostic Decoding Method for Message Reconstruction, Bio and Technosignature Detection
Authors:
Hector Zenil,
Alyssa Adams,
Felipe S. Abrahão
Abstract:
We present a signal reconstruction method for zero-knowledge one-way communication channels in which a receiver aims to interpret a message sent by an unknown source about which no prior knowledge is available and to which no return message can be sent. Our reconstruction method is agnostic vis-à-vis the arbitrarily chosen encoding-decoding scheme and other observer-dependent characteristics, such…
▽ More
We present a signal reconstruction method for zero-knowledge one-way communication channels in which a receiver aims to interpret a message sent by an unknown source about which no prior knowledge is available and to which no return message can be sent. Our reconstruction method is agnostic vis-à-vis the arbitrarily chosen encoding-decoding scheme and other observer-dependent characteristics, such as the arbitrarily chosen computation model or underlying mathematical theory. We investigate how non-random messages may encode information about the physical properties, such as dimension and length scales of the space in which a signal or message may have been originally encoded, embedded, or generated. We argue that our results have applications to life and technosignature detection and to coding theory in general.
△ Less
Submitted 9 May, 2024; v1 submitted 28 March, 2023;
originally announced March 2023.
-
On the Salient Limitations of the Methods of Assembly Theory and their Classification of Molecular Biosignatures
Authors:
Abicumaran Uthamacumaran,
Felipe S. Abrahão,
Narsis A. Kiani,
Hector Zenil
Abstract:
We demonstrate that the assembly pathway method underlying Assembly Theory (AT) is a dictionary-based encoding scheme for `counting copies', widely used by popular statistical compression algorithms, some of which have been applied to many areas, including systems biology, chemistry, and biosignature classification. We show that AT performs similarly in all cases (synthetic or natural) to other si…
▽ More
We demonstrate that the assembly pathway method underlying Assembly Theory (AT) is a dictionary-based encoding scheme for `counting copies', widely used by popular statistical compression algorithms, some of which have been applied to many areas, including systems biology, chemistry, and biosignature classification. We show that AT performs similarly in all cases (synthetic or natural) to other simple coding schemes and underperforms compared to system-related indexes based upon algorithmic probability that take into account the likelihood of related computable approximations of similar events. Our results also demonstrate that simple (and tractably computable) modular instructions can mislead AT, leading to failure in practice in capturing the properties of physical systems. These theoretical and empirical results imply that the assembly index, whose computable nature is not an advantage, does not offer substantial improvements over existing methods. In contrast, other resource-bounded (therefore also computable) indexes that approximate algorithmic (Kolmogorov) complexity show the ability to separate organic from inorganic molecules and even perform better on the mass spectral information used by the authors of AT. We show the predictive power of these other system-driven indexes based on their solid foundations and empirical results.
△ Less
Submitted 16 April, 2024; v1 submitted 30 September, 2022;
originally announced October 2022.
-
A Simplicity Bubble Problem in Formal-Theoretic Learning Systems
Authors:
Felipe S. Abrahão,
Hector Zenil,
Fabio Porto,
Michael Winter,
Klaus Wehmuth,
Itala M. L. D'Ottaviano
Abstract:
When mining large datasets in order to predict new data, limitations of the principles behind statistical machine learning pose a serious challenge not only to the Big Data deluge, but also to the traditional assumptions that data generating processes are biased toward low algorithmic complexity. Even when one assumes an underlying algorithmic-informational bias toward simplicity in finite dataset…
▽ More
When mining large datasets in order to predict new data, limitations of the principles behind statistical machine learning pose a serious challenge not only to the Big Data deluge, but also to the traditional assumptions that data generating processes are biased toward low algorithmic complexity. Even when one assumes an underlying algorithmic-informational bias toward simplicity in finite dataset generators, we show that current approaches to machine learning (including deep learning, or any formal-theoretic hybrid mix of top-down AI and statistical machine learning approaches), can always be deceived, naturally or artificially, by sufficiently large datasets. In particular, we demonstrate that, for every learning algorithm (with or without access to a formal theory), there is a sufficiently large dataset size above which the algorithmic probability of an unpredictable deceiver is an upper bound (up to a multiplicative constant that only depends on the learning algorithm) for the algorithmic probability of any other larger dataset. In other words, very large and complex datasets can deceive learning algorithms into a ``simplicity bubble'' as likely as any other particular non-deceiving dataset. These deceiving datasets guarantee that any prediction effected by the learning algorithm will unpredictably diverge from the high-algorithmic-complexity globally optimal solution while converging toward the low-algorithmic-complexity locally optimal solution, although the latter is deemed a global one by the learning algorithm. We discuss the framework and additional empirical conditions to be met in order to circumvent this deceptive phenomenon, moving away from statistical machine learning towards a stronger type of machine learning based on, and motivated by, the intrinsic power of algorithmic information theory and computability theory.
△ Less
Submitted 25 April, 2023; v1 submitted 22 December, 2021;
originally announced December 2021.
-
Emergence and algorithmic information dynamics of systems and observers
Authors:
Felipe S. Abrahão,
Hector Zenil
Abstract:
Previous work has shown that perturbation analysis in software space can produce candidate computable generative models and uncover possible causal properties from the finite description of an object or system quantifying the algorithmic contribution of each of its elements relative to the whole. One of the challenges for defining emergence is that one observer's prior knowledge may cause a phenom…
▽ More
Previous work has shown that perturbation analysis in software space can produce candidate computable generative models and uncover possible causal properties from the finite description of an object or system quantifying the algorithmic contribution of each of its elements relative to the whole. One of the challenges for defining emergence is that one observer's prior knowledge may cause a phenomenon to present itself to such observer as emergent while for another as reducible. By formalising the act of observing as mutual perturbations between dynamical systems, we demonstrate that emergence of algorithmic information do depend on the observer's formal knowledge, while robust to other subjective factors, particularly: the choice of the programming language and the measurement method; errors or distortions during the information acquisition; and the informational cost of processing. This is called observer-dependent emergence (ODE). In addition, we demonstrate that the unbounded and fast increase of emergent algorithmic information implies asymptotically observer-independent emergence (AOIE). Unlike ODE, AOIE is a type of emergence for which emergent phenomena will remain considered to be emergent for every formal theory that any observer might devise. 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.
△ Less
Submitted 30 September, 2021; v1 submitted 31 May, 2021;
originally announced May 2021.
-
Emergence of complex data from simple local rules in a network game
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
As one of the main subjects of investigation in data science, network science has been demonstrated a wide range of applications to real-world networks analysis and modeling. For example, the pervasive presence of structural or topological characteristics, such as the small-world phenomenon, small-diameter, scale-free properties, or fat-tailed degree distribution were one of the underlying pillars…
▽ More
As one of the main subjects of investigation in data science, network science has been demonstrated a wide range of applications to real-world networks analysis and modeling. For example, the pervasive presence of structural or topological characteristics, such as the small-world phenomenon, small-diameter, scale-free properties, or fat-tailed degree distribution were one of the underlying pillars fostering the study of complex networks. Relating these phenomena with other emergent properties in complex systems became a subject of central importance. By introducing new implications on the interface between data science and complex systems science with the purpose of tackling some of these issues, in this article we present a model for a network game played by complex networks in which nodes are computable systems. In particular, we present and discuss how some network topological properties and simple local communication rules are able to generate a phase transition with respect to the emergence of incompressible data.
△ Less
Submitted 23 September, 2020;
originally announced September 2020.
-
An Algorithmic Information Distortion in Multidimensional Networks
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Hector Zenil,
Artur Ziviani
Abstract:
Network complexity, network information content analysis, and lossless compressibility of graph representations have been played an important role in network analysis and network modeling. As multidimensional networks, such as time-varying, multilayer, or dynamic multilayer networks, gain more relevancy in network science, it becomes crucial to investigate in which situations universal algorithmic…
▽ More
Network complexity, network information content analysis, and lossless compressibility of graph representations have been played an important role in network analysis and network modeling. As multidimensional networks, such as time-varying, multilayer, or dynamic multilayer networks, gain more relevancy in network science, it becomes crucial to investigate in which situations universal algorithmic methods based on algorithmic information theory applied to graphs cannot be straightforwardly imported into the multidimensional case. In this direction, as a worst-case scenario of lossless compressibility distortion that increases linearly with the number of distinct dimensions, this article presents a counter-intuitive phenomenon that occurs when dealing with networks within non-uniform and sufficiently large multidimensional spaces. In particular, we demonstrate that the algorithmic information necessary to encode multidimensional networks that are isomorphic to logarithmically compressible monoplex networks may display exponentially larger distortions in the general case.
△ Less
Submitted 5 October, 2020; v1 submitted 12 September, 2020;
originally announced September 2020.
-
On the existence of hidden machines in computational time hierarchies
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
Challenging the standard notion of totality in computable functions, one has that, given any sufficiently expressive formal axiomatic system, there are total functions that, although computable and "intuitively" understood as being total, cannot be proved to be total. In this article we show that this implies the existence of an infinite hierarchy of time complexity classes whose representative me…
▽ More
Challenging the standard notion of totality in computable functions, one has that, given any sufficiently expressive formal axiomatic system, there are total functions that, although computable and "intuitively" understood as being total, cannot be proved to be total. In this article we show that this implies the existence of an infinite hierarchy of time complexity classes whose representative members are hidden from (or unknown by) the respective formal axiomatic systems. Although these classes contain total computable functions, there are some of these functions for which the formal axiomatic system cannot recognize as belonging to a time complexity class. This leads to incompleteness results regarding formalizations of computational complexity.
△ Less
Submitted 2 September, 2020;
originally announced September 2020.
-
Transtemporal edges and crosslayer edges in incompressible high-order networks
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
This work presents some outcomes of a theoretical investigation of incompressible high-order networks defined by a generalized graph representation. We study some of their network topological properties and how these may be related to real-world complex networks. We show that these networks have very short diameter, high k-connectivity, degrees of the order of half of the network size within a str…
▽ More
This work presents some outcomes of a theoretical investigation of incompressible high-order networks defined by a generalized graph representation. We study some of their network topological properties and how these may be related to real-world complex networks. We show that these networks have very short diameter, high k-connectivity, degrees of the order of half of the network size within a strong-asymptotically dominated standard deviation, and rigidity with respect to automorphisms. In addition, we demonstrate that incompressible dynamic (or dynamic multilayered) networks have transtemporal (or crosslayer) edges and, thus, a snapshot-like representation of dynamic networks is inaccurate for capturing the presence of such edges that compose underlying structures of some real-world networks.
△ Less
Submitted 13 May, 2019;
originally announced May 2019.
-
Learning the undecidable from networked systems
Authors:
Felipe S. Abrahão,
Ítala M. Loffredo D'Ottaviano,
Klaus Wehmuth,
Francisco Antônio Dória,
Artur Ziviani
Abstract:
This article presents a theoretical investigation of computation beyond the Turing barrier from emergent behavior in distributed systems. In particular, we present an algorithmic network that is a mathematical model of a networked population of randomly generated computable systems with a fixed communication protocol. Then, in order to solve an undecidable problem, we study how nodes (i.e., Turing…
▽ More
This article presents a theoretical investigation of computation beyond the Turing barrier from emergent behavior in distributed systems. In particular, we present an algorithmic network that is a mathematical model of a networked population of randomly generated computable systems with a fixed communication protocol. Then, in order to solve an undecidable problem, we study how nodes (i.e., Turing machines or computable systems) can harness the power of the metabiological selection and the power of information sharing (i.e., communication) through the network. Formally, we show that there is a pervasive network topological condition, in particular, the small-diameter phenomenon, that ensures that every node becomes capable of solving the halting problem for every program with a length upper bounded by a logarithmic order of the population size. In addition, we show that this result implies the existence of a central node capable of emergently solving the halting problem in the minimum number of communication rounds. Furthermore, we introduce an algorithmic-informational measure of synergy for networked computable systems, which we call local algorithmic synergy. Then, we show that such algorithmic network can produce an arbitrarily large value of expected local algorithmic synergy.
△ Less
Submitted 4 October, 2019; v1 submitted 8 April, 2019;
originally announced April 2019.
-
Expected Emergence of Algorithmic Information from a Lower Bound for Stationary Prevalence
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
We study emergent information in populations of randomly generated networked computable systems that follow a Susceptible-Infected-Susceptible contagion (or infection) model of imitation of the fittest neighbor. These networks have a scale-free degree distribution in the form of a power-law following the Barabási-Albert model. We show that there is a lower bound for the stationary prevalence (or a…
▽ More
We study emergent information in populations of randomly generated networked computable systems that follow a Susceptible-Infected-Susceptible contagion (or infection) model of imitation of the fittest neighbor. These networks have a scale-free degree distribution in the form of a power-law following the Barabási-Albert model. We show that there is a lower bound for the stationary prevalence (or average density of infected nodes) that triggers an unlimited increase of the expected emergent algorithmic complexity (or information) of a node as the population size grows.
△ Less
Submitted 12 December, 2018;
originally announced December 2018.
-
On incompressible multidimensional networks
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Hector Zenil,
Artur Ziviani
Abstract:
In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for new graph abstractions increases. This article presents an investigation of incompressible multidimensional networks defined by generalized graph representations. In particular, we mathematically study the lossless incomp…
▽ More
In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for new graph abstractions increases. This article presents an investigation of incompressible multidimensional networks defined by generalized graph representations. In particular, we mathematically study the lossless incompressibility of snapshot-dynamic networks and multiplex networks in comparison to the lossless incompressibility of more general forms of dynamic networks and multilayer networks, from which snapshot-dynamic networks or multiplex networks are particular cases. We show that incompressible snapshot-dynamic (or multiplex) networks carry an amount of algorithmic information that is linearly dominated by the size of the set of time instants (or layers). This contrasts with the algorithmic information carried by incompressible general dynamic (or multilayer) networks that is of the quadratic order of the size of the set of time instants (or layers). Furthermore, we prove that incompressible general multidimensional networks have edges linking vertices at non-sequential time instants (layers or, in general, elements of a node dimension). Thus, representational incompressibility implies a necessary underlying constraint in the multidimensional network topology.
△ Less
Submitted 29 April, 2020; v1 submitted 3 December, 2018;
originally announced December 2018.
-
Algorithmic information distortions and incompressibility in uniform multidimensional networks
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Hector Zenil,
Artur Ziviani
Abstract:
This article presents a theoretical investigation of generalized encoded forms of networks in a uniform multidimensional space. First, we study encoded networks with (finite) arbitrary node dimensions (or aspects), such as time instants or layers. In particular, we study these networks that are formalized in the form of multiaspect graphs. In the context of node-aligned non-uniform (or node-unalig…
▽ More
This article presents a theoretical investigation of generalized encoded forms of networks in a uniform multidimensional space. First, we study encoded networks with (finite) arbitrary node dimensions (or aspects), such as time instants or layers. In particular, we study these networks that are formalized in the form of multiaspect graphs. In the context of node-aligned non-uniform (or node-unaligned non-uniform and uniform) multidimensional spaces, previous results has shown that, unlike classical graphs, the algorithmic information of a multidimensional network is not in general dominated by the algorithmic information of the binary sequence that determines the presence or absence of edges. In the present work, first we demonstrate the existence of such algorithmic information distortions for node-aligned uniform multidimensional networks. Secondly, we show that there are particular cases of infinite nesting families of finite uniform multidimensional networks such that each member of these families is incompressible. From these results, we also recover the network topological properties and equivalences in irreducible information content of multidimensional networks in comparison to their isomorphic classical graph counterpart in the previous literature. These results together establish a universal algorithmic approach and set limitations and conditions for irreducible information content analysis in comparing arbitrary networks with a large number of dimensions, such as multilayer networks.
△ Less
Submitted 21 April, 2023; v1 submitted 27 October, 2018;
originally announced October 2018.
-
Emergent Open-Endedness from Contagion of the Fittest
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
In this paper, we study emergent irreducible information in populations of randomly generated computable systems that are networked and follow a "Susceptible-Infected-Susceptible" contagion model of imitation of the fittest neighbor. We show that there is a lower bound for the stationary prevalence (or average density of "infected" nodes) that triggers an unlimited increase of the expected local e…
▽ More
In this paper, we study emergent irreducible information in populations of randomly generated computable systems that are networked and follow a "Susceptible-Infected-Susceptible" contagion model of imitation of the fittest neighbor. We show that there is a lower bound for the stationary prevalence (or average density of "infected" nodes) that triggers an unlimited increase of the expected local emergent algorithmic complexity (or information) of a node as the population size grows. We call this phenomenon expected (local) emergent open-endedness. In addition, we show that static networks with a power-law degree distribution following the Barabási-Albert model satisfy this lower bound and, thus, display expected (local) emergent open-endedness.
△ Less
Submitted 21 June, 2018; v1 submitted 16 June, 2018;
originally announced June 2018.
-
Minimal Algorithmic Information Loss Methods for Dimension Reduction, Feature Selection and Network Sparsification
Authors:
Hector Zenil,
Narsis A. Kiani,
Alyssa Adams,
Felipe S. Abrahão,
Antonio Rueda-Toicen,
Allan A. Zea,
Jesper Tegnér
Abstract:
We introduce a family of unsupervised, domain-free, and asymptotically optimal model-independent algorithms based on the principles of algorithmic probability and information theory designed to minimize the loss of algorithmic information, and thereby avoiding certain deceiving phenomena and distortions known to occur in statistics and entropy-based approaches. Our methods include a lossless-compr…
▽ More
We introduce a family of unsupervised, domain-free, and asymptotically optimal model-independent algorithms based on the principles of algorithmic probability and information theory designed to minimize the loss of algorithmic information, and thereby avoiding certain deceiving phenomena and distortions known to occur in statistics and entropy-based approaches. Our methods include a lossless-compression-based lossy compression algorithm that can select and coarse-grain data in an algorithmic-complexity fashion (without the use of popular compression algorithms) by collapsing regions that may procedurally be regenerated from a computable candidate model. We show that the method can perform dimension reduction, denoising, feature selection, and network sparsification, while preserving the properties of the objects. As validation case, we demonstrate the methods on image segmentation against popular methods like PCA and random selection, and also demonstrate that the method preserves the graph-theoretic indices measured on a well-known set of synthetic and real-world networks of very different nature, ranging from degree distribution and clustering coefficient to edge betweenness and degree and eigenvector centralities, achieving equal or significantly better results than other data reduction and the leading network sparsification methods (Spectral, Transitive).
△ Less
Submitted 8 April, 2023; v1 submitted 16 February, 2018;
originally announced February 2018.
-
Algorithmic Networks: central time to trigger expected emergent open-endedness
Authors:
Felipe S. Abrahão,
Klaus Wehmuth,
Artur Ziviani
Abstract:
This article investigates emergence and complexity in complex systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks. One key studied question is how much emergent complexity (or information) arises when a population of computable systems is networked compared with when this population is isola…
▽ More
This article investigates emergence and complexity in complex systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks. One key studied question is how much emergent complexity (or information) arises when a population of computable systems is networked compared with when this population is isolated. First, we define a general model for networked theoretical machines, which we call algorithmic networks. Then, we narrow our scope to investigate algorithmic networks that optimize the average fitnesses of nodes in a scenario in which each node imitates the fittest neighbor and the randomly generated population is networked by a time-varying graph. We show that there are graph-topological conditions that cause these algorithmic networks to have the property of expected emergent open-endedness for large enough populations. In other words, the expected emergent algorithmic complexity of a node tends to infinity as the population size tends to infinity. Given a dynamic network, we show that these conditions imply the existence of a central time to trigger expected emergent open-endedness. Moreover, we show that networks with small diameter compared to the network size meet these conditions. We also discuss future research based on how our results are related to some problems in network science, information theory, computability theory, distributed computing, game theory, evolutionary biology, and synergy in complex systems.
△ Less
Submitted 19 March, 2019; v1 submitted 30 August, 2017;
originally announced August 2017.
-
The "paradox" of computability and a recursive relative version of the Busy Beaver function
Authors:
Felipe S. Abrahão
Abstract:
In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing subm…
▽ More
In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. We will thereby demonstrate the existence of a "paradox" of computability a la Skolem: a function is computable when "seen from the outside" the subsystem, but uncomputable when "seen from within" the same subsystem. Finally, we will raise the possibility of defining universal submachines, and a hierarchy of negative Turing degrees.
△ Less
Submitted 21 December, 2016;
originally announced December 2016.
-
Relativizing an incompressible number and an incompressible function through subrecursive extensions of Turing machines
Authors:
Felipe S. Abrahão
Abstract:
We show in this article that uncomputability is also a relative property of subrecursive classes built on a recursive relative incompressible function, which acts as a higher-order "yardstick" of irreducible information for the respective subrecursive class. We define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function and for the halting probability (…
▽ More
We show in this article that uncomputability is also a relative property of subrecursive classes built on a recursive relative incompressible function, which acts as a higher-order "yardstick" of irreducible information for the respective subrecursive class. We define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function and for the halting probability (or Chaitin's constant) Omega; respectively the Busy Beaver Plus (BBP) function and a time-bounded halting probability. Therefore, we prove that the computable BBP function defined on any Turing submachine is neither computable nor compressible by any program running on this submachine. In addition, we build a Turing submachine that can use lower approximations to its own time-bounded halting probability to calculate the values of its Busy Beaver Plus function, in the "same" manner that universal Turing machines use approximations to Omega to calculate Busy Beaver values. Thus, the algorithmic information carried by the BBP function is relatively incompressible (and uncomputable) at the same time that it still is occasionally reached by submachines. We point that this phenomenon enriches the research on the relativization and simulation of uncomputability and irreducible information.
△ Less
Submitted 15 December, 2016;
originally announced December 2016.
