Showing 1–42 of 42 results for author: Kiani, A

Assembly Theory Reduced to Shannon Entropy and Rendered Redundant by Naive Statistical Algorithms

Authors: Luan Ozelim, Abicumaran Uthamacumaran, Felipe S. Abrahão, Santiago Hernández-Orozco, Narsis A. Kiani, Jesper Tegnér, Hector Zenil

Abstract: In this paper we give answer to an argument trying to show the divergence of Assembly Theory from LZ compression. We formally proved that any implementation of the concept of `copy number' underlying Assembly Theory (AT) and its assembly index (Ai) is equivalent to Shannon Entropy and not fundamentally or methodologically different from algorithms like ZIP and PNG via an LZ compressing grammar. He… ▽ More In this paper we give answer to an argument trying to show the divergence of Assembly Theory from LZ compression. We formally proved that any implementation of the concept of `copy number' underlying Assembly Theory (AT) and its assembly index (Ai) is equivalent to Shannon Entropy and not fundamentally or methodologically different from algorithms like ZIP and PNG via an LZ compressing grammar. Here we show that the weak empirical correlation between Ai and LZW, which the authors offered as a defence against the previously proven result that the assembly index calculation method is an LZ scheme, is based on an incomplete and misleading experiment. When the experiment is completed and conducted properly, the asymptotic convergence to LZ compression and Shannon Entropy is evident and aligned with the mathematical proof previously offered. Therefore, this completes both the theoretical and empirical demonstrations that any variation of the copy-number concept underlying AT, which resorts to counting the number of object repetitions `to arrive at a measure for life', is equivalent to statistical compression and Shannon Entropy. We demonstrate that the authors' `we-are-better-because-we-are-worse' defence argument against compression does not withstand basic scrutiny, and that their primary empirical results separating organic from inorganic compounds have not only been previously reported -- sans claims to unify physics and biology -- but are also driven solely by molecular length, not by any special feature of life captured by their assembly index. Finally, we show that Ai is a special case of our Block Decomposition Method introduced almost a decade earlier. △ Less

Submitted 23 September, 2024; v1 submitted 27 August, 2024; originally announced August 2024.

Comments: 12 figures, 52 pages (minor tweaks and adding about 4 new refs of previous relevant work not cited by the authors of AT)

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.

Comments: 15 pages + appendix, 2 figures

Interfacial Tension Hysteresis of Eutectic Gallium-Indium

Authors: Keith D. Hillaire, Praneshnandan Nithyanandam, Minyung Song, Sahar Rashid Nadimi, Abolfazl Kiani, Michael D. Dickey, Karen E. Daniels

Abstract: When in a pristine state, gallium and its alloys have the largest interfacial tensions of any liquid at room temperature. Nonetheless, applying as little as 0.8 V of electric potential across eutectic gallium indium (EGaIn) placed within aqueous NaOH (or other electrolyte) solution will cause the metal to behave as if its interfacial tension is near zero. The mechanism behind this phenomenon has r… ▽ More When in a pristine state, gallium and its alloys have the largest interfacial tensions of any liquid at room temperature. Nonetheless, applying as little as 0.8 V of electric potential across eutectic gallium indium (EGaIn) placed within aqueous NaOH (or other electrolyte) solution will cause the metal to behave as if its interfacial tension is near zero. The mechanism behind this phenomenon has remained poorly understood because NaOH dissolves the oxide species, making it difficult to directly measure the concentration, thickness, or chemical composition of the film that forms at the interface. In addition, the oxide layers formed are atomically-thin. Here, we present a suite of techniques which allow us to simultaneously measure both electrical and interfacial properties as a function of applied electric potential, allowing for new insights into the mechanisms which cause the dramatic decrease in interfacial tension. A key discovery from this work is that the interfacial tension displays hysteresis while lowering the applied potential. We combine these observations with electrochemical impedance spectroscopy to evaluate how these changes in interfacial tension arise from chemical, electrical, and mechanical changes on the interface, and close with ideas for how to build a free energy model to predict these changes from first principles. △ Less

Submitted 30 October, 2023; originally announced October 2023.

Whispering LLaMA: A Cross-Modal Generative Error Correction Framework for Speech Recognition

Authors: Srijith Radhakrishnan, Chao-Han Huck Yang, Sumeer Ahmad Khan, Rohit Kumar, Narsis A. Kiani, David Gomez-Cabrero, Jesper N. Tegner

Abstract: We introduce a new cross-modal fusion technique designed for generative error correction in automatic speech recognition (ASR). Our methodology leverages both acoustic information and external linguistic representations to generate accurate speech transcription contexts. This marks a step towards a fresh paradigm in generative error correction within the realm of n-best hypotheses. Unlike the exis… ▽ More We introduce a new cross-modal fusion technique designed for generative error correction in automatic speech recognition (ASR). Our methodology leverages both acoustic information and external linguistic representations to generate accurate speech transcription contexts. This marks a step towards a fresh paradigm in generative error correction within the realm of n-best hypotheses. Unlike the existing ranking-based rescoring methods, our approach adeptly uses distinct initialization techniques and parameter-efficient algorithms to boost ASR performance derived from pre-trained speech and text models. Through evaluation across diverse ASR datasets, we evaluate the stability and reproducibility of our fusion technique, demonstrating its improved word error rate relative (WERR) performance in comparison to n-best hypotheses by relatively 37.66%. To encourage future research, we have made our code and pre-trained models open source at https://github.com/Srijith-rkr/Whispering-LLaMA. △ Less

Submitted 16 October, 2023; v1 submitted 10 October, 2023; originally announced October 2023.

Comments: Accepted to EMNLP 2023 as main paper. 10 pages. Revised math notations. GitHub: https://github.com/Srijith-rkr/Whispering-LLaMA

A Parameter-Efficient Learning Approach to Arabic Dialect Identification with Pre-Trained General-Purpose Speech Model

Authors: Srijith Radhakrishnan, Chao-Han Huck Yang, Sumeer Ahmad Khan, Narsis A. Kiani, David Gomez-Cabrero, Jesper N. Tegner

Abstract: In this work, we explore Parameter-Efficient-Learning (PEL) techniques to repurpose a General-Purpose-Speech (GSM) model for Arabic dialect identification (ADI). Specifically, we investigate different setups to incorporate trainable features into a multi-layer encoder-decoder GSM formulation under frozen pre-trained settings. Our architecture includes residual adapter and model reprogramming (inpu… ▽ More In this work, we explore Parameter-Efficient-Learning (PEL) techniques to repurpose a General-Purpose-Speech (GSM) model for Arabic dialect identification (ADI). Specifically, we investigate different setups to incorporate trainable features into a multi-layer encoder-decoder GSM formulation under frozen pre-trained settings. Our architecture includes residual adapter and model reprogramming (input-prompting). We design a token-level label mapping to condition the GSM for Arabic Dialect Identification (ADI). This is challenging due to the high variation in vocabulary and pronunciation among the numerous regional dialects. We achieve new state-of-the-art accuracy on the ADI-17 dataset by vanilla fine-tuning. We further reduce the training budgets with the PEL method, which performs within 1.86% accuracy to fine-tuning using only 2.5% of (extra) network trainable parameters. Our study demonstrates how to identify Arabic dialects using a small dataset and limited computation with open source code and pre-trained models. △ Less

Submitted 3 October, 2023; v1 submitted 18 May, 2023; originally announced May 2023.

Comments: Accepted to Interspeech 2023, 5 pages. Code is available at: https://github.com/Srijith-rkr/KAUST-Whisper-Adapter under MIT license

IHCV: Discovery of Hidden Time-Dependent Control Variables in Non-Linear Dynamical Systems

Authors: Juan Munoz, Subash Balsamy, Juan P. Bernal-Tamayo, Ali Balubaid, Alberto Maillo Ruiz de Infante, Vincenzo Lagani, David Gomez-Cabrero, Narsis A. Kiani, Jesper Tegner

Abstract: Discovering non-linear dynamical models from data is at the core of science. Recent progress hinges upon sparse regression of observables using extensive libraries of candidate functions. However, it remains challenging to model hidden non-observable control variables governing switching between different dynamical regimes. Here we develop a data-efficient derivative-free method, IHCV, for the Ide… ▽ More Discovering non-linear dynamical models from data is at the core of science. Recent progress hinges upon sparse regression of observables using extensive libraries of candidate functions. However, it remains challenging to model hidden non-observable control variables governing switching between different dynamical regimes. Here we develop a data-efficient derivative-free method, IHCV, for the Identification of Hidden Control Variables. First, the performance and robustness of IHCV against noise are evaluated by benchmarking the IHCV method using well-known bifurcation models (saddle-node, transcritical, pitchfork, Hopf). Next, we demonstrate that IHCV discovers hidden driver variables in the Lorenz, van der Pol, Hodgkin-Huxley, and Fitzhugh-Nagumo models. Finally, IHCV generalizes to the case when only partial observational is given, as demonstrated using the toggle switch model, the genetic repressilator oscillator, and a Waddington landscape model. Our proof-of-principle illustrates that utilizing normal forms could facilitate the data-efficient and scalable discovery of hidden variables controlling transitions between different dynamical regimes and non-linear models. △ Less

Submitted 5 April, 2023; originally announced April 2023.

Comments: 12 pages, 2 figures

MSC Class: 37M20

Latency-aware End-to-end Multi-path Data Transmission for URLLC Services

Authors: Liu Cao, Abbas Kiani, Amanda Xiang, Kaippallimalil John, Tony Saboorian

Abstract: 5th Generation Mobile Communication Technology (5G) utilizes the Access Traffic Steering, Switching, and Splitting (ATSSS) rule to enable multi-path data transmission, which is currently being standardized. Recently, the 3rd Generation Partnership Project (3GPP) SA1 and SA2 have been working on the multi-path solution for possible improvement from different perspectives. However, the existing 3GPP… ▽ More 5th Generation Mobile Communication Technology (5G) utilizes the Access Traffic Steering, Switching, and Splitting (ATSSS) rule to enable multi-path data transmission, which is currently being standardized. Recently, the 3rd Generation Partnership Project (3GPP) SA1 and SA2 have been working on the multi-path solution for possible improvement from different perspectives. However, the existing 3GPP multi-path solution has some limitations on ultra-reliable low-latency communication (URLLC) traffic in terms of reliability and latency requirements. In order to capture the potential gains of multi-path architecture in the context of URLLC services, this paper proposes a novel traffic splitting technique that can more efficiently enjoy the benefit of multi-path architecture in reducing user equipment (UE) uplink (UL) end-to-end (E2E) latency. In particular, we formulate an optimization framework that minimizes user's UL E2E latency via the joint optimization on the ratio of traffic assigned to each path and their corresponding transmit power. The performance of the proposed scheme is evaluated via well-designed simulations. △ Less

Submitted 21 October, 2023; v1 submitted 24 October, 2022; originally announced October 2022.

Comments: This work has been submitted to the IEEE for possible publication. 5 pages, 6 figures

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 an encoding scheme widely used by popular statistical compression algorithms. We show that in all cases (synthetic or natural) AT performs similarly to other simple coding schemes and underperforms compared to system-related indexes based upon algorithmic probability that take into account statistical repetitions bu… ▽ More We demonstrate that the assembly pathway method underlying assembly theory (AT) is an encoding scheme widely used by popular statistical compression algorithms. We show that in all cases (synthetic or natural) AT performs similarly to other simple coding schemes and underperforms compared to system-related indexes based upon algorithmic probability that take into account statistical repetitions but also the likelihood of other computable patterns. Our results imply that the assembly index does not offer substantial improvements over existing methods, including traditional statistical ones, and imply that the separation between living and non-living compounds following these methods has been reported before. △ Less

Submitted 14 August, 2024; v1 submitted 30 September, 2022; originally announced October 2022.

Journal ref: npj Systems Biology and Applications, volume 10, number 82, year 2024

Smart Traffic Monitoring System using Computer Vision and Edge Computing

Authors: Guanxiong Liu, Hang Shi, Abbas Kiani, Abdallah Khreishah, Jo Young Lee, Nirwan Ansari, Chengjun Liu, Mustafa Yousef

Abstract: Traffic management systems capture tremendous video data and leverage advances in video processing to detect and monitor traffic incidents. The collected data are traditionally forwarded to the traffic management center (TMC) for in-depth analysis and may thus exacerbate the network paths to the TMC. To alleviate such bottlenecks, we propose to utilize edge computing by equipping edge nodes that a… ▽ More Traffic management systems capture tremendous video data and leverage advances in video processing to detect and monitor traffic incidents. The collected data are traditionally forwarded to the traffic management center (TMC) for in-depth analysis and may thus exacerbate the network paths to the TMC. To alleviate such bottlenecks, we propose to utilize edge computing by equipping edge nodes that are close to cameras with computing resources (e.g. cloudlets). A cloudlet, with limited computing resources as compared to TMC, provides limited video processing capabilities. In this paper, we focus on two common traffic monitoring tasks, congestion detection, and speed detection, and propose a two-tier edge computing based model that takes into account of both the limited computing capability in cloudlets and the unstable network condition to the TMC. Our solution utilizes two algorithms for each task, one implemented at the edge and the other one at the TMC, which are designed with the consideration of different computing resources. While the TMC provides strong computation power, the video quality it receives depends on the underlying network conditions. On the other hand, the edge processes very high-quality video but with limited computing resources. Our model captures this trade-off. We evaluate the performance of the proposed two-tier model as well as the traffic monitoring algorithms via test-bed experiments under different weather as well as network conditions and show that our proposed hybrid edge-cloud solution outperforms both the cloud-only and edge-only solutions. △ Less

Submitted 7 September, 2021; originally announced September 2021.

Interfacial Tension Modulation of Liquid Metal via Electrochemical Oxidation

Authors: Minyung Song, Karen E. Daniels, Abolfazl Kiani, Sahar Rashidnadimi, Michael D. Dickey

Abstract: This progress report summarizes recent studies of electrochemical oxidation to modulate the interfacial tension of gallium-based alloys. These alloys, which are liquid at ambient conditions, have the largest interfacial tension of any liquid at room temperature. The ability to modulate the tension offers the possibility to create forces that change the shape and position of the metal. It has been… ▽ More This progress report summarizes recent studies of electrochemical oxidation to modulate the interfacial tension of gallium-based alloys. These alloys, which are liquid at ambient conditions, have the largest interfacial tension of any liquid at room temperature. The ability to modulate the tension offers the possibility to create forces that change the shape and position of the metal. It has been known since the late 1800s that electrocapillarity-the use of potential to modulate the electric double layer on the surface of metals in electrolyte-lowers the interfacial tension of liquid metal. Yet, this phenomenon can only achieve modest changes in interfacial tension since it is limited to potential windows that avoid reactions. A recent discovery suggests that reactions driven by the electrochemical oxidation of gallium alloys cause the interfacial tension to decrease from ~500 mN/m at 0 V to ~0 mN/m at ~0.8 V, a change in tension that goes well beyond what is possible via conventional electrocapillarity or surfactants. The changes in tension are reversible; reductive potentials return the metal back to a state of high interfacial tension. This report aims to summarize key work and introduce beginners to this field by including electrochemistry basics while addressing misconceptions. We discuss applications that utilize modulations in interfacial tension of liquid metal and conclude with remaining opportunities and challenges that need further investigation. △ Less

Submitted 3 February, 2021; originally announced February 2021.

CheXpedition: Investigating Generalization Challenges for Translation of Chest X-Ray Algorithms to the Clinical Setting

Authors: Pranav Rajpurkar, Anirudh Joshi, Anuj Pareek, Phil Chen, Amirhossein Kiani, Jeremy Irvin, Andrew Y. Ng, Matthew P. Lungren

Abstract: Although there have been several recent advances in the application of deep learning algorithms to chest x-ray interpretation, we identify three major challenges for the translation of chest x-ray algorithms to the clinical setting. We examine the performance of the top 10 performing models on the CheXpert challenge leaderboard on three tasks: (1) TB detection, (2) pathology detection on photos of… ▽ More Although there have been several recent advances in the application of deep learning algorithms to chest x-ray interpretation, we identify three major challenges for the translation of chest x-ray algorithms to the clinical setting. We examine the performance of the top 10 performing models on the CheXpert challenge leaderboard on three tasks: (1) TB detection, (2) pathology detection on photos of chest x-rays, and (3) pathology detection on data from an external institution. First, we find that the top 10 chest x-ray models on the CheXpert competition achieve an average AUC of 0.851 on the task of detecting TB on two public TB datasets without fine-tuning or including the TB labels in training data. Second, we find that the average performance of the models on photos of x-rays (AUC = 0.916) is similar to their performance on the original chest x-ray images (AUC = 0.924). Third, we find that the models tested on an external dataset either perform comparably to or exceed the average performance of radiologists. We believe that our investigation will inform rapid translation of deep learning algorithms to safe and effective clinical decision support tools that can be validated prospectively with large impact studies and clinical trials. △ Less

Submitted 11 March, 2020; v1 submitted 26 February, 2020; originally announced February 2020.

Comments: Accepted as workshop paper at ACM Conference on Health, Inference, and Learning (CHIL) 2020

Evolving Neural Networks through a Reverse Encoding Tree

Authors: Haoling Zhang, Chao-Han Huck Yang, Hector Zenil, Narsis A. Kiani, Yue Shen, Jesper N. Tegner

Abstract: NeuroEvolution is one of the most competitive evolutionary learning frameworks 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 advan… ▽ More NeuroEvolution is one of the most competitive evolutionary learning frameworks 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 algorithms. The results show that the two proposed strategies 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. △ Less

Submitted 31 March, 2020; v1 submitted 2 February, 2020; originally announced February 2020.

Comments: Accepted to IEEE Congress on Evolutionary Computation (IEEE CEC) 2020. Lecture Presentation

Journal ref: 2020 IEEE Congress on Evolutionary Computation (CEC)

Sepsis World Model: A MIMIC-based OpenAI Gym "World Model" Simulator for Sepsis Treatment

Authors: Amirhossein Kiani, Chris Wang, Angela Xu

Abstract: Sepsis is a life-threatening condition caused by the body's response to an infection. In order to treat patients with sepsis, physicians must control varying dosages of various antibiotics, fluids, and vasopressors based on a large number of variables in an emergency setting. In this project we employ a "world model" methodology to create a simulator that aims to predict the next state of a patien… ▽ More Sepsis is a life-threatening condition caused by the body's response to an infection. In order to treat patients with sepsis, physicians must control varying dosages of various antibiotics, fluids, and vasopressors based on a large number of variables in an emergency setting. In this project we employ a "world model" methodology to create a simulator that aims to predict the next state of a patient given a current state and treatment action. In doing so, we hope our simulator learns from a latent and less noisy representation of the EHR data. Using historical sepsis patient records from the MIMIC dataset, our method creates an OpenAI Gym simulator that leverages a Variational Auto-Encoder and a Mixture Density Network combined with a RNN (MDN-RNN) to model the trajectory of any sepsis patient in the hospital. To reduce the effects of noise, we sample from a generated distribution of next steps during simulation and have the option of introducing uncertainty into our simulator by controlling the "temperature" variable. It is worth noting that we do not have access to the ground truth for the best policy because we can only evaluate learned policies by real-world experimentation or expert feedback. Instead, we aim to study our simulator model's performance by evaluating the similarity between our environment's rollouts with the real EHR data and assessing its viability for learning a realistic policy for sepsis treatment using Deep Q-Learning. △ Less

Submitted 15 December, 2019; originally announced December 2019.

Comments: This project was done as a class project for CS221 at Stanford University

Deep Learning for the Digital Pathologic Diagnosis of Cholangiocarcinoma and Hepatocellular Carcinoma: Evaluating the Impact of a Web-based Diagnostic Assistant

Authors: Bora Uyumazturk, Amirhossein Kiani, Pranav Rajpurkar, Alex Wang, Robyn L. Ball, Rebecca Gao, Yifan Yu, Erik Jones, Curtis P. Langlotz, Brock Martin, Gerald J. Berry, Michael G. Ozawa, Florette K. Hazard, Ryanne A. Brown, Simon B. Chen, Mona Wood, Libby S. Allard, Lourdes Ylagan, Andrew Y. Ng, Jeanne Shen

Abstract: While artificial intelligence (AI) algorithms continue to rival human performance on a variety of clinical tasks, the question of how best to incorporate these algorithms into clinical workflows remains relatively unexplored. We investigated how AI can affect pathologist performance on the task of differentiating between two subtypes of primary liver cancer, hepatocellular carcinoma (HCC) and chol… ▽ More While artificial intelligence (AI) algorithms continue to rival human performance on a variety of clinical tasks, the question of how best to incorporate these algorithms into clinical workflows remains relatively unexplored. We investigated how AI can affect pathologist performance on the task of differentiating between two subtypes of primary liver cancer, hepatocellular carcinoma (HCC) and cholangiocarcinoma (CC). We developed an AI diagnostic assistant using a deep learning model and evaluated its effect on the diagnostic performance of eleven pathologists with varying levels of expertise. Our deep learning model achieved an accuracy of 0.885 on an internal validation set of 26 slides and an accuracy of 0.842 on an independent test set of 80 slides. Despite having high accuracy on a hold out test set, the diagnostic assistant did not significantly improve performance across pathologists (p-value: 0.184, OR: 1.287 (95% CI 0.886, 1.871)). Model correctness was observed to significantly bias the pathologist decisions. When the model was correct, assistance significantly improved accuracy across all pathologist experience levels and for all case difficulty levels (p-value: < 0.001, OR: 4.289 (95% CI 2.360, 7.794)). When the model was incorrect, assistance significantly decreased accuracy across all 11 pathologists and for all case difficulty levels (p-value < 0.001, OR: 0.253 (95% CI 0.126, 0.507)). Our results highlight the challenges of translating AI models to the clinical setting, especially for difficult subspecialty tasks such as tumor classification. In particular, they suggest that incorrect model predictions could strongly bias an expert's diagnosis, an important factor to consider when designing medical AI-assistance systems. △ Less

Submitted 17 November, 2019; originally announced November 2019.

Comments: Machine Learning for Health (ML4H) at NeurIPS 2019 - Extended Abstract

Algorithmic Probability-guided Supervised Machine Learning on Non-differentiable Spaces

Authors: Santiago Hernández-Orozco, Hector Zenil, Jürgen Riedel, Adam Uccello, Narsis A. Kiani, Jesper Tegnér

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 new approach requires less training data and is more generalizable as it shows greater resilience to random attacks. We investigate the shape of the discrete algorithmic space when performing regression or classification using a loss function… ▽ More 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 new approach requires less training data and is more generalizable as it shows greater resilience to random attacks. We investigate the shape of the discrete algorithmic space when performing regression or classification using a loss function parametrized by algorithmic complexity, demonstrating that the property of differentiation is not necessary 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 (i) machine learning can successfully be performed on a non-smooth surface using algorithmic complexity; (ii) that parameter 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; (iii) a formulation of an algorithmically directed search technique in non-smooth manifolds can be defined and conducted; (iv) 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. △ Less

Submitted 8 October, 2019; v1 submitted 7 October, 2019; originally announced October 2019.

Comments: 33 pages including appendix

Estimations of Integrated Information Based on Algorithmic Complexity and Dynamic Querying

Authors: Alberto Hernández-Espinosa, Héctor Zenil, Narsis A. Kiani, Jesper Tegnér

Abstract: The concept of information has emerged as a language in its own right, bridging several disciplines that analyze natural phenomena and man-made systems. Integrated information has been introduced as a metric to quantify the amount of information generated by a system beyond the information generated by its elements. Yet, this intriguing notion comes with the price of being prohibitively expensive… ▽ More The concept of information has emerged as a language in its own right, bridging several disciplines that analyze natural phenomena and man-made systems. Integrated information has been introduced as a metric to quantify the amount of information generated by a system beyond the information generated by its elements. Yet, this intriguing notion comes with the price of being prohibitively expensive to calculate, since the calculations require an exponential number of sub-divisions of a system. Here we introduce a novel framework to connect algorithmic randomness and integrated information and a numerical method for estimating integrated information using a perturbation test rooted in algorithmic information dynamics. This method quantifies the change in program size of a system when subjected to a perturbation. The intuition behind is that if an object is random then random perturbations have little to no effect to what happens when a shorter program but when an object has the ability to move in both directions (towards or away from randomness) it will be shown to be better integrated as a measure of sophistication telling apart randomness and simplicity from structure. We show that an object with a high integrated information value is also more compressible, and is, therefore, more sensitive to perturbations. We find that such a perturbation test quantifying compression sensitivity provides a system with a means to extract explanations--causal accounts--of its own behaviour. Our technique can reduce the number of calculations to arrive at some bounds or estimations, as the algorithmic perturbation test guides an efficient search for estimating integrated information. Our work sets the stage for a systematic exploration of connections between algorithmic complexity and integrated information at the level of both theory and practice. △ Less

Submitted 6 June, 2019; v1 submitted 9 April, 2019; originally announced April 2019.

Comments: 33 pages + Appendix = 44 pages

Journal ref: Entropy, 2019

Energy Efficient Resource Allocation in EH-enabled CR Networks for IoT

Authors: Ali Shahini, Abbas Kiani, Nirwan Ansari

Abstract: With the rapid growth of Internet of Things (IoT) devices, the next generation mobile networks demand for more operating frequency bands. By leveraging the underutilized radio spectrum, the cognitive radio (CR) technology is considered as a promising solution for spectrum scarcity problem of IoT applications. In parallel with the development of CR techniques, Wireless Energy Harvesting (WEH) is co… ▽ More With the rapid growth of Internet of Things (IoT) devices, the next generation mobile networks demand for more operating frequency bands. By leveraging the underutilized radio spectrum, the cognitive radio (CR) technology is considered as a promising solution for spectrum scarcity problem of IoT applications. In parallel with the development of CR techniques, Wireless Energy Harvesting (WEH) is considered as one of the emerging technologies to eliminate the need of recharging or replacing the batteries for IoT and CR networks. To this end, we propose to utilize WEH for CR networks in which the CR devices are not only capable of sensing the available radio frequencies in a collaborative manner but also harvesting the wireless energy transferred by an Access Point (AP). More importantly, we design an optimization framework that captures a fundamental tradeoff between energy efficiency (EE) and spectral efficiency (SE) of the network. In particular, we formulate a Mixed Integer Nonlinear Programming (MINLP) problem that maximizes EE while taking into consideration of users' buffer occupancy, data rate fairness, energy causality constraints and interference constraints. We further prove that the proposed optimization framework is an NP-Hard problem. Thus, we propose a low complex heuristic algorithm, called INSTANT, to solve the resource allocation and energy harvesting optimization problem. The proposed algorithm is shown to be capable of achieving near optimal solution with high accuracy while having polynomial complexity. The efficiency of our proposal is validated through well designed simulations. △ Less

Submitted 6 July, 2018; originally announced July 2018.

Hierarchical Capacity Provisioning for Fog Computing

Authors: Abbas Kiani, Nirwan Ansari, Abdallah Khreishah

Abstract: The concept of fog computing is centered around providing computation resources at the edge of network, thereby reducing the latency and improving the quality of service. However, it is still desirable to investigate how and where at the edge of the network the computation capacity should be provisioned. To this end, we propose a hierarchical capacity provisioning scheme. In particular, we conside… ▽ More The concept of fog computing is centered around providing computation resources at the edge of network, thereby reducing the latency and improving the quality of service. However, it is still desirable to investigate how and where at the edge of the network the computation capacity should be provisioned. To this end, we propose a hierarchical capacity provisioning scheme. In particular, we consider a two-tier network architecture consisting of shallow and deep cloudlets and explore the benefits of hierarchical capacity based on queueing analysis. Moreover, we explore two different network scenarios in which the network delay between the two tiers is negligible as well as the case that the deep cloudlet is located somewhere deeper in the network and thus the delay is significant. More importantly, we model the first network delay scenario with bufferless shallow cloudlets as well as the second scenario with finite-size buffer shallow cloudlets, and formulate an optimization problem for each model. We also use stochastic ordering to solve the optimization problem formulated for the first model and an upper bound based technique is proposed for the second model. The performance of the proposed scheme is evaluated via simulations in which we show the accuracy of the proposed upper bound technique as well as the queue length estimation approach for both randomly generated input and real trace data. △ Less

Submitted 3 July, 2018; originally announced July 2018.

Comments: Submitted to IEEE/ACM Transactions on Networking (June 2017)

Report number: TR-ANL-2017-002

The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

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-random… ▽ More 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. △ Less

Submitted 6 June, 2019; v1 submitted 18 May, 2018; originally announced May 2018.

Comments: 30 pages

Journal ref: Entropy, 21(6), 560, 2019

Symmetry and Algorithmic Complexity of Polyominoes and Polyhedral Graphs

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

Abstract: We introduce a definition of algorithmic symmetry able to capture essential aspects of geometric symmetry. We review, study and apply a method for approximating the algorithmic complexity (also known as Kolmogorov-Chaitin complexity) of graphs and networks based on the concept of Algorithmic Probability (AP). AP is a concept (and method) capable of recursively enumeration all properties of computa… ▽ More We introduce a definition of algorithmic symmetry able to capture essential aspects of geometric symmetry. We review, study and apply a method for approximating the algorithmic complexity (also known as Kolmogorov-Chaitin complexity) of graphs and networks based on the concept of Algorithmic Probability (AP). AP is a concept (and method) capable of recursively enumeration all properties of computable (causal) nature beyond statistical regularities. We explore the connections of algorithmic complexity---both theoretical and numerical---with geometric properties mainly symmetry and topology from an (algorithmic) information-theoretic perspective. We show that approximations to algorithmic complexity by lossless compression and an Algorithmic Probability-based method can characterize properties of polyominoes, polytopes, regular and quasi-regular polyhedra as well as polyhedral networks, thereby demonstrating its profiling capabilities. △ Less

Submitted 24 February, 2018; originally announced March 2018.

Comments: 18 pages, 4 figures + Appendix (1 figure)

Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism

Authors: Hector Zenil, Narsis A. Kiani, Allan A. Zea, Jesper Tegnér

Abstract: Complex data usually results from the interaction of objects produced by different generating mechanisms. Here we introduce a universal, unsupervised and parameter-free model-oriented approach, based upon the seminal concept of algorithmic probability, that decomposes an observation into its most likely algorithmic generative sources. Our approach uses a causal calculus to infer model representati… ▽ More Complex data usually results from the interaction of objects produced by different generating mechanisms. Here we introduce a universal, unsupervised and parameter-free model-oriented approach, based upon the seminal concept of algorithmic probability, that decomposes an observation into its most likely algorithmic generative sources. Our approach uses a causal calculus to infer model representations. We demonstrate its ability to deconvolve interacting mechanisms regardless of whether the resultant objects are strings, space-time evolution diagrams, images or networks. While this is mostly a conceptual contribution and a novel framework, we provide numerical evidence evaluating the ability of our methods to separate data from observations produced by discrete dynamical systems such as cellular automata and complex networks. We think that these separating techniques can contribute to tackling the challenge of causation, thus complementing other statistically oriented approaches. △ Less

Submitted 12 September, 2018; v1 submitted 18 February, 2018; originally announced February 2018.

Comments: 29 pages + 7 Sup Inf. 9 figures in total

Algorithmic Information Dynamics of Persistent Patterns and Colliding Particles in the Game of Life

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

Abstract: Without loss of generalisation to other systems, including possibly non-deterministic ones, we demonstrate the application of methods drawn from algorithmic information dynamics to the characterisation and classification of emergent and persistent patterns, motifs and colliding particles in Conway's Game of Life (GoL), a cellular automaton serving as a case study illustrating the way in which such… ▽ More Without loss of generalisation to other systems, including possibly non-deterministic ones, we demonstrate the application of methods drawn from algorithmic information dynamics to the characterisation and classification of emergent and persistent patterns, motifs and colliding particles in Conway's Game of Life (GoL), a cellular automaton serving as a case study illustrating the way in which such ideas can be applied to a typical discrete dynamical system. We explore the issue of local observations of closed systems whose orbits may appear open because of inaccessibility to the global rules governing the overall system. We also investigate aspects of symmetry related to complexity in the distribution of patterns that occur with high frequency in GoL (which we thus call motifs) and analyse the distribution of these motifs with a view to tracking the changes in their algorithmic probability over time. We demonstrate how the tools introduced are an alternative to other computable measures that are unable to capture changes in emergent structures in evolving complex systems that are often too small or too subtle to be properly characterised by methods such as lossless compression and Shannon entropy. △ Less

Submitted 5 April, 2018; v1 submitted 17 February, 2018; originally announced February 2018.

Comments: 18 pages + 1 sup page, 8 figures in total. Online complexity calculator: http://complexitycalculator.com/

Algorithmic Complexity and Reprogrammability of Chemical Structure Networks

Authors: Hector Zenil, Narsis A. Kiani, Ming-Mei Shang, Jesper Tegnér

Abstract: Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of applying a computational interventional calculus based on the principles of algorithmic probability to chemical structure networks. We profile the sensitivity of the elements and covalent bonds in a chemical structure networ… ▽ More Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of applying a computational interventional calculus based on the principles of algorithmic probability to chemical structure networks. We profile the sensitivity of the elements and covalent bonds in a chemical structure network algorithmically, asking whether reprogrammability affords information about thermodynamic and chemical processes involved in the transformation of different compound classes. We arrive at numerical results suggesting a correspondence between some physical, structural and functional properties. Our methods are capable of separating chemical classes that reflect functional and natural differences without considering any information about atomic and molecular properties. We conclude that these methods, with their links to chemoinformatics via algorithmic, probability hold promise for future research. △ Less

Submitted 18 March, 2018; v1 submitted 16 February, 2018; originally announced February 2018.

Comments: 19 pages + Appendix

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 present a novel, domain-agnostic, model-independent, unsupervised, and universally applicable approach for data summarization. Specifically, 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… ▽ More We present a novel, domain-agnostic, model-independent, unsupervised, and universally applicable approach for data summarization. Specifically, 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. Our approach outperforms state-of-the-art network reduction techniques by achieving an average improvement in feature preservation. Previous methods grounded in statistics or classical information theory have been limited in their ability to capture more intricate patterns and features, particularly nonlinear patterns stemming from deterministic computable processes. Moreover, these approaches heavily rely on a priori feature selection, demanding constant supervision. Our findings demonstrate the effectiveness of the algorithms proposed in this study in overcoming these limitations, all while maintaining a time-efficient computational profile. In many instances, our approach not only matches but also surpasses the performance of established network reduction algorithms. Furthermore, we extend the applicability of our method to lossy compression tasks involving images or any bi-dimensional data. This highlights the versatility and broad utility of our approach in various domains. △ Less

Submitted 27 August, 2024; v1 submitted 16 February, 2018; originally announced February 2018.

Comments: Online implementation at http://complexitycalculator.com/MILS/

Soft Computing Techniques for Dependable Cyber-Physical Systems

Authors: Muhammad Atif, Siddique Latif, Rizwan Ahmad, Adnan Khalid Kiani, Junaid Qadir, Adeel Baig, Hisao Ishibuchi, Waseem Abbas

Abstract: Cyber-Physical Systems (CPS) allow us to manipulate objects in the physical world by providing a communication bridge between computation and actuation elements. In the current scheme of things, this sought-after control is marred by limitations inherent in the underlying communication network(s) as well as by the uncertainty found in the physical world. These limitations hamper fine-grained contr… ▽ More Cyber-Physical Systems (CPS) allow us to manipulate objects in the physical world by providing a communication bridge between computation and actuation elements. In the current scheme of things, this sought-after control is marred by limitations inherent in the underlying communication network(s) as well as by the uncertainty found in the physical world. These limitations hamper fine-grained control of elements that may be separated by large-scale distances. In this regard, soft computing is an emerging paradigm that can help to overcome the vulnerabilities, and unreliability of CPS by using techniques including fuzzy systems, neural network, evolutionary computation, probabilistic reasoning and rough sets. In this paper, we present a comprehensive contemporary review of soft computing techniques for CPS dependability modeling, analysis, and improvement. This paper provides an overview of CPS applications, explores the foundations of dependability engineering, and highlights the potential role of soft computing techniques for CPS dependability with various case studies, while identifying common pitfalls and future directions. In addition, this paper provides a comprehensive survey on the use of various soft computing techniques for making CPS dependable. △ Less

Submitted 27 July, 2020; v1 submitted 25 January, 2018; originally announced January 2018.

Comments: IEEE Access

Predictive Systems Toxicology

Authors: Narsis A. Kiani, Ming-Mei Shang, Hector Zenil, Jesper Tegnér

Abstract: In this review we address to what extent computational techniques can augment our ability to predict toxicity. The first section provides a brief history of empirical observations on toxicity dating back to the dawn of Sumerian civilization. Interestingly, the concept of dose emerged very early on, leading up to the modern emphasis on kinetic properties, which in turn encodes the insight that toxi… ▽ More In this review we address to what extent computational techniques can augment our ability to predict toxicity. The first section provides a brief history of empirical observations on toxicity dating back to the dawn of Sumerian civilization. Interestingly, the concept of dose emerged very early on, leading up to the modern emphasis on kinetic properties, which in turn encodes the insight that toxicity is not solely a property of a compound but instead depends on the interaction with the host organism. The next logical step is the current conception of evaluating drugs from a personalized medicine point-of-view. We review recent work on integrating what could be referred to as classical pharmacokinetic analysis with emerging systems biology approaches incorporating multiple omics data. These systems approaches employ advanced statistical analytical data processing complemented with machine learning techniques and use both pharmacokinetic and omics data. We find that such integrated approaches not only provide improved predictions of toxicity but also enable mechanistic interpretations of the molecular mechanisms underpinning toxicity and drug resistance. We conclude the chapter by discussing some of the main challenges, such as how to balance the inherent tension between the predictive capacity of models, which in practice amounts to constraining the number of features in the models versus allowing for rich mechanistic interpretability, i.e. equipping models with numerous molecular features. This challenge also requires patient-specific predictions on toxicity, which in turn requires proper stratification of patients as regards how they respond, with or without adverse toxic effects. In summary, the transformation of the ancient concept of dose is currently successfully operationalized using rich integrative data encoded in patient-specific models. △ Less

Submitted 15 January, 2018; originally announced January 2018.

Comments: 37 pages, 3 figures. As accepted for the volume in reference

Journal ref: Computational Toxicology - Methods and Protocols, series in Methods in Molecular Biology, Springer Nature, 2017

Edge Computing Aware NOMA for 5G Networks

Authors: Abbas Kiani, Nirwan Ansari

Abstract: With the fast development of Internet of things (IoT), the fifth generation (5G) wireless networks need to provide massive connectivity of IoT devices and meet the demand for low latency. To satisfy these requirements, Non-Orthogonal Multiple Access (NOMA) has been recognized as a promising solution for 5G networks to significantly improve the network capacity. In parallel with the development of… ▽ More With the fast development of Internet of things (IoT), the fifth generation (5G) wireless networks need to provide massive connectivity of IoT devices and meet the demand for low latency. To satisfy these requirements, Non-Orthogonal Multiple Access (NOMA) has been recognized as a promising solution for 5G networks to significantly improve the network capacity. In parallel with the development of NOMA techniques, Mobile Edge Computing (MEC) is becoming one of the key emerging technologies to reduce the latency and improve the Quality of Service (QoS) for 5G networks. In order to capture the potential gains of NOMA in the context of MEC, this paper proposes an edge computing aware NOMA technique which can enjoy the benefits of uplink NOMA in reducing MEC users' uplink energy consumption. To this end, we formulate a NOMA based optimization framework which minimizes the energy consumption of MEC users via optimizing the user clustering, computing and communication resource allocation, and transmit powers. In particular, similar to frequency Resource Blocks (RBs), we divide the computing capacity available at the cloudlet to computing RBs. Accordingly, we explore the joint allocation of the frequency and computing RBs to the users that are assigned to different order indices within the NOMA clusters. We also design an efficient heuristic algorithm for user clustering and RBs allocation, and formulate a convex optimization problem for the power control to be solved independently per NOMA cluster. The performance of the proposed NOMA scheme is evaluated via simulations. △ Less

Submitted 13 December, 2017; originally announced December 2017.

Report number: TR-ANL-2017-007

Journal ref: IEEE Internet of Things Journal, 2018

An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems

Authors: Hector Zenil, Narsis A. Kiani, Francesco Marabita, Yue Deng, Szabolcs Elias, Angelika Schmidt, Gordon Ball, Jesper Tegnér

Abstract: We demonstrate that the algorithmic information content of a system is deeply connected to its potential dynamics, thus affording an avenue for moving systems in the information-theoretic space and controlling them in the phase space. To this end we performed experiments and validated the results on (1) a very large set of small graphs, (2) a number of larger networks with different topologies, an… ▽ More We demonstrate that the algorithmic information content of a system is deeply connected to its potential dynamics, thus affording an avenue for moving systems in the information-theoretic space and controlling them in the phase space. To this end we performed experiments and validated the results on (1) a very large set of small graphs, (2) a number of larger networks with different topologies, and (3) biological networks 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 high quality databases (Harvard's CellNet) with results conforming to experimentally validated biological data. Based on these results we introduce a conceptual framework, a model-based interventional calculus and a reprogrammability measure with which to steer, manipulate, and reconstruct the dynamics of non- linear dynamical systems from partial and disordered observations. The method consists in finding and applying a series of controlled interventions to a dynamical system to estimate how its algorithmic information content is affected when every one of its elements are perturbed. The approach represents an alternative to numerical simulation and statistical approaches for inferring causal mechanistic/generative models and finding first principles. We demonstrate the framework's capabilities by reconstructing the phase space of some discrete dynamical systems (cellular automata) as case study and reconstructing their generating rules. We thus advance tools for reprogramming artificial and living systems without full knowledge or access to the system's actual kinetic equations or probability distributions yielding a suite of universal and parameter-free algorithms of wide applicability ranging from causation, dimension reduction, feature selection and model generation. △ Less

Submitted 5 April, 2018; v1 submitted 15 September, 2017; originally announced September 2017.

Comments: 50 pages with Supplementary Information and Extended Figures. The Online Algorithmic Complexity Calculator implements the methods in this paper: http://complexitycalculator.com/ Animated video available at: https://youtu.be/ufzq2p5tVLI

Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, and modularity

Authors: Santiago Hernández-Orozco, Narsis A. Kiani, Hector Zenil

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, parti… ▽ More 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 statistical uniform but \textit{algorithmic 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 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. △ Less

Submitted 20 June, 2018; v1 submitted 1 September, 2017; originally announced September 2017.

Comments: 13 pages, 10 figures

HiDi: An efficient reverse engineering schema for large scale dynamic regulatory network reconstruction using adaptive differentiation

Authors: Yue Deng, Hector Zenil, Jesper Tégner, Narsis A. Kiani

Abstract: 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 base… ▽ More 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. 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 data set size and levels of noise. We show that the computation time is linear over various network sizes. △ Less

Submitted 7 June, 2017; v1 submitted 5 June, 2017; originally announced June 2017.

Comments: As accepted by the journal Bioinformatics (Oxford)

On The Fundamental Energy Tradeoffs of Geographical Load Balancing

Authors: Abbas Kiani, Nirwan Ansari

Abstract: Geographical load balancing can optimize the utilization of green energy and the cost of electricity by taking the advantages of green and price diversities at geographical dispersed data centers. However, higher green energy utilization or lower electricity cost may actually increase the total energy consumption, and is not necessarily the best option. The achievable energy tradeoffs can be captu… ▽ More Geographical load balancing can optimize the utilization of green energy and the cost of electricity by taking the advantages of green and price diversities at geographical dispersed data centers. However, higher green energy utilization or lower electricity cost may actually increase the total energy consumption, and is not necessarily the best option. The achievable energy tradeoffs can be captured by taking into consideration of a defined service efficiency parameter for geo-dispersed data centers. △ Less

Submitted 2 December, 2016; originally announced December 2016.

Comments: to appear IEEE Communications Magazine

Journal ref: IEEE Communications Magazine, Volume: 55, Issue: 5, May 2017

Towards Hierarchical Mobile Edge Computing: An Auction-Based Profit Maximization Approach

Authors: Abbas Kiani, Nirwan Ansari

Abstract: The multi-tiered concept of Internet of Things (IoT) devices, cloudlets and clouds is facilitating a user-centric IoT. However, in such three tier network, it is still desirable to investigate efficient strategies to offer the computing, storage and communications resources to the users. To this end, this paper proposes a new hierarchical model by introducing the concept of field, shallow, and dee… ▽ More The multi-tiered concept of Internet of Things (IoT) devices, cloudlets and clouds is facilitating a user-centric IoT. However, in such three tier network, it is still desirable to investigate efficient strategies to offer the computing, storage and communications resources to the users. To this end, this paper proposes a new hierarchical model by introducing the concept of field, shallow, and deep cloudlets where the cloudlet tier itself is designed in three hierarchical levels based on the principle of LTE-Advanced backhaul network. Accordingly, we explore a two time scale approach in which the computing resources are offered in an auction-based profit maximization manner and then the communications resources are allocated to satisfy the users' QoS. △ Less

Submitted 30 November, 2016; originally announced December 2016.

Journal ref: IEEE Internet of Things Journal, vol. 4, no. 6, pp. 2082-2091, Dec. 2017

A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity

Authors: Hector Zenil, Santiago Hernández-Orozco, Narsis A. Kiani, Fernando Soler-Toscano, Antonio Rueda-Toicen

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 upon Solomonoff-Levin's theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities e.g. as spotted by some popular los… ▽ More 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 upon Solomonoff-Levin's theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities e.g. as spotted by some 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 and to estimate an upper bound on the length of the shortest computer program that produces said 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 a free online algorithmic complexity calculator. △ Less

Submitted 18 June, 2018; v1 submitted 1 September, 2016; originally announced September 2016.

Comments: 39 pages, 46 with appendix. 15 figures total and 4 tables

ACM Class: H.1.1

Passivation-sensitive exciton finestructure produces excess Stokes shifts in colloidal quantum dots

Authors: Oleksandr Voznyy, Fengjia Fan, Alexander Ip, Amirreza Kiani, Susanna M. Thon, Kyle W. Kemp, Larissa Levina, Edward H. Sargent

Abstract: The excitonic finestructure of colloidal quantum dots (CQDs) is comprised of a manifold of transitions, of which only the lowest are populated and contribute to photoluminescence. This leads to a Stokes shift in emission relative to absorption. Here we show experimentally that the Stokes shift in Pb and Cd-based chalcogenide CQDs is correlated with the degree of surface passivation, and develop a… ▽ More The excitonic finestructure of colloidal quantum dots (CQDs) is comprised of a manifold of transitions, of which only the lowest are populated and contribute to photoluminescence. This leads to a Stokes shift in emission relative to absorption. Here we show experimentally that the Stokes shift in Pb and Cd-based chalcogenide CQDs is correlated with the degree of surface passivation, and develop a model that explains how coupling to the surface affects the core electronic states. Dark and bright transitions can reorder and split, increasing the Stokes shift even without the formation of deep traps. Our findings resolve the highly-debated topic of excess Stokes shifts in PbS nanocrystals as due to parity-forbidden transitions instead of traps. We predict that the Stokes shift in PbS can be eliminated via core stoichiometry control, a critical step towards enhancing the open circuit voltage in quantum dot solar cells. △ Less

Submitted 17 August, 2016; originally announced August 2016.

Evaluating Network Inference Methods in Terms of Their Ability to Preserve the Topology and Complexity of Genetic Networks

Authors: Narsis A. Kiani, Hector Zenil, Jakub Olczak, Jesper Tegnér

Abstract: Network inference is a rapidly advancing field, with new methods being proposed on a regular basis. Understanding the advantages and limitations of different network inference methods is key to their effective application in different circumstances. The common structural properties shared by diverse networks naturally pose a challenge when it comes to devising accurate inference methods, but surpr… ▽ More Network inference is a rapidly advancing field, with new methods being proposed on a regular basis. Understanding the advantages and limitations of different network inference methods is key to their effective application in different circumstances. The common structural properties shared by diverse networks naturally pose a challenge when it comes to devising accurate inference methods, but surprisingly, there is a paucity of comparison and evaluation methods. Historically, every new methodology has only been tested against \textit{gold standard} (true values) purpose-designed synthetic and real-world (validated) biological networks. In this paper we aim to assess the impact of taking into consideration aspects of topological and information content in the evaluation of the final accuracy of an inference procedure. Specifically, we will compare the best inference methods, in both graph-theoretic and information-theoretic terms, for preserving topological properties and the original information content of synthetic and biological networks. New methods for performance comparison are introduced by borrowing ideas from gene set enrichment analysis and by applying concepts from algorithmic complexity. Experimental results show that no individual algorithm outperforms all others in all cases, and that the challenging and non-trivial nature of network inference is evident in the struggle of some of the algorithms to turn in a performance that is superior to random guesswork. Therefore special care should be taken to suit the method to the purpose at hand. Finally, we show that evaluations from data generated using different underlying topologies have different signatures that can be used to better choose a network reconstruction method. △ Less

Submitted 14 September, 2016; v1 submitted 3 December, 2015; originally announced December 2015.

Comments: main part: 18 pages. 21 pages with Sup Inf. Forthcoming in the journal of Seminars in Cell and Developmental Biology

Quantifying Loss of Information in Network-based Dimensionality Reduction Techniques

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

Abstract: To cope with the complexity of large networks, a number of dimensionality reduction techniques for graphs have been developed. However, the extent to which information is lost or preserved when these techniques are employed has not yet been clear. Here we develop a framework, based on algorithmic information theory, to quantify the extent to which information is preserved when network motif analys… ▽ More To cope with the complexity of large networks, a number of dimensionality reduction techniques for graphs have been developed. However, the extent to which information is lost or preserved when these techniques are employed has not yet been clear. Here we develop a framework, based on algorithmic information theory, to quantify the extent to which information is preserved when network motif analysis, graph spectra and spectral sparsification methods are applied to over twenty different biological and artificial networks. We find that the spectral sparsification is highly sensitive to high number of edge deletion, leading to significant inconsistencies, and that graph spectral methods are the most irregular, capturing algebraic information in a condensed fashion but largely losing most of the information content of the original networks. However, the approach shows that network motif analysis excels at preserving the relative algorithmic information content of a network, hence validating and generalizing the remarkable fact that despite their inherent combinatorial possibilities, local regularities preserve information to such an extent that essential properties are fully recoverable across different networks to determine their family group to which they belong to (eg genetic vs social network). Our algorithmic information methodology thus provides a rigorous framework enabling a fundamental assessment and comparison between different data dimensionality reduction methods thereby facilitating the identification and evaluation of the capabilities of old and new methods. △ Less

Submitted 27 August, 2015; v1 submitted 23 April, 2015; originally announced April 2015.

Comments: 29 pages, 6 figures

Profit Maximization for Geographical Dispersed Green Data Centers

Authors: Abbas Kiani, Nirwan Ansari

Abstract: This paper aims at maximizing the profit associated with running geographically dispersed green data centers, which offer multiple classes of service. To this end, we formulate an optimization framework which relies on the accuracy of the G/D/1 queue in characterizing the workload distribution, and taps on the merits of the workload decomposition into green and brown workload served by green and b… ▽ More This paper aims at maximizing the profit associated with running geographically dispersed green data centers, which offer multiple classes of service. To this end, we formulate an optimization framework which relies on the accuracy of the G/D/1 queue in characterizing the workload distribution, and taps on the merits of the workload decomposition into green and brown workload served by green and brown energy resources. Moreover, we take into account of not only the Service Level Agreements (SLAs) between the data centers and clients but also different deregulated electricity markets of data centers located at different regions. We prove the convexity of our optimization problem and the performance of the proposed workload distribution strategy is evaluated via simulations. △ Less

Submitted 25 November, 2015; v1 submitted 7 April, 2015; originally announced April 2015.

Journal ref: IEEE Transactions on Smart Grid, 2016

Numerical Investigation of Graph Spectra and Information Interpretability of Eigenvalues

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

Abstract: We undertake an extensive numerical investigation of the graph spectra of thousands regular graphs, a set of random Erdös-Rényi graphs, the two most popular types of complex networks and an evolving genetic network by using novel conceptual and experimental tools. Our objective in so doing is to contribute to an understanding of the meaning of the Eigenvalues of a graph relative to its topological… ▽ More We undertake an extensive numerical investigation of the graph spectra of thousands regular graphs, a set of random Erdös-Rényi graphs, the two most popular types of complex networks and an evolving genetic network by using novel conceptual and experimental tools. Our objective in so doing is to contribute to an understanding of the meaning of the Eigenvalues of a graph relative to its topological and information-theoretic properties. We introduce a technique for identifying the most informative Eigenvalues of evolving networks by comparing graph spectra behavior to their algorithmic complexity. We suggest that extending techniques can be used to further investigate the behavior of evolving biological networks. In the extended version of this paper we apply these techniques to seven tissue specific regulatory networks as static example and network of a naïve pluripotent immune cell in the process of differentiating towards a Th17 cell as evolving example, finding the most and least informative Eigenvalues at every stage. △ Less

Submitted 24 January, 2015; originally announced January 2015.

Comments: Forthcoming in 3rd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO), Lecture Notes in Bioinformatics, 2015

Methods of Information Theory and Algorithmic Complexity for Network Biology

Authors: Hector Zenil, Narsis A. Kiani, Jesper Tegnér

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 Erdos-Renyi random graphs, and the recovery of topological… ▽ More 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 Erdos-Renyi 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. △ Less

Submitted 11 December, 2015; v1 submitted 15 January, 2014; originally announced January 2014.

Comments: 28 pages. Forthcoming in the journal Seminars in Cell and Developmental Biology

Perturbation Analysis of the Wholesale Energy Market Equilibrium in the Presence of Renewables

Authors: Arman Kiani, Anuradha Annaswamy

Abstract: One of the main challenges in the emerging smart grid is the integration of renewable energy resources (RER). The latter introduces both intermittency and uncertainty into the grid, both of which can affect the underlying energy market. An interesting concept that is being explored for mitigating the integration cost of RERs is Demand Response. Implemented as a time-varying electricity price in re… ▽ More One of the main challenges in the emerging smart grid is the integration of renewable energy resources (RER). The latter introduces both intermittency and uncertainty into the grid, both of which can affect the underlying energy market. An interesting concept that is being explored for mitigating the integration cost of RERs is Demand Response. Implemented as a time-varying electricity price in real-time, Demand Response has a direct impact on the underlying energy market as well. Beginning with an overall model of the major market participants together with the constraints of transmission and generation, we analyze the energy market in this paper and derive conditions for global maximum using standard KKT criteria. The effect of uncertainties in the RER on the market equilibrium is then quantified, with and without real-time pricing. Perturbation analysis methods are used to compare the equilibria in the nominal and perturbed markets. These markets are also analyzed using a game-theoretic point of view. Sufficient conditions are derived for the existence of a unique Pure Nash Equilibrium in the nominal market. The perturbed market is analyzed using the concept of closeness of two strategic games and the equilibria of close games. This analysis is used to quantify the effect of uncertainty of RERs and its possible mitigation using Demand Response. Finally numerical studies are reported using an IEEE 30-bus to validate the theoretical results. △ Less

Submitted 17 January, 2012; originally announced January 2012.

A Non-MDS Erasure Code Scheme For Storage Applications

Authors: Abbas Kiani, Soroush Akhlaghi

Abstract: This paper investigates the use of redundancy and self repairing against node failures in distributed storage systems, using various strategies. In replication method, access to one replication node is sufficient to reconstruct a lost node, while in MDS erasure coded systems which are optimal in terms of redundancy-reliability tradeoff, a single node failure is repaired after recovering the entire… ▽ More This paper investigates the use of redundancy and self repairing against node failures in distributed storage systems, using various strategies. In replication method, access to one replication node is sufficient to reconstruct a lost node, while in MDS erasure coded systems which are optimal in terms of redundancy-reliability tradeoff, a single node failure is repaired after recovering the entire stored data. Moreover, regenerating codes yield a tradeoff curve between storage capacity and repair bandwidth. The current paper aims at investigating a new storage code. Specifically, we propose a non-MDS (2k, k) code that tolerates any three node failures and more importantly, it is shown using our code a single node failure can be repaired through access to only three nodes. △ Less

Submitted 21 September, 2011; originally announced September 2011.

Comments: 6 pages, 2 figures

Cost-Bandwidth Tradeoff In Distributed Storage Systems

Authors: Soroush Akhlaghi, Abbas Kiani, Mohammad Reza Ghanavati

Abstract: Distributed storage systems are mainly justified due to the limited amount of storage capacity and improving the reliability through distributing data over multiple storage nodes. On the other hand, it may happen the data is stored in unreliable nodes, while it is desired the end user to have a reliable access to the stored data. So, in an event that a node is damaged, to prevent the system reliab… ▽ More Distributed storage systems are mainly justified due to the limited amount of storage capacity and improving the reliability through distributing data over multiple storage nodes. On the other hand, it may happen the data is stored in unreliable nodes, while it is desired the end user to have a reliable access to the stored data. So, in an event that a node is damaged, to prevent the system reliability to regress, it is necessary to regenerate a new node with the same amount of stored data as the damaged node to retain the number of storage nodes, thereby having the previous reliability. This requires the new node to connect to some of existing nodes and downloads the required information, thereby occupying some bandwidth, called the repair bandwidth. On the other hand, it is more likely the cost of downloading varies across different nodes. This paper aims at investigating the theoretical cost-bandwidth tradeoff, and more importantly, it is demonstrated that any point on this curve can be achieved through the use of the so called generalized regenerating codes which is an enhancement of the regeneration codes introduced by Dimakis et al. in [1]. △ Less

Submitted 14 April, 2010; v1 submitted 6 April, 2010; originally announced April 2010.

Comments: 8 pages,8 figures