Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLUNAR: Cellular Automata for Drifting Data Streams
288
0
0.0
(
0
)
Added by
Jesus L. Lobo
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
With the advent of huges volumes of data produced in the form of fast streams, real-time machine learning has become a challenge of relevance emerging in a plethora of real-world applications. Processing such fast streams often demands high memory and processing resources. In addition, they can be affected by non-stationary phenomena (concept drift), by which learning methods have to detect changes in the distribution of streaming data, and adapt to these evolving conditions. A lack of efficient and scalable solutions is particularly noted in real-time scenarios where computing resources are severely constrained, as it occurs in networks of small, numerous, interconnected processing units (such as the so-called Smart Dust, Utility Fog, or Swarm Robotics paradigms). In this work we propose LUNAR, a streamified version of cellular automata devised to successfully meet the aforementioned requirements. It is able to act as a real incremental learner while adapting to drifting conditions. Extensive simulations with synthetic and real data will provide evidence of its competitive behavior in terms of classification performance when compared to long-established and successful online learning methods.
rate research
Read More
The complexity of cellular automata is traditionally measured by their computational capacity. However, it is difficult to choose a challenging set of computational tasks suitable for the parallel nature of such systems. We study the ability of automata to emulate one another, and we use this notion to define such a set of naturally emerging tasks. We present the results for elementary cellular automata, although the core ideas can be extended to other computational systems. We compute a graph showing which elementary cellular automata can be emulated by which and show that certain chaotic automata are the only ones that cannot emulate any automata non-trivially. Finally, we use the emulation notion to suggest a novel definition of chaos that we believe is suitable for discrete computational systems. We believe our work can help design parallel computational systems that are Turing-complete and also computationally efficient.
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-Kr{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension 1, but also dimension 1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.
A generalized set of Clifford cellular automata, which includes all Clifford cellular automata, result from the quantization of a lattice system where on each site of the lattice one has a $2k$-dimensional torus phase space. The dynamics is a linear map in the torus variables and it is also local: the evolution depends only on variables in some region around the original lattice site. Moreover it preserves the symplectic structure. These are classified by $2ktimes 2k$ matrices with entries in Laurent polynomials with integer coefficients in a set of additional formal variables. These can lead to fractal behavior in the evolution of the generators of the quantum algebra. Fractal behavior leads to non-trivial Lyapunov exponents of the original linear dynamical system. The proof uses Fourier analysis on the characteristic polynomial of these matrices.
Coronavirus disease (COVID-19) which is caused by SARS-COV2 has become a pandemic. This disease is highly infectious and potentially fatal, causing a global public health concern. To contain the spread of COVID-19, governments are adopting nationwide interventions, like lockdown, containment and quarantine, restrictions on travel, cancelling social events and extensive testing. To understand the effects of these measures on the control of the epidemic in a data-driven manner, we propose a probabilistic cellular automata (PCA) based modified SEIQR model. The transitions associated with the model is driven by data available on chronology, symptoms, pathogenesis and transmissivity of the virus. By arguing that the lattice-based model captures the features of the dynamics along with the existing fluctuations, we perform rigorous computational analyses of the model to take into account of the spatial dynamics of social distancing measures imposed on the people. Considering the probabilistic behavioural aspects associated with mitigation strategies, we study the model considering factors like population density and testing efficiency. Using the model, we focus on the variability of epidemic dynamics data for different countries and point out the reasons behind these contrasting observations. To the best of our knowledge, this is the first attempt to model COVID-19 spread using PCA that gives us both spatial and temporal variations of the infection spread with the insight about the contributions of different infection parameters.
We numerically study the dynamics of elementary 1D cellular automata (CA), where the binary state $sigma_i(t) in {0,1}$ of a cell $i$ does not only depend on the states in its local neighborhood at time $t-1$, but also on the memory of its own past states $sigma_i(t-2), sigma_i(t-3),...,sigma_i(t-tau),...$. We assume that the weight of this memory decays proportionally to $tau^{-alpha}$, with $alpha ge 0$ (the limit $alpha to infty$ corresponds to the usual CA). Since the memory function is summable for $alpha>1$ and nonsummable for $0le alpha le 1$, we expect pronounced %qualitative and quantitative changes of the dynamical behavior near $alpha=1$. This is precisely what our simulations exhibit, particularly for the time evolution of the Hamming distance $H$ of initially close trajectories. We typically expect the asymptotic behavior $H(t) propto t^{1/(1-q)}$, where $q$ is the entropic index associated with nonextensive statistical mechanics. In all cases, the function $q(alpha)$ exhibits a sensible change at $alpha simeq 1$. We focus on the class II rules 61, 99 and 111. For rule 61, $q = 0$ for $0 le alpha le alpha_c simeq 1.3$, and $q<0$ for $alpha> alpha_c$, whereas the opposite behavior is found for rule 111. For rule 99, the effect of the long-range memory on the spread of damage is quite dramatic. These facts point at a rich dynamics intimately linked to the interplay of local lookup rules and the range of the memory. Finite size scaling studies varying system size $N$ indicate that the range of the power-law regime for $H(t)$ typically diverges $propto N^z$ with $0 le z le 1$. Similar studies have been carried out for other rules, e.g., the famous universal computer rule 110.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
