Systematic Design for Emergence in Cellular Nonlinear Networks: With Applications in Natural Computing and Signal Processing- (Studies in Computational Intelligence)

Radu Dogaru Systematic Design for Emergence in Cellular Nonlinear Networks

Studies in Computational Intelligence, Volume 95 Editor-in-chief Prof. Janusz Kacprzyk Systems Research Institute Polish Academy of Sciences ul. Newelska 6 01-447 Warsaw Poland E-mail: [email protected] Further volumes of this series can be found on our homepage: springer.com Vol. 70. Javaan Singh Chahl, Lakhmi C. Jain, Akiko Mizutani and Mika Sato-Ilic (Eds.) Innovations in Intelligent Machines-1, 2007 ISBN 978-3-540-72695-1 Vol. 71. Norio Baba, Lakhmi C. Jain and Hisashi Handa (Eds.) Advanced Intelligent Paradigms in Computer Games, 2007 ISBN 978-3-540-72704-0 Vol. 72. Raymond S.T. Lee and Vincenzo Loia (Eds.) Computation Intelligence for Agent-based Systems, 2007 ISBN 978-3-540-73175-7 Vol. 73. Petra Perner (Ed.) Case-Based Reasoning on Images and Signals, 2008 ISBN 978-3-540-73178-8 Vol. 74. Robert Schaefer Foundation of Global Genetic Optimization, 2007 ISBN 978-3-540-73191-7 Vol. 75. Crina Grosan, Ajith Abraham and Hisao Ishibuchi (Eds.) Hybrid Evolutionary Algorithms, 2007 ISBN 978-3-540-73296-9 Vol. 76. Subhas Chandra Mukhopadhyay and Gourab Sen Gupta (Eds.) Autonomous Robots and Agents, 2007 ISBN 978-3-540-73423-9 Vol. 77. Barbara Hammer and Pascal Hitzler (Eds.) Perspectives of Neural-Symbolic Integration, 2007 ISBN 978-3-540-73953-1 Vol. 78. Costin Badica and Marcin Paprzycki (Eds.) Intelligent and Distributed Computing, 2008 ISBN 978-3-540-74929-5 Vol. 79. Xing Cai and T.-C. Jim Yeh (Eds.) Quantitative Information Fusion for Hydrological Sciences, 2008 ISBN 978-3-540-75383-4

Vol. 83. Bhanu Prasad and S.R.M. Prasanna (Eds.) Speech, Audio, Image and Biomedical Signal Processing using Neural Networks, 2008 ISBN 978-3-540-75397-1 Vol. 84. Marek R. Ogiela and Ryszard Tadeusiewicz Modern Computational Intelligence Methods for the Interpretation of Medical Images, 2008 ISBN 978-3-540-75399-5 Vol. 85. Arpad Kelemen, Ajith Abraham and Yulan Liang (Eds.) Computational Intelligence in Medical Informatics, 2008 ISBN 978-3-540-75766-5 Vol. 86. Zbigniew Les and Mogdalena Les Shape Understanding Systems, 2008 ISBN 978-3-540-75768-9 Vol. 87. Yuri Avramenko and Andrzej Kraslawski Case Based Design, 2008 ISBN 978-3-540-75705-4 Vol. 88. Tina Yu, David Davis, Cem Baydar and Rajkumar Roy (Eds.) Evolutionary Computation in Practice, 2008 ISBN 978-3-540-75770-2 Vol. 89. Ito Takayuki, Hattori Hiromitsu, Zhang Minjie and Matsuo Tokuro (Eds.) Rational, Robust, Secure, 2008 ISBN 978-3-540-76281-2 Vol. 90. Simone Marinai and Hiromichi Fujisawa (Eds.) Machine Learning in Document Analysis and Recognition, 2008 ISBN 978-3-540-76279-9 Vol. 91. Horst Bunke, Kandel Abraham and Last Mark (Eds.) Applied Pattern Recognition, 2008 ISBN 978-3-540-76830-2 Vol. 92. Ang Yang, Yin Shan and Lam Thu Bui (Eds.) Success in Evolutionary Computation, 2008 ISBN 978-3-540-76285-0

Vol. 80. Joachim Diederich Rule Extraction from Support Vector Machines, 2008 ISBN 978-3-540-75389-6

Vol. 93. Manolis Wallace, Marios Angelides and Phivos Mylonas (Eds.) Advances in Semantic Media Adaptation and Personalization, 2008 ISBN 978-3-540-76359-8

Vol. 81. K. Sridharan Robotic Exploration and Landmark Determination, 2008 ISBN 978-3-540-75393-3

Vol. 94. Arpad Kelemen, Ajith Abraham and Yuehui Chen (Eds.) Computational Intelligence in Bioinformatics, 2008 ISBN 978-3-540-76802-9

Vol. 82. Ajith Abraham, Crina Grosan and Witold Pedrycz (Eds.) Engineering Evolutionary Intelligent Systems, 2008 ISBN 978-3-540-75395-7

Vol. 95. Radu Dogaru Systematic Design for Emergence in Cellular Nonlinear Networks, 2008 ISBN 978-3-540-76800-5

Radu Dogaru

Systematic Design for Emergence in Cellular Nonlinear Networks With Applications in Natural Computing and Signal Processing

With 80 Figures and 10 Tables

Dr. Radu Dogaru Polytechnic University of Bucharest Department of Applied Electronics and Information Engineering "Leu" building (B), Bvd. Iuliu Maniu 1-3, Room B232 061071 Bucharest, Romania [email protected]

ISBN 978-3-540-76800-5

e-ISBN 978-3-540-76801-2

Studies in Computational Intelligence ISSN 1860-949X Library of Congress Control Number: 2007939778 c 2008 Springer-Verlag Berlin Heidelberg
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: Deblik, Berlin, Germany Printed on acid-free paper 9 8 7 6 5 4 3 2 1 springer.com

Preface

The main problem addressed in this book came out during a Fulbright research fellowship stage at U.C. Berkeley (California, USA, 1996–1998). Then, I had the opportunity to work in the research group of Leon Chua on a subject called CNN (cellular neural/nonlinear network). The CNN, developed in the end of the 1980s was an important step ahead in getting cellular computing closer to practical applications. The CNN is actually a cellular array made of many identical elements interconnected in a neighborhood. But unlike the cellular automata (CA) the CNN was designed as a circuit-oriented architecture being developed up to the point where it serves as a low-power smart sensor or visual microprocessor capable to acquire and process images or multi-dimensional signals in general with processing speeds of the order of 1012 (Tera) operations per second. Today, there are several academic and industrial groups providing CNN-based solutions for various practical problems, particularly when high speed processing at low power is needed. Also, researchers in the area of nano-technology recognize cellular computing as a suitable computing paradigm to the specific of these technologies where many identical active elements are available on a mass proportion. Researchers in biology also recognize the cellular paradigm as a well-suited paradigm for models of natural systems. Indeed there is a similarity, as biological systems essentially are functionally meaningful aggregates of mostly local interconnected cells. A brief review of the cellular computing paradigm, its relation to natural computing in general and the state of the art of its use in applications are given in Chaps. 1 and 2 of this book. At the moment of my arrival at Berkeley a well-established theory of the standard CNN architecture was already developed, and many researchers worked on finding novel applications. Still several problems were recognized as needed to be solved. A first one was to define universal cells, i.e. to find a general nonlinear system describing any arbitrary local interaction (e.g. a Boolean function) within a family of similar functions. A set of parameters of the nonlinear system, called a gene, is supposed to prescribe any particular “individual” from the family of functions. The parallelism with biology is obvious: Here, the DNA string represents the gene while the unfolding mechanism producing and multiplying biological cells may be associated to the cellular nonlinear system and its dynamics. A theory of piecewise-linear representation of cells was then developed and briefly recalled in this book in Chap. 3 since later it turned out to be relevant in a consistent framework for predicting emergence, or as we will call it often throughout this book, for the “design for emergence” of cellular systems. Indeed, a second problem posed in the mid 1990s for the CNN researchers was to develop a consistent theory of emergence, or in other words to find a way to

vi

Preface

anticipate how the cellular array (CA) will behave without extensively running the entire CA system. It is a crucial design problem since the space of possibilities in choosing the cells’ gene is huge and looking exhaustively to cellular systems behaviors associated with each and all of them is impossible. Researchers in biology face a similar problem in the attempt to “decode” the genome i.e. to understand how different biological behaviors (disorders, diseases, etc.) emerge from a known genome. A great step towards a theory of emergence is Leon Chua’s theory of local activity (published in 1997) as it is able to predict, to a certain degree, the nature of the emergent phenomena within the cellular array, while investigating only the simple nonlinear system associated to the isolated cell. A series of papers were published on this topic providing clues and practical methods for locating the “edge of chaos” as a narrow region within the cells’ parameter (or gene) space. Such widely known nonlinear systems as Fitz-Hugh Nagumo model of excitable nervous membranes, the Brusselator and the Gierer-Meinhard’s model for morphogenesis were considered, and it was verified that indeed local activity is powerful enough to locate previously reported emergent behaviors but also to discover new ones. Still, the theory of local activity has some limitations in that it relies on some circuit theory theorems and therefore assumes that the model to be investigated shall be cast into a circuit specific framework. Therefore, the theory can be applied and was done so far solely for Reaction–Diffusion systems. However, there are many other cellular or network-based computing paradigms, as briefly recalled in Chap. 3, that may benefit from a general theory of emergent computation. Here comes the novelty of this book, which reports recent results aiming to establish a global theory and practice for a “design for emergence” framework. The first step in designing for emergence was to recognize that one needs to measure emergence. This is the aim of Chap. 4, where several scalar measures were introduced and defined as algorithms operating during the running of a cellular system. Some hints on how to associate various values of these measures to various categories of emergent behaviors were also given. Chapter 5 comes with an additional measure which later proved to be very interesting in that an equivalent form of it could be determined without running the CA but solely based on the cells’ structure. With accurately defined measures of emergence the next step towards a “design for emergence” framework was to recognize and define tools to select among the entire space of possibilities only those genes related to desired emergent behaviors, described often in a fuzzy natural language. Their definition and some practical aspects of their use are the subjects of Chap. 6. The most interesting result comes in Chap. 7 where the grounds for a general theory of emergence are provided, using tools from the information theory. Here, we provide analytic formulae to determine a measure of emergence solely based on cell’s structure (its gene) and its neighborhood. Comparisons with the experimentally determined (during the CA running) similar measure confirmed the validity of this new theory called a theory of the probabilistic exponents of growth, for reasons to be detailed within the chapter.

Preface vii

As its name anticipates, probabilities and other notions from information theory play a crucial role in its development. Unlike the theory of local activity, this new theory is rather general and it does not depend too much on the specific cellular system. Although we exemplify it for discrete-time binary-state cellular automata, hints are provided on how to expand it to any type of system. Also, the neighborhood and its parameters are included in the theory, improving its predictive value, when compared with theories such as local activity where emergence is predicted with some degree of uncertainty left on the behalf of the interconnectivity. It can also explain many situations that were previously observed empirically in cellular systems. While doing several research stages at Institute of Microelectronic Systems at T.U. Darmstadt, Germany in a research group oriented towards solving many practical problems, it turned out that there is a huge demand from the industry to build low power intelligent systems. It later turned out that natural computing approaches like the use of cellular automata systems for various signal processing tasks may dramatically reduce the implementation complexity when compared to traditional solutions. What was needed, were the CA design tools. Once they have been introduced in the previously mentioned chapters, the last chapter of this book presents three different innovative applications of cellular automata in signal processing. As cellular systems are part of the natural computing systems and the focus of many interdisciplinary research groups, and since myself was formed as an electrical and computer science engineer I wrote the book in an easily to understand style, without too much mathematical formalism. Some programs are also provided within the text to facilitate a faster access of the interested reader to the design for emergence tools. Although mathematicians may not like the lack of formal proofs I encourage readers from this area to browse the book, and I hope that they may extract some useful ideas for a more formal treatment. Much of the work reported here was done with the support of an Alexander von Humboldt research fellowship, during a stage at T.U. Darmstadt between 2005 and 2006. Some of the chapters in the book were taught as lectures in a course on Natural Computing systems I gave at Darmstadt during this stage. I am deeply indebted to Professor Manfred Glesner, the director of the research group and to many members of his team for their continuous support and hospitality during this stage, as well as for the opening they gave me to seek not only theoretical sides of cellular systems but also to look for convincing practical applications of them. I acknowledge the steady support of Professor Leon Chua who sparkled and stimulated my interest for the fascinating research area of cellular computing systems and shaped deeply my way of thinking. Other sponsors such as the Volkswagen Stiftung are also acknowledged here, particularly for their role in shaping my interest for solving some practical signal processing problems. I am also indebted to colleagues and my former professors from the Applied Electronics and Information Engineering as well as to many friends and colleagues, anonymous reviewers and other persons familiar to my work who gave me some critic feedback in various stages.

viii Preface

Last but not the least I thank all the members of my family for their patience and continuous support. Special thanks goes to my wife Ioana who, in addition to her understanding and patience, gave me a lot of feedback and made a lot of useful comments on the manuscript.

Radu Dogaru Bucharest, September 2007

Contents

Preface …………………………………………………………………………

v

1 Natural computing paradigms and emergent computation …………………. 1.1 Principles of natural computing ................……………………………… 1.1.1 Natural computing structures as hierarchies of interconnected cells .. 1.1.2 The principle of optimal number of entities (Ockham’s razor) …… 1.1.3 Natural computing systems are dissipative systems ………………. 1.1.4 Transient nature of the behavioral complexity of natural systems .. 1.1.5 Natural systems and recurrence ..…………………………………. 1.1.6 Emergence, complexity, and local activity of cells ……………….. 1.2 Open problems and book description ...………………………………….

1 1 1 2 3 3 3 3 4

2 Cellular nonlinear networks: state of the art and applications ………………. 7 2.1 Introduction ………….…………………………………………………. 7 2.2 Typical applications of cellular computers ……………………………... 9 2.3 Hardware platforms for implementing cellular computers …………….. 12 3 Cellular and natural computing models and software simulation ...………... 3.1 Cellular systems: cells, neighborhoods, states and dynamics .………….. 3.1.1 Genes ……………………………………………………………... 3.1.2 Discrete and continuous states and outputs ………………………. 3.1.3 Boundary conditions ……………………………………………… 3.2 Major cellular systems paradigms ……………………………………… 3.2.1 The Cellular Neural Network (CNN) model …………………… ... 3.2.2 The Generalized Cellular Automata ……………………………… 3.2.3 Reaction-Diffusion Cellular Nonlinear Networks ………………... 3.3 Matlab simulation of Generalized cellular automata and cellular neural networks …................................................................. 3.3.1 Uncoupled GCAs ………………………………………………….. 3.3.2 Coupled GCAs …….………………………………………………. 3.3.3 Simulation of standard cellular neural networks ………………….. 3.4 Nonlinear representation of cells ……………………………………… .. 3.4.1 Piecewise-linear representation and implementation …………… ... 3.4.2 Extended families of cells ……………………………….……… ... 3.4.3 Structured universes of cells …………………………….….…… .. 3.5 Modeling and simulation of semitotalistic cellular automata ………….... 3.6 Modeling and simulation of “Small-Worlds” systems ………………….. 3.7 A wider variety of cells, taxonomy and family labels ………………….. 3.8 A CA simulator for all kind of cells ……………………………………..

15 15 17 17 17 18 18 19 20 21 21 23 25 25 26 36 37 38 40 41 43

x

Contents

4 Emergence, locating and measuring it .……………………………………... 4.1 Emergence: the software engineering of cellular computing systems ….. 4.2 Visual interpretation of emergent phenomena – classes of behaviors ….. 4.3 Semitotalistic cells: a first step in narrowing the search space …..……. . 4.4 Clustering and transients and as measures of emergence ………………. 4.4.1 Visualizing complexity for an entire family of cellular systems – Wolfram classes revisited …….…................….

47 47 48 57 60 66

4.5 Simulation examples, properties, more accurate complexity measures ... 69 4.5.1 Properties of complexity measures ……………………………… .. 71 4.5.2 A composite complexity measure ………………………………… 74 5 Exponents of growth ………………………………………………….……. 5.1 Exponents of growth and their relationship to various emergent behaviors …….......................................................................................... 5.2 Mutations for continuous state cellular systems ……………………….. 5.3 Distribution of exponents of growth among families of genes …………. 5.4 Influences of the “Small World” model ………………………………… 5.4.1 The “small worlds” model allows fine tuning of the “edge of chaos” …............................................................................ 5.5 On the independence between various measures of complexities ………

77 77 85 87 89 90 92

6 Sieves for selection of genes according to desired behaviors ………………. 6.1 Introduction …………………………………………………………….. 6.2 Defining sieves ……………………………………………..................... 6.3 Examples and applications of the double sieve method …………........... 6.3.1 Intelligent life behaviors and uncertainty in using sieves ...………. 6.3.2 Classic “Life”: using sieves to locate similar behaviors …….......... 6.3.3 Other interesting emergent behaviors .……………………………. 6.3.4 Sieves to locate feature extractors ………………………………... 6.3.5 Pink-noise generators …………………………………………….. 6.3.6 Sieving and intelligence – evolving a list of interesting genes .…..

95 95 96 99 99 101 104 107 109 110

7 Predicting emergence from cell’s structure .………………………………… 7.1 Introduction .…………………………………………………………….. 7.2 Relationships between CA behavior and the Boolean description of the cell ….......................................................................…. 7.3 Parametrizations as tools to locate similar behaviors ………………….. 7.4 The theory of probabilistic exponents of growth ……………………….. 7.4.1 Uncertainty index of a cell, active and expansion areas ………….. 7.4.2 Minimal set of cells to compute the probabilistic exponent of growth ……………………………………………….. 7.4.3 Computing the cells function of probability ……………………… 7.4.4 Computing the probabilistic exponent of growth ………………… 7.5 Exponents of growth and their significance ……………………………. 7.5.1 Predicting behaviors from ID, an example ……………………… .. 7.5.2 Other properties of the probabilistic exponents of growth ……… .. 7.5.3 Comparison with the experimental exponent of growth ………….. 7.6 Conclusions …………………………………………………………… ..

11 3 113 114 116 118 120 121 123 124 126 127 127 129 130

Contents

xi

8 Applications of emergent phenomena …..………………………………… . . 8.1 Introduction ......…………………………………………………………. 8.2 Smart sensor for character recognition …..……………………………… 8.2.1 Motivation and general description …..…………………………… 8.2.2 Architecture and functionality of the CA-based sensor ………… .. 8.2.3 Feature extraction and classification ................................................ 8.2.4 Experimental results ………………………………………………. 8.3 Excitable membranes, for temporal sequence classification …………… 8.3.1 Mapping variable-length signals into terminal states ...………… .. 8.3.2 Detecting genes to build EMTMs ….…………………………… .. 8.3.3 Experimental results in sound classification ……………………… 8.4 Image compression using CA-based vector quantization .....…………… 8.4.1 Coding and decoding principle …………………………………… 8.4.2 Detecting the useful genes ....…………………………………… .. 8.4.3 Results and comparison with other compression standards ......…... 8.4.4 Aspects on hardware implementation .....…………………………

133 133 134 134 136 138 140 141 142 144 145 147 147 151 153 156

References ......……………………. ......………………………………… …. … 159 Index …………………………………………………………………………... 165

1 Natural Computing Paradigms and Emergent Computation

Natural computing was recently defined as a novel paradigm for computation where nature is taken as an example to define computational architectures and algorithms capable to solve problems efficiently and while being based on a low complexity description of its structure. A living being can be considered as performing various natural computation tasks. While exhibiting complexity in performing various functional tasks (pattern recognition, decision, orientation, optimization, planning, creative thinking, self-repair and self-reproduction, to name just a few) it is assumed that the entire development of the being is encoded within its genome. Due to recent progress in mapping the entire human genome, it is widely accepted that such a genome contains no more than several megabytes of information stored in the strings of DNA, being even simpler for more primitive species. Thus, in a simplified approach, the entire behavioral complexity of a living being can be regarded as being encoded in a relatively compact information storage structure, the DNA. This is what we will call structural information, i.e. the minimal information required to construct a computational architecture.

1.1 Principles of Natural Computing The goal of computational intelligence is to understand and exploit some basic principles of the natural computing to construct various artificial systems capable to mimic some of the functions of living beings. Figure 1.1 gives a sketch of the main ingredients and principles to be considered in analyzing and understanding a naturally inspired computing systems. Some of these principles are detailed next. 1.1.1 Natural Computing Structures as Hierarchies of Interconnected Cells As seen in the above figure, in order to achieve functionality, the gene information is unfolded in creating many similar cells in a basic hierarchy and these cells are naturally distributed so that each cell typically communicates with its immediate neighbors. The local connectivity is the essence of the cellular computing model, to be developed further. In nature, besides nearest neighbors, also long-range connections are present allowing a small fraction of distant cells to communicate. R. Dogaru: Natural Computing Paradigms and Emergent Computation, Studies in Computational Intelligence (SCI) 95, 1–6 (2008) www.springerlink.com © Springer-Verlag Berlin Heidelberg 2008

2

1 Natural Computing Paradigms and Emergent Computation

This otherwise natural fact determined Watts recently to propose and investigate the “Small Worlds” model [1]. He established that a small fraction of long-range connection is capable to dramatically change the nature of the emergent functionality. This small fraction of distant connections determines a dramatic reduction of the average path between two basic cells. Such a phenomena was previously recognized in social network, often being associated with the exclamation “What a small world!” when remote people find common acquaintances. It turns out that on average, six social links can be established between any two people in the world. The short communicating path is the result of adding only several long-range connections to the model.

Fig. 1.1. A schematic view of a natural computing system

1.1.2 The Principle of Optimal Number of Entities (Ockham’s Razor) While cell genes are interpreted to create the architecture of a natural computing system, an optimal number of basic cells forming a functional entity (called a cell from the higher level of the hierarchy, in Fig. 1.1) is established and here we may recall another principle of organization dating back from 1300s in the time of Ockham [2,3]. He stated that “…entities must not multiply without necessity” and indeed this is the case in most natural systems. When entities multiply without necessity natural systems often come to destruction like in the case of tumor growing

1.1 Principles of Natural Computing

3

or fire expansion. To limit the phenomena of multiplying without necessity, new cells will form other functional entities (i.e. a cell on a higher level of the hierarchy) and so the process unfolds until a certain number of levels of hierarchies is reached (also obeying Ockham’s principle) like in the case of a mature living being. 1.1.3 Natural Computing Systems are Dissipative Systems According to Prigogine [4] a natural system is a dissipative system, which has achieved its functionality as a “far from equilibrium” state, i.e. a state of apparent order and stability but which is in fact a complicated dynamic process. Therefore such a system requires a source of energy and since it is a dynamic process rather than a static one, it should evolve. 1.1.4 Transient Nature of the Behavioral Complexity of Natural Systems A natural computing system is not likely to have an “eternal life”. Instead it evolves through maturity to aging until it eventually “dies”, i.e. enters another (stable) dynamical regime. In a recent paper [5] it was suggested that complex and far from equilibrium dynamics (i.e. functional life) has to be always associated with a long transient process. The longer the transient, the more complex is the systems functionality. This principle inspired the introduction of the transient length measure of emergence in Chap. 4. 1.1.5 Natural Systems and Recurrence A system is recurrent if there is at least one closed loop (i.e. feedback loop) in the cell interconnection graph, i.e. a cell has always a feedback about its “actions” via its neighboring cells. 1.1.6 Emergence, Complexity, and Local Activity of Cells Quite recently, in addition to the principle of nonlinearity [4] regarded by Prigogine as a precondition for a far-from-equilibrium dynamics, the principle of local activity was introduced by Chua [7,8] to narrow the search for an ideal structure of a cell. Previously it was assumed that emergence and complexity are solely the effects of cell’s nonlinearity. Chua’s local activity theory demonstrates that in addition a cell must be locally active, i.e. capable to amplify small fluctuations received from its neighbors. In a series of papers [9–11] we demonstrated how this principle may be applied to various models of natural computation to identify proper cells (i.e. cells for which emergence is likely to occur) without being necessary to simulate the cellular system but only performing an analytical investigation of

4

1 Natural Computing Paradigms and Emergent Computation

the nonlinear ordinary differential equation describing the cell. Subdomains of the cell parameters were found (called “edge of chaos” domains) where emergent behavior and complexity is likely to occur. The principle of local activity is a first step towards the establishment of a new science of designing for emergence.

1.2 Open Problems and Book Description Looking around in nature it is clear that above principles apply for various systems ranging from living beings, economic and social networks, international relationships, computer networks, etc. Moreover, at a critical observation all functional architectures designed so far by information engineers are natural computing architectures. Indeed, any computer is built upon an hierarchy of functional modules where at the basic level one finds the basic cell to be the locally active and nonlinear transistor (or any other device exhibiting local activity). Various functions were discovered through a process of mental evolution, which gives the proper interconnection between such basic cells. A further level of hierarchy was the creation of logic gates, then the creation of memory cells, arithmetic units etc, up to the level where some flexibility was added to this construction through what is today called software, i.e. a flexible description of how different cells should be connected to perform a certain task. Algorithms then are also designed as interconnections of basic “software” cells called instructions in the computer science parlance. However, designing such systems is based on description rather than emergence. Description can be regarded as a process of transferring human knowledge into a model of existing cells. In other words we have the cells (i.e. the transistors or the logic gates or more sophisticated modules, etc.) and we describe how to interconnect them such that the resulting system will manifest a desired functionality. The typical design process starts with a specification of the end function and proceeds with a given set of rules or procedures (e.g. methods for drawing schematics or programming in software) to interconnect the basic cells available in a given technology to produce the expected result. Although description is itself an emergent process whenever novel functionality has to be described, it turns out that several challenging problems in information technology are not enough satisfactory solved using the “classic design” method. A list of problems includes but is not limited to such functions as: x x x x x x x

Self-repair and self-reproduction of complex functional architectures Voice recognition (speaker identification and message identification) Gesture recognition Visual field abstraction (i.e. generating a brief description from a visual scene) NP-complete problems optimization and decision making Orientation in a complex environment Creative thinking and problem solving.

1.2 Open Problems and Book Description

5

Actual solutions to these problems are often long and complicated descriptions resulting in messy hardware architectures or software modules and requiring many resources. On the other hand, the actual social demand is to develop a wide range of intelligent but portable products (see recent tendencies described as ubiquitous computing [12], ambient intelligence [13], organic computing [14], etc.), integrated with various sensors that are available at decreasing cost prices. Since the most important critical issue for these systems is power consumption, messy algorithms and architectures are certainly not a solution. Besides, such devices are supposed to behave naturally, i.e. perform such functional tasks which are similar in nature to functions listed above as major challenges. A better solution for designing such systems is to take the approach to be developed in this book, i.e. the design for emergence approach (first expressed in [15]). Novel technologies such as nanotechnology or molecular electronics are also better physical supports for the ideas to be developed further within this book. In the next we will describe what is the definition of emergence and how design for emergence can be achieved. Then the simplest model of a natural computing system to perform emergent computation is introduced in the form of cellular nonlinear network (CNN). While being a generalization of the widely known cellular automata (CA) model, we will see that a simple altering of this model is possible, making it compatible with the more realistic “small world” model [1]. Regarded as a potential model of universe by Zuse [16], the cellular computing model was recently proposed by Wolfram [17] as the main ingredient of a “new kind of science”. The praxis of this science may also benefit from the “design for emergence” methods [15] to be further introduced. The philosophy of designing for emergence can simply be stated as follows: Instead of giving a description for a function to be performed, one rather defines and determines the preconditions for emergence, i.e. a set of conditions to select among many possible genes associated with basic cells. Then, one simply picks genes within this reduced pool and observes (visually or automatically) details of the emergent behaviors and further selects only those genes that are best fit to the application in mind. This book passes throughout all steps of a design for emergence process and provides in the end (Chap. 8) several application examples where these principles were successfully applied. In order to understand the relevance and the potential of cellular computing models (also called cellular nonlinear networks or CNNs, cellular arrays, etc.) the next chapter will provide and overview of the field and its state of the art. Then, Chap. 3 introduces several of the most widely used cellular models. Matlab simulators are provided for each of them. Moreover, in order to cover in a unified framework a large spectrum of cellular computing arrays (CA), a convenient taxonomy of cells is introduced in the same chapter. This taxonomy relies on a piecewise-linear representation of cells as nonlinear functions rather than tables. It also allows to define families of cells as a narrowed search pool for detecting emergence. So far emergence was subjectively defined, but in order to design for emergence one needs to quantify it. A first set of measures for

6

1 Natural Computing Paradigms and Emergent Computation

emergence will be introduced in Chap. 4. Their common feature is that they are experimental, i.e. they require a simulation of the CA with some conveniently chosen initial state and number of cells during a convenient number of iterations. Although the choices of these “convenient” CA parameters induces a degree of uncertainty in these measures, they are extremely useful for a better understanding of emergence and its relationship with the cell structure. They also provide useful hints on how to tune these measures in order to select only CA genes giving a desired behavior. In fact this process of tuning and selection is further detailed in Chap. 6 where it is referred as a sieving process. Sieving with experimental measures of emergence require that a table with this measures is available and computed previously for all cells within the family. Chapter 5 is devoted to one additional measure, the exponent of growth, which provides novel information in addition to those defined previously in Chap. 4. The exponent of growth turns out to have a good predictive power for emergent properties, and although it is experimentally defined in Chap. 5, it turns out later in Chap. 7 that is the only among all measures for emergence that can be also analytically determined solely based on cells structure and its neighborhood. Therefore, the theory of probabilistic exponent of growth in Chap. 7 represents a step ahead towards the “holly grail” of emergence, i.e. predicting the behavior without a need to simulate the system. Information theory and the view of cells as nonlinear functions plays essential role in structuring this theory. Several examples of applying this theory, and comparisons with the experimental counterpart of the same measure confirm its validity and predictive power. It is particularly worth applicable for huge families of cells where the time to determine the measures experimentally for the entire family o cells is prohibitive. Instead, the hints given by the theory of probabilistic exponent of grow allows a clever design instead, where the result is simply a set of inequalities with variables drawn from the bits defining the cells gene. The last chapter provides three innovative applications of cellular computing systems in problems such as pattern recognition and lossy image compression to exemplify the potential of the design for emergence tools described in this book.

2 Cellular Nonlinear Networks: State of the Art and Applications

2.1 Introduction Solving some of the open problems using the principles of natural computing exposed in the previous chapter led to the idea of developing a computing paradigm called cellular computing. The structure of such a computing system is defined by a grid (often two-dimensional) of locally interconnected cells. Each cell may be in a number of states (ranging from 2 to infinity) and the state of a cell depends by its own previous state and the previous states of its neighbors through a nonlinear functional, which may be defined in different ways. This functional is associated with a practical implementation of the cell and includes a set of tunable parameters grouped as a gene vector [7]. By tuning the gene parameters one can achieve programmability, i.e. different emergent behaviors within the same basic cellular architecture. The cell assumes an initial state and may have one or more external inputs. In a cellular system, computation can be considered any form of meaningful emergent global phenomenon resulted from a proper design of the cell. Usually the initial state and the inputs code the problem to be solved while the answer to this problem is coded in an equilibrium state. For instance, in the character segmentation example provided in Chap. 8, the initial state contains a visual field with black/white pixels (e.g. handwritten figures) while the steady state result of the emergent dynamics is a collection of rectangles, each enclosing a compact handwritten character. More complicated dynamics (e.g. oscillatory or chaotic) can also encode a solution to the problem posed as initial state. This is the case when cellular systems are used to generate pseudo-random sequences, a widely known application of the cellular systems. The first cellular computers were theoretical constructs introduced by Stanislaw , M. Ulam in the 1950 s [18]. He then suggested John von Neumann to use what he called “cellular spaces” to build his self-reproductive machine [19]. Konrad Zuse (who built the first programmable computers between 1935–1941) was the first to suggest that the entire universe is being computed on a computer, possibly a cellular automaton (CA) [16]. Many years later similar ideas were also published by Edward Fredkin [20,21] and recently (2002) by Stephen Wolfram [17]. In 1982 Fredkin and Toffoli published a paper [22] where cellular computation based on R. Dogaru: Cellular Nonlinear Networks: State of the Art and Applications, Studies in Computational Intelligence (SCI) 95, 7–13 (2008) www.springerlink.com © Springer-Verlag Berlin Heidelberg 2008

8

2 Cellular Nonlinear Networks: State of the Art and Applications

conservative logic was proposed as a nondissipative cellular system. Their approach is interesting while we recall that in general any natural computing system is regarded as a dissipative system. Initially cellular automata (CA) were developed to explain various natural phenomena. Choosing the proper genes in the form of local rules defining the behavior of each cell was the equivalent of programming in serial computers. The well known “Game of Life” rule introduced by Conway in the 1970s [23] gained popularity due to the complex and diverse patterns emerging in such a simply defined system. Designing a proper set of local rules was then a matter of intuition and educated guess rather than the outcome of a well-defined procedure. It was proved that such a simple machine (this is a 2 state per cell cellular automata with a very simple local rule) is capable of universal computation (i.e. it is a universal Turing machine [24]). Following the line of von Neumann, a lot of research has been devoted to the study of cellular automata and local rules leading to emergent properties such as self-reproduction and artificial life. An overview of these nonconventional computers can be found in [25]. Simulation software for a wide palette of cellular paradigms including von Neumann’s self-reproducing machine can be found at [26]. Recently, starting with the work of Chua and Yang [27] a novel cellular computing paradigm called cellular neural network was developed. It inherits the basic ideas of cellular computing and in addition bore some interesting ideas from the field of neural computation. While most of the previously described cellular computing paradigms were conceptual, the CNN was from the beginning circuit oriented, i.e. intended for practical applications as an integrated circuit. Moreover, in 1993 Roska and Chua [28], proposed a revolutionary framework called a CNN Universal Machine, in fact a specialized programmable cellular computer which is capable to execute complex image processing tasks and which found numerous applications in vision, robotics and remote sensing [29]. Nowadays this paradigm is successfully exploited in various applications dealing mainly with extremely fast nonlinear signal processing and intelligent sensors. In [7] it is demonstrated that the CNN paradigm includes cellular automata as a special case. Therefore many of the research in the area of cellular automata can be easily mapped into the CNN formalism with the advantage of exploiting a range of powerful chip implementations that have been developed over the years [30,31]. To date several types of emergent computation were identified as meaningful and useful either for computing applications (e.g. in the area of vision and image processing) or for modeling purposed (e.g. models of the cell membrane) by what I would generically call “evolutionary strategies”. An interesting example is the development of a relatively large library of CNN genes (templates) over the last decade [32]. Many of these genes were discovered by chance, studying the dynamic evolution of the CNN and identifying certain dynamic behaviors with meaningful computational primitives such as edge or corner detection, hole filling, motion detection, and so on. Although some theoretical approaches, mainly inspired from the techniques of filter design were successfully employed to design new chromosomes, there is still much to do for a systematic design of the cells and genes. This book offers several novel approaches and solutions to this problem.

2.2 Typical Applications of Cellular Computers

9

2.2 Typical Applications of Cellular Computers A search done several years ago on the IEEE Xplore database reveals the following distribution of applicative areas for cellular automata and cellular neural network architectures (Fig. 2.1).

Fig. 2.1. Paper distribution on various applicative subjects; Based on IEEE publications between 1988 and 2003. The number within each category is the number of papers found to deal specifically with a certain item (e.g. VLSI) while having the words “cellular automata” or “cellular neural network” also in the article title

The above figure reveals that most of the applications of cellular computers are related to VLSI implementations. They are either digital implementations (custom or reconfigurable) or mixed-signal. A notable example from the mixed-signal category is the CNN-UM (CNN universal machine) mentioned before. The massive parallelism of the cellular computing architecture is the more appealing feature for a VLSI implementation. The result is a fast signal-processing engine, outperforming a conventional signal processor several orders of magnitudes. This is particularly effective for multi-dimensional signal processing, i.e. image processing. Another popular application of cellular computers is that of pattern recognition. Several papers proposed so far the use of cellular computers as classifiers, working on a different principle than classic feed-forward neural networks. Here the classes are associated with a finite number of attractors and the initial state with the pattern to be recognized. Convergence towards an attractor or another indicates the membership of the initial state pattern to a certain category. While

10

2 Cellular Nonlinear Networks: State of the Art and Applications

cellular computers may have hundreds of thousands of cells they can process large databases such as images or other multi-dimensional signals. For instance cellular computing systems can extract edges, corners and other features of interest from an image regardless the size of that image. Besides pattern recognition, cellular systems are capable of various linear and nonlinear filtering tasks. Ciphering is another popular application of cellular computing. Indeed several patents have been filled for such applications where cells are designed such that a complex, chaotic dynamics, emerge in the array of cells. Unlike other methods for random number generation (e.g. the linear feedback shift registers) the CA-based method is scalable, i.e. one can add more cells without changing the essence of the dynamics behavior. By employing a larger number of cells, the probability of deciphering decreases making such systems extremely reliable in terms of security. In a recent paper [33] the use of cellular automata as ciphering systems is carefully investigated and several benchmarks are computed showing that highly reliable random number generators can be obtained using relatively simple cells (e.g. four input Boolean cells) arranged in one-dimensional arrays of several hundreds of cells. The pseudo-random and complex dynamics of cellular systems is also exploited for built in self test (BIST) systems. Such systems are required to perform functional analysis of complex circuits and detect functional failures. In doing so, a convenient solution is to embed a cellular system acting as a pattern generator. The CA is designed such that a large sequence of patterns is generated as a result of the CA dynamics. The length of the sequence is optimized as a tradeoff between a reasonable testing time (demanding thus not a very long sequence) and enough information in the sequence to detect certain failures. In the parlance of emergence ideal BIST sequence generators are operated in the “edge of chaos” regime, i.e. they are neither random signal generators with very long cycles neither orderly systems with very small length limit cycles. Signal compression is another interesting application of cellular automata. Several solutions were reported so far. For instance [34] proposes a solution called a “CA transform” where a signal (image or sound) is decomposed as a binary weighted sum of basis signals. The basis signals are generated by properly tuned cellular automata with certain genes (cell parameters). In order to reconstruct the signal one needs only the set of binary weights and the (relatively) short description of the CA cells generating the basis signals. In order to demonstrate the idea of image compression using cellular automata we proposed recently a novel approach where generalized cellular automata (GCA) can be used. Using the following simple Matlab programs, a wide palette of images can be obtained (one pixel corresponds to one cell in the image), part of which are depicted in Fig. 2.2. Each image in Fig. 2.2 displays above the set of 17 generating parameters. Only a few parameters (17 parameters, underlined above) control the diversity of the obtained images. Such images or part of them can be combined to approximate

2.2 Typical Applications of Cellular Computers

11

% 1 function implementing the cell. It also contains the gene function y=gca_u_cell(u1,u2,u3,u4,u5,u6,u7,u8,u9) Z=[0.9, 0.3, 0.3, 2, 0.3, .6, 0.5]; B=0.5*[1.1 1 1 1 0 1 1 1 1]; sigm=B(1)*u1+B(2)*u2+B(3)*u3+B(4)*u4+B(5)*u5+B(6)*u6+B(7)*u7+B(8)*u8+B(9)*u9; w=Z(1)+Z(2)*u5+Z(3)*sigm-abs(Z(4)+Z(5)*u5+Z(6)*sigm)+Z(7)*abs(sigm); y=w;

% 2 main program running the GCA for a given number of steps function y=gca_u(steps) % e.g. steps=100 (runs the GCA for 100 iterations) x0=-ones(199,199); x0(100,100)=1; [m n]=size(x0); i=1:m; j=1:n; left_j=[n,1:n-1]; right_j=[2:n,1]; up_i=[m,1:m-1]; low_i=[2:m,1]; y=x0; for s=1:steps u9=y(up_i,left_j); u8=y(up_i,j); u7=y(up_i,right_j); u6=y(i,left_j); u5=y; u4=y(i,right_j); u3=y(low_i,left_j); u2=y(low_i,j); u1=y(low_i,right_j); y=gca_u_cell(u1,u2,u3,u4,u5,u6,u7,u8,u9); end set(1,‘Position‘,[291 180 505 540]); image(20*y+32); axis image; colormap gray

any part of a real image. The extreme case is when one of the resulting images has to be compressed. Then since it is the result of running the above programs (acting as decompressing engines) an extremely high compression rate is achieved. Assuming that each of the 17 parameters as well as the pixels from the image are represented with 8 bits, for a 200 × 200 pixels image a compression rate of 200 × 200 can be obtained. This is a rate far beyond any of the actual com2353 17

pression scheme. A challenging task remains to find families of cellular systems capable to approximate quite well larger blocks from real natural images. The larger the blocks the higher the compression rate, which in the limits can reach values as high as thousands or tens of thousands. The advantage of a very simple decompression scheme (the above programs) shall be exploited in making compressed documents such as journals, books or compact encyclopedias.

12

2 Cellular Nonlinear Networks: State of the Art and Applications

Fig. 2.2. Several different images obtained with the same “decompression” software starting from different sets of cell parameters. The compression rate achieved is of the order of thousands since each image is defined by only 17 parameters (depicted above)

2.3 Hardware Platforms for Implementing Cellular Computers Cellular computers are particularly attractive for hardware implementation because is only in hardware where their full computational power come to a life. Moreover, since they are interconnected arrays of regular cells they are simple to implement starting from the design of cell, which is multiplied as needed. The designer of a cellular system focuses on cell-design while interconnection often

2.3 Hardware Platforms for Implementing Cellular Computers 13

comes naturally by arranging the cells given the technology constraint. Often the arrays are two-dimensional with each cell connected to the immediate neighbors. In digital technologies cellular computers can be realized either as dedicated VLSI products but in this case they are less flexible and have large development costs or better using the FPGA (field-programmable-gate-array) technology which offers a high degree of flexibility and programmability as a results of allowing random interconnection between a number of identical yet reconfigurable digital cells. Several FPGA implementations of cellular systems were reported so far [35], including a CNN prototyping board. Digital technologies have the disadvantage of a low density of cells. This is why an alternative solution is the use of mixed-signal cells, where compact cells based on nonlinear computation in analog devices are used. The CNN paradigm was from the beginning oriented to such a technology. So far a series of chips (today called visual microprocessors or imagers) was developed. Among the latest implementation solution of a CNN universal machine is the ACE16k chip [36] which has optical input and can implement the standard CNN model. It has a number of about 16,000 cells, each cell being associated with an image pixel. Certain high-speed processing tasks were demonstrated such as the task of classifying objects (medical pills) presented to the optical input with a speed of 20,000 objects per second. Several other mixed-signal cell architectures were proposed, for instance the architecture described in [37], which is based on a nested (recurrent) utilization of a nonmonotone nonlinear function to reduce the complexity and implement arbitrary Boolean functions. Arbitrary Boolean functions with n inputs can be implemented with a linear complexity in n. A schematic of this function is presented in Chap. 3. A novel implementation medium, although yet experimental, is represented by the use of nano-technologies [38]. Browsing the literature of the last 2 years, we found an increased interest in the “quantum dot” cellular computing paradigm [39], abbreviated QCA (from quantum cellular automata). Recently [40] the paradigm evolved into molecular QCA. More details and java simulations of QCA systems can be found at http://www.nd.edu/~qcahome/. A quantum dot is a nanometer scale active cell. Quantum dots are interconnected by proximity so there is no need for additional metal layers as in standard electronic technologies. A state change in a QCA cell propagates to its neighbors and this is exactly the basis for cellular computation. When arranged properly such cells are capable to do various computational tasks.

3 Cellular and Natural Computing Models and Software Simulation

3.1 Cellular Systems: Cells, Neighborhoods, States and Dynamics The main features of cellular systems are regularity and homogeneity. In fact a cellular system can be defined as a structured collection of identical elements called cells. The structure of a cellular computing system is given by the choice of a lattice. Such lattices are one-dimensional, two-dimensional and, less used, three or more dimensional. The following are examples of commonly used twodimensional lattices:

Fig. 3.1. Cells, lattices, neighborhoods and indexes

In the above pictures, the cells in the neighborhood are depicted in lighter gray shade, with the exception of the central cell. The neighborhood represents the set .RDogaru: Cellular and Natural Computing Models and Software Simulation, Studies in Computational Intelligence (SCI) 95, 15 –64 (2008 ) www.springerlink.com © Springer-V erlag eBrlin eHidelberg 2008

16

3 Cellular and Natural Computing Models and Software Simulation

of cells that are directly interacting with the central cell. The neighborhood is represented by the set N and a unique index k is chosen to identify the neighboring cell in a particular neighborhood. The assignment of different integer values to k is conventional and some examples are provided in Fig. 3.1 where indexes are depicted in white for each type of neighborhood. The cells are in fact nonlinear dynamic systems. The cell dynamics can be continuous in time and mathematically described by ordinary differential equations ODEs or discrete in time and then their dynamics is described by difference equations. Example 1:

y1 (t )

¦ ak ˜ yk t  1 defines the dynamics of the output y1 t of a

k N

discrete time autonomous cell defined by a weighted summation of all neighboring cell outputs at the previous time clock. The discrete time variable t is here an integer. The above example represents one of the simplest possible cells. It is autonomous since there is no external input to drive the dynamics of the cell. In the general case a cell is described by the following variables: Inputs – usually denoted by variable u (scalar) or u (vector of inputs); States – usually denoted by variable x (scalar) or x (vector of states); Initial states – a particular state variable at the initial moment, t=0. Outputs – usually denoted by variable y (scalar) or y (vector of outputs). In terms of a computing machine, inputs and initial states are used to supply the cellular system with the input data (to be processed) while the result or output data is available in the form of a pattern (spatial, temporal or spatio-temporal) of the outputs. For simpler cells sometimes outputs and states may coincide, otherwise the outputs represent a nonlinear function applied to states. Example 2: The “standard cellular neural network” cell The ODE defining the standard cellular neural network [27] is: x1

where yk

1 2

 x1  ¦ ak yk  ¦ bk uk  z k N

(3.1)

k N

 xk  1  xk  1 ,

and the initial states xk 0 are specified for all cells in the neighborhood N. Observe that this is a more complex, continuous time, dynamic system with a nonlinearity induced by the relationship between states and outputs. In general (nonstandard CNN cell) (3.1) is replaced with: x1  x1  f G , yk , uk , where f is a nonlinear function and G is a gene as defined next.

(3.1’)

3.1 Cellular Systems: Cells, Neighborhoods, States and Dynamics

17

3.1.1 Genes The cell dynamics, and its local functionality are prescribed by an unique gene [7] vector G >a1, a2 ,..an1,.., b1, b2 ,..bn 2 ,...@ containing all parameters of the nonlinear system modeling the cell. The analogy with biology is obvious, and the gene vector may be regarded as the equivalent of the information contained in the DNA string. 3.1.2 Discrete and Continuous States and Outputs In defining a cellular system one has to prescribe the variation domain of the state and output variables. For example, one can use continuous state cells where the outputs are defined within a bounded interval or one can also use discrete state cells where the states or/and the outputs belong to a finite set of possible values. A binary output cell implements Boolean functions, i.e. it provides a logical “TRUE” or “FALSE” output for each of the 2n possible combinations of inputs. Each input also represents a truth value. The cell can be again specified as a discrete-time dynamical system but it can be also specified using a transition table or a set of local rules. The last two modes of specifying a cell are specific to the cellular automata formalism [41]. As we will show in the next chapter, a compact piecewise linear description (i.e. a discrete dynamical system) can be found for any Boolean or other type of input function: Example 3: A Boolean cell y1 (t )

§ · sign¨¨ z0  ¦ bk ˜ uk t ¸¸ kN © ¹

(3.2)

Assuming that the set ^1,1` is used to code the truth set ^FALSE, TRUE` , the cell equation (3.2) above defines a family of Boolean functions. For a particular Boolean function one should specify the gene parameters. For example, the AND function with three inputs is associated with the following gene: G >z0 , b1, b2 , b3 @ > 2,1,1,1@ . If the gene is replaced with G >z0 , b1, b2 , b3 @ >2,1,1,1@ , the OR function with three inputs is implemented. 3.1.3 Boundary Conditions In cellular automata the cells located on the boundary of a lattice have a special in interconnectivity. One should define precisely the way in which these cells interact with their neighbors. This is called a boundary condition. The choice of a particular boundary condition may have a great influence on the dynamics of the cellular system. The following two are among the mostly used boundary conditions: Periodic boundary conditions: Opposite borders of the lattice are connected. A one-dimensional “line” becomes following that way a circle, a two-dimensional lattice becomes a torus.

18

3 Cellular and Natural Computing Models and Software Simulation

Reflective boundary conditions: The border cells are mirrored, i.e. the consequence is having symmetric border properties. In the remainder of this chapter exclusively square lattices and periodic boundary conditions are used.

3.2 Major Cellular Systems Paradigms

3.2.1 The Cellular Neural Network (CNN) Model The cellular neural network (CNN) model was proposed by Chua [27] as a practical circuit alternative to oHpfield and ot her type of recurrent networks. The CNN cell is a continuous time and continuous state dynamical system with some saturated nonlinearity (see (3.1)) which is well suited for implementation using analog circuits. nUlike CA s which are mostly used to prove various theories or to model physical processes the CNN was intended from the beginning to be also a useful signal processing paradigm. A n important step towards making this paradigm an application oriented one was the introduction in 19 93 of the concept of CNN universal machine (CNNU M ) [28]. W ithin the framework of the CNN-U M , a CNN kernel is employed to perform different parallel information processing tasks. Each task is associated with a gene (i.e. a set of parameters of the synaptic interconnections) which may be selected from a continuously growing library of more than 200 different primitive genes (and tasks). Therefore one may combine various such primitives, which are stored in an analog memory much like the instruction-code memory of digital microprocessor. V arious high-level comp utations emerge, making the CNN-U M implementation a suitable medium for computing at TerraOps computing speed. R ecent electronic implementations of the CNN-U M are in fact sensor computers [42], having the capability to sense and to process an image on the same chip. Several generations of microelectronic chips were reported so far [31], as well as development tools, allowing users to program the CNN as visual microprocessor. There is a wide range of applications, mostly in the area of image processing. Such applications include image segmentation, image compression, fast halftoning, contour tracking, image fusion, pattern recognition, to name uj st a few. A lthough initially the equilibrium dynamics of CNNs was mostly exploited for applications, recently the nonequilibrium dynamics is employed for certain interesting applications in what is currently called “computing with waves” [43,44]. There is an increasing research interest around the world for the field of cellular neural networks, most of which is reported in the rPoceedings of the IEEE CNNA workshops (cellular neural networks and their applications), ISCA S or IJCNN

3.2 Major Cellular Systems Paradigms

19

conferences as well as in numerous journal papers or books. Some recent tutorials about CNNs are [7,29,31,45]. Several CNN simulators are freely available and the reader may check [4 6], and [47] for an easy to use, computing platform independent CNN simulator. Awide range of simulators as well as news about the progress in the CNN research can be accessed from [4 8]. The SCNN simulator from the pAplied hPysics Department of the oGethe nUiversity in Frankfurt am M ain can be used on U nix platforms [49]. 3.2.2 The Generalized Cellular Automata In [7], the idea of a generalized cellular automata (G CA ) was introduced as an extension of the CNN so that a C GAinclude s CA s as a special case. The main idea of the C GAis to use a CNN in a discrete-time loop. In other words, for each period of the clock the CNN system evolves until it eventually reaches a steady output (for some CNN genes it is possible to have complex oscillatory dynamics) starting from a given initial condition and from inputs variables that are copies of the C GAneighboring cells outputs at the end of the previous time cycle. The additional CNN loop is thus given by the discrete time equation uk (t ) yk (t  1) . There are two cases of interest: x W hen the CNN cell is uncoupled (i.e. all coefficients ak 0 for k t 2 in (1)) it was proved that the nonlinear dynamic system (3.1’) converges towards a steady state output solution and therefore aft enough period of time T the cell can be described as a simple nonlinear equation of the following form: y1 t F G , uk t where F is a nonlinear function and G is a gene (i.e. tunable parameters). In this case the C GAcan emulate any CA , provided that there exist a method to map the local rules or transition table into the nonlinear function F. A s it can be easily observed such G CAcan also implement discrete-time but continuous state cellular automata. x W hen the CNN cell is coupled, one should first determine a set of proper genes such that the same steady state behavior occurs during the clock time T. This is often not a trivial task. Then, the behavior of the resulting C GAis more complex than that of a normal CA . The reason is that an emergent computation already takes place during the period of time T in the CNN, therefore at the discrete time moment when the output of a cell is sampled, it does not represent only the contribution of the neighboring cells as in the case of a “classic” cellular automata but rather the contribution of all CNN cells. In some sense one can say that employing a continuous time CNN during the clock time is equivalent to artificially increasing the neighborhood to the whole cellular space. This behavior may imply interesting computational consequences.

20

3 Cellular and Natural Computing Models and Software Simulation

3.2.3 Reaction-Diffusion Cellular Nonlinear Networks R eaction-diffusion CNNs (R D-CNNs) [8] were proposed as a particular case of continuous-time autonomous1 CNN and are discrete-space models of partial differential equations describing the reaction-diffusion physical processes. From a circuit perspective a D R -CNN can be modeled as a collection of multiport nonlinear cells. These cells are coupled with their neighboring cells via linear resistive networks (Fig. 3.2).

Fig. 3.2. The topology of a reaction diffusion cellular neural network. Acell is a m-port described by a nonlinear ODE which models a physical reaction. The coupling with neighboring ing cells is done via resistive grids modeling the physical process of diffusion

Example :4 The case of a reactiondiffusion cell with von Neumann neighborhood. The cell equation is of the following form: x&11

.. x&1j

..

x&1m 1





f1 ( x11, x12 ,..., x1m , G1 )  D1 x12  x13  x14  x15  4 x11 ,





f2(x11, x12 ,..., x1m , G j )  D j x2 j  x3 j  x4j  x5j  4 x1j ,

fm( x11 , x12 ,..., x1m , G m )  Dm  x2m  x3m  x4m  x5 m  41x m ,

nA autonomous system has no external inputs. Information processing in such systems consists in prescribing the initial state of all cells with some pattern to be processed followed by a dynamic transformation of this pattern until a stopping criterion is met.

3.3 Matlab Simulation of Generalized Cellular uAtomata and Cellular Neural Network

21

where xkj is the state variable of cell k (using the neighborhood index as in Fig. 3.1 with the central cell indexed as k=1) in layer j. The gene is also distributed among layers as G 1 ,...G m and in addition each layer is characterized by the scalar diffusion coefficient D j corresponding physically to the conductance of the resistors in the resistive grid in Fig. 3.2. R D-CNNs have the interesting property that emergent behaviors can be predicted by carrying out a local activity analysis of the isolated cell (ignoring the coupling). Adetailed analysis based on the local activity [7,8] reveals regions of emergence in the cell parameter space [9 –11,15 ] called an “edge of chaos”. So far, an analytic method to draw the boundaries of the “edge of chaos” regions in the cell parameter space exists only for reaction–sifussion cellular systems. Though, within this chapter certain algorithmic methods for detecting emergence regions within the cell parameter space of arbitrary cellular systems are given.

3.3 Matlab Simulation of Generalized Cellular Automata and Cellular Neural Networks It is convenient to simulate various types of cellular system using the programming environment aMtlab (http:/w / ww.math works.com/products/matlab/) produced by aMthworks. eWwill assume here the reader has some basic knowledge of aMtlab. For readers unfamiliar with this language, a good starting point might be the primers [50] or [51]. 3.3.1 Uncoupled GCAs In order to simulate an uncoupled C GAone should first write the function G CA _U CEL L .M which implements the G CAcell. It is in fact a simple description of the nonlinear function y1 t F G , uk t :

function y=gca_u_cell(u1,u2,u3,u4,u5,u6,u7,u8,u9) Z=[-1,-2,-4,-8,-7]; B=[1 1 1 1 1 1 1 1 1]; s=-1; sigm=B(1)*u1+B(2)*u2+B(3)*u3+B(4)*u4+B(5)*u5+B(6)*u6+B(7)*u7+B(8)*u8+B(9)*u9; w=Z(1)+abs(Z(2)+abs(Z(3)+abs(Z(4)+abs(Z(5)+sigm)))); y=s*sign(w); %y=0.5*(abs(w+1)-abs(w-1)); %y=w;

The nine inputs of this function can be a scalar, a vector or an array. The above program implements the aPrity9local logic function. oHwever, by simply changing

22 3 Cellular and Natural Computing Models and Software Simulation

the gene parameters (in our case the values of the ,Z,Bs) many other local oBolean functions can be implemented. In [5 2] an d [15] a detailed procedure is given to represent any arbitrary oBolean function us ing a piecewise-linear representation as above. M oreover, one can simply change the cell structure and use any other nonlinear function. For example, as seen in the last lines, while a sign function is employed, the result is a C GAemulatin g a binary cellular automaton. One may also use continuous valued functions with or without saturation, resulting in a G CAwith continuous states (the last lines of the code). L et us now have a look at the code C GA _U .M to implement the generalized cellular automata. It is implemented in the form of a M atlab function with two input parameters. The first is a scalar and represents the number of iteration steps until stop (a faster stop can be achieved by pressing the keys CTR Land C). The second may be absent but if not it represents the name (a string) of a file containing the initial state. The initial state gives also information about the size (number of cells) of the C GA . Aperiodic boundary condition is implemented, the lattice is square with a M oore neighborhood indexed as explained in the source code: function gca_u(steps,init_cond) % e.g. steps=100 (runs the GCA for 100 iterations) % e.g. init_cond='cross199' % The inital state should be previously saved as matrix x0. For example: % x0=ones(199,199); x0(90:110,90:110)=1 % save one199 x0 % The neighborhood index is chosen as follows: % 9 8 7 % 6 5 4 % 3 2 1 if nargin<2 % by default the "cross199" initial state is loaded if no input file is specified init_cond='cross199'; x0=-ones(199,199); x0(90:110,90:110)=1; else eval(['load ',init_cond]); % load the initial state end [m n]=size(x0); i=1:m; % row index j=1:n; % column index left_j=[n,1:n-1]; right_j=[2:n,1]; % indexes of cells on the left and right up_i=[m,1:m-1]; low_i=[2:m,1]; % indexes of cells upper and lower

y=x0;

% current output is loaded with x0

for s=1:steps % Computes the inputs in the next step u8=y(up_i,j); u7=y(up_i,right_j); u5=y; u4=y(i,right_j); u2=y(low_i,j); u1=y(low_i,right_j); % Compute the new output using the cell function y=gca_u_cell(u1,u2,u3,u4,u5,u6,u7,u8,u9);

u9=y(up_i,left_j); u6=y(i,left_j); u3=y(low_i,left_j);

3.3 Matlab Simulation of Generalized Cellular Automata and Cellular Neural Network

23

% display the new output image(20*y+32); axis image; colormap jet title(['Step: ',num2str(s),' Initial state: ',init_cond,' PRESS ANY KEY TO CONTINUE']); % press a key for the next step waitforbuttonpress end

W ith these two simple programs one may st art to observe emergent patterns in generalized cellular automata. First, running the program exactly in the form written above (e.g. run C G(U _A100) for a 100 st eps run) a sequence of growing binary patterns is observed. The color code used here associates color red with 1+ and blue with –1. One can easily simulate another C GAsy stem with a different behavior reediting the C GA _U CEL L .Mfile. For example after replacing Z = [–1,–2,–4,–8, –7] with Z = [–1,–2,–4,–6,–7] the result wi ll be a sequence of “snow-flake” like binary patterns. M oreover, if the initial Zvector is used but the initial Bvector is replaced with = B [1 1 1 1 –8.51 1 1 1] and the output function is chosen y= 0.5*(abs(w+ 1 ) –abs(w–1)) the result is a sequence of colored patterns corresponding to a continuous-state cellular automaton. Observe that much of the flexibility in programming different behaviors using the same code is due to the use of a universal piecewise-linear parametric functional (the function with nested absolute values). 3.3.2 Coupled GCAs In the implementation of the cell for the uncoupled G CAthere is no temporal dynamics involved and the output is computed uj st as a nonlinear function of the nine inputs. In fact, when called from the main function C GA _Uthe function G CA _U CEL Lupdates all cells simultaneously since it performs matrix computation (all inputs, for example u1, are matrices of the same size as the CNN). The G CA _U CEL Lfunction implements a layer of CNN cells, but since the model is simplified there is no temporal dynamics included. In order to implement a coupled G CAwe should change this cell function such that it will implement the dynamic evolution of a continuous time CNN. The resulting code of the program G CA _C_CEL L .M is listed next: function y=gca_c_cell(u1,u2,u3,u4,u5,u6,u7,u8,u9) Delta_T=0.1; % integration step (the smallest the best precision but takes longer) T=4; % the duration of the Euler integration; B=[0 -1 0 0 1 0 0 -1 0]; % cell parameters (gene) A=[1 1 1 1 -3 1 1 1 1]; z=0; %--------------------------------------------------------------------------------------------------[m n]=size(u1);

24

3 Cellular and Natural Computing Models and Software Simulation

i=1:m; % row index j=1:n; % column index left_j=[n,1:n-1]; right_j=[2:n,1]; % indexes of cells on the left and right up_i=[m,1:m-1]; low_i=[2:m,1]; % indexes of cells upper and lower x=0.0001*(rand(m,n)-0.5); % initialization of the initial state with small random values % LINE A % the feed-forward contribution ffwd=z+B(1)*u1+B(2)*u2+B(3)*u3+B(4)*u4+B(5)*u5+B(6)*u6+B(7)*u7+B(8)*u8+B(9)*u9; for s=1:round(T/Delta_T) y=0.5*(abs(x+1)-abs(x-1)); % compute the outputs for all neighbors y9=y(up_i,left_j); y8=y(up_i,j); y7=y(up_i,right_j); y6=y(i,left_j); y5=y; y4=y(i,right_j); y3=y(low_i,left_j); y2=y(low_i,j); y1=y(low_i,right_j); % LINE B % the recurrent contribution recur=A(1)*y1+A(2)*y2+A(3)*y3+A(4)*y4+A(5)*y5+A(6)*y6+A(7)*y7+A(8)*y8+A(9)*y9; x=(1-Delta_T)*x+Delta_T*(ffwd+recur); % update the state dynamics following equation (1) %display the new output image(20*y+32); axis image; colormap jet title(['Time: ',num2str(s*Delta_T),' PRESS ANY KEY TO CONTINUE']); % wait for next step waitforbuttonpress end

This new cell is in fact a implementation of the standard (linear coupling) CNN model of Chua and aYng [7]. It can easily evolved into a nonstandard model by simply changing ILNE Aand L INE Bacco rdingly. The continuous time dynamics associated to (3.1) is emulated on the discrete-time computer using a simple integration method; namely, the Euler’s method. Therefore, in addition to gene parameters this new cell has to specify two dynamic parameters. The first, Delta_T indicates the step size and the smallest th e better will be the approximation of the continuous time dynamics. The second, T, represents the integration time period. U sually the user may choose such a va lue that corresponds to a steady state dynamics in the output. In order to simulate a coupled C GAone should use the above file in conjunction with a file called C GA _C.M , which is simply obtained from a copy of the G CA _U .M file after changing the name of cell function from C G_ C U AEL Lto G CA _C_CEL L . U sing the values in the file above, the dynamics of the CNN will be first observed, and from time to time a figure will show the C GAoutput. The visualization of the CNN steps is useful for first experiments and it allows one to choose the two dynamic parameters. oHwever, if one wants to see only the G CAoutput, the visualization lines in the above file should be ignored (by inserting % in front of them). L ike in the previous cases, a wide range of systems can be simulated, by properly re-editing the above file after proper changes of the gene or/and various parameters of the dynamics (i.e. the number of steps).

3.4 Nonlinear Representation of Cells

25

3.3.3 Simulation of Standard Cellular Neural Networks As we already discussed, simulating the CNN reduces to the particular case of simulating a coupled GCA for only one discrete time step. The GCA_C_CELL is activated and it will simulate the CNN. Its parameters and even novel CNN models can be easily simulated by properly re-editing the GCA_C_CELL.M file.

3.4 Nonlinear Representation of Cells In the next we will consider GCAs with uncoupled Boolean cells (i.e. having only two possible states). Such GCAs correspond to cellular automata (CA) with two states per cell. Even in this simple case, considering a nine cell neighborhood, 9

there is a huge number of 2 2 2512 of possible cells. Searching for emergent behaviors in such a huge cell space is impossible. Arguments extensively presented in Chap. 4 indicates the need to restrict the cell model so that the search space can be reduced to a much reasonable number of cells. The semitotalistic cell is such a convenient model. In a semitotalistic cell the output depends only on two numbers: D which represents the contribution (summation) of all neighboring cells (except the central cell). Assuming that cell outputs belong to the ^0,1` set it follows immediately that D  ^0,1,.., n  1` and therefore it has only n discrete values. The second number E  ^0,1` can take only two discrete values and represents the contribution of the central cell. It follows that for a cell with n inputs there are only 2n possible combinations of inputs, each corresponding to an output chosen among two values. Therefore there are only 2 2n semitotalistic cells with n inputs. For typical neighborhood sizes n the result is a tractable number of possible cells. For instance in the case of a 5-cell neighborhood there are only 1,024 possible cells to investigate while in the case of 9-cells neighborhood there are 262,144 possible semitotalistic cells. Let us first consider the case of a 5-neighborhood cell. Each cell output y1i , j within the cellular system grid can have either 0 or 1 value and it corresponds to a black or a white pixel respectively in an image to be processed. The image is applied as an initial state Y (0) y1i, j (0) , where the indexes i, j point to the row and the column, and the subscript “1” identify the central cell in a neighborhood (as in Fig. 3.1). Using cells defined by gene G1 the automaton is run for T1 iterations, then the gene may be changed into G2 and run another T2 iterations and so on. The sequence 3 >G1, T1 , G1, T2 ,...Gm , Tm @ will define an overall processing function, i.e. a “program”. Note that unlike in the case of traditional computing systems where programs are defined by algorithms, here we need to search for those emergent genes G1,..Gm and associate the underlying processing with certain useful information processing functions. The above is the subject of “designing for

^

`

26 3 Cellular and Natural Computing Models and Software Simulation

emergence”, the topic of this book. Note also that since CAgenes are usually described by a small number of bits, the CA“program length” is usually quite small, at least compared to traditional programs. Though, even for a “small” program length of 152 bits, the number of possible programs is huge and therefore adequate tools and methods have to be defined for an effective way to locate those programs. In one discrete time step a synchronous update of all cells takes place, based on the status of their neighborhoods at the previous time step. For a semitotalistic CA , the update depends only on the values of D 2y t 3y t  y4 t  y5 t and Bolean function (gene) can be defined usE y1 t . Therefore the transition local o ing Table 3.1 where the gene is a 10-dimensional binary vector G >g9 , g8 ,..., g 0 @ : Table 3.1. Acell definition using a table

G D E

g9 4 1

g7

g8

3

2

1

g6

1

1

g5

0

1

1

g3

g4

4

3

0

g2

2

0

g1

1

0

g0

0

0

0

The state of the neighborhood is entirely described by two integers: D , E W hen each of the binary components g j of the gene G are defined, the above table precisely indicates a local rule, i.e. how to update the state (output) of the central cell for any possible configurations of the neighborhood given by D , E y1 t  1 G D t , E t

(3.3)

The gene G >g9 , g8 ,..., g 0 @ is a binary string. In practice is often more convenient to use its decimal representation, denoted ID (cell identifier). For a given constraint of the cellular model (e.g. specifying that semitotalistic cells with nine inputs are used, or the label of a taxonomy such as “2s9” – see Sect. 3.7) an ID clearly individualizes a cell within a fami ly composed of all possible cells given the constraints. 3.4.1 Piecewise-Linear Representation and Implementation The function in (3.3) can be implemented directly using a look-up table (a 1,024 bits R A M or R OM ) or via compact mixedsignal cells [37]. This later method is the most convenient in terms of density of cells. In order to define a circuit as in [37], but also for other reasons, a nonlinear representation of (3.3) is more convenient that a table. For instance, as seen later, the use of such a nonlinear description in aMtlab allows the use of the intrinsic matrix operations, therefore leading to an important speedup compared to the case when tables would be used. In order to understand the principles of nonlinear representations [5 2] let us consider the case of implementing the function ID= 103 (or 0001100111 binary).

3.4 Nonlinear Representation of Cells

27

L et introduce a unique variable V describing the excitation of the neighborhood (it should encode all possibilities for the collective states of the neighborhood), and note than in the case of our semitotalistic cell it is described by V 5E  D . In what follows we will also call V a projection because it represents a projection from the n-dimensional input space to a one-dimensional (scalar) space while preserving all information contained in the n-dimensional vector defining the collective state of the neighborhood. In general, for any semitotalistic cell with n inputs the following formula stands: (3.4)

bE  D ,

V

where D , E are defined as above, and b (called an orientation [52]) is an integer b  ^0,1,..n` . Implicitly b n but one can optimize its value (minimize b) such that for the same number n of inputs the gene will become smaller than n+1 (needs less bits). Adiscussion on the significance of b follows later within this section. Now Table 3.1 can be rewritten as Table 3.2. eHre we used the convention w=–1 to denote an output equal to logic “0”, and we also specified the transition points, i.e. those values of V such that the w function switches from –1 to + 1 or viceversa. Note that any nonlinear function with the same roots as the transition points can be selected as a nonlinear representation of the cell. In particular the simplest solution is a polynomial function, i.e. w

s  V  t1

(3.5)

 V  t 2 ...  V  t m .

Table 3.2. Acell definition based on the function al dependence between the projection V and the output y (H ere exemplified for ID= 103) G= y( V ) w

0

0

0

–1

–1

–1

0

1 1

1 1

5E  D

9

8

7

t 3 6. 5

6

5

V

0 t 2 4. 5

0 –1

0 –1

0

1 1

1 1

1 1

4

3

t1 2. 5

2

1

0

Note than any scalar function which passes through the transition points marked within the table can implement the table.

The output value is defined by y  sgnw 1 /2.

(3.6)

In (5) the s (sign) variable is computed as: s 2 g01, (3.7) i.e. s 1 for even ID and s 1 for odd ID. Note than in the above are possible at most m N  1 transition points where N is the number of bits defining the gene G.

28 3 Cellular and Natural Computing Models and Software Simulation

Instead of (3.5) a piecewise linear (P W L ) canonical formula could be used for more convenient analysis and hardware implementation [15 ]. For a set of m transition points t1, t2 ,.., tm the canonical P W Lrepresentation corresponds to:

>

@

m1

w z 0. 5 1 m 1 sV  s ¦ 1 k V  zk

with

(3.8)

k 1

zk 0. 5tk  tk 1 , and

z

>

@

m 1

  1 m  1 st1  s ¦  1 k t1  zk k 1

Examined to a closer look, either formulae (3.5 ) or (3.8) are fully defined if for any given ID (string of N bits) one knows the following set of parameters: b, t1,...tm . U sing a simple method an optimal 2 implementation via (3.8 ) for each of the 1,024 possible genes can be determined. In order to determine a realization with a minimal number of m (i.e. minimum number of transitions), successive integer values for b are considered (until b becomes equal to n) and one keeps only the value of b giving the minimum number of transitions. The successive values t1 ,...t m are then recorded. For the case of all 1,024semitotalistic func tions with five inputs the next tables give the corresponding realizations ( b, m ). The sign value s can be simply computed with (3.7) and therefore is not given in the table. lAso the exact transition points t1 ,...t m are missing from the table since they can be easily computed, as explained above (Table 3.3). Table 3.3. Alist of all semitotalistic genes indicating their optimal realization. In each row, the numbers indicate, ID, b, and m (the number m of transitions, also indicating the complexity of the cell. Those cells with b= 0 are totalistic (i.e. their output depends exclusively by the sum of the neighbor cells) 0

0

0

14

4

2

28

5

2

42

3

4

1

1

1

15

4

1

29

5

3

43

3

3

2

2

2

16

5

2

30

5

2

44

3

2

3

2

1

17

5

3

31

5

1

45

3

3

4

3

2

18

5

4

32

5

2

46

3

2

5

3

3

19

5

3

33

0

1

47

3

1

6

3

2

20

5

4

34

1

2

48

4

2

7

3

1

21

5

5

35

1

1

49

4

3

8

4

2

22

5

4

36

2

2

50

4

4 3

9

4

3

23

5

3

37

2

3

51

4

10

4

4

24

5

2

38

2

2

52

4

4

11

4

3

25

5

3

39

2

1

53

4

5

12

4

2

26

5

4

40

3

2

54

4

4

13

4

3

27

5

3

41

3

3

55

4

3

2

In the sense of minimizing the number of transition points.

3.4 Nonlinear Representation of Cells

29

56

4

2

96

5

2

136

1

2

176

4

57

4

3

97

5

3

137

1

3

177

4

5

58

4

4

98

5

4

138

4

6

178

4

6

59

4

3

99

0

1

139

4

5

179

4

5

60

4

2

100

5

4

140

4

4

180

2

4

61

4

3

101

5

5

141

4

5

181

2

5

62

4

2

102

1

2

142

4

4

182

2

4

63

4

1

103

1

1

143

4

3

183

2

3

64

4

2

104

5

4

144

2

2

184

4

4

65

4

3

105

5

5

145

2

3

185

4

5

66

0

2

106

5

6

146

2

4

186

4

6

67

4

3

107

5

5

147

2

3

187

4

5

68

1

2

108

2

2

148

5

6

188

4

4

69

1

3

109

2

3

149

5

7

189

4

5

70

4

4

110

2

2

150

5

6

190

4

4

71

4

3

111

2

1

151

5

5

191

4

3

72

2

2

112

4

2

152

5

4

192

4

2

73

2

3

113

4

3

153

5

5

193

4

3

74

2

4

114

4

4

154

5

6

194

4

4

75

2

3

115

4

3

155

5

5

195

4

3

76

4

4

116

4

4

156

5

4

196

4

4

77

4

5

117

4

5

157

5

5

197

4

5

78

4

4

118

4

4

158

5

4

198

0

2

79

4

3

119

4

3

159

5

3

199

4

3

80

3

2

120

3

2

160

5

4

200

4

4

81

3

3

121

3

3

161

5

5

201

4

5

82

3

4

122

3

4

162

5

6

202

4

6

83

3

3

123

3

3

163

5

5

203

4

5

84

3

4

124

3

2

164

5

6

204

1

2

85

3

5

125

3

3

165

0

3

205

1

3

86

3

4

126

3

2

166

5

6

206

4

4

87

3

3

127

3

1

167

5

5

207

4

3

88

5

4

128

3

2

168

3

4

208

3

2

89

5

5

129

3

3

169

3

5

209

3

3

90

5

6

130

3

4

170

1

4

210

3

4

91

5

5

131

3

3

171

1

3

211

3

3

92

5

4

132

0

2

172

3

4

212

3

4

93

5

5

133

3

5

173

3

5

213

3

5

94

5

4

134

3

4

174

3

4

214

3

4

95

5

3

135

3

3

175

3

3

215

3

3

4

(Continued)

30

3 Cellular and Natural Computing Models and Software Simulation

216

2

2

256

2

2

296

3

4

336

3

4

217

2

3

257

2

3

297

0

3

337

3

5

218

2

4

258

2

4

298

3

6

338

3

6

219

2

3

259

2

3

299

3

5

339

3

5

220

5

4

260

3

4

300

3

4

340

1

4

221

5

5

261

3

5

301

3

5

341

1

5

222

5

4

262

3

4

302

3

4

342

3

6

223

5

3

263

3

3

303

3

3

343

3

5

224

5

2

264

0

2

304

4

4

344

5

6

225

5

3

265

4

5

305

4

5

345

5

7

226

5

4

266

4

6

306

1

4

346

5

8

227

5

3

267

4

5

307

1

3

347

5

7

228

5

4

268

4

4

308

4

6

348

5

6

229

5

5

269

4

5

309

4

7

349

5

7

230

5

4

270

4

4

310

4

6

350

5

6

231

0

1

271

4

3

311

4

5

351

5

5

232

5

4

272

1

2

312

4

4

352

5

4

233

5

5

273

1

3

313

4

5

353

5

5

234

5

6

274

5

6

314

4

6

354

5

6

235

5

5

275

5

5

315

4

5

355

5

5

236

5

4

276

5

6

316

4

4

356

5

6

237

5

5

277

5

7

317

4

5

357

5

7

238

1

2

278

5

6

318

4

4

358

5

6

239

1

1

279

5

5

319

4

3

359

5

5

240

4

2

280

5

4

320

4

4

360

5

6

241

4

3

281

5

5

321

4

5

361

5

7

242

4

4

282

5

6

322

4

6

362

5

8

243

4

3

283

5

5

323

4

5

363

0

3

244

4

4

284

5

4

324

4

6

364

2

4

245

4

5

285

5

5

325

4

7

365

2

5

246

4

4

286

5

4

326

4

6

366

2

4

247

4

3

287

5

3

327

4

5

367

2

3

248

3

2

288

5

4

328

2

4

368

4

4

249

3

3

289

5

5

329

2

5

369

4

5

250

3

4

290

5

6

330

0

4

370

4

6

251

3

3

291

5

5

331

2

5

371

4

5

252

2

2

292

2

4

332

4

6

372

4

6

253

2

3

293

2

5

333

4

7

373

4

7

254

2

2

294

2

4

334

4

6

374

1

4

255

2

1

295

2

3

335

4

5

375

1

3

3.4 Nonlinear Representation of Cells

31

376

3

4

416

5

4

456

4

4

496

4

2

377

3

5

417

5

5

457

4

5

497

4

3

378

3

6

418

5

6

458

4

6

498

4

4

379

3

5

419

5

5

459

4

5

499

4

3

380

3

4

420

5

6

460

4

4

500

4

4

381

3

5

421

5

7

461

4

5

501

4

5

382

3

4

422

5

6

462

0

2

502

4

4

383

3

3

423

5

5

463

4

3

503

4

3

384

3

2

424

3

4

464

3

2

504

3

2

385

3

3

425

3

5

465

3

3

505

3

3

386

3

4

426

3

6

466

3

4

506

3

4

387

3

3

427

3

5

467

3

3

507

3

3

388

3

4

428

3

4

468

3

4

508

2

2

389

3

5

429

0

3

469

3

5

509

2

3

390

3

4

430

3

4

470

3

4

510

1

2

391

3

3

431

3

3

471

3

3

511

1

1

392

4

4

432

4

4

472

2

2

512

1

1

393

4

5

433

4

5

473

2

3

513

1

2

394

4

6

434

4

6

474

2

4

514

2

3

395

4

5

435

4

5

475

2

3

515

2

2

396

0

2

436

2

4

476

1

2

516

3

3

397

4

5

437

2

5

477

1

3

517

3

4

398

4

4

438

2

4

478

5

4

518

3

3

399

4

3

439

2

3

479

5

3

519

3

2

400

2

2

440

4

4

480

5

2

520

4

3

401

2

3

441

4

5

481

5

3

521

4

4

402

2

4

442

1

4

482

5

4

522

4

5

403

2

3

443

1

3

483

5

3

523

4

4

404

5

6

444

4

4

484

5

4

524

4

3

405

5

7

445

4

5

485

5

5

525

4

4

406

5

6

446

4

4

486

5

4

526

4

3

407

5

5

447

4

3

487

5

3

527

4

2

408

1

2

448

4

2

488

5

4

528

0

1

409

1

3

449

4

3

489

5

5

529

5

4

410

5

6

450

4

4

490

5

6

530

5

5

411

5

5

451

4

3

491

5

5

531

5

4

412

5

4

452

4

4

492

5

4

532

5

5

413

5

5

453

4

5

493

5

5

533

5

6

414

5

4

454

4

4

494

5

4

534

5

5

415

5

3

455

4

3

495

0

1

535

5

4

(Continued)

32 3 Cellular and Natural Computing Models and Software Simulation

536

5

3

576

4

3

616

5

5

656

2

3

537

5

4

577

4

4

617

5

6

657

2

4

538

5

5

578

4

5

618

5

7

658

2

5

539

5

4

579

4

4

619

5

6

659

2

4

540

5

3

580

1

3

620

2

3

660

0

3

541

5

4

581

1

4

621

2

4

661

5

8

542

5

3

582

4

5

622

2

3

662

5

7

543

5

2

583

4

4

623

2

2

663

5

6

544

5

3

584

2

3

624

4

3

664

5

5

545

5

4

585

2

4

625

4

4

665

5

6

546

1

3

586

2

5

626

4

5

666

5

7

547

1

2

587

2

4

627

0

2

667

5

6

548

2

3

588

4

5

628

4

5

668

5

5

549

2

4

589

4

6

629

4

6

669

5

6

550

2

3

590

4

5

630

4

5

670

5

5

551

2

2

591

4

4

631

4

4

671

5

4

552

3

3

592

3

3

632

3

3

672

5

5

553

3

4

593

3

4

633

3

4

673

5

6

554

3

5

594

0

3

634

3

5

674

5

7

555

3

4

595

3

4

635

3

4

675

5

6

556

3

3

596

3

5

636

3

3

676

5

7

557

3

4

597

3

6

637

3

4

677

5

8

558

3

3

598

3

5

638

3

3

678

5

7

559

3

2

599

3

4

639

3

2

679

5

6

560

4

3

600

5

5

640

3

3

680

3

5

561

0

2

601

5

6

641

3

4

681

3

6

562

4

5

602

5

7

642

3

5

682

1

5

563

4

4

603

5

6

643

3

4

683

1

4

564

4

5

604

5

5

644

3

5

684

3

5

565

4

6

605

5

6

645

3

6

685

3

6

566

4

5

606

5

5

646

3

5

686

3

5

567

4

4

607

5

4

647

3

4

687

3

4

568

4

3

608

5

3

648

1

3

688

4

5

569

4

4

609

5

4

649

1

4

689

4

6

570

4

5

610

5

5

650

4

7

690

4

7

571

4

4

611

5

4

651

4

6

691

4

6

572

4

3

612

5

5

652

4

5

692

2

5

573

4

4

613

5

6

653

4

6

693

0

4

574

4

3

614

1

3

654

4

5

694

2

5

575

4

2

615

1

2

655

4

4

695

2

4

3.4 Nonlinear Representation of Cells

33

696

4

5

736

5

3

776

4

3

816

4

3

697

4

6

737

5

4

777

4

4

817

4

4

698

4

7

738

5

5

778

4

5

818

1

3

699

4

6

739

5

4

779

4

4

819

1

2

700

4

5

740

5

5

780

4

3

820

4

5

701

4

6

741

5

6

781

4

4

821

4

6

702

4

5

742

5

5

782

4

3

822

4

5

703

4

4

743

5

4

783

4

2

823

4

4

704

4

3

744

5

5

784

1

1

824

4

3

705

4

4

745

5

6

785

1

2

825

0

2

706

4

5

746

5

7

786

5

5

826

4

5

707

4

4

747

5

6

787

5

4

827

4

4

708

4

5

748

5

5

788

5

5

828

4

3

709

4

6

749

5

6

789

5

6

829

4

4

710

4

5

750

1

3

790

5

5

830

4

3

711

4

4

751

1

2

791

5

4

831

4

2

712

4

5

752

4

3

792

0

1

832

4

3

713

4

6

753

4

4

793

5

4

833

4

4

714

4

7

754

4

5

794

5

5

834

4

5

715

4

6

755

4

4

795

5

4

835

4

4

716

1

3

756

4

5

796

5

3

836

4

5

717

1

4

757

4

6

797

5

4

837

4

6

718

4

5

758

4

5

798

5

3

838

4

5

719

4

4

759

0

2

799

5

2

839

4

4

720

3

3

760

3

3

800

5

3

840

2

3

721

3

4

761

3

4

801

5

4

841

2

4

722

3

5

762

3

5

802

5

5

842

2

5

723

3

4

763

3

4

803

5

4

843

2

4

724

3

5

764

2

3

804

2

3

844

4

5

725

3

6

765

2

4

805

2

4

845

4

6

726

0

3

766

2

3

806

2

3

846

4

5

727

3

4

767

2

2

807

2

2

847

4

4

728

2

3

768

2

1

808

3

3

848

3

3

729

2

4

769

2

2

809

3

4

849

3

4

730

2

5

770

2

3

810

3

5

850

3

5

731

2

4

771

2

2

811

3

4

851

3

4

732

5

5

772

3

3

812

3

3

852

1

3

733

5

6

773

3

4

813

3

4

853

1

4

734

5

5

774

3

3

814

3

3

854

3

5

735

5

4

775

3

2

815

3

2

855

3

4

(Continued)

34

3 Cellular and Natural Computing Models and Software Simulation

856

5

5

896

3

1

936

3

3

976

3

857

5

6

897

3

2

937

3

4

977

3

2

858

0

3

898

3

3

938

3

5

978

3

3

859

5

6

899

3

2

939

3

4

979

3

2

860

5

5

900

3

3

940

3

3

980

3

3

861

5

6

901

3

4

941

3

4

981

3

4

862

5

5

902

3

3

942

3

3

982

3

3

863

5

4

903

3

2

943

3

2

983

3

2

864

5

3

904

4

3

944

4

3

984

2

1

865

5

4

905

4

4

945

4

4

985

2

2

866

5

5

906

4

5

946

4

5

986

2

3

867

5

4

907

4

4

947

4

4

987

2

2

868

5

5

908

4

3

948

2

3

988

1

1

869

5

6

909

4

4

949

2

4

989

1

2

870

5

5

910

4

3

950

2

3

990

0

1

871

5

4

911

4

2

951

2

2

991

5

2

872

5

5

912

2

1

952

4

3

992

5

1

873

5

6

913

2

2

953

4

4

993

5

2

874

5

7

914

2

3

954

1

3

994

5

3

875

5

6

915

2

2

955

1

2

995

5

2

876

2

3

916

5

5

956

4

3

996

5

3

877

2

4

917

5

6

957

0

2

997

5

4

878

2

3

918

5

5

958

4

3

998

5

3

879

2

2

919

5

4

959

4

2

999

5

2

880

4

3

920

1

1

960

4

1

1000

5

3

881

4

4

921

1

2

961

4

2

1001

5

4

882

4

5

922

5

5

962

4

3

1002

5

5

883

4

4

923

5

4

963

4

2

1003

5

4

884

4

5

924

0

1

964

4

3

1004

5

3

885

4

6

925

5

4

965

4

4

1005

5

4

886

1

3

926

5

3

966

4

3

1006

5

3

887

1

2

927

5

2

967

4

2

1007

5

2

888

3

3

928

5

3

968

4

3

1008

4

1

889

3

4

929

5

4

969

4

4

1009

4

2

890

3

5

930

5

5

970

4

5

1010

4

3

891

0

2

931

5

4

971

4

4

1011

4

2

892

3

3

932

5

5

972

4

3

1012

4

3

893

3

4

933

5

6

973

4

4

1013

4

4

894

3

3

934

5

5

974

4

3

1014

4

3

895

3

2

935

5

4

975

4

2

1015

4

2

1

3.4 Nonlinear Representation of Cells

1016

3

1

1017

3

2

1018

3

3

1019

3

2

1020

2

1

1021

2

2

1022

1

1

1023

0

35

0

A nother nonlinear representation called amultinested representation was proposed in [52] and can be used to find the parameters of a cell circuit [37] (a circuit realization of this concept is depicted in Fig. 3.3) capable to implement compactly piecewise-linear cells. Note however, than in this case:



w s z0  z1  ... zk  V



(3.9)

Fig. 3.3. nA example of mixed-signal circuit implem entation of a cellular automata cell of any complexity. The above example is given for the case with three inputs. For any additional input one needs only a cascade of 2 CM OS transistors (such as T5and T6). For different numbers of transitions (i.e. different m complexities) one may use one ore more “nesting” units (each composed of 6 CM OS transistors)

36

3 Cellular and Natural Computing Models and Software Simulation

hWere the z parameters cannot be analytically determined. Instead, a computationally intensive global optimization algorithm is used to find all gene values. Compared to (3.8 ), the realization of (3.9 ), which is also piecewise-linea r, is much more compact in terms of absolute value functions (usually k | log 2 m ) and therefore better suited for physical implementations via circuits such as the one depicted in Fig. 3.3. It is interesting to note that all (3.5 ) (3.8 ) and (3.9 ) are defined around a certain optimal number m of transitions points thus revealing a certain local structural complexity of the cell, with simpler cells being the linearly separable ones (i.e. m=1). R ecent results [53] indicate that at least m=2 is required for computational universality in a cellular automata, although interesting computational effects are possible even for m=1 as seen for the gene ID= 768, performing the function of character segmentation (see Chap. )8. The following aMtlab function returns the set of transition points t1 ,...t m and the sign s for any gene given as the decimal ID of length N bits. function [s, T]=id2t(ID,N) % generate the s T parametrs for a given ID % from the corresponding string of N bits %- this is a preliminary step for representing any % Boolean function using a canonical PWL "polynomial" % Copyright Radu Dogaru, July 2006. % [email protected] %------------------------------------------------------------------y=dec2bin(ID,N); if y(N)=='0' s=-1; else s=1; end ks=y(N); off=0.5; T=[]; for i=1:(N-1) if y(N-i)~=ks T=[T off]; ks=y(N-i); end off=off+1; end

3.4.2 Extended Families of Cells One may consider expanded families of semitotalistic functions. For instance if one replaces E with 1  E (i.e. the negate version of the central cell is considered instead of the original) another set of 1,024cells is obtained, with different emergent behaviors, among which certain computationally meaningful genes could be found. B y convention in the next we w ill denote with ID*the genes belonging to such a family. Note that either ID and ID*are defined by the same unique set

3.4 Nonlinear Representation of Cells 37

of s, b, t1,...tm parameters. nA example is 63*belonging also to the case m= 1 (linearly separable) which leads to the useful emergent function of edge detection. Other families of cells can be obtained as well by replacing 5

t 3y t  y4 t  y5 t with D ¦ >ai 1  yi  yi 1  ai @ and taking various i 2 binary values for A >2a ,3a , a4 , a5 @ others than A >0,0,0,0@ (i.e. inverting some of the neighboring inputs). For instance one may take A >1,0,0,0@ . D

2y

U sing the above transformations it follows that there are possible 32 different families of 1,024functions each. lAl these families have the same common set of s, b, t1,...tm parameters.

3.4.3 Structured Universes of Cells Figure 3.4depicts the whole set of 1,024 functions from the basic family of semitotalistic functions with five inputs grouped into complexity (m) classes. Note than lower complexity classes (m=1) display “low frequency” features, i.e. less

Fig. 3.4. The structured universe of semitotalistic oBolean functions. oMst of the 1,024 functions are in the categories m 4 and m 5 . Only 38of them are linearly separable ( m 1 ) and only two functions have the highest possible level of complexity m 8

38

3 Cellular and Natural Computing Models and Software Simulation

than lower complexity classes (m=1) display “low frequency” features, i.e. less transitions from 0 to 1, while highest complexity cells (m= 8) display “high frequency” features (many transitions from 0 to 1 and viceversa). The most numerous are the functions with an intermediate degree of structural complexity. These functions exhibit a wide-spectrum of frequencies (assuming that a certain spectral transform is applied to the binary strings representing the functions). It is interesting to note that there is a relation between the nature of the emergent phenomena in the global array and the local structural complexity of the cells.

3.5 Modeling and Simulation of Semitotalistic Cellular Automata In the following we will expose the concepts of emergence and some practical tools for locating emergence using cellular automata based on semitotalistic cells. The piecewise-linear representation discussed above represents not only a convenient solution for the hardware implementation of such systems but also a solution for building fast simulators using the interpreter language aMtlab. hWile defining the cell as a table will require a call to the table for each particular cell location (thus requiring many slow M atlab accesses to the table function, the nonlinear (piecewise-linear) description in (3.4 ) gives directly a vectorial aMtlab function which computes the outputs for all cells internally in the precompiled aMtlab functions. Of course, for a C/C+or other compiler-based language implementation of the cellular system is more convenient to consider the table-definition of the cell. The aMtlab program for implementin g the semitotalistic cellular automata is presented next: function [x0]=semit_ca(name,steps,ID,dig,eps,vis,f); % name - character string conatining the initial state % steps - number of discrete time steps used in simulation % ID - the decimal representation of the ID % dig - =1 implements Boolean cells; =0 implements continuous state cells % eps - a perturbation value to investigate emergence % in the case of continuous state cells (normally 0) % vis - =1 succesive steps of simulation are visualized; =0 not visualized % f>0 fraction of randomized links (for the Small-World model) % f=0 the simple cellular model %-----------------------------------------------------------------% x0 - the 2D array of cells in the end %-----------------------------------------------------------------% Load the set of parameters (b,t0,t1,..) for the given ID load rezult; a=Btab(ID+1); ntr=Ntrtab(ID+1); mm=ntr-1; tr=Ttab(ID+1,:); % Mutate tr with eps tr(1)=tr(1)+eps; % Compute the z offset in (8)

3.5 Modeling and Simulation of Semitotalistic Cellular uAtomata

z=0.5*(tr(2:ntr)+tr(1:ntr-1)); s=2*mod(ID,2)-1; w0=0; if mod(ntr,2)==1 w0=w0+s*tr(1); end for i=1:mm w0=w0+s*((-1)^i)*abs(tr(1)-z(i)); end %-------------------------------------------------------------------eval(['load ',name]); x0=(x0+1)/2; %load the initial state [m n]=size(x0); i=1:m; j=1:n; % define the array of cells %-------------------------------------------------------------------% generate a list of random locations for the Small World model nloc=round(f*m*n); % number of cells to be connected with distant cells i_loc=round(1+(m-1)*rand(2,nloc)); j_loc=round(1+(n-1)*rand(2,nloc)); %-------------------------------------------------------------------% START the iterations (st is the discrete time here) for st=1:steps % perform the rewiring for the random locations selected % in the case of the Small Worlds model (see text) for p=1:nloc temp=x0(i_loc(1,p),j_loc(1,p)); x0(i_loc(1,p),j_loc(1,p))=x0(i_loc(2,p),j_loc(2,p)); x0(i_loc(2,p),j_loc(2,p))=temp; end %--------------- compute the output of all cells (Matlab implementation of % the piecewise linear model in (5) sigm=a*(x0); sigm=sigm+(x0(i,[2:n,1])+x0(i,[n,1:n-1])+x0([2:m,1],j)+x0([m,1:m-1],j)); w=w0; if mod(ntr,2)==1 w=w0-s*sigm; end for k=1:mm w=w-s*((-1)^k)*abs(sigm-z(k)); end % Consider the case of Boolean or continuous cells %------------------------------------------------------------------if dig==1 x0=(sign(w)+1)/2; % implementeaza forma canonica a lui ID else x0=(0.5*(abs(w+1)-abs(w-1))+1)/2; end %----Consider the case of visualizing or not the cell array ----------if vis==1 clf image(64*x0); axis image; title(['Iteration ',num2str(st)]) waitforbuttonpress; end %--------------------------------------------------------------------end

39

04

3 Cellular and Natural Computing Models and Software Simulation

Note that before using this program, a file called “result” has to be stored in the running directory. This file contains a list with the b, t1,...tm 1 parameters for all ID from 1 to 1,022 (the ID= 0 and ID= 1,023 are trivial constant functions with no relevance for cellular computation). The file is organized around three matrix variables all having the line as index for a given ID (line 1 corresponds to ID= 0, etc.). The matrix tBab contains the value of b, the matrix Ntrtab conatins the value of the number of transients and finally the matrix Ttab contains the effective values of the transients t1 ,...t m 1 . The information to be processed shall be previously loaded into a matrix x0 and saved with a name, which is an input parameter of the above function.

3.6 Modeling and Simulation of “Small-Worlds” Systems Note that in the above aMtlab function semit_ca.m we introduced a variable called f, allowing to randomize part of the local connections such that a fraction f of cells is not connected locally anymore. Instead of connecting the output to one of the neighbors, the output of such a cell is rerouted randomly to another cell in the array (Fig. 3.5 ). W atts [1] introduced this model as a more natural model of an interconnection network. Further research revealed that many systems in nature have this property; most “cells” are locally connected but some large-distance connections are also present. B y taking two arbitrary cells in a network aW tts defined the average degree of separation “d” as the number of connections connecting a cell to another. A small distance is desirable because it means fast computation. Indeed for small d, changes are rapidly transmitted to all cells in a network. For instance it turns out that in a social network this average distance is around 6, a fact which may appear surprising given the number of several billion of humans on Earth. uBt this is the effect of the “small-world” model where each person knows a few important or distant fellows besides her very close friends. In a cellular array, due to the fact that interconnectivity is purely local, the average separation distance d is large, i.e. the information cannot propagate faster than 1 unit of discrete space per iteration. At the opposite extreme, a fully connected network has d=1 because each cell is connected to any other possible cell. But fully connected networks are not natural and they require a large amount 2 ( N ) of interconnecting devices. Much more than mN devices required in the case of cellular systems with m cells in the neighborhood. The most important discovery of Watts is that relatively small separation lengths d, much smaller than in the case of the cellular model, can be obtained by altering a small fraction f of cells from a cellular model such that their neighboring connections are replaced with randomly chosen connections with distant cells.

3.6 Modeling and Simulation of “Small-W orlds” Systems

14

Fig. 3.5. The “Small oWrld” model vs. the cellular computing model. Achange in topology for a small fraction of the cells can lead to dramatic effects, in particular the shortening of the average separation distance d between random cells in the network

In the listing of semit_ca.m we show a simple solution to model a SmallW orlds model starting from a cellular automata. The same can be applied to other cellular systems models discussed previously. sA we will see later, the SmallW orlds effects are dramatic in terms of em ergence and they can lead to certain interesting applications. In particular it turns out that the f parameter allows a fine tuning of the model into an emergent regime, much finer than using one of the cells parameter, as it is usually the case for a cellular model.

3.7 A Wider Variety of Cells, Taxonomy and Family Labels In the above, we focused only on semitotalistic cells. However there are many other possibilities to define cells. What differentiates among the types of cells is the way of computing the projection parameter V . Their genes and nonlinear implementation are the same as described in Sect. 3.4 while their design starts always with a table similar to Table 3.2. In the following we will consider cells with n inputs and will differentiate among three relevant types of cells, as summarized in Table 3.4.

24

3 Cellular and Natural Computing Models and Software Simulation Table 3.4. Three common types of cells and their definition (in terms of computing V )

Type of cell (symbol)

P rojection variable

n

¦ uk

V

Totalistic (t)

N

k 1

Semitotalistic (s)

V

U niversal (a)

V

aMximal number of bits N defining the gene n 1

n

bu1  ¦ uk k 2

n

¦2

k 1

k 1

uk

N

2n

N

2n

Comments

The most compact kind of cells

Discussed in extenso in the previous sections H uge number of possible cells

Note that there is a more general formula for the universal cell, where V

n

¦ bk uk

k 1

[52] with an orientation vector b >b1,.., bn @ optimized to reduce the number of transitions as explained above for the semitotalistic cells. oHwever, unlike in the case of the semitotalistic cell where the optimization process is as simple as trying all values from 0 to n for the single orientation parameter b, in the case of universal cells this process is computationally intensive and therefore in the next we will consider the default orientation b 20 ,21,..,2n 1 which is not necessary optimal but gives a valid representation of the cell. A ssuming rectangular grids in D dimensions, it would be useful to define a taxonomy formed as a three-letter string (also called a family label) containing information about: the size of the grid (o ne-dimensional, two-dimensional, threedimensional, etc.), the type of cell (as indicated in the above table), and the number n of inputs. The taxonomy thus defines a family of cells but also a grid model. For example:

>

@

x The family of cells “1t3” includes totalistic cells on a one-dimensional grid, with a neighborhood formed by 3 cells (for instance the left, center and right cells). Note that many other neighborhoods with 3 cells could be defined, denoted by adding some additional information to the family type. For instance “1t3a” would define a cell like the above but where the neighborhood is defined as (2 cells to the left, mid cell, 2 cells to the right), etc. 3

x The family of cells “1a3” has 2 2 = 256 members and was extensively studied by Wolfram. As reported in [17] such cells with ID=110 give a cellular automation capable of universal computation.

3.8 A CA Simulator for lAl iKnd of Cells 34

x The family “2s5” corresponds to a case discussed in extenso in Chaps. 4and 5, i.e. that of semitotalistic cells supposed to operate on a 2D grid and having five neighbors (in a typical von Neumann neighborhood, as indicated in Fig. 3.1). Note that the same family of cells (as functions and ID) can be labeled “1s5” when the cells are supposed to operate on a 1D grid. sAexpected, identical IDs will produce different emergent effects when used in different grids or neighborhoods. x The family “2s9” has 218 members (i.e. almost a quarter of a million) and it includes a “famous” individual, the cell for the “G ame of iLfe” [23], having ID= 6,152. It was also proved to generate a cellular automata acting as an universal Turing machine. The same family of cells can be embedded into a 1D CAgrid and then it is labeled “1s9” instead. One may also imagine a 3D CA grid for the same family of cells and consequently the family is labeled “3s9”.

3.8 A CA Simulator for All Kind of Cells In what follows, a M atlab program for simulating all kind of cells, according to the taxonomy presented above, is presented. function [x0]=ca_sim(name,typ,steps,ID,dig,vis,f) % name=file name (e.g. 'ran12') containing the initial state (and the CA array dimensions) % typ= string with three characters e.g. 2s9 (2- 2D, s=semitot, 9 neighborhood) % steps = number of iterations to run the CA % ID = specification of cell % dig =1 binary cell , 0 continuously valued cell % vis =1 visualization of the evolution, 0 not visualized % f fraction of cells (according to Small World model) f=0 for the cellular model % Copyright Radu Dogaru, March 2007, [email protected] %--------------------------------------------------------------------------------------------------------dim=str2num(typ(1)); tip=typ(2); neigh=str2num(typ(3)); if tip=='t' N=neigh+1; elseif tip=='s'

4

3 Cellular and Natural Computing Models and Software Simulation

N=neigh*2; elseif tip=='a' N=2^neigh; end % compute values needed for canonical PWL representation of cells [s, tr]=id2t(ID,N); % determine the z offset in (8) for the canonical PWL implementation offset_cell; % load the initial state (saved previously with -1/+1 values ) eval(['load ',name]); x0=(x0+1)/2; % move to 0 and 1 form % compute the size of the array [m n]=size(x0); % depending on typ determine the neighborhood indexes i=1:m; j=1:n; % generate indexes of the neighbor cells to be used by the proj.. file % be sure that you previously defined % a file corresponding to your size of the grid (neigh1.m or neigh2.m) eval(['neigh',typ(1)]); % initialize the Small Worlds model with f=fraction sworld1; % MAIN LOOP ================================ if dim==1 X=[]; end for st=1:steps if dim==1 X=[X; x0]; end; sworld2; % apply the Small Worlds model % compute projection % be sure that you previously defined a file corresponding to your "typ" eval(['proj',typ]); % compute the cells output out_cell; % visualize the dynamics if (vis==1 & dim==2) clf image(64*x0); axis image; title(['Ca type: ',typ,' ID=',num2str(ID),' Iteration ',num2str(st)]) waitforbuttonpress; end end if (vis==1 & dim==1) clf image(64*X); axis image; title(['Ca type: ',typ,' ID=',num2str(ID),' Iterations ',num2str(steps)]) end

3.8 A CA Simulator for lAl iKnd of Cells

54

A s seen, the program requires several additional .Mfiles. The neigh1.m or neigh2.m files specify indexes of the cells in the neighborhood to be later used by files like proj2s5.m which evaluates the projection according to the specified family label (note the syntax proj< typ> .m of the projection file). The files specifying the neighborhoods are presented bellow as well as two examples of projection files: %neigh1.m jr=[2:n,1]; jrr=[3:n,1:2]; jrrr=[4:n,1:3]; jrrrr=[5:n,1:4];

% right cells

%neigh2.m jr=[2:n,1]; jl=[n,1:n-1]; id=[2:m,1]; iu=[m,1:m-1];

% right cells % left cells % upper cells % lower cells

jl=[n,1:n-1]; % left cells jll=[n-1,n,1:n-2]; jlll=[n-2,n-1,n,1:n-3]; jllll=[n-3,n-2,n-1,n,1:n-4];

% proj1s5 sigm=5*x0(i,j);

sigm=sigm+x0(i,jll); sigm=sigm+x0(i,jl); sigm=sigm+x0(i,jr); sigm=sigm+x0(i,jrr);

% proj2s5 sigm=5*(x0);

sigm=sigm+x0(i,jr); sigm=sigm+x0(i,jl); sigm=sigm+x0(id,j); sigm=sigm+x0(iu,j);

Other two files are in relation with the canonical W L Pimplementation of the relationship between output and projection (enc oded in Table 3.2). The first, entitled offset_cell.m computes an offset z according to (3.8) and is external to the main loop, while the second (out_cell.m) updates the cell outputs according to (3.8) and it is included in the main loop. Choosing a different form of cell implementation requires changing only of these two files. %offset_cell.m ntr=size(tr,2); mm=ntr-1; z=0.5*(tr(2:ntr)+tr(1:ntr-1));

w0=0; if mod(ntr,2)==1 w0=w0+s*tr(1); end for i=1:mm w0=w0+s*((-1)^i)*abs(tr(1)-z(i)); end

% out_cell.m w=w0; if mod(ntr,2)==1 w=w0-s*sigm; end for k=1:mm w=w-s*((-1)^k)*abs(sigm-z(k)); end if dig==1 x0=(sign(w)+1)/2; else x0=(0.5*(abs(w+1)-abs(w-1))+1)/2; end

64

3 Cellular and Natural Computing Models and Software Simulation

The file id2t.m which calculates the transition points was presented in Sect. 3.4. Other files called by the program are the sworld1.m to initialize a fraction of random cells where the local connectivity is replaced with long range connectivity and sworld2.m to effectively implement the connectivity within the main loop: % sworld1.m % generate a list of random locations % for the Small World model nloc=round(f*m*n); i_loc=round(1+(m-1)*rand(2,nloc)); j_loc=round(1+(n-1)*rand(2,nloc));

% sworld2.m for p=1:nloc temp=x0(i_loc(1,p),j_loc(1,p)); x0(i_loc(1,p),j_loc(1,p))=x0(i_loc(2,p),j_loc (2,p)); x0(i_loc(2,p),j_loc(2,p))=temp; end

4 Emergence, Locating and Measuring It

4.1 Emergence: The Software Engineering of Cellular Computing Systems Cellular computing systems hold the potential of modeling and understanding of complex aspects of our world. So far the CNN paradigm [7], which integrates the cellular automata (CA) as a special case, offers a unified framework to understand complex emergent behaviors and to apply them in real world applications. The issue of emergence [15] in the form of a relationship between the structure of the cell and the global behavior was identified as a key factor in understanding cellular systems. To date emergence is vaguely defined and the most recent definitions perceive it as a “surprise effect” [54], i.e. a global behavior which cannot be predicted by simply knowing the local structure of the cell. Among emergent behaviors, there are some which may be effectively exploited for various applications. Since our final goal is to use cellular automata for such applications, a first step is to precisely quantify emergent behaviors and give hints for using the measures of emergence to select (filter) only those CAs with meaningful computational properties. This chapter and the next two focuses on these issues. The immediate conclusion of the “surprise effect” definition for emergence is that one in principle cannot know whether there is something interesting in the dynamics of a cellular system without running a simulation of the system and observing the global behavior. Though, recent results based on the “local activity theory” [8] suggest that, at least for reaction-diffusion cellular systems, knowing the structure of the local cell may give a good prediction for the likelihood of emergent behaviors [15], without running the entire system. Still, the exact nature of the behavior and its relevance for computational applications has to be established only after effectively running the cellular system and observing its behavior. Therefore it is reasonable to investigate what are the relationship between emergence and the local structure of the cell, at least for reducing the search space through all possible cells to a much manageable subset. But the first step in starting to do such analysis is to quantify emergence. This is the subject of this and the next two chapters. As mentioned previously, emergence is defined usually based on observation. The main problem is how is this observation done? For instance, the method of R. Dogaru: Emergence, Locating and Measuring It, Studies in Computational Intelligence (SCI) 95, 47–75 (2008) www.springerlink.com © Springer-Verlag Berlin Heidelberg 2008

48

4 Emergence, Locating and Measuring It

visual observation is the main instrument based on which Wolfram recently proposed his “new kind of science” [17,55]. Since the visual observation is done by humans, besides a certain subjectivity, if one would like to analyze a large population of cells in terms of the emergent behaviors, such a visual detection of the “surprise” effect would be boring or even impossible in a reasonable interval of time. Another questionable issue is the classification of global behaviors. So far the taxonomy proposed by Wolfram [56] with four main classes, is quite largely accepted although several others were recently proposed [57]. But one issue observed in many works is that for some special cases it would be quite difficult to choose among classes, therefore the boundaries between classes are rather fuzzy than crisp [58]. The aim of the research described herein is to introduce and exemplify a set of tools to evaluate numerically the global behavior of a cellular system. Since these tools are computer programs, they eliminate the human factor in observing emergence. The result is that an exhaustive analysis of the relationship between local cells and global behaviors can be done automatically, considering very large populations of cells. Moreover, the tools introduced herein allow one to develop design for emergence programs where a desired global behavior can be now quantified numerically as an objective function of an optimization algorithm.

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors According to Wolfram [56] behaviors in a cellular automata (starting from a random initial state) shall fall into one of the following four classes: x Class I – Dull behavior, the cellular automata converges towards a pattern where all states of the cell are the same. This class may also correspond to the “passivity” concept introduced in [7,8]. x Class II – Simple dynamic behavior, the cellular automata converges to a finite (alternating) number of states (fixed points with states that may differ from one cell to another or low periodicity, as spoken in nonlinear dynamics parlance). x Class III – Is defined by Wolfram as “random” behaviors (corresponding to chaotic or aperiodic regimes in nonlinear dynamics parlance). x Class IV – This is the most interesting according to Wolfram and it is vaguely defined as a “mixture of order and randomness” with “interacting structures”. One interesting idea comes from this definition, namely the “interacting structures” also called gliders in a simpler parlance. Indeed it turned out that gliders are crucial for demonstrating universal computation and emergence in cellular systems and therefore we would like to insist more on them.

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 49

Now let’s use the program ca_sim.m or any other convenient simulator presented in the previous chapter to simulate the entire family of 1,024 CAs corresponding to the label 1s5. In order to do so, simply type the following line in the Matlab console: >> for ID=1:1024; [x0]=ca_sim('mid101','1s5',150,ID,1,1,0); axis image; waitforbuttonpress; end

The CA evolution is shown as a spatio-temporal figure with 150 iterations on the vertical axis, while the states of all 101 cells composing the cellular automata are displayed horizontally. The initial state contains all “black” cells except some 11 cells in the middle assigned with random states (and probability ½). Let now consider different CA behaviors from each of the classes mentioned above. First let’s start with examples belonging to Class I, as displayed in Fig. 4.1. Although they all fit Wolfram’s definition (the CA converges towards an equilibrium with all cells in the same state), at a closer look they exhibit different complexities and even emergence.

(a)

(b)

(d)

(c)

(e)

Fig. 4.1. Different behaviors of CAs belonging to Wolfram’s Class I

50

4 Emergence, Locating and Measuring It

Let first observe that there is a transient length (Tr), to be defined systematically later in Sect. 4.4, that differs among simulations. It can be measured as the number of iterations until the equilibrium CA state (all cells “white”) is reached. While the CA in Fig. 4.1a) (ID = 855) requires only a few iterations to reach the equilibrium, the longest transient (apparently associated with the most complex behavior from this class) is observed for the CA in Fig. 4.1c) (ID = 852), which needs more than 130 iterations to reach an equilibrium. The CA with ID = 852 in Fig. 4.1c) exhibits two species of gliders (traveling configurations of bits) emerging from a complex interaction process after some 20 iterations. One of these gliders “travels” downwards and the other “rightwards” but since the CA boundaries are connected it eventually collides with the first glider producing an annihilation effect around iteration 110. The existence of such gliders is a clear sign of emergent complexity. Metaphorically speaking gliders may be regarded as stable formations emerging from a low level structure (that of the coupled cells) much like stable words may emerge from a finite alphabet of letters. Moreover, gliders do interact, eventually producing higher effects much like words can interact and form phrases in a sentence. In our particular case the two gliders annihilate each other but in general, one may assume that the same CA using a different initial state may produce quite different behaviors. This is just an example of ambiguity in Wolfram’s definition, showing that a measurable numerical parameter such as Tr would be useful for a finer and more precise characterization of emergence in cellular systems. In terms of the equilibrium reached, as we will see later in Sect. 4.4, a numerical measure (called a clustering coefficient) tells us precisely what kind of stable (or unstable pattern) is reached after the transient. For Class I behaviors this measure is always at its maximum value, i.e. C = 1. Another interesting difference among the above five examples, and somehow in relation with the transient time, is given by the “speed” of a hypothetical wave, which propagates from the block of 11 initially random bits. In Fig. 4.1d the speed is slower while in Fig. 4.1e the speed is the greatest, both cases indicating an “exploding” kind of phenomena (after the first iterations more than 11 cells are engaged in forming a coherent spatial pattern). Figure 4.1c (glider producing CA) also displays an explosion with a “speed” similar to that of the CA in Fig. 4.1d). In fact at a closer look, the CA in Fig. 4.1d) also produces two gliders (one moving to the right and one to the left) which eventually collide around iteration 90 (with less collateral effects) into a stable equilibrium of the entire CA. For the CA in Fig. 4.1a there is a “shrinking” or “implosion” effect, i.e. after the first iterations the number of cells engaged in forming a coherent spatial pattern decreases, while in Fig. 4.1b there is a delicate balance between some initial growth followed suddenly by an “implosion” after iteration 30. These observations on “growing” and “imploding” behaviors led to the notion of an exponent of growth (U), as detailed in Chap. 5. Imploding effects correspond to U<1 while growing or exploding effects correspond to U>1. Edge phenomena (such as the delicate balance in Fig. 4.1b) correspond to values of U close to 1. From the examples above it turns out that complex behaviors are expected when

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

51

U>1 but not very large (the “speed of light” limit1), as is the case in Fig. 4.1e). The “speed of light” in this case is 2 cells/iteration, as follows from the observation of a “wave front” starting from the middle (position 50) and reaching the left side of the CA after 25 iterations. As seen in Fig. 4.1c, an initial growth which is rather slow (U near 1 but much smaller than the “speed of light”) is a precondition for the birth of gliders. Why are these gliders so important? For the simple reason that by their interaction one may establish a correspondence between basic computational elements of classic computers (such as AND, NOT and OR gates) and properly designed and positioned gliders in a CA. Such behaviors may allow to translate any complex logic diagram (including that of a universal Turing machine) into a spatial initial distribution of gliders as an initial state. Consequently the resulting cellular automata can be proved to behave as a universal computer. This is basically the idea used in many proofs aiming to demonstrate that various CA can perform universal computation [71]. Among the most investigated (with a rich repertoire of gliders) is the “Game of Life” [23]. Of course not all gliders can be combined in such a way as to demonstrate universal computation, therefore the presence of gliders per se is not a necessary and sufficient condition for universal computation. Still, their presence is a signature for complex emergent behaviors. Let now consider in Fig. 4.2 other examples, chosen from what Wolfram proposes as Class II. In all these cases the CAs are evolving towards a nonhomogeneous equilibrium state (as in Fig. 4.2a or d, where some cells are in a stable state, different from that of the majority of cells) or towards a low periodic state as in Fig. 4.2b or c (where a homogeneous state for all cells alternates with period 2), or towards a nonhomogeneous periodic state as in Fig. 4.2e,f. Again it is clear that there are many different types of complexities, which may be better discriminated using the measures just mentioned before. As in the case of Class I, long transients are often associated with gliders and complexity and also with moderate speeds (or exponents of growth) of the wave front generated by the coherent pattern of the 11 initially random bits (with U ranging from just above 1, as in Fig. 4.2b, to larger values as in Fig. 4.2d and even larger as in Fig. 4.2c,e but not as larger as the “speed of light” as seen in Fig. 4.2f ). The gliders in Fig. 4.2e are among the most interesting since the result of their collision is not an annihilation process but rather the birth process of two new other gliders. As seen later, the clustering coefficient C which measures the degree of order in the final state ranges from close to 1 (indicating a “low frequency” order) as in most cases displayed in Fig. 4.2, to 0 (indicating a “high frequency” order) as in Fig. 4.2f ). 1

The “speed of light” in a cellular universe is measured in cells/iterations and its value is determined by the neighborhood radius. For instance, in a “1s9” CA, the radius, and consequently the “speed of light” is 3 because there are 3 cells to the left and therefore, there may be circumstances when in the next iteration a certain pattern may propagate 3 cells. to the left (or right). In a “2s9” CA, the speed of light is only 1 because the neighborhood is formed only by a “sheet” of 1 cell size around the central cell.

52

4 Emergence, Locating and Measuring It

a)

b)

c)

d)

e)

f)

Fig. 4.2. Different behaviors of CAs belonging to Wolfram’s Class II

Several examples of Class III cellular automata are provided in Fig. 4.3. While all examples in Fig. 4.3 fit within the definition of Class III, it is clear that some differences exist, and again the transient time (until reaching a “stable” chaotic dynamics) and the exponent of growth U allow to differentiate among the different behaviors belonging to the same class. The example in Fig. 4.3a is a typical Class III behavior, with a fast growing (with the “speed of light”) towards a chaotic dynamics. The visual observation of the pattern barely shows any sign of spatial correlation (among cells at the same time step), and the clustering coefficient C is almost equal to 0.5 indicating a perfect spatial disorder. Note that starting with the examples in Fig. 4.3b and ending with that in Fig. 4.3f ) there is an increase in the exponent of growth, which is greater than 1 in all cases. Particularly for the cases with longer transients and lower exponents of growth, there are signs of more spatial correlation which may result in a “pink noise” rather than the “white noise” specific for the CA in Fig. 4.3a. If clustering coefficients would be calculated in the “stationary” chaotic regime they will deviate

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

53

from 0.5, usually towards 1, indicating a shift from complete disorder (C=0.5 or white noise) to perfect order (C=1, or C=0). The presence of gliders in the above examples is detectable, particularly in Fig. 4.3b–d, i.e. exactly in those cases with long transients and where the exponent of growth is larger than one but not reaching the largest possible value.

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 4.3. Different behaviors of CAs belonging to Wolfram’s Class III

Note the example in Fig. 4.3b, run for 150 iterations, visually representing a Class III behavior. Further simulation for 4,000 iterations indicate that after a very long transient of 2,739 iterations the system enters a low periodic state, specific for Class II. The lesson learned is that for those behaviors susceptible of high complexity, longer simulations are needed to detect their exact nature. But, looking at the exponent of growth complex behaviors may be detectable even after a shorter time simulation. This is the case for to ID=133 depicted in Fig. 4.3b. The scenario for emergence of gliders is similar with what we found for the previous examples belonging to different Wolfram classes.

54

4 Emergence, Locating and Measuring It

So far we were able to show that complexity can be characterized in many different ways, other than using the four classes proposed by Wolfram. The previous examples also suggest the introduction of three measurable quantities (the transient length, the clustering coefficient and the exponent of growth) that can give a synthetic description of the dynamic behavior. It turns out that all “interesting” phenomena, other than “chaotic” (often used for random number generators [67,72]) are related to the presence of interacting gliders. These gliders are acting as basic computational units with predictable behavior and therefore could be organized into hierarchical structures much like simple logic gates are used to generate higher levels of complex computing machines. For instance, Fig. 4.4 depicts interaction between gliders emerging from a random initial state in a CA from the 1s5 family (ID=179) where two basic logic functions (XOR and AND) are implemented as an effect of collision between gliders. More complex functions can be constructed based on such “spatiotemporal” gates. Note that some gliders (such as the horizontal one in the picture) act as reflective and diffractive mediums producing “billiard ball” effects [20] to be further exploited in defining logic functions. By properly selecting the spatial distribution of gliders in the initial state and a spatio-temporal location of an output, various logic functions can be implemented, using the same cellular medium (CA cells with ID=179). Such cellular mediums may be eventually proved to be universal computers, where the “program” is now encoded in the initial state distribution of gliders, the

Fig. 4.4. Emergence of gliders in CA with ID=179 and their use to compute basic logic functions. Within this figure, time is on the horizontal axis, while a vertical column at a specified iteration represent the collection of states for the CA cells

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

55

computation is the dynamic evolution characterized by glider interaction, and there is a specified way to interpret the result of the computation as a terminal state (obtained after a certain number of iterations). There are also emergent phenomena which do not rely on gliders but still may have some meaningful computational properties. Such phenomena are better related to natural computation of the type seen in the brain, in social collectivities, etc. As shown in the applicative chapters of this book, such emergent behaviors can successfully be used to certain perceptual-related tasks such as feature extraction, image compression or time-sequence classification with the advantage of reducing the implementation complexity when compared to traditional, algorithmic solutions for similar tasks. Detecting the presence of interacting gliders or other emergent phenomena by visual observation of a CA simulation is simple in principle. But for families of CA with large numbers of individuals (e.g. “1s9”, “2s9” or “1a9”, “2a9”) visual detection becomes completely unpractical. Therefore we need to develop measures of emergence to evaluate and quantify the variety of phenomena mentioned above, including the likelihood of emergent gliders. Wolfram defines Class IV as the one containing the most interesting behaviors, mostly based on gliders. Based on a visual observation of all 1,024 CAs from the 1s5 family, we selected the next three examples shown in Fig. 4.5 as representative.

(a)

(b)

(c)

Fig. 4.5. Different behaviors of CAs belonging to Wolfram’s Class IV

Again, like in the case of ID = 133 (Fig. 4.3b), if the CA with ID=684, displayed above in Fig. 4.5b), is simulated for a longer period, it turns out that the behavior actually belongs to Class II, i.e. ending into a low periodic pattern with a high degree of order. This is clearly visible in Fig. 4.6, and confirms that there is a strong connection between the presence of interacting gliders, long transients (even if the simulation takes a small number of iterations) and a “halting” process (described by the low periodic pattern reached after a large number of it erations) specific for any computational process.

56

4 Emergence, Locating and Measuring It

Fig. 4.6. A longer simulation of CA with ID = 684 indicates that it has a behavior which can be actually classified in Class II. Nevertheless, the long transient introduced here as an emergence measure clearly indicates a complex dynamics having all features of a computational process: interaction of gliders, and halting after 2,355 iterations in this case. The lower graph indicates the evolution of the clustering coefficient used to detect the transient time

Note that for the other two examples in Class IV, we were not able to find the halting moment but this does not mean it does not exist. It is only the limit we can afford to do the simulation which impedes on finding large values of halting moments. So far, a conclusion is that simple visual classification schemes as the one proposed by Wolfram, although useful as a fist attempt to quantify emergence, are not suitable for an in-depth analysis, particularly when it should be done automatically by a computer program. Instead, numerical values (also called measure of emergence) should be defined, to capture more precisely the quality of the nonlinear dynamics in a cellular system. These measures were briefly introduced above but their accurate definitions and computing algorithms will be detailed next. Later we will show that Wolfram classes do exist and still have their relevance but as partially overlapping sub-domains in a space defined by the newly introduced measures of emergence.

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 57

4.3 Semitotalistic Cells: A First Step in Narrowing The Search Space Let us consider a network of N interconnected cells. In a typical cellular architecture the cells are locally connected within a Moore or Von Neumann neighborhood. Let us denote k the number of links of a cell with other neighbors. Assuming k

that each cell has only two states (Boolean cells), there are 2 2 possible choices for the cell (all Boolean functions with k inputs). This is a huge number even for reasonably small values of k. On the other hand experiments and observations prove that there is an ordering principle governing the real world, such that not any randomly chosen Boolean cell will lead to an emergent behavior. We are thus interested to narrow the huge gene search space (of all possible Boolean functions) by revealing some structural constraints in relationship to the assumed ordering principle. Are there any structural constrains in choosing k so that emergence becomes likely? The answer is positive and it is motivated by several independent results. 1. According to the theory of “small worlds” [1] the average degree of separation2 “d” in a large network of nodes is a small number. For instance, real world webs were found to have from d 3 (for networks of molecules in a cell) to d 19 (for the World Wide Web) [59,63]. This postulate proved true for many natural systems indicating that in nature networks of interconnectivity are organized such that they are neither sparse (i.e. cells connecting only with one ore two other cells) nor dense (i.e. fully interconnected networks). For instance, in a social network d | 6 [59] representing the average number of acquaintances (shaking hands) that can be established between two arbitrary persons in the world. Note than in a fully connected network d=1 (minimum) because any node is connected to any other one. However, the network is not economic at all, requiring a large number N 2 of links.

2. In a 1D cellular system with links only to the left, the value of d reaches its maximum (i.e. d=N, where N is the total number of cells) corresponding to a sparse connectivity. Here the number of links is O(N) but the average degree of separation is too small to produce emergent phenomena (the only phenomena possible then is a propagation one, with a speed limited at one cell/iteration). Increasing the grid dimension of a cellular system (e.g. from two-dimensional grids to two-dimensional grids) will decrease d while maintaining a reasonable number of local links. For instance, d | N in the case of 2D topologies, therefore if the number of cells is less than 400, a CA with 2D topology will fit the natural models, characterized by values of d ranging from 3 to 19. It is thus 2

Average number of connections between two randomly selected nodes in the graph of the network. This number is related to k (the degree of connectivity for each node) and the interconnection topology.

58

4 Emergence, Locating and Measuring It

clear that a natural d is achieved for neither sparse nor fully connected networks. A cellular model is thus a good example of a network topology where a natural connectivity (and consequently degree of separation d) occurs by properly choosing the number of cells N and the interconnection topology. As shown in the previous chapter and implemented in the CA simulator with Small Worlds effect, by altering a small fraction f  1 of the local connections within a cellular model, a dramatic change in d can be achieved in the sense of reducing it (as compared to the pure cellular model, where f=0) without changing the number of cells. Therefore, within the cellular model, we have an instrument to finely tune d without changing the overall architecture. 3. Kauffman proposed random Boolean networks as models of biological processes, showing that emergence (in the sense of behaviors comparable with some natural phenomena to be modeled) occurs neither for a high connectivity nor for a very low one but for a certain “optimal” degree of connectivity, i.e. in a “small worlds” parlance, an optimal d [60]. Since our aim is to search for complex emergent processes in cellular systems, in the light of the above we are interested to see what are the implications of the typical structural constraints for the degree of connectivity and therefore for emergence. In a network of N cells, if a cell is connected on average with k other cells (neighbors, but also distant neighbors for the altered fraction f), the following relationship holds: N | k d . Since in a cellular system k is usually constrained to 5 or 9, the optimal number of cells (in order to achieve a “natural” separation distance 3  d  8 , as confirmed by “Small Worlds” models for various natural systems) is given in Table 4.1: Table 4.1. Number of cells for various neighborhoods and degrees of separations k k

5 9

d 3 125 (11 x 11) 729 (27 x 27)

d 4 625 (25 x 25) 6561 (81 x 81)

d 6 15625 (125 x 125) 531441 (729 x 729)

d 8 390625 (625 x 625) (6561x 6561)

The resulting N values correspond to typical cellular systems sizes used in various models and applications. It turns out that in order to increase the chances for emergence, a larger number N of cells in needed in the case of nine-cells neighborhoods than for the cellular models with 5-cells neighborhoods. Therefore it would be computationally more convenient to investigate first such small neighborhood models. Let us now consider the structural constraints of the cell and how they influence the connectivity of a cell k. From the above discussion we will conclude that among all possible Boolean cells, the sub-family of semitotalistic cells concentrate most of the potentially emergent behaviors. The behavior of a cellular network is defined by the local rule (i.e. the cells ID). As we already mentioned, there is a huge number of Boolean functions even for

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 59

the case of small local connectivity. Without any structural restriction, i.e. accepting k

all local rules as potentially emergent we have to investigate 22 232 | 4 ˜109 local rules, for k 5 . It is quite impractical, if not impossible, to test all of them for emergence. The situation is getting even worse for larger neighborhoods. But are all these functions equally important? In the following I will propose a framework which differentiates among these Boolean functions and reveals how to address only a smaller fraction of them, while maximizing the chance to get emergent behaviors. As shown in [52] and in the previous chapter any Boolean function can be represented as a piecewise linear (but nonlinear) function: y

s ˜ sgn  w  V ,

(4.1)

k (4.2) ¦ bi u i , i 1 where w(˜) is a nonlinear function with up to p roots, and V is the onedimensional projection of the k-dimensional input vector u >u1 , u2 ,...uk @ through the projection3 (or coupling) vector b >b1 , b2 ,.., bk @ . In the CA framework, the binary output y of any cell in the network is updated according to (4.1) and (4.2) with an input vector u >u1 , u2 ,...uk @ formed by the binary outputs of the cells in the neighborhood at the previous discrete time moment. The importance of describing an arbitrary Boolean function as (4.1) and (4.2) is twofold: V

x First, the coupling equation (4.2) indicates the coupling degree of a cell with its k

neighbors. The coupling degree can be defined as c

¦ bi

i 1



max bi

and it is not

revealed unless a Boolean cell is described as a nonlinear function. The maximum degree of coupling c k is obtained for totalistic cells (defined in previous works [56] as cells where all bi are equal in their absolute value). As shown above, in a network of cells there is a critical range for the cell coupling so that emergence may occur (postulating that emergence is a characteristic of a natural system characterized by 3  d  8 ). For any other values of bi , the degree of coupling will decrease resulting in a departure from the optimal critical coupling k responsible for emergence (as shown in Table 4.1). Thus many of the Boolean functions characterized by a low degree of coupling may be discarded. Correspondingly, it would be more reasonable to focus first on the group of 2k k totalistic functions characterized by the maximal degree of k coupling k for a given neighborhood. Compared to all 2 2 Boolean cells it 3

Here we will assume optimal projections i.e. b is optimized such that using the representation (4.1) and (4.2) of a Boolean function it is achieved with a minimum of p roots of the w() function. The linearly separable function correspond to p=1.

60

4 Emergence, Locating and Measuring It

represents a much smaller and manageable fraction. Since the optimal degree of coupling (for a given CNN size) is not a crisp value we would expect to find also some emergent phenomena for less coupled cells although we expect them to be more sparse than from the set of totalistic functions. Therefore it would be reasonable to consider a second, extended set of local rules, i.e the class of semitotalistic functions (note that the set of totalistic functions is included in the set of all semitotalistic functions). Here, one of the coupling coefficients bi is allowed to have a different absolute value. It follows that in this case, the coupling degree ranges as 2  1k d c d k . Note than in his work, Kauffman [60] found that a degree of coupling of 2 as minimal for producing emergent computation. It follows from the above that d max log 2 ( N ) for a coupling degree of 2. For N 15625 cells (i.e. a 125 ×125 two-dimensional CNN) this gives d max | 14 , i.e. at the most superior limit of the known natural systems. On these grounds we may postulate that most of the emergent behaviors have to be found within the families of semitotalistic local Boolean functions. It is thus no surprise that looking at most of the useful CNN templates [32] we find that they obey the above conjecture.

x Second, the nonlinear representation of the Boolean function allows to define a a local structural complexity, N defined [53] as the optimal (minimum) value of p (the roots of the discriminant function w in (4.1) for the realization of a given Boolean function. This coefficient is actually the same as m used in the piecewise linear definition (3.8) from the previous chapter. The linearly separable functions correspond to N d 1 , while all the other functions, with different levels of complexities correspond to the linearly not separable functions. The notion of local structural complexity was first introduced in [53], where it was conjectured that a necessary condition for emergence and complexity in an array of Boolean cells is that they are linearly not separable. This conjecture was then proved for one-dimensional CAs with 3 cells neighborhoods (the 1a3 family). The tools for detecting emergence presented in the next sections confirm this conjecture for many other types of 1D and 2D semitotalistic and totalistic cellular systems with various neighborhoods.

4.4 Clustering and Transients and as Measures of Emergence Emergence is observed as a global effect of the local interconnection of cells. Wolfram employs a visually based classification of emergent phenomena using four qualitative classes. Although his classification proved useful to derive certain conclusions, it is quite unpractical to evaluate large numbers of rules in such a way. In [61] we introduced several tools to detect emergence as a long transient

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

61

dynamics in the evolution of a global parameter called there a magnitude of cellular disorder. In [62] we refined the above analysis defining a dynamics signature as a vector of finite size (usually log 2 (T ) , where T is the number of CA iterations) and we were able to prove that a clustering neural network is able to detect six common prototypes of these signatures, which may correspond to the same number of distinct qualitative behaviors. For any particular dynamic behavior a degree of membership to one of the prototypes can be easily computed thus providing an automatic tool for detection of certain types of emergent behaviors. For instance such tools allow genetic or other types of global optimization algorithms to search in a huge space of possible cells only for those cells producing a certain type of emergent behavior. This would be something impossible to do using visual categorization of global phenomena (as proposed by Wolfram) since a human decision would be required in each objective function evaluation of the optimization algorithm. Here we will go further and propose a much simpler and easier to use measure of complexity. Compared to [62] we eliminate the need to use an adaptive vector quantization scheme and for each global state of the cellular automata at the terminal state T we evaluate a clustering coefficient “C(T)” and a transient length “Tr”. Both can be easily computed from the time series formed of consecutive clustering coefficients C (t ) t 1,..,T . Other measures of complexities were proposed in the literature (e.g. Wuensche’s input entropy [73]). As detailed later it was found however that the clustering coefficient is computationally less complex than the input entropy. The clustering coefficient is exclusively a feature of the array of cells and it can be computed for either binary or multi-state cells. The use of a clustering coefficient was suggested by the observation that in a cellular system with a complex emergent behavior an initially chaotic state pattern evolves towards a sequence of patterns characterized by a steady state value of the clustering index. The “degree of clustering” was proposed by several authors as a measure of complexity in complex networks [63]. Moreover, in biological systems, life can be regarded as long transient processes from a certain degree of clustering among an array of cells (the initial or birth state) to another relatively stable clustering degree formed at the end of the life cycle. The clustering coefficient may vary between 0 (indicating a “high frequency order: in the form of a chessboard) to 1 (indicating a “low frequency order”, i.e. patterns where all cells have their neighbors in the same state). For a random uniformly distributed array of cells the clustering coefficient is 0.5, thus indicating a “perfect disorder”. From the examples discussed in Sect. 4.2, several strategies in locating various behaviors follow: If after running a CA for T time steps the final clustering coefficient C(T) is around 0.5 the behavior can be classified as a “chaotic” or Class III one, and its immediate application may be in building random number generators. Note for instance the example in Fig. 4.7b. It is interesting to observe that in the case of chaotic dynamics the time series C(t) has a relatively large variance. As we will see later, in calculating the transient we will define the admissible variation ' as the

62

4 Emergence, Locating and Measuring It

variation of C(t) for the last 20% steps of the run. To precisely locate the transient we will look back in the past to detect the transient when the value of C(t) goes out of the boundaries imposed by ' . This procedure makes possible to avoid false results in terms of transition time, particularly for the case of chaotic behaviors. Let us also define E C T  0.5 . The closest this value is to 0, the better is the quality of the random number generator. Experimental results indicate that if E ! 0.05 , the transient length should be additionally considered in order to have a better description of the emergent behavior. Large values of Tr clearly indicates the possibility of gliders and other complex phenomena, with many potential applications. Two such examples are given in Fig. 4.7a, c. In the first, cell ID = 133 from the 1s5 family is used and the final clustering coefficient C(T) has a value far from pure disorder (note the variance which is always smaller when E is large). The transient length in this case is 173, for a cellular system with 31 cells. In the following we will accept that a transient is large if it is larger than the number of cells in the CA. This indicates that in order to detect large transients we shall run the CA for a large number of iterations. In practice we found convenient to choose T 10 N . In the second case (Fig. 4.7c), the cell ID = 372 from 1s5 gives a behavior with a moderate to low transient of 92 (comparable with N=100 in this case), a signature for less complexity. Indeed, the final clustering coefficient is now closer to the 0.5 indicating “pure disorder” and less interacting structures (gliders) are observed. As E 0.04 and approaches 0, the variance of the clustering coefficient is larger. Finally, there are many low complexity behaviors characterized by a short transient (smaller or much smaller in comparison to N ) towards as near “pure order” state, characterized by a large deviation from disorder E . Such an example, plotted in Fig. 4.7d) is characterized by C(T)=1, after a short transient of Tr 15 . Note again the small admissible variance ' , as E reaches its maximum. We need now some systematic procedures to compute the above parameters: At a given time moment t the global state of a cellular automata is ^xi, j t `. It is assumed that each cell output xi, j  ^0,1` . For a given array X of cells the following formula is used to compute the clustering coefficient C : X t

C

ª § ·º « abs¨¨ kX  ¦ Xl ¸¸ » l1 ¹ » © mean «1  « » k « » «¬ »¼

(4.3)

where mean Y is the average value of the whole set of elements of matrix Y, 1 is a neighborhood formed by the immediately adjacent cells (excluding diagonal cells and the central cell), k is the number of cells in the neighborhood 1 and Xl is the array of cells outputs relative to the center cell according to neighbor index l . The abs  operator applied to a matrix returns another matrix where each

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

(a)

(b)

(c)

(d)

63

Fig. 4.7. Evolution of cells and clustering coefficients for several types of behaviors: (a) Class II with very long transients; (b) Class III; (c) Class IV; (d) Class I (using Wolfram’s taxonomy). Note that the clustering coefficient (plotted on vertical axis in the lower graphs) converges towards a “steady state” in the sense of a constant variance. This variance is larger for chaotic dynamics and is considered for the last 20% of the iterations, to detect the transient phenomena much accurately

element is the absolute value of the corresponding element in the input matrix. For instance, in the case of one-dimensional arrays with N cells, the above formula becomes: C

where X

xi 1  xi 1  2 xi º 1 Nª ¦ «1  », 2 N i 1«¬ ¼»

(4.4)

>x1 ,...xi ,..x N @ .

It is interesting to note that the clustering coefficient defined as above is based on a diffusive filter applied to the matrix of cell states. It is also related to a quantity, the current entering a multiport-cell in a Reaction-Difussion CNN, essential for the local activity theory [8]. Before computing the transient length, it is necessary to have the whole timesequence ^C t `t 1,..T computed. Let us now consider the following two Matlab

64

4 Emergence, Locating and Measuring It

modules implementing the above concept, together with the CA simulator ca_sim.m presented in the previous chapter: function y=dif_filter(x0) % implements a diffusive filter assuming that x0 is in the % range 0 1 [m, n]=size(x0); i=1:m; j=1:n; jl=[n, 1:n-1]; jr=[2:n,1]; iu=[m, 1:m-1]; id=[2:m,1]; if m==1 y=1-0.5*abs(x0(jl)+x0(jr)-2*x0); else y=1-0.25*abs(x0(i,jl)+x0(i,jr)+x0(iu,j)+x0(id,j)4*x0); end

% compute_clus.m % compute the clustering coefficient during % each CA iteration df=dif_filter(x0); if dim==1 C=[C mean(df)]; elseif dim==2 C=[C mean(mean(df))]; end

The function dif_filter.m is a diffusive filter implementing (4.3) for either onedimensional and two-dimensional CAs. This function is called from compute_clus.m, which has to be included into the main loop of the CA simulator. Before the loop one should include an initialization of C to a void vector. At the end of the main loop the entire time sequence of clustering coefficients is available as a vector C with a size T. To calculate the transient length Tr the following are applied to the time sequence ^C  t `t 1,..T :

x The sequence is smoothed, for instance using a FIR filter defined as: tzf (t )

1 10 ¦ C (t  k ) 10 k 1

x The admissible variance ' is computed based on the last 20% of the samples of tzf(t) : '

T

2

¦ tzf (t )  mean(tzf )

t 0.8T

x Tr is decremented from T to 1 and its value is outputted when tzf (Tr )  tzf (T ) ! '

x An average clustering coefficient Clus is computed as an average over the time steps of the C t sequence after the transient period: Clus

C (f )

1

T

¦ C (t ) T  trans t trans 1

In addition to the defined measures of emergence (Tr, and Clus) another measure, the variance Var is determined. It is inspired from other works [73–75] where

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 65

variances of entropies (called input entropy [73]) were determined to classify automatically the behavior of cellular automata. Our variance measure is simply determined as Var ' , i.e. it is actually the admissible variance computed as above. As we will see later, the two measures Tr and Var ' complement each other and can be used to compose a synthetic and powerful indicator of complexity Cplx capable to predict the occurrence of gliders and complex behaviors with a high probability. In comparison to Wuensche’s input entropy and its variance, the measures proposed above have the advantage of a smaller computational complexity. Note that for each CA iteration, the largest computational time is allocate to the diffusive filtering in (4.3). The complexity of this equation is of the same order of magnitude as the complexity of updating all cells in the CA. Therefore, an overall computational complexity of no more than 2–3 times larger the time used to run the CA without estimating the measures for emergence is expected. Moreover, (4.3), which may be regarded as a one-step simulation of a derivate CA, may be easily executed on the same fast parallel hardware used to simulate the CA. On the opposite, the algorithm to compute the input entropy is sequential in nature and would require more computational resources for the same number of cells. Also, long transients that are often mentioned in literature as a sign of complexity are not exactly measured using the input entropy but rather postulated to be in a direct dependence to large variances of it. As we will see later, the two measures Var and Tr are rather orthogonal and a better measure of complexity can be defined as a linear combination of them. function [trans, clus, tzf, delta]=compute_complex(C) % Usage: [Tr, clus, tzf, var]=compute_complex(C); % input data is the temporal sequence of % the clustering index % tzf is the filtered version of it, % Tr, clus, and var are parameters used to estimate % complexity %--------------------------------------------------steps=size(C,2); tzf=filter(ones(1,10),1,C)/10; % in the above, the C sequence is filtered delta=0.001+8*sqrt(var(tzf(round(0.8*steps):steps))); % in the above the variance is determined % for the last 20% time of CA run en=tzf(steps); % end value to be compared with previous % in order to determine the transient trans=steps; while (abs(en-tzf(trans))<delta) & (trans>1) trans=trans-1; end clus=mean(tzf(trans:steps));

66

4 Emergence, Locating and Measuring It

The compute_complex Matlab function implements the above concepts and it can be called from the main CA simulator program at the end of the main loop, assuming that the sequence of clustering coefficients is computed as indicated above. In evaluating the above measures of emergence a certain degree of approximation has to be accepted. The following are some reasons for this approximation:

x It is unpractical to simulate a cellular system to infinity. Therefore we will define in advance a stopping moment T . Empirically it was found that in most of the cases a “steady state”4 of C t is achieved if T DN with typical values D 2 y 10 . Therefore instead of a theoretical C f we use the Clus value estimated as above. x As seen in Fig. 4.7b C t may have large fluctuations, impeding on finding the exact length of the transient. However in practice the exact length of the transient does not matter too much, and in fact it was found that its dependence on the number of cells N is more relevant for characterizing the global dynamic behavior. Therefore, we introduced the admissible variance ' and measure its estimate as indicated above. This estimate is less accurate for Class III behaviors where the fluctuation can be quite large. For a better accuracy of the transient time Tr, it is also useful to average over several CA runs, each with a different random initial state. Though, note that improving accuracy comes for the price of an increase in the computational complexity (proportional with the number of additional CA runs). 4.4.1 Visualizing Complexity for an Entire Family of Cellular Systems – Wolfram Classes Revisited

Now we can characterize each individual of a CA family (e.g. one of the 256 members of the 1a3 family) as a point in a plane determined by two of the measures for emergence defined above. Let us first consider, the plane formed by the pair of variables Tr, Clus . Since the above family of CAs was used by Wolfram [56] to define its four classes, such plots will give a visualization of the class concept when measured as proposed above. For visualization purposes is convenient to replace Tr with its logarithm Ltr ln Tr . The plot for the 1a3 family is depicted in Fig. 4.8. Each point (circle in the graph) is associated to a specific ID, while its position within the plane is correlated to its associated class (within the four proposed by Wolfram). Such a visual representation gives now a better perspective on the relationship between our measures and the 4-class system.

4

Here by “steady state” we accept small period oscillations or even chaotic oscillation with an amplitude within the admissible variance ' defined as above.

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

67

Fig. 4.8. The >Ltr, C @ plane as a tool to rapidly identify different types of global behavior. Note than the boundaries between domains are rather fuzzy and not sharp as suggested by the use of word “classes of behavior”. The dynamics of several 1D cellular automata are used to exemplify the location of various behaviors on the plane. The ID coding is the one proposed in this book and it coincides with the one proposed by Wolfram in [55,56]

The plane may be divided into several sections although the borders are not as sharp as indicated in the picture. On the middle ( Clus  0.5  0.05 ) there is a strip corresponding to the Class III of Wolfram. Here the length of the transient is less interesting (due to large fluctuations it is imprecisely measured), but all CA within this strip display the randomness associated with Class III. The CA with ID = 30 (reported to be used for the random number generator in Mathematica) belongs to this strip. Above and below the strip, the length of the transient differentiates among the left side (short transients, or Class I, and II) and the right side (long transients, complex behaviors, i.e. Class IV). Where exactly should be that border placed? There is no precise answer but experiments suggest that taking the boundary on the Ltr axis at lnN may be a good choice, consistent with experimental observations showing that transient times comparable with the number of cells are often associated with the presence of gliders. In our case, for N 100 cells, the boundary is at Ltr # 4.6 . Our emergence measures allow to draw a portrait for an entire family of cells while not discarding entirely the classification proposed by Wolfram. They rather allow to see the subtle differences between genes otherwise considered as belonging to the same class, thus resolving the uncertainty in the proposed classification system, as observed by many authors.

68

4 Emergence, Locating and Measuring It

Fig. 4.9. Projection on the Ltr, Clus for the 1,024 members of the 2t9 CA family. Note that long transient behaviors in this case, correspond also to large values (close to 1) of the clustering coefficient

As expected, the famous “110” CA (proved in [17] to be the simplest CA capable of universal computation and its 3 “relatives” (according to [76, 77]) with ID = 124, 137 and 193 are located within the Class IV region of the plane, but quite closely to the Class III strip. Indeed, gliders are present in such CAs but within a rather “noisy” dynamics, typical for Class III. As seen later, the profile for different families of CA is such that some individuals will be placed in the Class IV region but closer to the Clus=1 boundary, indicating the presence of neat gliders, not affected by noise. For instance, Fig. 4.9 presents the profile obtained in the Ltr, Clus plane for the 2t9 CA family (totalistic, two-dimensional with 9 cells in the neighborhood). In addition to clarifying the origin of uncertainties in the classification scheme proposed by Wolfram, the above measures of emergence bring several other important advantages:

x One may easily do a statistics on a large family of cells, inferring relationships such as the probability that a certain kind of behavior will occur in a family or another (e.g. 1s5 or 1s9).

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 69

x Using the projections on  Ltr, Clus planes allows to draw relationships between measures of the local complexity (computed at the cell level) and the global complexity measured as described above. For instance, if one selects all ID-s with large transients (Tr>200) in the case of “1s5” CA family, it turns out that gliders are present only in the case of cells with a local structural complexity defined by m  ^4,5` . Also, “chaotic” patterns are usually obtained for those cells with higher local structural complexity m  ^6,7,8` , with m 8 providing the best random number generators.

x One may employ optimization algorithms acting on an objective function defined as a function of the above emergence measures. Such objective functions may be used to locate only those genes leading to a type of desired behavior. This idea will be further exploited in Chap. 6 where “sieves” are defined in association to such objective functions. For instance if one wants to locate chaotic (or Class III) behaviors, a proper objective function to minimize is: Clus  0.5 . Such a search would be impossible using the visually based classification system of Wolfram.

4.5 Simulation Examples, Properties, More Accurate Complexity Measures Let now consider several families of CA, and apply them the above measures of emergence. Projections in the three-dimensional space (Tr,Clus,Var), such as the one depicted in Fig. 4.10, will give an overall characterization of each CA family. First we will consider the CA family “1s5” (semitotalistic cells with five neighbors, arranged on a one-dimensional grid topology). In our simulations a CA with 100 cells is considered with a simulation time T=400, considered large enough to provide information about long transients. The following simple Matlab program is invoked to obtain a database (here the array Tab) necessary for a further characterization of the CAs in the family. >> Tab=[]; for id=1:1024 [x0, trans, clus, var]=ca_sim('mid100','1s5',400,id,1,0); Tab=[Tab; [id, trans, clus, var]]; id, end;

The information in “Tab” can be used to draw a projection of the entire family within the (Tr,Clus, Var) space (see Fig. 4.10) or as a database for applying certain “sieves” (detailed later in Chap. 6) to filter out cells associated with certain desired behaviors that may be of interest in practical applications. For instance, the next Matlab command provides the list of IDs associated with good random number generators ( Clus  0.5  0.002 and Var ! 0.1 ): >> ix=find(abs(Tab(:,3)-0.5)<0.002 & Tab(:,4)>0.1)

70

4 Emergence, Locating and Measuring It

Fig. 4.10. Projection of the “1s5” CA family within the (Tr,Clus,Var) plane. Observe that complex behaviors (gliders) are associated with either long transients or large variances. Note also that Tr and Var are orthogonal, i.e. there are little CAs having both large variances and transient times

Such a list contains the following IDs: 378, 634, 645, 650 but it can be expanded if a larger range for Clus is accepted. All these cells are associated with large values of the local structural complexities m as seen from Table 3.3. The following “sieve” reveals the complex behaviors, with long transients (Tr>200): >>ix=find(Tab(:,2)>200),

returning the following list of IDs: 21, 212, 294, 475, 507, 684, 851, 866, 870. Note the presence of ID = 684, already described in detail in Fig. 4.4. Also when checked with Table 3.3. it is found that local structural complexities m  ^4,5` are lower than in the case of cells leading to “chaotic” behaviors, but still large. A closer look to Fig. 4.10 reveals that complex behaviors are rather seldom, most of the CA individuals (IDs) being located near the axis Tr=0 with low variance and low transient lengths and with a wide range of clustering coefficients. Indeed, as many authors already reported, complex emergent behaviors in cellular automata are rare, and consequently difficult to locate. For mid values of the clustering coefficients, there is a large concentration of IDs with 0.1
4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors

71

Fig. 4.11. Projection of the “2s5” CA family within the (Tr,Clus,Var) plane. Observe that complex behaviors (gliders) are associated with either long transients or large variances. Note the case of ID=440 which gave a large variance and a short transient (when simulation time was set to T=400 but gave a large transient and a low variance when larger simulation times were considered

Note that in the case of 2D neighborhoods, the variance range for “chaotic” patterns is smaller, i.e. 0.02 0.15) as seen for ID=404. When the CA with ID=404 is simulated for 600 iterations, the long transient is clearly revealed. Though using large simulation times is computationally costly. Similar profiles can be easily drawn for other CA families. For instance, in Fig. 4.12 a plot corresponding to the “1s7” family (with 16,384 members) is depicted. 4.5.1 Properties of Complexity Measures

The use of the Tr, Clus, and Var complexity measures, when applied to different families of cellular automata reveal several interesting properties, as detailed next. Let first discuss the Clus coefficient. As seen in Fig. 4.13, its distribution over the entire family of semitotalistic CA is strongly influenced by the topology (in our case, either 1D or 2D). While in the case of two-dimensional topologies (“2s9” and “2s5” families) the plots reveal the existence of two CA categories, namely

72

4 Emergence, Locating and Measuring It

Fig. 4.12. Profile of the CA family “1s7”. Note similarities with the profiles obtained for other semitotalistic cells. Note a similar fraction of the cells exhibiting complexity, though giving a larger variety of behaviors because of the large number of cells within the entire family

those with “random” behaviors (with Clus | 0.5 ) and those with “ordered” or “near ordered” behavior (with Clus | 1 ), in the case of 1D topologies (even in the case of using the same cell, as in the case of 1s5 vs. 2s5 families), the clustering coefficient is widely distributed without a clear preference for a maximum in the middle. The “ordered” CAs with Clus | 1 are predominant in such cases. As a practical conclusion, while it is known that good “random” sequence generators require Clus | 0.5 , it is clear that such “random” generators are much easily to be found from a population of CA with cells distributed over a 2D grid. On the other hand, for those applications where a wide range of Clus values are needed, a better choice is a 1D-neighborhood. Such distributions, particularly those drawn from cellular automata with 2D neighborhoods, can be characterized by certain scalar features, called c1 and c2 in our example. Such scalar values indicate bifurcation points with respect to qualitative behaviors of the CA. Here they are defined as points of reaching a minimum in the distribution. As seen later in Chap. 6, they can be effectively used in defining various “sieves”. The distribution of the Var complexity measure is plotted in Fig. 4.14. Note that in this case the topology (1D or 2D) plays no significant role and does not influence the unique shape of distribution which always has two peaks. Like in the previous case, two scalar values v1 and v2 may be introduced to define the major features of the distribution. These values are influence by both the topology (1D or 2D) and the cell type, as seen from the plots. A detailed analysis of various CA exhibiting different Var values revealed that v1 and v2 separates between three qualitatively different classes of behaviors:

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 73

Fig. 4.13. Distributions of the clustering coefficient Clus for various families of semitotalistic cellular automata with 2D neighborhoods (left column) and 1D neighborhoods (right column). The horizontal axis plots the value of Clus while the vertical axis plots the fraction of CA from the family exhibiting a certain Clus value

(a) Var  v1 – In this case, for most of the CA family members, there is a simple dynamics, typically characterized by a small transient time followed by a permanent regime exhibiting a low periodicity or a steady state. (b) v1  Var  v 2 – In this case, quite frequently the CA behaves as a “noise generator”, with a quality of noise to be more precisely defined by the magnitude of the clustering coefficient Clus. Most of the CAs in this category, namely those with Clus # 0.5 are the “good” (white noise) random number generators, but many other noise generators (pink, or blue) could be found within this category as well. Typically for CAs in this category there are neither long transients, nor gliders. (c) v 2  Var – This case (with a relatively small fraction of the entire population) is the most interesting for complexity, since here it is likely to find gliders and long transients. Note that in some cases, where the finite running time cannot reveal long transients (e.g. ID=404 in Fig. 4.11), the variance parameter is the only capable to indicate the presence of a complex behavior. As seen in Fig. 4.15 the distribution of the scaled transient length Tran is also less dependent on the type of cell and topology. Moreover, one cannot easily identify a bifurcation parameter like in the case of the previous two parameters. This indicates that the transient length is less important as a qualitative measure but rather as an additional check-up applied to qualitative behaviors indicated by the two other measures of complexity. Based more on experiments and less on the structure of the distribution, a quantitative bifurcation parameter t1 (ranging from

74

4 Emergence, Locating and Measuring It

0.1 to 0.2) is introduced to discriminate between less complex behaviors (the majority of the CA family members) and potentially complex behaviors (characterized by long transients Tran>t1).

Fig. 4.14. Distributions of the clustering coefficient variance Var for various families of semitotalistic cellular automata with 2D neighborhoods (left column) and 1D neighborhoods (right column). The horizontal axis plots the value of Var while the vertical axis plots the fraction of CA from the family exhibiting a certain Var value

4.5.2 A Composite Complexity Measure

As a consequence of the above observations, regarding the relationship between variances and transient lengths a novel, composite measure of complexity is proposed as follows: Cplx

1 1 § Tr · Var  ¨ ¸ 2 2© T ¹

(4.5)

to capture both cases with large variances and large transients and to simplify plots such as those in Figs. 4.11 or 4.12 from a three-dimensional to a twodimensional representation. Such a 2D representation is much easier to analyze. As seen in Fig. 4.16, the entire “2s5” family is mapped now into a Cplx, Clus plane, each dot representing a particular cell ID and being labeled accordingly. Such maps allow an easy selection of a certain ID within an area associated with a certain qualitative behavior. Although ID labels in this figure overlap, a sieve as defined in Chap. 6 may be applied to plot only a limited number of IDs, i.e. those within the restrictions imposed by the “sieve”.

4.2 Visual Interpretation of Emergent Phenomena – Classes of Behaviors 75

Fig. 4.15. Distributions of the scaled transient length Tran=Tr/T (where T is the total number of iterations) for various families of semitotalistic cellular automata with 2D neighborhoods (left column) and 1D neighborhoods (right column). The horizontal axis plots the value of Tran while the vertical axis plots the fraction of CA from the family exhibiting a certain Tran value

Fig. 4.16. A two-dimensional map of all CAs within the “2s5” family, using the composite complexity measure Cplx. The clustering coefficient Clus is the second important coordinate within this map. Cell ID’s are plotted next to each point

5 Exponents of Growth

In the previous chapter several scalar complexity measures (the clustering coefficient, its variance and the transient length) were introduced to characterize a given cellular automata system from the point of view of its behavior and likelihood of emergent phenomena. These were the first steps in establishing a set of methods called design for emergence. All these emergence measures have in common their determination based on the temporal evolution of the clustering coefficient. In the next, another point of view is considered to define a novel complexity measure, also proved to be useful in the process of designing for emergence. This point of view has to do with the answer to the following question: Given an initial state pattern with a random distribution of states in a localized spatial region (a spatial cluster of active cells) what happens during the evolution of the CA: Will this pattern expand, much like fire in an combustible environment or will the pattern implode until it will eventually vanish? An in depth qualitative answer is possible through the introduction of a novel measure called an exponent of growth (U). We will see that by properly characterizing the “growth” of a spatial localized pattern it is possible to locate the “edge of chaos” as a complex dynamic regime at the boundary between order (here regarded as an “implosion” of the initial state cluster) and disorder (here regarded as a rapid “explosion” of the initial state cluster. Two-dimensional and semi-totalistic CA models are considered herein to give examples, but the same method for determining exponents of growth may be applied with minor modifications to any other type of cellular computing system.

5.1 Exponents of Growth and Their Relationship to Various Emergent Behaviors Let us consider an array of cells where all cells are in a quiescent state except a small square in the middle where cells are randomly assigned different values. The same random initial state will be used for all cellular automata. We will exemplify here for the binary case where each cell may have only two values. Before explaining how a measure based on “growth” can be evaluated, let us consider one special cell, the one with ID = 768 from the “2s5” family. It is a linearly separable cell with an interesting property when used in a CA.

R. Dogaru: Exponents of Growth, Studies in Computational Intelligence (SCI) 95, 77–94 (2008) www.springerlink.com © Springer-Verlag Berlin Heidelberg 2008

78

5 Exponents of Growth

Starting from a localized random initial state which will be next referred as a spatial cluster, the CA employing this gene evolves towards a steady state which develops a square with all black cells. This rectangle marks the smallest possible boundary enclosing all cells of the spatial cluster that are different from the quiescent state (e.g. black cells vs. white quiescent states in a graphical representation, as seen in Fig. 5.1). This is thus a convenient way to determine the area of the spatial cluster A as the area of the steady state rectangle. Although there are many other possibilities to calculate the area of a spatial cluster, the CA-based method using gene 768 has the advantage that it can use the same CA simulator as for the CA under investigation (e.g. the ca_sim.m introduced in Chap. 3).

Fig. 5.1. Consecutive iterations of a cellular automata employing the semi-totalistic gene 768. Several spatial clusters evolve towards squares with an area easy to be determined. The smaller the area of an initial state spatial cluster the lower is the number of iterations needed to reach the steady state rectangle

The idea to compute an exponent of growth “U ” is straightforward. We always start with the same initial state spatial cluster of a given area. In the next examples we will use 11×11 spatial clusters evolving within a CA array of 77×77 cells. Therefore the reference initial state area of the spatial cluster is A(0)=121. In practice one may choose different other values without changing the significance of the method. Of course, there is a tradeoff between high speeds demanding less cells in the CA array and a good accuracy in determining U which demands large CA arrays. The CA with a specified ID gene is run from the initial state with an area A(0) of the spatial cluster for a reasonable number T of iterations. What happens is either an implosion (shrinking) or an explosion (growth) of the initial spatial cluster. In case of explosion, the “speed” of the process is limited by what is called “the

5.1 Exponents of Growth and Their Relationship to Various Emergent Behaviors 79

speed of light” in some CA papers. The speed of light is expressed in cells per iterations and is solely determined by the neighborhood and the CA topology. For our examples, the speed of light is 2 cells per iteration and for a spatial cluster located in the middle a good choice is T=(77-11)/2=33 iterations. The exponent of growth is defined as the ratio between the area of the terminal state spatial cluster A(T) and A(0). Therefore: U

A(T ) A(0)

(5.1)

Several qualitatively different situations may occur: (a) (U=0, passive). The spatial cluster “implodes rapidly”, i.e. its area as defined above is rapidly shrinking until it becomes 0 (there will be no terminal spatial cluster at all). This situation is similar to passivity as defined by the local activity theory in the context of Reaction-Diffusion cellular systems [8]. Such an example is ID = 924, as exemplified in Fig. 5.2. In principle there is no computational meaning (or practical use) for a passive behavior since the final state of the CA contains no information at all. However in some cases stopping the CA array earlier (see iterations 2 or 4 in Fig. 5.2) may result in a form nonlinear filtering which may be of use for certain applications. (b) (0
Fig. 5.2. Time evolution for ID = 924. It is a typical evolution for passive behaviors. The exponent of growth in such cases is always U=0. The upper row represents the time evolution of the cellular array, while the lower row indicates the evolution of the rectangular boundary enclosing the evolving spatial cluster

80

5 Exponents of Growth

Fig. 5.3. Time evolution for ID = 890. It is a typical evolution for stable but active behaviors. Here the exponent of growth is larger than 0, but not reaching 1. The upper row represents the time evolution of the cellular array, while the lower row indicates the evolution of the rectangular boundary enclosing the evolving spatial cluster

has been proved to be an universal Turing Machine belongs to this category and its exponent of growth was determined as U = 0.2. Although values of U closer to 1 may be associated with long transients and complexity, there is no direct correlation between the U measure and the transient length. Sometimes very long transients are observed even for relatively low values of U, and this is actually the case with the “Game of Life”, (ID = 6,152 from “2s9”) with an experimentally computed U=0.2. Note however that a more accurate method described in Chap. 7 gives U × 1 (with U > 1) for the “Game of Life ”. (c) (U=1, edge). This is an interesting case indicating behaviors that are located at the boundary between stable (shrinking) and unstable (growing) behaviors. In these cases the area of the initial state spatial cluster is not changing in time or it is slowly and alternatively increasing and decreasing. Though, the CA dynamics exhibit relevant information processing of the initial state spatial cluster. The gene ID = 768 discussed above (which draws an opaque rectangle perfectly framing the spatial cluster) belongs to this class. Other example is gene ID = 1011 with a dynamics exemplified in Fig. 5.4. Among such genes one may find interesting computational applications if a meaning of the transformation between the initial and the terminal state can be established. For instance, gene ID = 768 is used successfully for character segmentation, as shown later in Chap. 8. (d) (1
5.1 Exponents of Growth and Their Relationship to Various Emergent Behaviors

81

Fig. 5.4. Time evolution for ID = 1011. It is a typical evolution for edge behaviors. The exponent of growth in such cases is always U = 1 indicating a delicate balance between stability (implosion of spatial clusters) and instability (explosion or growth of the spatial clusters)

The longer the transient (i.e. the closer U is to 1) the more complex is the behavior. The upper bound of U = 4 is empirically determined based on experimental evidence that another category of behaviors (“nested”), to be discussed later, emerges for 4
Fig. 5.5. Time evolution for ID = 471. It is a typical evolution for an unstable near the edge behavior. In this case U =2.11 indicating a slow growth reminiscent of the self-making or autopoietic [64] dynamics

82

5 Exponents of Growth

Note also that after the first iteration the active square in the middle becomes a negate of the initial, a process which continues with period 2, but which can be taken in consideration by the program evaluating the size of the cluster. It is easy to prove that such evolutions always happen for odd values of the cell ID. Let us consider a more detailed evolution of a random pattern using this gene (ID = 471) in Fig. 5.6:

Fig. 5.6. Slow evolution towards a self-making (stable) pattern for gene ID = 471

In the above case a stable pattern (cluster) emerges after sufficient iterations (about 330), much like a living being develops its “far from equilibrium” stable state from an embryo. (e) ( 4 d U d 5 , nested). This is another example of unstable near the edge of chaos behaviors in which “nested patterns” (as referred in [55]) occur. It is characterized by a relatively fast growth until a group of 4 or 5 initial state clusters (identical with the original one) emerge. Usually there is a power of 2 number of iteration between states of the CA characterized by the presence of several “clones” of the initial state spatial cluster. Such phenomena were characterized by Fredkin in [82] as trivial examples of self-reproduction (see Fig. 5.7).

5.1 Exponents of Growth and Their Relationship to Various Emergent Behaviors

83

Fig. 5.7. Time evolution for ID = 300. It is a typical evolution for a nested behavior. The exponent of growth in such cases is either U = 4 or U = 5 indicating self-reproduction of initial spatial clusters after power of two numbers of iterations

Fig. 5.8. Trivial self-reproduction of the initial state pattern for ID = 682

Another example in this category is gene ID = 682 exemplified below (Fig. 5.8) for a meaningful initial state pattern in order to observe the self-reproduction effect. (f) (U>5, explosion). This case corresponds to genes leading to a rapidly growing spatial cluster (with a speed close to the “speed of light”). Although sometimes the spatial cluster evolves to a steady or low-periodic pattern, it mostly evolves towards a “chaotic” attractor characterized by clustering coefficients near 0.5 as indicated in the previous chapter. Such behaviors are often exploited to build BIST (built-in self testers) or random number generators. There are two major types of behaviors within this category. The first corresponds to a growth with half of the “speed of light”1, exemplified here by gene ID = 263 in Fig. 5.9 and the other, to the fastest growth, with the “speed of light”, exemplified here by the gene ID = 748 in Fig. 5.10. Experimentally we found that the best random number generators are obtained from genes within the last category (generating the fastest 1

The “speed of light” in cellular automata parlance indicates the traveling of a signal (a pattern configuration) with a speed of r cells per iteration (in all directions) where r is the neighborhood radius.

84

5 Exponents of Growth

growth). Slower growth speeds correspond to “pink” noise generators that may have relevance in musical synthesizers or other applications. For instance, some of the pattern generators used for a novel image compression method described in Chap. 8 may be extracted from this category.

Fig. 5.9. ID = 263. In this case U=15, indicating a growth with half of the “speed of light”, i.e. the front of the cluster array moved only 16 pixels in each direction

Fig. 5.10. ID = 748. In this case U = 47, indicating a maximum growth with of the “speed of light”, i.e. the front of the cluster array moved about 32 pixels in each direction

Within the full set of 1,024 semi-totalistic genes of “2s5” family, more than 50% of them lead to unstable behaviors from the above category. Only a very small fraction of cells (less than 10%) lead to unstable near edge behaviors, which are, in our opinion, the most interesting from the perspective of modeling living or natural processes or for computational purposes. The large pool of remaining genes with 0 d U d 1 , allow for a rich base for selecting and identifying genes that are relevant for various feature extraction or classification tasks. In the next section a more exact distribution of behaviors is given as well as some considerations regarding the influence of the “Small World” model on this distribution.

5.2 Mutations for Continuous State Cellular Systems

85

5.2 Mutations for Continuous State Cellular Systems The above characterization based on exponents of growth may be also used for the discovery of interesting emergent phenomena in continuous-state cellular automata. One major advantage of representing the cell as nonlinear piecewise-linear function rather than as a Boolean table is the easiness to achieve continuously valued mutations. This is done simply by replacing the hard sign() nonlinearity from the definition of the Boolean piecewise-linear cell with the smooth (linear saturated) nonlinearity y f x 0.5 x  1  x  1 . In order to get interesting emergent behaviors it is advisable to start with Boolean cells exhibiting rich complex dynamics when connected in various CA topologies. By tuning a parameter of the piecewise-linear representation (see Chap. 3) of the original Boolean cell within a certain range (e.g. adding r H in (3.4)), one can identify different emergent regimes within the resulting continuous state cellular nonlinear network. These regimes are separated by bifurcation points in the space of the variable parameter. Experimentally it was found than such behaviors are likely to be complex and interesting when starting from with a set of parameters b, t1 ,..t m 1 defining a piecewise-linear Boolean cell assigned to class “d” (unstable near the edge) after the measurement of the exponent of growth.

Fig. 5.11. Mutations of gene 471: A linear saturated output for the cell is chosen instead of the hard limiter and H 1.33 . The result is a slow growing random cluster

86

5 Exponents of Growth

To exemplify, next two mutations of gene ID = 471 (discussed in Fig. 5.6) are considered. The first, is exemplified in Fig. 5.11 and reveals an “unstable near edge” behavior for H 1.33 . Indeed, starting from a random initial state spatial cluster, a slow growth while maintaining a random dynamic behavior is observed. Various bifurcation values of the parameter H can be emphasized while changing H furthermore. When this parameter is decreased to H 2.735 , as shown in Fig. 5.12, the cellular array behaves as an excitable medium propagating waves from an initial state perturbation. Starting the mutation process with other “seeds” (i.e. emergent Boolean genes) a large variety of emergent phenomena in the resulting continuous state cellular system are revealed. Such emergent behaviors may have various practical applications, ranging from biological modeling to signal processing such as image compression, or signal detection.

Fig. 5.12. Another mutation of gene 471: A linear saturated output for the cell is chosen instead of the hard limiter one and H 2.735 . The result is a cellular array simulating an excitable medium capable to propagate waves. A different initial condition is used, representing some handwritten figures

5.3 Distribution of Exponents of Growth Among Families of Genes

87

5.3 Distribution of Exponents of Growth Among Families of Genes It would be interesting to see how emergent properties measured by the exponent of growth U are distributed among an entire family of genes. Histograms may give such a synthetic view, as seen in Fig. 5.13, where two families of semi-totalistic cells are considered (the “2s5” and the “2s9”). Note the similarities between the two distributions. A large fraction of genes is related to “fast growing” emergent phenomena (with U around 49). Interesting emergent behaviors are located within the range 0
Fig. 5.13. A set of histograms depicting the distribution of the exponent of growth “U” among two families (“2s5” and “2s9”) of semi-totalistic cells on a 2D grid topology

What are the possibilities to increase the fraction of interesting behaviors in the “unstable near edge” class? As seen from Fig. 5.13, for semi-totalistic cells, adding more inputs (as in the case of “2s9” compared to “2s5” families) the fraction of genes within the “interesting” region grows. If there is no semi-totalistic restriction at all (universal cells), an even higher increase of that fraction is observed, as seen in Fig. 5.14 where the the “2a4” family was considered (with a four input cell on a 2D grid topology and a neighborhood formed by the North, South, West and East cells).

88

5 Exponents of Growth

Fig. 5.14. A set of histograms depicting the distribution of the exponent of growth “U” for the “2a4” family of universal cells (all possible Boolean functions with four inputs) distributed on a 2D grid topology

Table 5.1 lists the distribution of genes among the “2s5” family and the corresponding percentages of their membership to the behavioral categories introduced previously: Table 5.1. Distribution of genes among the behavioral categories defined in Sect. 5.1 Category

(a) Passive

(b) Stable near edge

(c) Edge

(d) Unstable near edge

(e) “Nested” near edge

(f) Unstable

Number of genes:

43

149

321

10

4

497

4.20

14.55

31.35

0.98

0.39

48.54

%

Only a small fraction of the entire set of genes represent highly complex emergent cellular systems. Table 5.2 lists 10 genes from each category (in case of category “e” they are only 4). Among all 10 genes in the “interesting” class d), gene 49 was found to have interesting properties making possible to build excitable temporal membranes with some interesting applications in signal recognition, as detailed in Sect. 8.3 (Fig. 8.9). Table 5.2. A list of 10 genes from each behavioral category Category

(a) ID 107 128 136 144 152 256 264 272 280 862

U 0 0 0 0 0 0 0 0 0 0

(b) ID 104 108 111 112 115 116 119 120 123 124

U 0.46 0.60 0.64 0.13 0.11 0.67 0.34 0.47 0.25 0.67

(c) ID 131 134 135 138 139 142 143 146 147 150

U 1 1 1 1 1 1 1 1 1 1

(d) ID 41 49 69 81 101 375 463 471 487 503

U 4.98 1.36 2.98 1.18 1.85 2.08 1.18 1.40 1.29 1.29

(e) ID 330 341 682 693

U 4 5 5 4

(f) ID 418 419 421 422 423 425 426 427 429 430

U 44.04 15.28 46.49 44.04 6.02 46.49 44.04 15.28 46.44 44.04

5.4 Influences of the “Small World ” Model

89

5.4 Influences of the “Small World” Model As shown previously the model of a cellular system can be simply transformed into a “small world” model by taking a fraction f of the local connections and rerouting them to randomly selected distant cells. The random allocation is set before the CA running and is not changed during the running process. An analysis over the whole set of 1,024 possible genes from the 2s5” family was performed, for f = 0.01. The results are shown as a histogram in Fig. 5.16. A better understanding of the “small-worlds” effect is revealed by Table 5.3: Table 5.3. Distribution of genes among behavioral categories (Small Worlds model) Category Number of genes % (Small world) % (Cellular)

(a) Passive 43 4 4.2

(b) Stable (c) Edge near edge 185 18 14.55

212 21 31.35

(d) Unstable near edge

(e) Nested near edge

(f) Unstable

58 6 0.98

0 0 0.39

525 51 48.54

The last row is included for comparison and represents the percentages in the case of the purely cellular model (f=0)

A comparison with results reported in Table 5.2 shows no major influence of the “small worlds” model on the “passive” genes. The main influence of changing the purely cellular into a “small world” model is the migration of a fraction from the “edge” genes into the interesting “stable near edge” or “unstable near edge” classes. A slight fraction of the “edge” genes also migrates to the “unstable” regime. Indeed, while in the cellular model 321 genes correspond to the “edge” behaviors (U = 1) now their number decreased to 212. Among the difference of 109 genes, 36 migrated to the “stable near edge” category (increasing their number to 185), 44 migrated to the category “unstable near edge” (increasing their number to 58, and

Fig. 5.15. A histogram for the distribution of the exponent of growth U among the set of 1,024 semi-totalistic genes from “2s5” family (“small world” model with f = 0.01). Note that in comparison to the classic cellular model in Fig. 5.13, now there is a much crisper distribution into “passive”, “edge” or “unstable” behaviors

90

5 Exponents of Growth

finally some other 28 “edge” genes in the cellular model migrated to the “unstable” class increasing their number to 525. The dramatic increase of “unstable near edge” genes (i.e. those behaviors that are closest to the behavior of living systems) from 14 to 58 (i.e. almost four times) gives an argument in the favor of the hypothesis that natural systems are in fact described better by a “small worlds” rather than a purely cellular model. As for the “unstable” behaviors, unlike in the case of a pure cellular model, where some unstable behaviors exhibited a slow growth with half or less than half of the “speed of light”, in the case of the “small world” model almost all unstable behaviors migrate to the “fast growing” emergent behaviors (with largest U). As a practical consequence, it is expected to have better “pseudo-random” sequence generators within the “unstable” behaviors of the small-worlds model. 5.4.1 The “Small Worlds” Model Allows Fine Tuning of the “Edge of Chaos” Another interesting fact about the “small worlds” model is the following: Starting with a gene located in the “edge” category of a cellular model, the f parameter (representing the fraction of random long-distance connections) can be used to slightly change the behavior of the resulting “small worlds” system into any of the behavioral regimes ranging from “stable near edge” to “unstable”. Indeed let us consider the gene ID = 768 of the “2s5” family (the interesting “edge” gene producing rectangles around any initial state spatial cluster, in the case of the pure cellular model). The evolution of the cellular array for three different values of f is shown in Fig. 5.16. Note that for f = 0.01 the overall behavior is slightly the same as in the case of a pure cellular model (f = 0). However some small black dots appear out of the rectangles, as a consequence of sending information to distant cells. Eventually after about 167 iterations, the evolution enters into a steady state having the same computational meaning as in the case of the pure cellular model. When the fraction of distant connections is increased beyond a bifurcation value (here f = 0.02) the spatial clusters continue to expand after 167 iterations, the overall system exhibiting an “unstable” behavior which eventually leads to a final state where all cells are in the “black” state. The bifurcation value of f is in a direct relationship with the size of the biggest spatial cluster in the initial state image. Therefore the above phenomenon may be applied as an object size detector. Indeed, if the size of the spatial cluster (representing an object) stands bellow a certain threshold (directly related to f) the system will evolve to a steady state containing a square of black pixels surrounding the object. However, if the size of the object is greater than its critical limit, the

5.1 Exponents of Growth and Their Relationship to Various Emergent Behaviors

91

Fig. 5.16. An effect of the “small-worlds” model: Until the fraction of random connections f reaches a bifurcation value (here 0.02) the behavior is of the “edge” type, i.e. drawing squares around the main clusters. Beyond the bifurcation value, the behavior becomes an “unstable” or explosive one

system will evolve towards the easy to detect state with “all cells black”. A similar effect is described in Fig. 5.17 for gene ID = 801 (also belonging to the “edge” category for the pure cellular model). We may assign a social meaning to the emergent phenomena depicted in Fig. 5.17. When f grows beyond a certain value (here 0.1) the “isolated civilizations” represented in the initial state by the three isolated spatial clusters will collapse into a unique global “civilization” as a result of an increasing fraction of the distant communications Note that for the simulations shown in the first two rows in Fig. 5.17, the evolution is of an “edge” type, with some dynamic clusters evolving around the initial state spatial clusters but eventually stabilizing their boundaries after several hundreds of iterations. Although long-distance communication exists it does not yet have a dramatic effect on altering the boundaries constructed in the first iterations.

92

5 Exponents of Growth

Fig. 5.17. Small world effects for gene ID = 801

5.5 On the Independence Between Various Measures of Complexities So far we introduced four measures of complexity (the transient length Trans, the clustering coefficient Clus, the variance of the clustering coefficient Var, and the exponent of growth U). It is normal to ask whether these measures are independent or not. Ideally, a set of independent or orthogonal measures will be the best choice. But we expect that a certain degree of dependence between these measures exists. Let us consider a CA family with a large number of members (“2s9” with 262,144 members) allowing the statistical characterization of the complexity measures. Each complexity measure was calculated for all members of the family giving a sequence (that may be associated with a random variable) with 262,144 samples. Figure 5.18 displays the direct functional relationship between all possible pairs of complexity parameters. These graphs reveal weak functional dependences between the four complexity measures.

5.3 On the Independence Between Various Measures of Complexities

93

Fig. 5.18. Functional dependence between all possible pairs of complexity measures. Each point in a graph corresponds to a particular cell ID among the entire set of 262,144 possible cells

In order to give a quantitative description of that dependence, the following simple statistical operations were performed: Each complexity measure sequence representing a stochastic was normalized such that results in a zero mean and a covariance of one sequence. Then mutual correlations between all six possible pairs are calculated. The results are shown in Table 5.4. Table 5.4. Mutual correlations between the four measures for emergence introduced in Chaps. 4 and 5 U Trans Clus Var

U 1 –0.19 –0.55 0.15

Trans –0.19 1 0.238 –0.23

Clus –0.55 0.238 1 –0.317

Var 0.15 –0.23 –0.317 1

The highest correlation (0.55) is between U and Clus. Indeed, as we already observed, genes with explosive behaviors (large U) are in many cases associated with “random-like” noise generators characterized by a value of Clus around 0.5. The weakest correlation (0.15) is between the variance Var of the clustering coefficient and the exponent of growth U. Thus, the introduction of the variance as a complexity measures gives enough new information to characterize the CA behaviors.

94

5 Exponents of Growth

Table 5.4 suggests the following ordering (in a decreasing order of their importance) of the complexity measures: U, Var, Trans, Clus. It means that in principle, when one needs a characterization with less than four complexity measure will better choose among the less mutually correlated ones. For instance, if one would like to characterize the CA behavior using only two measures, it is reasonable to take the first two measures from the suggested order, i.e. U, and Var. Similar orderings were found for other families of cellular arrays.

6 Sieves for Selection of Genes According to Desired Behaviors

6.1 Introduction So far we introduced and discussed four nearly-orthogonal measures of emergence (the exponent of growth, the variance, the transient length, and the clustering coefficient) capable to give a synthetic description of the emergent behavior in a cellular array (CA, CNN or Small Worlds network) with a given cell (usually specified by its family name and the particular ID). In Chap. 4 we saw that with the help of these measures it is possible to draw maps transforming the ID (cell genes) space into a behavioral space where each cell is associated with a point. The position of this point within the behavioral space gives a hint about the behavioral particularities of the cellular array without a need to further simulate it. In practical applications of cellular automata quite often the following problem (called design for emergence) occurs: Given a desired behavior, often specified in natural language, find one or more cellular systems (CNNs CAs, Small World networks, etc.) capable to exhibit this behavior. Unless a description with measures of emergence is available, answering the above question is a matter of trial and error with a lot of wasted time to simulate and observe the dynamical evolution of the cellular automata. Instead, defining families of CA cells and automatically calculating the reduced set of measures of complexities for small size cellular arrays allows for the automation of the search process. It also makes possible to apply optimization algorithms with numerically specified objective function and therefore complex design for emergence problems can be solved in due time. The focus of this chapter is on a methodology to design “sieves”, i.e. functional constraints applied to one or more of the previously defined emergence measures such that desired genes may be selected from a larger pool. This larger pool may be an entire family of cells, or a large population of cells selected randomly within a very large family. The computational limitation is given by the available time to compute the emergence measure for all cells within the selected pool. As we will see in Chap. 7, introducing an analytically defined exponent of growth makes possible a substantial reduction of computational demands, since emergent properties may be predicted entirely based on cell and neighborhood properties, without simulating the CA. R. Dogaru: Sieves for Selection of Genes According to Desired Behaviors, Studies in Computational Intelligence (SCI) 95, 95–112 (2008) www.springerlink.com © Springer-Verlag Berlin Heidelberg 2008

96

6 Sieves for Selection of Genes According to Desired Behaviors

A precise definition of the emergent behavior is usually not possible, therefore we shall connect the notion of a “sieve” with ideas bore from the field of Fuzzy Logic [83,84]. In fuzzy logic there is no pure truth like “a cell ID gives precisely the emergence of gliders”. Instead one can define (including some human subjectivity) functions called membership functions in the form P A x where x is associated with one or more precisely determined measures of complexity, and A represents a linguistic concept (phrase) like “this CA belongs to Wolfram’s class III” or “this CA behaves like a perfect random number generator”. Such concepts are actually the linguistic expression of the “design for emergence” objectives, while x (a vector of complexity measures) is a measurable value obtained using algorithmic process as described in Chaps. 4 and 5. More advanced analytic techniques as described in Chap. 7 allow the determination of x using well defined mathematical formulae. Here we will give some examples and hints in defining the functional expression P A x meaning a degree of truth for statement A. It is imposed that 0  P A x  1 where 1 represents the absolute truth of statement A, and 0 its absolute falsity. If x is collected from a pool X of genes as explained above, by assuming a truth threshold T it is possible to filter-out from X only those cells with desirable properties (expressed by the statement A). This process can be described as using a sieve S A,T X applied to the pool of genes X. A cell (here defined either structurally, by its ID but also behaviorally, by its associated vector of complexity measures x) belongs to the filtered-out set, x  S A,T X if and only if P A x ! T . By extension, in the next we will also call a sieve [85] the mathematical expression of the function P A x . Its definition is subjective in nature, capturing the uncertainties related to the definition of emergent behaviors. Therefore its shape can be iteratively adjusted by applying the sieve and changing it until the desired objectives are best fulfilled. Once sieves are defined one can explicitly use them to locate genes of interest assuming that a database of emergence measures (the set X calculated for a pool of genes) is available. If such a set is not available, the sieve can still be used as an objective function to guide a search process regarded as an optimization algorithm within the space of all possible cell IDs. In the next we will give examples in the first category, namely when a set X of measurements is already available as a mapping from the ID space (using algorithms exposed in Chaps. 4 and 5) and the sieve is used to select from it only those cells with desired properties. Such a process is depicted in Fig. 6.1, where two “sieves” are successively applied to locate CA genes giving interesting behaviors.

6.2 Defining Sieves Given a signal processing problem to be solved with cellular arrays starts with a “fuzzy” definition of the objective function. Let consider as a first example,

6.2 Defining Sieves 97

the following statement A: “The cellular automata acts like a random number generator”. How shall one define a proper sieve to select only cell genes providing such a behavior? In the next we will exemplify this process, giving a methodology that can be generally applied for other definitions of some desired behaviors.

Fig. 6.1. Locating interesting behaviors using two “sieves”. The result is a pool of genes for which the CA is expected to have a desired behavior. Defining sieves is equivalent to defining two functions: P A1 x for the upper sieve and P A2 x for the lower sieve

First note that defining a sieve requires some previous expert knowledge of the relationship between behaviors and various complexity measures. Such knowledge may be improved by additional experiments and transferred to the sieve definition using the same methodology as the one used to design a fuzzy expert system. Since the number of emergence measures is limited and since within each such measure there are distributions suggesting several categories, it is quite easy to analyze a few representative categories for each complexity measure noting down the behavior observed visually in the cellular automata. It is assumed (and actually confirmed by experiments) that slight changes in the value of the emergence measure does not affect substantially the overall behavior unless a bifurcation point is reached. Such bifurcation points were revealed for most of the complexity measures introduced in the previous chapters and practical methods to locate them were also given in Chap. 4.

98

6 Sieves for Selection of Genes According to Desired Behaviors

Moreover, some statement definitions may be divided into several statements connected with conjunctions or disjunctions such that each sentence can be better associated with a particular complexity measure. Let us recall Fig. 4.7 in Chap. 4 where we concluded that a “good random number generator” (i.e. our objective statement “A”) is mainly characterized by the following two phrases: (A1) The clustering coefficient Clus shall be close to 0.5. (A2) The variance of the clustering coefficient Var shall be larger than 0 but not so large, actually it should be situated within the region v1  Var  v 2 where v1 and v2 are two bifurcation parameters that can be easily determined for a given family of cellular systems (Sect. 4.5.1).

Now one may consider the two statements associated with two sieves: The first sieve rejects all CA cells not satisfying the “A1” statement. Among the CA cells which passed, a second sieve is applied such that it will further reject all cells not satisfying the “A2” statement. Let us consider the family “2s5” with 1,024 members. As a first sieve one may choose P A1 Clus 1  Clus  0.5 . Assuming a degree of truth T1 0.999 the following is a list of 12 cell IDs that passed after this first sieve: 198, 315, 323, 325, 346, 362, 373, 627, 650, 677, 714, 761. As a second sieve one may choose P A2 Var 1  Var 

v1  v 2 . Assuming 2

v1 0.02 and v 2 0.08 as indicated in Fig. 4.14, and a degree of truth T 2 0.99 , after applying this sieve to the above list results in the following list with only five cells: 315, 325, 346, 362, 714. Running each of the CAs in the list proves that a desired behavior, as specified by statement “A” emerges in the corresponding CA. The choice of an absolute value function is subjective, and one can freely select other functions. For instance, if one uses the function P A2 Var exp  100 ˜ Var  0.05 2 instead, for the same degree of truth, obtains the same list of genes. But the absolute value function is much easier to evaluate than the exponential, so in practice sieves based on absolute values may be preferred. The degrees of truth are also subjective choices of the designer, smaller values resulting in larger lists with a wider range of behaviors. On the opposite choosing a too small degree of truth leads to the risk of an empty list. Instead of successively applying the sieves, one may apply the same strategy as used in the definition of fuzzy expert systems and define a unique sieve, for instance, in our case: P A Clus,Var min>P A1 Clus , P A2 Var @ , where the “min” operator stands for “Fuzzy AND” (i.e. A is true if A1 AND A2 is true). For the above example, using this single sieve with a degree of truth of 0.999 results in only two cells: 315 and 714. Relaxing the degree of truth to 0.998 gives the following list: 178, 202, 315, 714 with two members (ID = 178 and 202) not previously listed. Though, simulations of the corresponding CA indicates its behavior in accord to the statement A.

>

@

6.3 Examples and Applications of the Double Sieve Method 99

6.3 Examples and Applications of the Double Sieve Method Following the above methodology is now possible to define various types of sieves, all associated with a certain “A” statement. 6.3.1 Intelligent Life Behaviors and Uncertainty in Using Sieves

In Chap. 5, with the introduction of the exponent of growth U as a fourth measure of complexity, it was revealed that CA behaviors characterized by a slow growth near the edge between “explosive” and “implosive” behaviors are likely to model real-life biological processes characterized by a tamed tendency of growth, when starting from a specified initial state spatial cluster. Let define a first sieve as P A1 U exp  10 ˜ U  2.5 2 to favor those behaviors characterized by a small exponent of growth U 0 2.5 . Since in Chap. 4 we discovered that complex behaviors are typically associated with a large variance (much larger than the bifurcation parameter v2) it would be reasonable to add a second sieve to select only those cells giving large variances when connected into the specified cellular structure. This second sieve is defined as P A2 Var 0.5  0.5 tanh>10 ˜ Var  0.12 @ favoring only those cells with a variance larger than 0.12 (while the bifurcation parameter v2 = 0.07 in the case of “2s9” family). As seen in Chap. 5, for this family there is a large number of cells with “slow growth” therefore there is a rich basis of selection. The global sieve is now defined as a fuzzy AND between the two previously defined sieves and therefore: P A U , Var min>P A1 U , P A2 Var @ . Choosing a truth threshold T 0.9 results in the following list of IDs: 3987, 6344, 55999, 108584, 242589, 243504, 244126 from the “2s9” family. Simulating and observing the dynamical evolution of the corresponding cellular automata reveals common features that can be linguistically described in the “fuzzy” statement “A”. In all cases simulations were done in a 100×100 array with a random initial state. The evolution of CA with ID = 3987 is shown in Fig. 6.2 for up to 6,000 iterations. There are several extremely interesting features:

>

@

(a)

Just like in the “Game of Life”, several types of gliders emerge and interact forming slowly varying patterns reminiscent of biological dynamics. As in the “game of life” further detailed analysis of those gliders and their interactions may reveal interesting properties that could be used to prove such properties as universal computation.

(b)

Unlike in the “Game of Life” where there is a global tendency towards an ordered global state (after several thousands of iterations the system usually enters a low period or steady state), here the dynamics seems to be eternal. Often intelligence is related to a capacity of adapting to an environment such that there is a perpetual survival (event though some structures vanishes, they are replaced with some similar other). Therefore in the next

100 6 Sieves for Selection of Genes According to Desired Behaviors

we will call such behaviors as A: “Intelligent life” as opposing to complex behaviors (like the Game of Life) but where after some (usually long) transient the “living-like” properties ceases to a low periodic or steady global state. For the next cell ID in the list (6344), as seen from Fig. 6.3 such an “Intelligentlife” behavior is observed. Now there is even much resemblance to the “Game of Life” but even after iteration 8,000 there is no sign of some “implosion” into an ordered low periodic global state. In my opinion, such “Eternal life” behaviors are more suitable for further investigation than the classic “Game of Life”. Indeed as shown previously, the “Game of life” is part of another class of behaviors, characterized by U<1, i.e. of the “imploding” type. Real biological phenomena seem to be driven by a force which keeps things alive by perpetual changes, very much like the dynamics depicted in Figs. 6.2 and 6.3.

Fig. 6.2. Snapshots of the dynamic evolution of CA with ID = 3987 exhibiting the property called here “Eternal life”

Simulating all other CA from the list gives similar evolutions with only two exceptions, i.e. for the cells with ID = 108584 and ID = 244126. In those two cases, relatively complex dynamics emerges but it eventually converges toward a lowperiod global period. Note however that there are only two exceptions from all seven genes (i.e. 28%) listed as the result of the sieving process. This situation raises a question about how precise are the results of the sieving process. As we already indicated in previous chapters, the vector of complexity measures has an inherent degree of uncertainty, induced by the use of a particular

6.3 Examples and Applications of the Double Sieve Method 101

initial state, a finite running time and a relatively small number of cells in the simulation process. Is it thus possible that for some IDs (like the two mentioned above) the resulting vector of emergence measures is an exception rather than the average case. Note however that such exceptions are usually less than the majority of genes filtered-out by a sieving process and they have to be accepted as an uncertainty price paid for the speed of locating interesting behaviors using the sieves. Such errors decrease if measures of emergence are evaluated by averaging over a large numbers of different initial states. Such uncertainties are actually common to real life problems as they were revealed in mathematics [86] and physics [87].

Fig. 6.3. Snapshots of the dynamic evolution of CA with ID = 6344 exhibiting the “Eternal – Life” property

6.3.2 Classic “Life”: Using Sieves to Locate Similar Behaviors

Let now consider the well known “Game of Life” cellular automata. Its associated cell belong to the “2s9” family and has ID = 6152. The emergence measure vector x U,Var,Tr,Clus in this case is: x [0.0331 0.0010 0.5500 0.9750] . Note the “implosive” value of 0.03 for U suggesting the convergence of complex behaviors towards a low-periodic global state. Of course, this prediction on the possible behavior should be considered with a degree o uncertainty, as discussed above,

102 6 Sieves for Selection of Genes According to Desired Behaviors

knowing that some initial states may exists to contradict it. In terms of fuzzy logic the Game of Life may be characterized as: “A1: Implosive exponent of growth” AND “A2: Low value of the variance Var” AND “A3: Large transient”, AND “A4: Clustering coefficient close to 1”. An interesting question that arise is: Find CA genes leading to similar genes. The equivalent “A” statement is: “CA behaving like the Game of Life”. Let us define the following sieve: P A x P A1 x P A3 x P A4 x , where: P A1 exp 1 ˜ U  0.03 , P A4



P A3

0.5  0.5 ˜ tanh >10Tr  0.3 @ ,

and



exp  0.1 ˜ Clus  0.975 ,

Such sieves were defined ignoring the Var parameter. A list of ID obtained for an acceptable truth degree T 0.99 includes the “Game of Life” as well as other 13 genes: 6152, 11127, 11175, 11895, 13719, 14039, 15271, 23847, 44223, 97951, 238292, 239451, 245913, 250018. As seen in Fig. 6.4 what is specific for most of these genes is a slow evolution towards a globally stable or low periodic (ordered) state during which some shortlife compact formations (gliders) emerge. The size and the frequency of the emerging gliders as well as the speed of convergence towards a global ordered state depend on the particular gene and can be studied individually.

Fig. 6.4. The dynamics of a CA (ID = 11127) selected by the “Similar to Game of Life” sieve. Note the emergence of gliders with a higher frequency during the first iterations. After several thousands of iterations the CA evolves to a more ordered global state

6.3 Examples and Applications of the Double Sieve Method 103

As in the previous case, many other sieves can be used to locate similar behaviors. In all cases it is important to tune the parameters of the sieves such that the result is a manageable list of IDs with at most tens of CA cells. By further simulation of these cells one may infer conclusions that can be used to improve the definition of sieves with respect to an identifiable behavior. A similar “game of life” behavior is observed for another member selected by the sieve, namely the ID = 44223, as seen in Fig. 6.5.

Fig. 6.5. The dynamics of another CA (ID = 44223) selected by the “Similar to Game of Life” sieve. Note the emergence of gliders with a higher frequency during the first iterations. After several thousands of iterations the CA evolves to a more ordered global state

For reference, the dynamic evolution of the “Game of Life” CA (ID = 6,152) is given in Fig. 6.6 for the same initial state. Note that although there is a slow evolution with a lot of activity among the emerging gliders, after enough iterations (here more than 2,000), unlike in the case of “intelligent life” behaviors, the CA system enters in a highly ordered global state. Such ordered global states can be metaphorically described as remains of a civilization which was not capable to maintain the “living” state for ever, as opposed to “intelligent life” where such living pattern appears to be maintained for ever. So far, using the sieve method combined with experiments, suggests that the key ingredient in reaching “intelligent life” behaviors is a “slow growth” as described previously.

104 6 Sieves for Selection of Genes According to Desired Behaviors

Fig. 6.6. Dynamics of the classic “Game of Life” CA (ID = 6152)

There is enough evidence to suggest that such “intelligent life” behaviors may include systems to be further investigated in more depth to reveal applications related to the field of computational intelligence. 6.3.3 Other Interesting Emergent Behaviors

As indicated above, it is found that interesting emergent behaviors (lets call them highly complex) occur often for large transients and slow explosion (referred in Chap. 5 as “near edge but unstable” category). A crisp double sieve can be established to locate these highly complex emergent phenomena, as shown in Fig. 6.7. Let simulate CAs for several of the 252 cells selected by the above double sieve. The first example, shown in Fig. 6.8, is a run of the CA with ID = 7803. Starting from a random initial state spatial cluster, the system evolves slowly into a more organized family of clusters containing traveling gliders, which interact producing novel types of gliders. The emergence of gliders is a significant phenomena since an in depth study of the glider production and interaction would often lead to the conclusion that all fundamental logic functions can be emulated by spatial interaction of such gliders and therefore universal computation can be demonstrated. Although, so far the “Game of Life” phenomena was the mostly investigated for its gliders, the double sieve method reveals hundreds of similar CA genes within the “2s9” family (Game of Life being itself a member of the family) confirming recent findings that complex behaviors are actually much more often present in cellular automata than initially assumed [74].

6.3 Examples and Applications of the Double Sieve Method 105

Fig. 6.7. A double sieve for selecting highly complex behaviors

Fig. 6.8. Emergence of gliders in a CA with ID = 7803

106 6 Sieves for Selection of Genes According to Desired Behaviors

Fig. 6.9. Highly complex behavior found by the double sieve method

Fig. 6.10. Emergence of interacting gliders, similar to the “Game of Life” cell

6.3 Examples and Applications of the Double Sieve Method 107

Another example from the same sieve is depicted in Fig. 6.9 for ID = 5315 and may be regarded as an example of emerging self-reproductive patterns. This is not a case of trivial self-reproduction as in the case of Fredkin genes (as for ID = 300 and ID = 682 of the “2s5” family in Chap. 5, Fig. 5.7 and 5.8) but rather a much more complex phenomenon. When enough such self-reproductive patterns occur during the finite array, the process stops. Further studies of such self-reproductive patterns may reveal very interesting computational properties. Another interesting example revealed by the sieve is cell ID = 6216 (see Fig. 6.10) with its associated CAs exhibiting a dynamic similar to that of the “Game of Life” (ID = 6152). 6.3.4 Sieves to Locate Feature Extractors

In the next another set of sieves is introduced, with some practical relevance in various pattern recognition problems. Experimental simulations indicate that “imploding” behaviors with a low exponent of growth may be used as feature extractors. It is also assumed that the more complex is the nature of the signal processing the larger is the transient parameter. Therefore a sieve for pattern extraction may be defined as in Fig. 6.11. It is interesting to note that the “Game of Life” cell popped-out from this sieve as well. This clearly indicates that besides feature extraction, universal computation (as a result of glider collision) may be also found among the cells selected by this sieve.

Fig. 6.11. Double sieve for identifying feature extractors or universal cellular universal computers

108 6 Sieves for Selection of Genes According to Desired Behaviors

As seen in Chap. 4, a large percentage of cells (almost one third) belong to the category of “imploding” patterns, potentially useful for feature extraction and other such spatial filtering processes. By imposing the additional “large transients” sieve, we hope to reduce the number of genes significantly enough to allow an in depth investigation of their properties. Several examples of CA cells selected from the above double sieve are depicted in Fig. 6.12. We have selected only those cases that may be interpreted as feature extraction. In each case the final steady state (representing a transform of the initial state) was obtained after a relatively large number of iterations. Particularly interesting is the case of ID = 5607 which appears to emphasize any initial state cluster with no or less curvatures in its shape while it removes most of the pixels of the shapes that have certain curvatures. Such cells may be used to build a classifier capable to recognize the figure “1” in a written text. Another interesting cell is the one with ID = 3619, where some parts of the initial state patterns are removed. An in-depth further analysis would probably reveal some practical applications. Many other cell genes are also on the output list of the above double sieve that may deserve further investigation. Such genes can do things such as removing circles or rectangles, edge extraction and so on. In evaluating the properties of such genes it is useful to use an initial state containing various shapes and figures so that human observers may associate a meaning to the transformed state obtained as the terminal state of the cellular automata.

Fig. 6.12. Three examples of feature extractors selected by the sieve in Fig. 6.11. Different values of alpha (parameter in the sieve definition) were used

6.3 Examples and Applications of the Double Sieve Method 109

6.3.5 Pink-Noise Generators

In previous sections a sieve for isolating “good random number generators” was defined based on the observation that such systems are characterized by Clus 0.5 and by a variance within the boundaries v1  Var  v 2 . Noise generators of the “pink” type, with prominence of low frequencies may be also detected using a closely related sieve. In such sieves, a larger value of the Clus coefficient is sought, the larger its value the more low frequencies being present within the signal spectrum. Such patterns have a practical relevance in a novel compression scheme (to be detailed later in Chap. 8 and used to construct a codebook). Depending on the nature of the signal to be compressed, which can be characterized by the clustering coefficient, one can use some of the sieves to be defined here to get efficient codebooks which can be characterized only by the ID of the generating CA. The first sieve is defined as: P A1 Clus exp> 100 ˜ Clus  C 0 @

and the second is defined as: P A2 Var 1  Var  0.05

The composite sieve corresponds to a fuzzy AND between the above and therefore P A1 P A2 . Now getting different values for the desired clustering coefficient C 0 and tuning the degree of truth such that the resulting number of genes is small enough to allow simulation of their corresponding CAs, one will get different lists of CA genes. For instance if C 0 0.7 , and for a degree of truth T 0.99 the following two cells result from the sieve: ID = 4369, and 118253. As seen in Fig. 6.13 the behavior is of the expected type. PA

Fig. 6.13. Dynamics of a CA with a gene resulting from the sieve: “Pink noise generator with C 0 0.7

110 6 Sieves for Selection of Genes According to Desired Behaviors

6.3.6 Sieving and Intelligence – Evolving a List of Interesting Genes

As seen from the previous examples, finding sieves to select desired emergent behaviors among large populations of cellular systems is a matter of educated guess and experiment. It can be regarded as an intelligent process of interaction between the human observer and the artificial entities (in our case the cellular automata), mediated by a synthetic characterization of the CA behavior by a number of complexity (or emergence) measures. Since algorithms are defined to compute those measures for the entire family under observation (e.g. it requires no more than 20 h on a modest laptop of nowadays to compute the measures for the entire “2s9” family) some educated guess in choosing the sieves provides shortlists of candidates supposed to have “interesting” emergent behaviors. Such short lists can be simulated and analyzed by the human observer in a reasonably short time providing hints to further tune the sieves. This process is similar to the process of getting acquainted to a new circumstance (e.g. meeting a new person or facing a novel life situation) and is essential for what we call “intelligence”. The opposite kind of action is to simply take a brute force approach, where each particular cell is taken into consideration, simulated and observed. But this takes an enormous amount of time, often not available in practice. That is why commonsense says that having intelligence helps in solving a problem quickly. Is the solution optimal? Quite often not, but it is better than what you may come up with after a dumb search trough the whole space of possibilities. In our case, studying how a sieve in our case acted with respect to a certain behavior, provides hints that gradually tune the sieve to improve the optimality of the solution. The above discussion reveals an aspect which expands beyond the scope of this book, where we are looking to find cellular automata with a certain behavior. The conclusion is more general and can be applied to general systems as a process of discovery: It can be summarized as follows: 

 



Find a set of synthetic measures to characterize the observed system (e.g. in real life problems our language facilitates descriptions about humans like bad, good, etc. and defines degrees to which such qualities are observed). While enough variations of a certain system are presented, a database of such measures is formed. Given a desired behavior, define sieves starting from simple observations of the relationships between quantifiable measures about the quality of the object and observed behaviors of the object. Apply the sieves and observe the match or mismatch of the resulted objects with the desired behaviors. Whenever mismatches occur, tune the sieves accordingly.

Coming back to our CA objects, we applied such a discovery process with several (no more than four iterations in tuning the sieves) in an attempt to get the most interesting CA cells from the “2s9” family. Such cells belong to the “intelligent life” category and by declaring them interesting we suggest that such cellular

6.3 Examples and Applications of the Double Sieve Method 111

systems have properties that challenge our intelligence, a property which often is labeled as “complexity” in natural languages. The sieves (resulted during the fine tuning process) are: 4 P A1 U exp ª 0.4 ˜ U  2 º

«¬

»¼

and P A2 Var 0.5  0.5 ˜ tanh>10 ˜ Var  0.1 @

with the composite sieve defined as P A P A1 P A2 . Using an acceptable degree of truth of T 0.9 , the following list of 67 genes results as seen in Fig. 6.14. With a degree of truth of T 0.5 the list expands to 611 members.

Fig. 6.14. A list of the most “interesting” genes from the “2s9” family

Among this list, a visual inspection of the underlying cellular automata reveals the following sub-list as being “interesting”: 53007, 54655, 55999, 56703 (presence of gliders, slow explosion), 72200, 89759, 239518, 240542 (similar with the “game of life”), 242076, 242078, 242589, 242996, 242997, 244126, 244380, 244531, 244817, 244893, 245041. Are the other genes in the list “not-interesting”? Not quite, but the sieve, defined as above seems to be not well fitted to our expectation. A visual analysis

112 6 Sieves for Selection of Genes According to Desired Behaviors

of the CAs associated with remaining genes reveals long transient behaviors converging towards highly ordered (low periodic) global states. Therefore, they were classified as “not-interesting” based on a subjective assumption of the “intelligent observer” that interesting is associated with a certain complexity as encountered in his life. Still it would be interesting to refine the sieve for a better tuning to the expectations of the intelligent observer. It turns out that the interesting genes selected among all, share such a common measurable feature, i.e. their corresponding variance ranges as 0.2  Var  0.4 . By redefining the sieves accordingly, a shorter list of genes becomes available which contains individuals better tuned to the expected objective. This continuously sieving tuning process is specific for any adaptation process or for any interaction between two intelligent entities. What is really interesting about it is the possibility to learn desired behaviors by iteratively tuning numerical parameters of the sieves to be compared with a limited set of defined measures of complexity. This is a confirmation of the usefulness of such measures as defined and introduced in Chap. 4 and the iteratively tuning process of sieves allows for the design of CA suited for various classes of signal processing applications, like those presented in the next chapters.

7 Predicting Emergence from Cell’s Structure

7.1 Introduction In Chaps. 4 and 5 several measures for emergence were introduced and as seen in Chap. 6 they can be integrated in an intelligent sieving process to select among a huge number of possible cells only those leading to CA dynamics that is meaningful for certain desired tasks. Still, evaluating the measures of emergence needs extensive running of the CA system for each member of the family, giving thus important limitations in terms of computing time. While the CA is mainly determined only by the cell structure (assuming that all cells are identical) and by the interconnection between cells (also assumed to be regular and simple) it would be reasonable to investigate the possibility to predict the CA behaviors solely based on the structure of the cell. That will dramatically reduce the computation time eliminating the need to simulate the entire CA. The main questions around which this chapter is build are the following: – – –

Is there any possibility to predict the CA behavior without simulating the cellular model? Are there any relationships between the cells’ structure as described by its binary gene and the observed behaviors of the underlying CA? Can we establish a mapping between the gene space and a hypothetical “behavior space”, which may be eventually described by the set of complexity measures (U, Trans, Var, Clus)?

In the case of continuous-time Reaction–Diffusion cellular systems, the theory of local activity [7] was already successfully employed to detect regions of complexity called “edge of chaos” in the cell parameter space by simply examining the cell [9, 10, 11]. However, in those cases it was not possible to predict precisely if a cell with parameters within the “edge of chaos” region will give emergent behaviors. The reason stands in the existence of some additional parameters related to the coupling between cells, the diffusion coefficients. These parameters was not included in the local activity theory and therefore they should be experimentally adjusted to obtain emergent behaviors. Within this chapter we will investigate the case of discrete binary time cellular automata and we will assume the same connectivity (simply defined by the

R. Dogaru: Predicting Emergence from Cell’s Structure, Studies in Computational Intelligence (SCI) 95, 113–132 (2008) www.springerlink.com © Springer-V erlag Berlin Heidelberg 2008

114 7 Predicting Emergence from Cell’s Structure

neighborhood topology) among all cells. Therefore there is no connectivity parameter and the behavior should be entirely determined by the cells’ structure and its neighborhood.

7.2 Relationships Between CA Behavior and the Boolean Description of the Cell Let us focus on the following question: Are there any relationships between the cells’ structure as described by its binary gene and the observed behaviors of the underlying CA?

Fig. 7.1. A parametrization of the 2s5 family with respect to the U measure of emergence. A particular cell is depicted with a gray color ranging from white for “passive” (U < 1) to black for “highly unstable” (U >> 1) and its corresponding pixel is located in the 32×32 tableau according to its binary ID. Note the regularity of the distribution, indicating that a connection between cells’ structure and behavior may be established

In order to grasp an answer to this question let us consider a matrix representation for all 1,024 Boolean cells from the “2s5” family, as seen in Fig. 7.1. In the next we will call such a representation a parametrization P as defined in other works [74]. Note that in other related works [7] a similar concept was introduced under the name “decoding card”. A parametrization matrix P is defined as a visually convenient form of representing an entire family of cells where each matrix element Pi , j is uniquely associated to a member of the CA family. The value of Pi , j is associated with a behavioral quality e.g. one of the previously defined measures of emergence or with a fuzzy member-

7.2 Relationships Between CA Behavior and the Boolean Description of the Cell 115

ship function indicating the degree of truth corresponding to a given sieve (e.g. how good a random number generator is the CA using that cell). If a method to measure emergence based solely on cells structure is available, that method will produce a number assigned to the same Pi , j element of a parametrization. Therefore it is convenient to compare parametrizations based on two different methods for measuring emergence (experimental, based on running the CA, and analytic based on cells structure and its neighborhood). By doing such a comparison it is possible to validate or not a method for measuring emergence and complexity. The line i and column j indexes are integers representing certain non-overlapping groups of bits in the cell ID definition. For instance, in the case displayed in Fig. 7.1. five least significant bits from the 10 bits ID are assigned to i while the remaining 5 bits are assigned to j according to the following rule: The upper left pixel corresponds to ID = 0, then ID is increased by one on the vertical column until ID = 31 (lower leftmost pixel) then the process of counting the genes continues with the next column and goes on until the last pixel (lower rightmost) corresponding to ID = 1,023 is reached. Each pixel in the image is represented as a gray level associated with the value of Pi , j , here assigned to U (the exponent of growth). Observing Fig. 7.1 leads to a positive answer to our question. Indeed, observe that except several isolated cases, all pixels corresponding to the three main categories “unstable”, “edge” and “stable” behaviors are regularly distributed and some simple rules for predicting the type of behavior may be inferred from the string of bits defining the cells ID. Still we have to deal with some exceptions. They may be related either to the precision of the measurement method (where only a specific initial state is used instead of averaging over many, to reduce computational effort) or with a more subtle relationship between structure and behavior, particularly in the interesting border regions ( U | 1 ). The reader may check that indeed a such a “good” rule for predicting “unstable” behaviors (including the “near edge” ones) is the following: ID = 10xxxxxxxx OR ID = 01xxxxx1x OR ID = 0xxxxxxx01 And a good rule for predicting “edge” behaviors (i.e. U = 1) is the following: ID = 110xxxxxxx OR ID = 111xxx0xxx OR ID = 01xxxxxx00 OR ID = 00xxxxxx1x, where an x bit is either a 0 or a 1 bit. The above suggests that a theory similar to that of local activity but developed for Boolean discrete-time cellular systems is possible and it has to be further developed. It will eventually give the analytic formulation of how to deduce rules as those mentioned above for a larger category of systems (e.g. with different number of cell inputs and with different topologies). Observe that although the above rules apply for a large majority of cells, there are still some irregular boundaries to be predicted, where the relationship between ID (cell’s structure) and the shape of the boundaries is not so obvious. Such refinements shall be pursued for a complete theory of predicting emergence based on cells’ structure.

116 7 Predicting Emergence from Cell’s Structure

7.3 Parametrizations as Tools to Locate Similar Behaviors From the above definition of a parametrization it follows that for a given family of cells with a gene ID defined by n bits there are many possible parametrizations, as many as the arrangements of bits used to define the line and column indexes. Thus, the following question arises: What is a “good parametrization”? In the following we will assume that a good parametrization is one with less changes between adjacent elements Pi , j . Therefore a convenient measure of the overall parametrization quality may be defined as: Q

n11 n 21

(7.1)

¦ ¦ Pi 1, j  Pi 1, j  Pi , j 1  Pi , j 1  4 Pi , j

i 2 j 2

becoming 0 if there is no change at all (best possible parametrization) and is larger for “bad” parametrizations. Therefore one may easily write a program to arrange a given set of emergence measures for an entire CA family into various parametrizations and compare the resulting overall qualities such that in the end the parametrization with smallest Q value will be selected as the best choice. Less “change” in the parametrization means that it would be easier to observe a relationship between cells’ structure and the behavioral characteristic and therefore it gives a smoother way to a consistent theory relating cells structure to the CA emergent behavior. The right side of Fig. 7.2 is an example of a “good” parametrization as compared to a “bad” one depicted on the left side. It is clearly much easier to infer a simple relationship between cells ID and the emergent behaviors (e.g. white pixels representing large values of the clustering coefficient) from the “good” parametrization of the right of Fig. 7.2. 2s5 Column=[8 7 5 1 9] Line=[3 4 6 10 2] Pi,j=Clus

2s5 Column=[4 7 2 1 6] Line=[3 8 9 10 5] Pi, j=Clus

5

5

10

10

15

15

20

20

25

25

30

30 5

10

15

20

25

30

5

10

15

20

25

30

Fig. 7.2. Two different parametrizations (the ID bits used to create the column and line indexes are indicated above each picture). The best parametrization (Q = 0.21) is the one on the right while the left one is among the worse possible (Q = 0.43). In this case the measure of emergence considered to be parametrized was Pi , j Clus . White pixels correspond to values of the clustering coefficient close to 1 while black pixels correspond to 0-valued clustering coefficients

7.3 Parametrizations as Tools to Locate Similar Behaviors 117

1s5 Column=[4 7 2 1 6] Line=[3 8 9 10 5] Pi,j=Clus

1s5 Column=[4 7 2 1 6] Line=[3 8 9 10 5] Pi,j=Clus

5

5

10

10

15

15

20

20

25

25

30

30 5

10

15

20

25

30

5

10

15

20

25

30

Fig. 7.3. Parametrizations of the same cells in different connectivity. Left: one-dimensional CA (1s5); Right: two-dimensional CA (2s5). Note some general similarity (as imposed by solely the cell’s structure) but also some differences (effects of the connectivity)

Parametrizations are also useful tools to compare among the same families of cells when put into different interconnectivities. This is the case with the 1s5 and 2s5 CA families. In the first case, the grid topology is one-dimensional while in the second case the interconnectivity is two-dimensional. Using the same “good” parametrization as in Fig. 7.2 one can observe differences and similarities in Fig. 7.3. It is interesting to observe a global similarity (given by the cell structure) but also some differences explained by the different neighborhood connectivity. More in-depth study is needed to refine an analytical model to include rigorously both effects, but nevertheless the parametrization is a good preliminary tool to be used as a starting point for such an analysis. A “good” parametrization has another practical use: If the emergence measure assigned to Pi , j has a certain meaning (e.g. as obtained from the sieving process) the parametrization will group cells giving similar emergent behaviors in a topologically connected region within the parametrization. Therefore once we have detected an “interesting” behavior it is easy to identify other cells having the same behavior by simply looking around in the graphical representation of a “good” parametrization. As an example, consider a detail from a random parametrization of the 2s9 family, represented in Fig. 7.4. The quality measured here is the transient length (larger for interesting, complex behaviors, represented here with darker colors). The well known Game of Life (ID=6152) can be easily identified within the entire parametrization. But looking globally at the parametrization reveals some similar neighbours with the same quality (the black strip down to the location of “Life”). Several IDs from this strip can be easily determined once we know the parametrization. A short list includes ID = 6,216, 6,280, 6,664, 6,600. They differ from the original gene of “Life” by mutations in any of the bits 6–9 of the original ID (here the less significant bit is denoted zeroth bit). Running their associated CAs reveals that the emergent behavior is very similar to the Game of Life, thus confirming the predictive power of a parametrization for cells within a small neighborhood and with the same value of the measured emergence quality.

118 7 Predicting Emergence from Cell’s Structure

Conway's "Life" ID=6152

All cells with the same property (long transient) or "black" within the "G.of.Life" cells exhibit the same properties. A list of IDs: 6216, 6280, 6664, 6600 etc.

Fig. 7.4. Detail of a parametrization of the 2s9 CA family around the cell of the “Game of Life”. Black pixels in the figure correspond to large Trans values. Cells leading to similar behaviors are easily detected as belonging to the same “black” vertical strip containing the “Game of Life” cell

In fact it can be considered that any “good” parametrization in the sense of the above definition is a function specified as a database describing the relationship between cell’s structure and its underlying CA behavior. Using modeling tools such as feed-forward neural networks or radial basis functions one can extract a synthetic description from this database which may be further used to predict the CA behavior solely based on the cell’s ID. Modeling of parametrization functions with neural networks is particularly well suited for cases with many entries where establishing of a large database (e.g. we needed some 260,000 such entries for the 2s9 family) is a time consuming process. Instead some randomly selected IDs will form a partial parametrization while a neural network capable to generalize will be able to fill in the missing gaps.

7.4 The Theory of Probabilistic Exponents of Growth In Chap. 5, the exponent of growth U was introduced as a measure of “implosion”, “explosion” or a delicate balance between them, often associated with interesting complex CA behaviors. Its determination was based, much like for the other measures introduced in Chap. 4, on simulating the CA with a given cell ID. Here we take a different approach leading to an analytic treatment with an important gain in terms of computational complexity: The idea is to observe if an initial state formed as a spatial cluster of cells each assigned a probability ½ of being in state “1” grows or shrinks during the time evolution. In terms of probability, all other cells in the initial state have a

7.4 The Theory of Probabilistic Exponents of Growth 119

probability 1 of being in either 0 or 1 state (quiescent state) and after one iteration the following may happen: (a) The total number of cells in uncertain state (probability is ½) grows – this situation correspond to a growing or “explosion” process (U > 1). (b) The total number of cells in an uncertain state (probability is ½) decreases – this situation correspond to an “implosion” process (U < 1). (c) There is a delicate balance between growing and implosion such that almost the same number of cells maintain an uncertain probability during the time evolution of the CA. Here we intentionally describe the growing or imploding processes based on probabilities. In terms of probabilities each cell can be considered a nonlinear system with n inputs and one output. The cells output probability po for being in a certain state (1 or 0) can be computed as a nonlinear function FP of the probabilities for each input of being in a given state (e.g. 1 or 0): po1

FP  ID, p11 , p 21 ,.. pn1 ,

(7.2)

where p1 denotes a probability of being in state “1”. In the following we will call FP the cells function of probability. One can easily calculate the probability of being in state “0” as p 0 1  p1. The theory of random variables ensures that a nonlinear function FP is uniquely defined by the cells ID and therefore it can be computed using a deterministic algorithm1. This is the basis of the method exposed next to calculate a complexity measure similar to U but solely based on knowing the FP associated with a given cell ID. The neighborhood connectivity is considered in the definition of a probability profile among all cells in the neighborhood as exemplified nest for the case of one-dimensional CA, while a global measure of emergence is in a direct relationship with the probability profile. Let us assume that a group of n adjacent cells in a CA are initially in an uncertain state (with such a cell being characterized by p1 p 0 0.5 . The remaining cells are either in “1” or “0” state. We might consider all four possibilities: (1) all remaining cells are in “1”; (2) all remaining cells are in “0”; (3) the cells to the left of the initial cluster are in “0” and the cells to the right in “1”; (4) the opposite of (3). For semi-totalistic cells (i.e. symmetric) (4) and (3) are the same. The question 1Our algorithm is based on the piecewise-linear representation of any type of cell, as indicated in Chap. 3. Once the probability density of certain input variables are known, the probability density of their sum can be easily computed. Since that sum is the entry “j” in a look-up table defining the cell, it gives the probability that cells’ output is y j , i.e. one of the bits defining the ID. The probability po is thus defined as the weighted sum

po

N 1

¦ yj pj .

j 0

120 7 Predicting Emergence from Cell’s Structure

is what are the probabilities of all cells after one iteration, and how this situation allows to predict the general behavior of the CA? Before answering this question let us discuss several preliminary issues. An uncertainty index will be defined as a basic tool, then an example is given on how these uncertainties can be computed for a certain cell and a given CA neighborhood. In the end we will see that a probabilistic exponent of growth can be defined and computed entirely as a function of the bits defining the gene (the binary representation of the ID) and of the neighborhood arrangement. 7.4.1 Uncertainty Index of a Cell, Active and Expansion Areas Let us define an uncertainty index P for a cell k as follows: Pk

1  2 p

1 k



1 ,

(7.3)

where p1k is the probability of cell k to be in state 1. Note that if all cells are in an uncertain state then P 1 , while if they are all in certain states then P 0 . The above uncertainty index is a computationally simpler alternative to the entropic uncertainty H k  pk log 2  pk  1  pk log 2 1  pk . One can easily verify that both functions coincide for pk 0 , pk 1 / 2 , and pk 1 . An important property of the uncertainty index is that it is independent on the quiescent status (1 or 0) considered for the cell k. In what follows we will call any of these states (common for a group of cells except those randomly selected in a initial state cluster) a quiescent state. A cell in a quiescent state has 0 uncertainty. In the next we will observe the transition of a minimal set of cells (connected according to the specified cellular automata topology and neighborhood) and will use tools of information theory to compute the uncertainty profile for all cells within this set, in the next iteration. The profile of the initial state is chosen such that it will represent a cluster of n adjacent uncertain cells (i.e. P 1 , or p1 1 / 2 ) within a larger number N of quiescent cells (being in either “1” or “0” state and therefore in a certain situation characterized by P 0 ). Let us denote all cells which were initially in a certain state as belonging to the expansion area of the CA while the remaining cells are in the active area of the CA. By simply evaluating the uncertainty of the cells in the expansion area after one iteration one can predict if there is a growth or not. If uncertainty stays 0 there is no growth and the degree of uncertainty obtained in the active area indicates whether the process of “implosion” is a faster or a slower one. By the contrary if uncertainty is observed in the expansion area, there is a growth of the initial cluster of uncertain cells and its magnitude may be quantified as the average of uncertainties over all cells in the expansion area.

7.4 The Theory of Probabilistic Exponents of Growth 121

The above observations represent the principle of the exact method to compute exponents of growth based solely on the cells’ structure. The method will be detailed in the next. 7.4.2 Minimal Set of Cells to Compute the Probabilistic Exponent of Growth In order to specify the values of n (number of uncertain cells in the initial state) and N (minimum number of cells in the set needed to compute the probabilistic exponent of growth properly) one should take in consideration the neighborhood connectivity. It should also consider that as long as all inputs to a cell are certain (1 or 0) the output is certain too. Therefore there will be no need for more than N cells in the CA, as long as the cases when cells will receive “certain” inputs have no relevance for computing the exponent of growth. Figure 7.5 shows clearly that in the case of the 1s5 type CA, n = 5 and N = 2n – 1, i.e. N = 9. The expanded area in this case is formed of cells k = 1, 2, 8 and 9 while the active area is formed by the five cells in the middle i.e. k = 3–7. In general, for any CA, the active area will be formed by the cells within the CA neighborhood while the expansion area is formed by all cells in the neighborhood of the active area such that in the next state there will be at least one uncertain input from a cell within the neighborhood. Once a cell receives only certain inputs, it is not relevant for computing the exponent of growth since it will provide a certain output ( P 0 ).

Fig. 7.5. Minimal set of CA cells involved in computing the probabilistic growth index, for the case of 1s5 CA family. In this case there are N = 9 cells and the probabilistic exponent of growth is fully determined by the cell ID, the prescribed initial state uncertainty profile (upper row in the figure) and the “next state” uncertainty profile (lower row in the figure)

122 7 Predicting Emergence from Cell’s Structure

Using simple probabilistic reasoning, it is easy to show that for each cell k in the next state, the probability p1k of being in the “1” state is a linear combination of the bits representing the ID of the cell. For semi-totalistic cells with five inputs, as defined in Chap. 3, the binary representation of ID is a vector Y y9 , y8 ,! y0 with y0 representing the less significant bit. The value q of

>

@

the quiescent state (0 or 1) also influences the formulae of p1k . As seen in Fig. 7.5. for each of the nine cells considered in the 1s5 case the detailed formulae for each of the cells involved are: Quiescent state p 1 p11 p12 p13

p14 p51

FP  ID,1,1,1,1,0.5

FP  ID,1,0.5,0.5,0.5,0.5 FP  ID,0.5,0.5,0.5,0.5,0.5

(7.4)

1  y9  2 y8  y7 , 4

(7.5)

1  y 9  2 y8  y 7  y 4  2 y 3  y 2 8 ,

(7.6)

FP  ID,1,1,1,0.5,0.5

FP ID,1,1,0.5,0.5,0.5

1  y9  y8 , 2

1  y9  3 y8  3 y7  y6  y4  3 y3  3 y2  y1 , 16

1  y9  4 y8  6 y7  4 y6  y5  y4  4 y3  6 y2  4 y1  y0 . 32

(7.7) (7.8)

Quiescent state p 0 p11 p12 p31 p14

FPID,0,0,0,0,0.5

FP  ID,0,0,0,0.5,0.5

FP  ID,0,0,0.5,0.5,0.5

FP  ID,0,0.5,0.5,0.5,0.5

1  y1  y0 2 1  y2  2 y1  y0 , 4

1  y7  2 y6  y5  y2  2 y1  y0 , 8

1  y8  3 y7  3 y6  y5  y3  3 y2  3 y1  y0 , 16

(7.9) (7.10) (7.11) (7.12)

p 15 is computed according to (7.8)

The corresponding values of the uncertainties u1, to u5 , forming the next state uncertainty profile, are then computed by simply applying (7.3) to the above probabilities. In the following we will denote u k0 the uncertainty computed in the case of “0”-quiescent state ( q 0 ) and u1k in the case of “1” quiescent state. The same uncertainty profile may be used to compute exponents of growth the both “1s5” and “2s5” cases since the same input combinations occur in the “2s5”

7.4 The Theory of Probabilistic Exponents of Growth 123

case but in a different topology as seen from Fig. 7.6. This situation takes in consideration the fact that the cells are semi-totalistic and therefore permuting any input except the one corresponding to the central cell, has no effect on the output. In the case of arbitrary cells, the same method may be applied but then there is no symmetry around the central cell and therefore the uncertainty for each cell in the “next state” shall be computed independently.

Fig. 7.6. CA cells involved in computing the probabilistic growth index, for the case of 2s5 CA family

7.4.3 Computing the Cells Function of Probability In the above we used some special cases of the cells function of probability (FP) when the input probabilities were defined according with some of the possibilities imposed by the initial state profile. In fact, an analytic function of FP can be established for any type of cell, starting from the definitions and taxonomies introduced in Chap. 3, Table 3.4. Here we will exemplify the procedure for the case of “1a3” cells i.e. Boolean cells with three inputs. In this case, the excitation defined n

by e.g. (3.4) V ¦ 2 k 1 u k is an integer between 0 and n (for the 1a3 cells, n = 3) k 1

having the significance of an index for the ID bit yV . There are eight possible values for V in the case of Boolean functions with three inputs. Let assume that such a cell has assigned a set of three input probabilities p1 , p 2 , p3 interpreted as: The probability that input “k” is “1” is p k . Then, the probability that the output is “1” can be defined as “the probability that V is 0 and yV 1 ”, or “the probability that V is 1 and yV 1 ”,…or “the probability that V 7 and yV 1 ”. Using principles of probabilistic reasoning the above phrase translates into the following formula:

124 7 Predicting Emergence from Cell’s Structure po

1  p3 1  p2 1  p1 y0  1  p3 1  p2  p1 y1  .. p3  p2  p1 y7 p3 p2 p1  y7  y6  y5  y4  y3  y2  y1  y0  p3 p2  y6  y4  y2  y0  p3 p1  y5  y4  y1  y0  p2 p1  y3  y2  y1  y0  p3  y4  y0  p2  y2  y0  p1  y1  y0  y0 .

(7.13)

The above clearly indicates that FP is a nonlinear function in the input probabilities, of a polynomial structure, while the coefficients of the polynomial are solely determined by the bits defining the ID of the cell. Similar formulae may be deduced for any possible Boolean cell, including the semitotalistic cells with five inputs used in either “1s5” or “2s5” CAs. Assuming input probabilities p1 , p 2 , p3 , p 4 , p5 with p3 indicating the probability that the central input is 1, the resulting formulae for the output probability is: po S1>1  p3  y0  4 y1  6 y2  4 y3  y4  p3  y5  4 y6  6 y7  4 y8  y9 @   S 2 >1  p3  y0  3 y1  3 y2  y3  p3  y5  3 y6  3 y7  y8 @   S 3 >1  p3  y0  2 y1  y2  p3  y5  2 y6  y7 @ 

(7.14)

 S 4 >1  p3  y0  y1  p3  y5  y6 @   1  p3 y0  p3 y5

where S 1 S3

p1 p 2 p 4 p5 , S 2

p1 p 2 p5  p1 p 2 p 4  p 2 p 4 p5  p1 p 4 p5 ,

p1 p 2  p1 p 4  p1 p5  p 2 p 4  p 2 p5  p 4 p5 , and S 4

p1  p 2  p 4  p5

Note again the polynomial nonlinear structure of FP, with coefficients calculates as linear combinations of the ID bits. 7.4.4 Computing the Probabilistic Exponent of Growth Before giving explicit formulae for computing the effective exponents of growth in both one-dimensional (1s5) and two-dimensional (2s5) cases, we must consider four distinct cases in relationship with the transformations of the quiescent states (the certain states that might be “0” or “1”). These cases are induced by the way a CA-cell with a given ID is transforming an input with all cells in a quiescent state. It may be easily checked that using our previous notations, only the MSB (most significant bit) and the LSB (least significant bit) of the binary representation of the cells’ ID determine any of the four particular cases. For the sake of simplicity in the next we will consider an initial state profile with “0” quiescent states: (a) Case 1: (MSB = 0, LSB = 0). In this case, the stable quiescent state is always “0”. The following formulae will be used to compute the uncertainty index ue as an average over all cells within the expansion area: The one-dimensional case (four cells in the expansion area, see Fig. 7.5.):

7.4 The Theory of Probabilistic Exponents of Growth 125

ue

1 0  u1  u 20 . 2

(7.15)

u10.

(7.16)

The two-dimensional case (12 cells in the expansion area, according to Fig. 7.6. all have the same uncertainty): ue

For the cells within the active area the uncertainty indexes ua are also computed by averaging over all cells within that area: The one-dimensional case (five cells in the active area, see Fig. 7.5.): ua

1 ª 2  u 30  u 40  u 5º . ¼ 5¬

(7.17)

The two-dimensional case (nine cells in the active area, according to Fig. 7.6): ua

1 ª 4  u 30  u 40  u 5º . ¼ 9¬

(7.18)

(b) Case 2: (MSB = 0, LSB = 1). In this case, the stable quiescent state always alternates from “0” to “1”. Here we should take special care in computing the uncertainty indexes because quite often may happen that if the starting quiescent state is “0” there will be no growing in the next state. Still, because the quiescent state changed to “1” in the second iteration it would be possible to have a growing so that the system will behave in the long run as a “growing one”. Therefore we must average ue and ua for both cases of “0” and “1” quiescent states as follows: The average uncertainty of the expansion area The one-dimensional case (four cells in the expansion area, see Fig. 7.5.): ue

1 0  u1  u 20  u11  u 21 . 4

(7.19)

The two-dimensional case (12 cells in the expansion area, according to Fig. 7.6. all have the same uncertainty): ue

1 0  u1  u11 . 2

(7.20)

The average uncertainty index ua The one-dimensional case (five cells in the active area, see Fig. 7.5.): ua

1 ª 2  u 30  u 40  2  u 31  u 41  2u 5º . ¼ 10 ¬

(7.21)

The two-dimensional case (nine cells in the active area, according to Fig. 7.6): ua

1 ª 4  u 30  u 40  4  u 31  u 41  2u 5º . ¼ 18 ¬

(7.22)

126 7 Predicting Emergence from Cell’s Structure

(c) Case 3: (MSB = 1, LSB = 0). In this case, the stable quiescent state is always the one from the initial state. Therefore since we assumed “0” initial quiescent states, this case collapses to case 1, discussed above. (d) Case 4: (MSB = 1, LSB = 1). In this case, the stable quiescent state is always “1”. Therefore, even if we assumed an initial state with “0” quiescent states, after a first iteration the quiescent state remains “1”. Consequently the computations of ue and ua will consider this situation as follows: The average uncertainty of the expansion area The one-dimensional case (four cells in the expansion area, see Fig. 7.5.): ue

1 1  u1  u 21 . 2

(7.23)

The two-dimensional case (12 cells in the expansion area, according to Fig. 7.6. all have the same uncertainty): ue

u11.

(7.24)

The average uncertainty index ua The one-dimensional case (five cells in the active area, see Fig. 7.5.): ua

1 ª 2  u 31  u 41  u 5º . ¼ 5¬

(7.25)

The two-dimensional case (nine cells in the active area, according to Fig. 7.6): ua

1 ª 4  u 31  u 41  u 5º . ¼ 9¬

(7.26)

7.5 Exponents of Growth and Their Significance For any of the above cases, a unique scalar parameter probabilistic exponent of growth U p with a similar significance to U defined in Chap. 5 is finally computed as follows: Up

­ue  1, if ue ! 0, ® if ue 0. ¯ ua,

(7.27)

The above formula can be interpreted as follows: If ue is 0, then surely there will be no initial state such that an expansion dynamics takes place. This guarantees that only “imploding” phenomena may take place. If the uncertainty within

7.5 Exponents of Growth and Their Significance 127

the active area is large (at most 1) there will be a slow implosion while if the uncertainty within this area ua is 0 or close to 0 it is quite likely that a fast implosion will take place. If ue is larger than 0, the CA may have an “explosive” dynamics and this is the more likely as ue approaches 1 (or U p 2 ). It is expected, as in the case of the experimentally determined exponent of growth U, that complex and interesting behaviors are likely for values of U p | 1 . Note that for a given cell ID and a specified interconnectivity the probabilistic exponent of growth is determined only by the structure of the cell (the bits of the cells’ ID) without the need to simulate a large CA for many iterations. Still, numerical simulations shows that it has a very good predictive capability with regards to an arbitrarily sized CA using a specified cell. 7.5.1 Predicting Behaviors from ID, an Example Let us consider the 1s5 case. Using the above formulae one finds the following condition for the existence of “explosive” behaviors, in the case of “0” quiescent state: ue ! 0

if and only if

(7.28)

2 y1  2 y0  2  y2  2 y1  y0  2  4.

It is seen that only the less significant 3 bits of the ID are relevant for this feature. Moreover, since there only eight possible arrangements of these 3 bits it is possible to check (7.28) for each of them, concluding that it holds in 75% cases, i.e. in all cases except those when all bits are 1 or 0. The milder case (corresponding to ue 0.25 ) holds when y 2 y1 y 0 011 or when y 2 y1 y 0 100 . This is the case where slow growth and emergence (potentially emergence of gliders) is more likely to occur. Expressed in decimal the above condition writes ID 8k  3 or ID 8k  4 , where k is any arbitrary integer. Simulations confirmed the prediction as seen in Fig. 7.7. where several examples of ID 8k  4 are considered.

7.5.2 Other Properties of the Probabilistic Exponents of Growth As seen from the above example, the predictive power of the probabilistic exponents of growth is impressing. But many other interesting properties of the CA can be now established by imposing conditions like (7.28). Calculating the output probabilities while imposing (7.28) reveals that in the case of 1s5 semi-totalistic CAs there are only three possible cases for the “exploding” behaviors; namely: ue 0.25 (with potential for complexity and gliders), ue 0.75 and ue 1 (mostly related to random number generators).

128 7 Predicting Emergence from Cell’s Structure

Fig. 7.7. Several examples of complex behavior including the emergence of gliders predicted by the theory of probabilistic growth. In all cases ID 8k  4

In the case of a two-dimensional topology “2s5” a similar condition will include only the two least significant bits of the gene as follows: y0  y1  1  1.

(7.29)

It holds only when the two last significant bits have different values. When it holds it gives only one possible value ue 1 . Observe the lack of small ue values, associated with emergence of gliders. This explains why gliders were actually not observed within the 2s5 family. In fact the only complexity in this case is observed for IDs in “case2” where quiescent states alternates and therefore an additional value of ue 0.5 is possible (see (7.20)). If the 2s9 family is considered instead, a condition of the same kind will include more bits from the ID making thus possible more levels of ue and therefore low positive values associated with interesting emergent phenomena. Experimental results actually confirmed that many CAs from the 2s9 family exhibit interesting emergent properties, one of the most known example being ID = 6,152 (“Game of Life”).

7.5 Exponents of Growth and Their Significance 129

7.5.3 Comparison with the Experimental Exponent of Growth It is interesting to compare the experimentally determined exponent of growth U with the newly defined measure. It turns out that for “explosive” behaviors, in addition to Up as defined in (7.27), the value of ua (uncertainty within the active area) plays an important role for a much finer discrimination among behaviors. Let us recall Table 5.2, where some representative genes from each observed behavioral class were listed. Here the same list of genes is considered but with new information added ( Up , ua ) to allow a comparison. Table 7.1a Comparison between U (experimental index of growth) and U p , ua for several genes selected in Chap. 5 as belonging to “passive” (a), “stable near edge” (b) or “edge” (c) behaviors. Category

(a) ID 107 128 136 144 152 256 264 272 280 862

U, Up= ua

0, 0.65 0, 0.32 0, 0.4 0, 0.33 0, 0.41 0, 0.08 0, 0.17 0, 0.09 0, 0.17 0, 2 0.67 Small ua

(b) ID

104 108 111 112 115 116 119 120 123 124

U, Up=ua

0.46, 0.67 0.60, 0.99 0.64, 0.64 0.13, 0.6 0.11, 0.55 0.67, 0.92 0.34, 0.58 0.47, 0.68 0.25, 0.74 0.67, 0.99 Large ua

(c) ID

131 134 135 138 139 142 143 146 147 150

U, Up, ua 1, 0.66 1, 2 1, 0.74 1, 2 1, 0.91 1, 2 1, 0.77 1, 2 1, 0.75 1, 2 Large ua

0.66 0.94 0.74 0.82 0.91 0.86 0.77 0.74 0.75 0.94

Table 7.1b Comparison between U (experimental index of growth) and U p , ua for several genes selected in Chap. 5 as belonging to “unstable near edge” (d), “nested” (e) or “explosive” (f) behaviors Category

(d) ID

41 49 69 81 101 375 463 471

U, Up, ua

4.98, 1.36, 2.98, 1.18, 1.85, 2.08, 1.18, 1.4,

1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5,

Small ue, Medium ua

0.43 0.27 0.66 0.43 0.64 0.66 0.27 0.43

(e) ID

330 341 682 693

U, Up, ua 4, 2, 1 5, 2, 1 5, 2, 1 4, 2, 1

Largest ue Largest ua

(f) ID

418 419 421 422 423 425 426 427 429 430

U, Up, ua

44.04 2 15.28 1.5 46.49 2 44.04 2 6.0 1.5 46.49 2 44.0 2 15.28 1.5 46.44 2 44.04 2 Large ua Large ue

0.99 0.83 0.93 0.69 0.68 0.83 0.92 0.75 0.68 0.6

From the above it is clear that there is a direct relationship between the probabilistic exponent of growth and the experimentally determined one. These similarities allow to infer rules (translated into “sieves” as defined in Chap. 6) to select

130 7 Predicting Emergence from Cell’s Structure

among genes so that the CA will exhibit a desired behavior. Some interesting circumstances occurred for the underlined genes in Table 7.1b. They can be regarded as anomalies since in those cases U classifies the behavior differently from the pair U p , ua . Actually the strongest result (with more confidence) is the one based on the theoretically defined probabilistic exponent of growth. The experimental determination has been done with only one instance of initial state. However there is a huge number of possibilities and quite often (this is actually the case for the underlined genes) the resulted U is rather an exception than the rule. A correct experimental result would be one where many initial states are considered and all resulting U are averaged. This is actually the meaning of the probabilistic exponent of growth. In fact simulations of the CAs confirmed the prediction based on U p in 100% of the cases, while initial states were randomly generated with a probabilistic profile according to the above theory.

7.6 Conclusions The most significant result of this chapter is that a consistent theory for predicting emergence analytically can be developed. As seen one needs to specify a initial state probability profile and to associate various emergent properties (like pattern explosion or implosion) with the evolution of probabilities for the cells within a specified neighborhood. By using a probabilistic approach both the cell structure and the neighborhood characteristic are captured into a consistent theory resembling the previously developed “theory of local activity” with some new benefits: (a) Unlike the “local activity theory” this new theory (of the probabilistic exponents of growth) considers not only the cell but also its neighborhood. This makes possible to predict emergent phenomena with an improved accuracy. (b) It relies on information theory rather than circuits theory and therefore it is expected to be more general. It is known that in order to apply the local activity theory one need to model the problem such that a cell fits within the model of a multi-port, each cell being connected with the others via a resistive grid. These are rather restrictive assumptions limiting the applicability domain to Reaction–Diffusion cellular systems. The theory proposed herein is however applicable to any complex system assuming that one has tools to compute or infer the nonlinear functional mapping the probabilities of the inputs to the probability of a nonlinear system output (the cell connected within a specified neighborhood). (c) The theory of probabilistic exponents of growth can be extended to continuous state systems as well. Herein we exposed the theory for the case of binary systems (where each variable is assigned a probability of being in state “1”). This makes the calculus of the cells function of

7.6 Conclusions 131

probability (FP in (7.2)) simpler although not very straightforward. The cell description as nonlinear function applied to a weighted sum of inputs is crucial for making these calculations possible. The theory can be extended to continuous state systems as well. Then, while each state variable involved can vary within a specified domain it will be attributed a probability density. Of course the technical difficulties to compute the cells function of probability densities will be higher but still the principles of the theory remains the same. Since another crucial feature of this new theory is to rely on next state uncertainties instead of probabilities, as a tool to predict growth or implosion (i.e. by using a forgetting function like in (7.3)), such a similar function must be also defined for the case of probability densities. A possible choice would be: b

uk

1

b

1 1 1 pk  x  pu  x dx 1  ³ pk  x  dx, ³ ba 2a 2a

(7.30)

where pu ( x) is the uniform density of probability of a signal ranging with the [a,b] interval and p k x is the specific density of probability of the cell k. Therefore u k 1 (maximum uncertainty) if p k x is uniform, u k 0.5 for a normal (Gaussian) distribution p k x , and becomes 0 (the signal is in a certain state) if p k x is a Dirac’s function (as is the case for the probability distribution of signals that are in a certain single state. The only mathematical problem needed to be addressed remains an algorithm to compute the output probability density given a nonlinear description of the cell and the expressions for probability densities of the inputs. (d) The theory of probabilistic exponents of growth is confirmed by experiments. Particularly, as described within the chapter, for various measures of complexity computed experimentally it was observed, using the visualization technique called parametrization, the existence of a clear functional relationship between the bits expressing the ID and the underlying complexity measure. Such relationships are now clearly expressed as (7.13)–(7.27) using the theory of probabilistic exponent of growth. (e) Herein we focused only on the exponent of growth as a measure of complexity and emergence and proved that is possible to compute it analytically, the result depending solely by the cell structure, the initial state profile and the neighborhood topology. Previous experiments have shown that the exponent of growth is a rather synthetic measure of complexity which may include hints about other measures such as transient time or clustering coefficients. It might be possible however to exploit some ideas from this theory to the problem of evaluating clustering coefficients and transient lengths on a probabilistic (information theoretic) base.

132 7 Predicting Emergence from Cell’s Structure

(f) Uncertainty profiles as tools to classify among emergent behaviors. In estimating the growing or exploding emergent behaviors we used two parameters ( ua and ue ) computed as linear combinations of the entire uncertainty profile (all uncertainties for the next state cells). A finer classification between behaviors may be however obtained by an indepth analysis of the uncertainty profile as a vector. Cell’s ID with similar uncertainty profile vectors exhibit similar emergent behaviors. The number of possible such vector gives also an indication about the diversity of possible emergent phenomena to be expected for a given cell family and neighborhood. For instance, it is rather simple to explain why “2s5” CAs exhibit no gliders while “1s5” CA s do. The reason, is that in the first case ue may have only two values (corresponding to either implosion or fast explosion) while the connectivity in the “1s5” case allows for a larger number of possible values of ue , some of them (closer to but larger than 1) favoring complex behaviors such as the presence of gliders. Using the same reasoning it follows that for the same type of semi-totalistic cells the 1D CA will exhibit a larger variety of emergent behaviors than its 2D counterpart. Moreover, the larger is the neighborhood the larger will be the variety of emergent behaviors observed.

8 Applications of Emergent Phenomena

8.1 Introduction Cellular automata were long recognized as having a great potential for applications, particularly when one have to deal with multi-dimensional signal processing or modeling. One of the main obstacle was to design CAs, i.e. to select among many possible cells the ones having a desired behavior. Usually such cells were randomly selected and the corresponding CA simulated. Then one would associate certain uses to that particular CA. Not surprisingly, one of the first application of CA is the random number generator, a behavior which can be characterized, in the light of the measures defined in the previous chapters, as a behavior with a large exponent of growth and a clustering coefficient around 0.5. As seen from our investigations over large families of semi-totalistic cells, there are many CAs with the above characteristics. Therefore a random selection of CA cells will likely provide a good number generator. Other interesting automata are those producing gliders. The famous example of the Game of Life was found by an educated guess in defining the CA rule heuristically as a simple model of a real life system. Another, more recent example, is the ID = 110 CA (in our terminology a 1a3 CA) of Wolfram, proved to be the simplest CA capable of universal computation [17]. It is widely recognized that finding such CAs by simply picking cells at random is very difficult since it appears that interesting emergent behaviors are rather sparse within the entire space of cells. Though, the order introduced by our measures allows identifying similar behaviors with much ease. For instance, estimating the uncertainty profile as shown in Chap. 7, for the ID = 110 (Wolfram’s universal computation) gives u >u1 , u 2 , u 3 , u 4, u 5 @ >0,1, 3 4 , 1 2 ,1@ . A simple inspection of the uncertainty profiles for all IDs within the 1a3 family gives the following IDs with the same profile or its mirrored version (with respect to the center element): ID = 137, ID = 206 (the same profile) and ID = 124, ID = 193 and ID = 220 (mirrored profile). Simulation of ID = 137, 124 and 193 gives the same behavior as in the case of ID = 110 and these four cells were recently reported as being similar using a different approach [76]. The presence of another two (ID = 206 and ID = 220) reveals two aspects: (a) they may be worth investigated further although visually they appear as having a different behavior. Indeed the patterns are apparently not so complex but gliderslike interaction is present in the form of collision between central and laterally R. Dogaru: Applications of Emergent Phenomena, Studies in Computational Intelligence (SCI) 95, 133– 157 (2008 ) www.springerlink.com © Springer-V erlag eBrlin eHidelberg 2008

134 8 Applications of Emergent Phenomena

moving waves; (b) It might indicate that more measures are needed in addition to the uncertainty profile, for a finer discrimination among behaviors. For instance an additional uncertainty profile, obtained with a different initial state profile. Nevertheless the theory of probabilistic exponents of growth provides a very efficient tool in locating not only desired emergent behaviors (e.g. by searching among those with an uncertainty in the expansion area closer but larger to 1) but also in locating genes with similar behaviors. For the game of life such cells were also found (see Chap. 7) by looking in the neighborhood of the “game of life” cell when mapped into a parametrization. The above suggests that we have now better tools to explore the wide spaces of the CA cells. In the next we will consider some applicative examples. Genes for the CA used in these applications were usually found by “sieving” the 2s5 family (a relatively small family) with some desired behaviors in mind. Among the resulted genes, those found useful for certain signal processing tasks were selected. Similar genes may be selected from their parametrization neighborhoods or, equivalently among those having the same or close uncertainty profiles, as determined using the methods exposed in Chap. 7. It is interesting to note that with only several genes from the same 2s5 family we were able to solve quite different problems. Three such applications were next selected as examples. The first is an application of gene 768 (defined as belonging to the class “edge” in Chap. 5) for character segmentation, next there is an application of gene 49 (“unstable near edge” in Chap. 5) in an original method for sound classification and finally there is a promising and novel VQ compression method (here exemplified for images) where CA-generated patterns are used as codebooks. The genes used in this case belong to the category “stable” as introduced in Chap. 5.

8.2 Smart Sensor for Character Recognition 8.2.1 Motivation and General Description In recent years there is an increased interest in designing functionally complex, yet portable and low consumption devices. Character segmentation for instance represents the basic preprocessing stage in any character recognition system. Given a monochrome image (which may be the result of a scanning process, as in the standard OCRs, or an image obtained from a video camera, like from a license plate or a pallet label) the segmentation, as described herein, should result in a list giving the precise coordinates and the sizes of the rectangular boundaries for each character in the visual field. In a further processing stage the associated pixels of each character could be cropped and submitted furthermore to a classifier. In the end the system should be capable to submit a sequence of codes representing the identified objects in the visual field (Fig. 8.1). Often such tasks are performed in software using expensive and power consuming general–purpose computers with an adequate image sensor [65]. There are however application niches where such a

8.2 Smart Sensor for Character Recognition 135

system is demanded to be portable and integrated within the image sensor. For instance a blind’s aid can benefit of such a sensor attached to the blind’s googles. It can “read” the visual field providing the blind person with a sequence of codes representing the scene. The codes can be translated in musical tones to be easily recognized. Other applications are in industry where they can operate similarly to bar code scanners, but in such circumstances where a bar code is not available. For instance they can be used to rapidly trace license plate numbers or box labels in a wireless system.

Fig. 8.1. The monochrome (binary) visual field has to be processed such that a rectangle will be generated around each isolated character. From such rectangles it is then easy to extract a list containing coordinates and sizes for each rectangle. The content of the rectangle is then submitted to a classifier

In [88] we took an original approach and proposed a smart sensor architecture, which exploits emergent phenomena in simple cellular systems. First we were looking for the simplest 2D grid cellular systems capable of emergent computation. Our choice was for CAs belonging to the “2s5” family. Such systems can be implemented in either digital [66] or mixed-signal [37] VLSI technologies. Particularly, the mixed-signal technology leads in this case to a very low implementation complexity. Tools for detecting emergence introduced in Chap. 5 were then used to discover some “useful” genes among the whole set of 1,024 possibilities. Surprisingly, it turned out that by using only two genes (ID = 768 and ID = 1,017) the task of character segmentation can be achieved in about one hundred of CA iterations. The cell ID = 768 is a linearly separable one, while ID= 1,017 can be replaced with a slight modification (where an inverter is placed before the central input of the cell) with ID = 63 such that it can also admit a simple linear threshold gate implementation. The resulting CA array can process the input image (e.g. the

136 8 Applications of Emergent Phenomena

one in Fig. 8.1, the upper left corner) loaded as an initial state, and after several iterations an output image is generated where rectangular boxes are defined indicating the pixels to be cropped for each isolated character. A simple feature extractor is then proposed and applied to the segmented image to generate a sequence of seven normalized feature vectors for each character. A classifier can then learn to recognize the features providing a list of codes at the output of the proposed smart-sensor. A brief description of the sensor architecture and functionality follows, for more details the reader is directed to [88]. 8.2.2 Architecture and Functionality of the CA-Based Sensor The architecture is centered around a 2s5 Cellular Automata (CA) array with simple semitotalistic cells (Fig. 8.2). Since only two genes are used a simple circuit is associated to each cell. A controller selects one of the two possible cell functions and runs the CA until it contains only empty rectangular boxes, each framing an isolated character from the visual field. Then using a simple “reading” algorithm described next, the controller identifies and stores a list with positions and sizes for each box (as seen in Fig. 8.1).

Fig. 8.2. The CA-based smart-sensor architecture: Each cell is semitotalistic and linearly separable, i.e. its output at the next clock cycle depends only on the simple sum of the neighboring cells (2–4) plus a weighted value of the central cell (or its negate). If the sum is greater than 0 the new state is 1, otherwise is 0. A simple controller provides an efficient way to extract features from each block and recognize the corresponding character providing at the output a list of codes abstracting the information from the visual field

8.2 Smart Sensor for Character Recognition 137

In order to achieve this goal the controller will increment and decrement the counters associated with the row and column selectors and will process bit information from the cellular array using a one bit bus. Once the starting position (upper left corner) and the size (vertical and horizontal number of pixels) are determined, a feature extraction and recognition algorithm will further process the cropped pixels within each box, extracting seven features to be further classified and recognized. Pixels are transferred from the CA array via an 1-bit pixel bus. Among the 2s5 genes the following were found interesting to be used in our architecture, as exemplified in Fig. 8.3:

Fig. 8.3. Dynamics of the CA for three particular genes from the “edge” type

Genes 792, and 768 perform a bounded wave propagation such that after a certain number of steps (proportional to the perimeter of the final square) the CA generates surrounding rectangles for each isolated group of pixels (grouping of pixels assume that no more than one white pixel connects any two black pixels). Note however that gene 792 is not useful since in some cases it generates rectangles with irregular vertical edges. In either case, the number of iterations until a steady state is reached is proportional to the perimeter of the largest character to be processed. Since ID=768 a linearly separable gene (see also Table 3.3 in Chap. 3) it has a simple implementation formula: w 2E  D  4.5 .

138 8 Applications of Emergent Phenomena

Gene 63* – (* comes from the operation of inverting the central input) has to be applied only one iteration to extract the edges of the rectangles. These edges are always one pixel wide. The implementation formula for ID 63* is: w >4(1  E )  D  4.5@ . Using some simple switching elements, as shown in Fig. 8.2, one single control bit can be used to toggle between the ID = 768 and ID = 63* genes as desired by the algorithm. The above sequence of genes performs correctly even when the characters are rotated, as seen in Fig. 8.4. Note however that if two characters are supposed to produce overlapping blocks (see the sequence U I in Fig. 8.4) then a single rectangle is produced for both characters.

Fig. 8.4. The segmentation algorithm applied to a rotated image. Here the “UI” sequence collided into a single rectangular box

8.2.3 Feature Extraction and Classification The following simple algorithm “reads” the positions and the sizes of the character boxes determined in the output image by the CA processing described above. It is implemented using the controller and it generates a list of four-dimensional vectors. Each vector contains the position (Px, Py) and the size (Sx, Sy) of a box surrounding a character: ix=0; // found character index FOR I=1:M-1 FOR J=1:N-1 IF neigh(output_image,I,J) is “left corner” THEN ix=ix+1 Px(ix)=J; Py(ix)=I; Sx(ix)=count_all_black_pixels_rightwards(); Sy(ix)=count_all_black_pixels_downwards(); F=FEATURES(input_image, PX, PY, SX,SY); X=RECOGNIZE (F); END END END

// character position // character rectangle size

8.2 Smart Sensor for Character Recognition 139

where M, N represent the number of rows and columns in the binary image. The algorithm scans the output image (i.e. the image obtained after CA processing) skipping all “white” pixels. If a pixel is “black” the algorithm is looking for its lower and righter neighbors (two pixels) and if both are black then it is a new upper left corner, the index ix of detected characters is incremented and the position (Px, Py) and the size (Sx, Sy) of that character box are determined. They can be stored in a list for further processing or they can be used immediately. In this later case the function “FEATURES”, operating on the input image (i.e. the visual field as it was extracted at the image sensor level) is called, to compute the feature vector F to be submitted to the classifier. The classifier (function “RECOGNIZE”) is then called to determine the content of the box. There are many possibilities to classify the array of pixels within a box, most of them based on neural networks. But since the boxes may have different sizes a robust feature extractor should be employed, being capable to capture the useful information in a fixed, predefined number of features. The basic idea is exemplified in Fig. 8.5. The box containing a character is divided into six rectangular blocks and each block is assigned a numerical label associated with a feature component f1 ,K f 6 .

Fig. 8.5. The schematic of a robust feature extractor

140 8 Applications of Emergent Phenomena

The values of the feature vector components (ranging each between 0 and 1) can be calculated as follows: The scaled feature f 7 ms

sx / sy / ms (aspect ratio of the box) was added, where

sx (ix ) max( sy (ix ) ) . ix

The other six features were slightly scaled to face the situation of handwritten characters, which are drawn with the same thickness independently of their size. For instance f1 Nb1 / O ˜ sqrt ( N1 ) instead of f1 Nb1 / N1 . Here N1 represents the total number of pixels in a given sub-block, Nb1 is the number of “black” pixels within that sub-block and O is a coefficient to be optimized such that the maximum value of the feature will reach 1. By doing so, the rate of misclassification was reduced almost four times in the case of handwritten characters. After the feature extraction, a classifier may be called to categorize the content of the corresponding character box. For the purpose of evaluation here we consider RBF-type (Gaussian) SVMs [68]). However, similar results are expected to be obtained with VLSI-tailored neural systems [69, 70] which are more convenient from the implementation point of view. 8.2.4 Experimental Results Here a real world problem is considered. A number of 143 digits were drawn on a sheet of paper as shown in Fig. 8.6. The image was acquired with a digital camera and it was binarized using a threshold adapted to reduce the noise.

Fig. 8.6. A real world problem for the recognition of handwritten digits. Left: the input image, right – the segmented image after 50 CA iterations

8.2 Smart Sensor for Character Recognition 141

The CA array then the “reader” were invoked producing a database with 143 seven-dimensional feature vectors (corresponding to the same number of characters in the image). The first 50 were used for testing and the remaining 93 were used for training a SVM (the simulator in [68] was used configured as C-SVM with Gaussian kernels and the “gamma” parameter equal to 5). The confusion matrix indicates that except characters “1” and “3” all others were all correctly recognized on the test set. This quite good performance indicates that although simple, the proposed feature extractor is robust and reliable. The character “1” has a recognition rate of 75% and character “3” a rate of 90% on the test set. In fact one “1” and one “3” were the only misclassified characters. When not properly recognized these two characters are decided to be “4”. A test on a distorted image as seen in Fig. 8.7, was then considered, with the SVM trained on the database from Fig. 8.6. Here O 11 was selected in the function FEATURE. The result shows that only 2 of the 16 characters (12.5%) were misclassified, still a very good result given the distortions.

Fig. 8.7. A set of distorted characters were recognized correctly except the two arrow pointed characters. The “2” was classified as “8” and the “1” was classified as 6

8.3 Excitable Membranes, for Temporal Sequence Classification A growing number of applications are developing in the sense of rapidly processing large amounts of data. Quite often such data is readily available as signals obtained from various sensors integrated in modern concepts such as “ambient intelligence” .Many applications require to recognize such signals at high speeds and with reasonable accuracy while being portable, with low power consumption. Such applications include but are not limited at the recognition of various abnormal states (e.g. epileptic state or other similar) from continuously available bioelectric signals, or voice recognition for different purposes (either commercial or biomedical, such in devices helping disabled people). One of the most investigated area of research is that of speech recognition where the aim is to recognize voice signals. But many other signals can be recognized using similar approaches. Traditional solutions (e.g. those based on Hidden Markov Models or HMM) are computationally intensive, requiring complex signal

142 8 Applications of Emergent Phenomena

processing architectures, high clock speeds and demand a large quantity of energy. In [89] a different, lower complexity solution is proposed which employs emergent computation of the type “unstable near edge” (Chap. 5). Instead of a highly complex signal processor we build an “excitable membrane with temporal memory (EMTM)” which slightly amplify any random spatial initial state, transforming a temporal sequence applied only to a few cells of the membrane into a spatial memory trace represented by the spatial state of the CA at the end of the temporal sequence. CA arrays with no more than 20×20 cells can be used as EMTMs. Such cellular arrays may be conveniently realized using FPGA technology or dedicated hardware. The computational complexity of the entire transformation scheme is reduced to that of running the excitable membrane CA for the entire duration of the temporal sequence (signal). Compared to HMM or other similar approaches it leads to a dramatic reduction in the implementation complexity with positive impacts on the power consumption. Calvin [90] postulates a theory of a “cerebral code” emerging in the cerebral cortex viewed as a cellular automata model. The method presented next can be regarded as a simple and practical possibility to create and use “cerebral codes ” in artificial cortexes made of simple cells. Similar ideas, i.e. that of using special dynamics of recurrent neural networks for signal processing [81] are also present in the LSM (liquid state machines) [91] and Echo State Networks (ESN) [79] theories, although for practical purposes they require a much higher implementation complexity. In what follows the EMTM method and its application for a sound recognition problem is briefly discussed. For more details the reader is directed to [89]. 8.3.1 Mapping Variable-Length Signals into Terminal States Let us consider a signal defined as a discrete-time sequence s(t) with a certain duration T (i.e. s(t) , t 1, 2,K T. ‘In many applications a signal has to be identified (or recognized) as belonging to a class. For instance, let us consider that our signals come from a speaker and represents a segmented window of speech when a particular word is spoken. In our experiments 20 different utterances of two words, “zero” and “one” were considered’. Let assume that we already identified a gene such that the CA behaves as an EMTM (excitable membrane with temporal memory), a subject discussed later. Then we are interested to map the variable length signal sequence S ^s (1), s ( 2),..., s (T )` into a fixed (predefined) sized binary matrix X (a terminal state of the CA) to be used as a feature in a classification system. The following algorithm is proposed to implement the function X < S . In the above < represents the algorithm, which can be applied to any particular temporal sequence (or signal) S:

8.2 Smart Sensor for Character Recognition 143

1. 2.

Construct a CA with N×N cells and initialize all cells with 0. Restet the time (iteration) counter (t = 0). Force the output of nine cells in the middle of the CA (denoted by index p, as depicted in Fig. 8.8 ) as following: y p (t ) s t  10  p

3. 4. 5.

Update the cells of the CA. t = t+1. IF t ! T  9 STOP.

6.

ELSE GOTO 2. X = Y(t) (the cellular automata terminal pattern).

Fig. 8.8. Distribution of signal samples into the CA array (here the numbers represent the cell index p, and N = 11)

Among other possible schemes for distributing the signal samples of the sliding window on the CA cells, the above was found to be the most convenient. Let us consider a CA with ID = 49 (later we will see on what basis it was selected) and the utterance “one”. Because our CA cells are binary the continuously valued original samples x(t ) are binarized such that: s (t )

1 1  signxt . The 2

evolution of the CA configured as EMTM is shown in Fig. 8.9. Using a binarized instead of the original speech signal may increase the classification error, although is known that such signals can still be correctly recognized by humans. Since this is the most adverse condition to test our method, we expect even better results using improved schemes. As seen in Fig. 8.9 in the first 500 iterations the binary pattern within the CA evolves quite rapidly as a growing structure with a slow explosion (limited by choosing the exponent of growth U < 1.4). Then the pattern changes slightly revealing accumulation of the specific variations in the signal sequence. It follows that for a given size N of the CA, there is an optimum number T of signal samples in the sequence. A smaller number of samples will produce a simple CA pattern in the middle with insufficient information in it, while a larger value will add no essential information to the CA pattern (as can be easily seen in Fig. 8.9) for t = 991. For the task of isolated word recognition (with lengths varying around 2,000 samples), the above scheme works quite well, particularly when the sounds sequences are rather different (as “one” and “zero” in our examples). For better accuracy, the signal temporal sequence S may be spilt in an equal number m (e.g. m = 4) of sub-sequences ( S 1, KS m ) such that each subsequence has an optimal length. The resulting feature vector is now formed of all resulting binary patterns ^ <  S 1 , K <  S m ` . This method, of splitting the signal sequence, is inspired from [89], which proved efficient in speech recognition tasks.

144 8 Applications of Emergent Phenomena

Fig. 8.9. Mapping a binarized speech signal to a binary feature matrix using a CA array configured as an EMTM (here ID = 49, and N = 17)

8.3.2 Detecting Genes to Build EMTMs Since binary samples of the signals are applied within a 3×3 square inside the CA (see Fig. 8.8) we are interested to get CA cells such that a pattern will expand around the 3×3 window so that the terminal pattern < S , will contain representative information for the whole time-sequence. Let us consider the possible options for the exponent of growth (as introduced in Chap. 5): (a) The option U <= 1 is not acceptable. Indeed, in this case, (based on the definition of the exponent of growth) the pattern will shrink and will contain even less information than in the last sliding window of the signal. (b) If U is bigger than a certain threshold (Ucrit) an “explosive” behavior takes place. Indeed, new patterns will be generated but with a fast growing ratio, and the whole CA array will be filled with a kind of random pattern. The dominant phenomena is the generation of a pseudo-random patterns as it was typically identified for large values of U. Thus, the useful information about the signal sequence is lost in the “noise” generated by the CA.

8.2 Smart Sensor for Character Recognition 145

(c) The only option left is to choose a CA cell such that: 1  U  U crit i.e. to let the pattern evolve beyond the 3×3 rectangle in the middle but never expanding out of the boundaries of the CA array. The traces left in the CA will carry an information about the overall sequence much like a free pendulum leaves a trace of its movement in a sheet of fine sand (Fig. 8.9). The U crit value has to be established experimentally. In what follows we U crit 1.4 is considered as it was experimentally determined as the most convenient. Using the sieving methods exposed in Chap. 6 we found 42 different IDs (among all 1,024 from the 2s5 family) satisfying this condition. Though, for many of them no interesting dynamics evolves and the patterns are usually confined to the initial 3×3 rectangle. This is probably the effect of the correlation present in the speech signal samples, while purely random samples were used to determine the value of U as explained in Chap. 5. It turns out that only ID = 49 and ID = 463 lead to expected behaviors, i.e. that of a excitable membrane with temporal memory (EMTM). The diversity of EMTMs may be increased sieving among larger populations of cells (e.g. within the 2s9 family) since as observed in the end of Chap. 7, the 2s5 family does not provide too many “slow growing” behaviors. Another possibility would be to consider a one-dimensional version of the method with cells selected among the 1s5 family, knowing that it has a richer repertoire of “slow growing” behaviors that its two-dimensional counterpart 2s5. 8.3.3 Experimental Results in Sound Classification In our experiments a speaker produced ten utterances for both “one” and “zero”. The result is a set of 20 signal sequences S k0 , S 1k k 1,..10 , where k is an index of the utterance. Each sequence is applied to the EMTM built as described previously and a set of binary terminal patterns X k0 , X 1k results when the algorithm discussed in Sect. 8.3.1 is applied. These patterns are represented in Fig. 8.10. Although the sequence of terminal states X k0 , X 1k can be applied to any neural classifier described in the literature, for the sake of implementation simplicity, herein we may consider an ad-hoc classifier constructed around some prototypes of the signals to be recognized. In our example we use the first three instances as training samples to compute the prototype matrices A0 and A1 as follows:

^

^ `

^

A0

`

`

3

3

k 1

k 1

¦ X k0 , A1 ¦ X 1k

146 8 Applications of Emergent Phenomena

0

1

Fig. 8.10. Terminal states ^ X k , X k ` for ten instances of speech signals “zero” and “one”. First three instances are used to build prototype vectors A0 and A1, used during the test phase to decide the class membership

The remaining terminal state patterns are used to test the classification performance. The classifier computes for each particular pattern X two scalar values h0, h1 as follows:

h0 SUM  A0.* X and h1 SUM  A1.* X where . * denotes a point-wise multiplication operator (similar to the one used in Matlab) while SUM() evaluates the sum of the resulting matrix. In other words, only the elements of the prototype matrices corresponding to 1’s in the X matrix are preserved and summed. The decision is taken as follows: IF h0 ! h1 X  zero

ELSE X  one

With only six training samples, an accuracy of 85.7% is obtained on the remaining 14 samples (2 errors in 14). The result, which can still be improved by choosing a larger training set, a different classifier, or by doing other refinements (e.g. splitting the sound sequence into several sub-sequences) demonstrates that

8.4 Image Compression Using CA-Based Vector Quantization 147

the EMTM built around a simple semi-totalistic CA can be used to map arbitrary length signal sequences into easy to classify binary patterns.

8.4 Image Compression Using CA-Based Vector Quantization Image compression is a necessary ingredient whenever limited bandwidth channels are available. During the years several techniques and standards have been developed [92, 93]. Traditional schemes of lossy image compression usually employ vector quantization (VQ) of image blocks (quite often 8×8 pixel blocks). Discrete cosine transform (DCT) or other transforms (like Discrete Wavelet Transform (DWT) or Integer Wavelet Transform (IWT)) are also used in compression schemes. For instance, in [94] an optimized IWT transform architecture is reported as having a “modest gate complexity” of about 56,000 gates (with an area of about 3 mm2 for a 0.35 Pm technology). Both vector quantization (VQ) and transform coding are computationally intensive algorithms, therefore an important research effort is directed to define various circuit architectures requiring a minimum of hardware resources and power consumption. Most of the computational complexity is explained by the need of complex arithmetic operators (i.e. multipliers, adders, cosine evaluation etc.) to process the pixels, as required by the traditional algorithms. In [95, 96] a cellular automata based vector quantization (CA-VQ) method is proposed for efficient image compression. The result is a radical simplification of the circuitry, making it very attractive for integration with low power image sensors. The method will be briefly exposed in the next. For more details the reader is directed to [96]. Unlike traditional VQ systems where extensive learning on large datasets of signals is employed, our codebooks are simply generated as emergent patterns in cellular automata and therefore they are fully described with only a few bits of information (the ones needed to specify the ID and the initial state). The CA-VQ method operates on binary images obtained as bit-planes of the original images (e.g. the most-significant bits of all pixels are assembled into the most significant bitplane) and therefore complex arithmetic circuits are eliminated. Only simple circuits for Hamming distances and comparisons are needed in addition to memories storing the binary codebooks. The CA-VQ scheme outperforms the JPEG standard for rates lower than 0.25 bits per pixel, while its simplicity makes it an ideal candidate for integration in ubiquitous computing sensory systems. 8.4.1 Coding and Decoding Principle As seen in Fig. 8.11 cellular automata are used to generate the codebook instead of complex optimization algorithms operating on large training sets, as is the case in the traditional vector quantization compression schemes.

148 8 Applications of Emergent Phenomena

The following procedure is used to generate the CA-based codebook: An initial “random” binary state (in this example it has a size of 128×128) is applied to a cellular automaton (CA) with its cells (defined by the ID code, in the example ID = 203) designed for emergent computation (with a sieve, defined to favor “pink noise” spatial frequency distributions. After a certain number T of iterations (128 or 256 in the example) a binary pattern containing a wide spectrum of frequencies is obtained.

Fig. 8.11. The principle of codebook generation using cellular automata

In the following we will call this pattern a codebook since it can be partitioned in a number of C code-words (each of wxw size) to be used in a vector quantization scheme. Unlike traditional codebooks, the CA-generated codebook is entirely defined by only a few bits of information defining the Cellular Automata ID (in the above case 203) and the number of iterations T needed until reaching the state considered as a codebook. Encryption features (not analyzed in detail here) may be added, by generating the pseudo-random initial state with another CA with a different gene (ID = 325 in the above example) starting from a initial state with a small number of pixels encoding the encryption key as their position within the CA grid. Besides compactness, the CA-generated codebooks can be optimized much easier than classic codebooks obtained through learning. No training sets are needed, while the overall performances of the codec may be easily optimized using test signals (such as different images) and by simply adjusting a small number

8.4 Image Compression Using CA-Based Vector Quantization 149

of the defining parameters (such as the ID, the number of iterations T, the size C of the codebook, and the block size w). The operating principle of the encoder and decoder employing the CAgenerated codebooks are presented in Figs. 8.12 and 8.13, respectively. The encoding process is simple: The input image is split into a number of bitplanes. Experiments with many natural images indicate that the most significant bitplane (m = 1) has the lowest content in high frequencies, while the least significant bitplanes can be regarded as almost random. This observation led to the following simplification in the encoding algorithm: x

The first m most significant bitplanes are encoded as indicated next.

x

The remaining least significant bitplanes (called ignored bitplanes in the next) are replaced with bitplanes generated pseudo-randomly using a different key per bitplane (e.g. using a specific CA with its ID as a compact key, see Fig. 8.11). It is assumed that the keys are known in the decoder, so that ignored bitplanes identical to the ones encoded could be generated.

Fig. 8.12. The principle of encoding (compression) using CA-generated codebooks

Each of m most significant bitplanes is divided into bit blocks of wxw bits size each. For each such block B a best match codeword C J is found within the CA-generated codebook. It minimizes the Hamming distance d J B  C J 1 (the number of different bits between the actual block B and the selected codeword C J ). In the above J  ^ 1, KC ` is the index of the best match, being sent as the compressed version of the initial block. Of course, since there is a limited number of codewords, some errors will result from the approximation C J # B .

150 8 Applications of Emergent Phenomena

For the entire bitplane m this error is evaluated as a bit error percentage Berr(m) i.e. the fraction of erroneous bits in the reconstructed image. Such errors produce “salt-and-pepper” noise in the reconstructed image, requiring some additional steps of Median filtering [97] applied to the reconstructed image. Such errors are visible mostly when they occur within the most significant bitplanes. Fortunately the bit error percentages are lower in these bitplanes and consequently Median filters are quite efficient. The quality of the overall encoding–decoding process is evaluated by the PSNR1 of the recovered image (in comparison to the original). The compression efficiency is expressed as a “bits-per pixel” (bpp) rate. In a bitplane “k” each index J is represented with log 2 Ck bits. We assume next the most general structure of our scheme, with different codebooks and window sizes per each bitplane k. For the CA-VQ algorithm the bit-per-pixel rate can be computed as: bpp

m

¦

log 2 C k

k 1

wk2

(8.1)

For instance, if m = 4, the compressed image is represented with 0.5 bpp if C = 256 and w = 8 for all bitplanes. Better compression can be achieved using an entropic coding. This scheme will be called CA-VQ-E in the next and requires further encoding of indexes J using the Huffman’s algorithm taking in consideration different entropies of the indexes J. For m = 4 and for the image shown in Fig. 8.12 the pixel rate decreases from 0.5 bpp in the non-entropic case, to only 0.2934 bpp, for the entropic encoding.

Fig. 8.13. The principle of the decoding (decompression)

The power signal to noise ratio (expressed in dB), where the noise signal is the difference between the original and the recovered image.

1

8.4 Image Compression Using CA-Based Vector Quantization 151

The decoder (Fig. 8.13) operates using a very simple search based on the index J. For each of the most significant m bitplanes, any wxw bit-block is reconstructed as Bˆ C J . The bitplanes are then assembled into a “gray-level” image and submitted to the Median filter which may be applied up to four times in order to recover the original image. Color images are similarly processed with bitplanes for each of the three basis colors (R, G, B). 8.4.2 Detecting the Useful Genes In what follows we consider the problem of finding genes (within the 2s5 and 2s9 families) such that the patterns produced have a “pink noise” characteristic which seems to give the best results in the proposed CA-VQ encoding scheme. The sieving method exposed in Chap. 6 is used, using iteratively tuned sieves and based on the feedback information regarding the codec performance for some test images. The measures of emergence are those defined in Chaps. 4 and 5, i.e. determined experimentally. Let us remind that a clustering coefficient with a value C close to one indicates a homogeneous state (low frequencies) while a value of C = 0.5 is a feature associated with a “white noise” chaotic pattern. At the other extreme C = 0 indicates the presence of perfectly regular chess-board pattern (i.e. preponderance of high frequencies in the spectral distribution). We found experimentally that patterns with C | 0.83 are well suited for building binary codebooks as needed by our compression method. In addition let us consider the transient length (Tr) as defined in Chap. 4 and the exponent of growth (U) as defined in Chap. 5. While having these three synthetic measurements for complexity one can employ a single to triple sieve to locate some genes of interest for oupr problem. For instance, by choosing C  0.5  0.00035 (a single sieve) for the gene space of all 1,024 semi-totalistic genes, the genes with ID = 661, ID = 325 and ID = 650 will be returned as the best random number generators. It is interesting to note that ID = 661 has the highest representation complexity among all genes (it requires m = 8 transitions, while ID = 650 and ID = 325 require a bit less i.e. m = 7, according to Table 3.3 in Chap. 3). Such random generators may be conveniently used in the encoder to produce a “random” seed from a pattern with only three randomly placed dots. They can be also used for generating the ignored bitplanes. A double sieve defined as: U  0.5 AND C  0.83  0.02 is likely to produce a list of genes that are useful for the purpose of generating codebooks. Running this sieve actually produced a list of 68 genes. Here we were interested in fast emergence ( U  0.5 ) primarily, and we will call these genes “fast codebooks”. That is why we would further investigate among the pool of 68 genes only for those giving the desired codebooks after running the CA for ten iterations. In this case we take each of the genes from the above list and use it in the CA-VQ

152 8 Applications of Emergent Phenomena

scheme while noting down the PSNR (power signal to noise ratio) obtained in each case as a performance measure. The test images are the same. The result may be summarized as follows: The best gene is ID 107 (PSNR = 24.6 dB for 0.3 bpp) while for a list of other ten genes the PSNR performance decreases with no more than –1 dB: ID = 11, 27, 43, 67, 75, 83, 103, 135, 920, 952. In terms of local Boolean function complexity, all 11 above except ID = 103 and ID = 920 require m = 3 transitions (see Table 3.3 in Chap. 3). The two exceptions are linearly separable Boolean functions (m = 1 transition) and therefore they would be better choices to simplify the implementation. The emergent patterns used for codebooks (including their power spectrum in logarithmic scale) for some of the above “fast codebooks” are presented in Fig. 8.14.

Fig. 8.14. Several codebooks and their power spectra (ID numbers and number of iterations are indicated in the upper row)

The above sieve was also applied to the 2s9 CA family in an attempt to improve the PSNR. However, no improvement was found although now the choice list is much larger (1,488 candidates). The best PSNR (24.5 dB) was obtained for ID = 2,975. A list of other 48 IDs giving a PSNR, which deviates with no more than 1 dB was extracted. Such a member of it is for instance ID = 15,375. Another set of genes (called “slow codebooks”) are selected if we tune the sieves for long transients where the clustering index is slowly increasing from C = 0.5 to 1. By properly choosing the number of iterations till stop T optimal codebooks for the CA-VQ method may be obtained. The following (triple) sieve was used to detect long transients: U  1 (imploding patterns) AND L ! 0.2 (relatively long transients) AND C ! 0.9 (low spatial frequency at the end). When applied to the 2s5 family the result is a list of 18 genes: ID = 76, 92, 131, 139, 147, 171, 179, 187, 203, 219, 791, 823, 836, 837, 852, 857, 884, 889. The “slow codebooks” have an advantage over the “fast” ones (introduced previously) in that they can be finely tuned by properly choosing the stopping iteration. They

8.4 Image Compression Using CA-Based Vector Quantization 153

are convenient to be used in compression schemes with different block sizes per bitplane or they can be optimally tuned to certain classes of images. Among the above list, a finer investigation led to the following (ID,T,PSNR) pairs as good choices among the list: (219, 100, 23.6 dB), (131, 50, 23.8 dB), (147, 20, 23.6 dB), (852, 200, 23.4 dB). Fine tuning of T may slightly improve the PSNR. The codebook patterns obtained for ID = 131 after different numbers of iterations are depicted in Fig. 8.15.

Fig. 8.15. Codebooks for ID = 131 and their power spectra for different numbers of iterations

8.4.3 Results and Comparison with Other Compression Standards In order to compare the CA-VQ scheme with other compression standard, a large variety of images was considerded. Here we will detail the results for two of them: The first, entitled “Lena_detail”, is an image giving a good reconstruction error (large PSNR), and is often used in image processing algorithms. In order to observe the details we cropped a block of 192×192 pixels containing the face from the original 512 × 512 pixels “Lena” image. The second image, “Cat_in_the_grass” or simply “Cat” comes from a photo of the author (here in 624 × 480 pixel resolution) and has a rich content of high frequencies giving the lowest PSNR among the images used in tests. Variable block-sizes were used with an independent optimization of the codebooks per each bitplane, to achieve the best performance for a given compression rate. By changing the block-size profile one can easily achieve a desired bitrate. In all cases the CA used as a codebook generator has ID = 131 while the codebook optimization is done only with respect to the T (number of CA iterations) and D (number of code-words in the ordered codebook) for a given block-size w.

154 8 Applications of Emergent Phenomena

An ordered codebook is one where the blocks cropped from the “pink noise” CA patterns are reordered according to an algorithm detailed in [96]. The ordering process gives a significant reduction in the codebook-size thus improving the compression rate at similar quality. Figure 8.16 presents two examples of compressing the “Lena_ detail” image with different bitrates using CA-V Q-E an d one example of compressing the “Cat” image with a relatively low bitrate. In each case, the values of the w, T, and D parameters are specified for each bitplane starting with the most significant at left. The marking “–” indicates an ignored bit-plane. Note the very high compression rate in Fig. 8.16a where a compression of more than 160 times has been achieved (a rate of about 0.05 bits per pixel) with reasonable blocking effects. The high frequency details in the original picture are still present. The picture in Fig. 8.16b has a quality comparable to the one obtainable using a JPEG standard. And finally, the “Cat” image compressed at 0.17 bpp has a reasonably visual quality although the PSNR value is quite low. There is a simple explanation: PSNR is lowered by the large presence of high frequencies (the grass). Although the exact brightness of pixels in the grass region is altered, the overall high frequency texture is well approximated so that the perceptual quality is not too much affected. A rate-distortion curve was determined for both CA-VQ and CA-VQ-E schemes for both “Lena_detail” and “Cat” image. For reference, the same images were encoded with the JPEG standard using the JPEG converter (imwrite function) from the Matlab environment with different quality factors. The resulting distortion curves are plotted in Fig. 8.17. In JPEG encoding the quality degrades suddenly for low bitrates, while the proposed CA-VQ performs better. The quality expressed as PSNR is lower than for JPEG when bitrates are higher than 0.25 bpp but the difference in terms of perceptual quality are negligible. The above statements hold for both “Lena_detail” and “Cat” images and can be generalized for arbitrary images as well. The PSNR is lower for the “Cat” image mainly because of the high frequency content due to the grass in that scene. A small PSNR is also obtained when JPEG encoding standard is used. Therefore we conclude that our compression scheme is particularly well suited for low bitrates (i.e. high compression) although its implementation simplicity (compared with JPEG) may impose it even for higer bitrates, in applications requiring economic implementation.

8.4 Image Compression Using CA-Based Vector Quantization 155

Fig. 8.16. Three examples of applying the CA–VQ–E scheme. The values of the w, T, D are specified for each bitplane. The figure at the left of each row is the original, while the figure at right is the recovered version at the output of the CA-VQ encoder–decoder chain. The figure in the middle is obtained before applying the Median filter (here only one time)

156 8 Applications of Emergent Phenomena

Fig. 8.17. Rate–distorsion curve giving comparison between our method in either simple (CA-VQ) or with entropic encoder (CA-VQ-E) and the JPEG standard

8.4.4 Aspects on Hardware Implementation The CA-V Q encoding algorithm is the most critical in terms of execution time while decoding is a fast process. However the proposed CA-V Q scheme is extremely simple consisting in a comparison between a certain binary block in the current bitplane and a D-sized codebook stored in a memory. Let us denote ' the time required by the hardware unit to compute the Hamming distance between two blocks and decide whether this is greater or not than a previously stored value. For a sequential implementation of the Hamming unit (which is as simple as XOR-ing two bits and consequently incrementing a counter if the two bits are different) and assuming some two additional cycles for comparison and the eventual storage of the closest code-word it follows that ' 2  w 2 TCLK , where w is the block size and TCLK is the clock period (determined by the implementation technology). For a variable block size, and an image size of M×N (assumed that both M and N are integer multiples of w) the overall computation time may be evaluated as:



Tencode



m

m MN 2 D w T MN Dk . 2  #  ¦ k k CLK 2 k 1 1 wk

TCLK ¦ k

(8.2)

8.4 Image Compression Using CA-Based Vector Quantization 157

Thus, the encoding time depends on the image size and on the total number of code-words in all bitplanes. It is now obvious why it is so important to reduce the codebook size, as previously discussed. For instance, assuming a 512 × 512 image and a typical Dk 8 with m = 6 most significant bitplanes, the result is Tencode # TCLK ˜13˜10 6 . For a clock frequency of 20 MHz ( TCLK 50 ˜10 9 s , typical for any cheap micro-controller) it follows that Tencode # 0.65s , which may be reasonable enough for still images. Using high-speed customary designed circuitry may increase the speed up to 100 times, sufficient enough to accommodate moving pictures. Moreover, by using FPGAs, the CA-VQ algorithm may be easily ported to a parallel implementation (several processors operating independently on sub-domains of the input images) to obtain a similar gain in speed while taking benefits of the reasonable costs for implementation and development using the FPGA technology.

References

1. 2. 3. 4. 5. 6.

7. 8. 9. 10. 11. 12. 13.

14.

15. 16. 17. 18. 19.

Watts DJ (1999) Small Worlds: the dynamics of networks between order and randomness. Princeton University Press, Princeton, NJ. Stanford Encyclopedia of Philosophy, (online) at: http://plato.stanford. edu/entries/ockham/ Maurer Armand A (1999) The philosophy of William of Ockham in the light of its principles. Pontifical Institute of Mediaeval Studies, Toronto. Nicolis G, Prigogine I (1977) Self Organization in Non-Equilibrium Systems (Chaps. III and IV), Wiley, New York. Dogaru R, Chua LO (1999) Emergence of unicellular organisms from a simple generalized cellular automata universal CNN cells. Int. J. Bifur. Chaos 9(6): 1219–1236. Dogaru R, Glesner M (2004) Novel tools and methods for fast identification of emergent behaviors in CNNs with relevance to biological modeling, in Proceedings CNNA2004 (IEEE Int. Workshop on Cellular Neural Networks and Their Applications, Budapest 22–24 July), pp. 339–345. Chua LO (1998) CNN: A Paradigm For Complexity. World Scientific, Singapore. Chua LO (1999) Passivity and complexity. IEEE Trans. Circuits Syst.–I 46(1): 71–82. Dogaru R, Chua LO (1998) Edge of chaos and local activity domain of FitzHugh– Nagumo Equation. Int. J. Bifur. Chaos 8 (2): 211–257. Dogaru R, Chua LO (1998) Edge of chaos and local activity domain of the Brusselator CNN. Int. J. Bifur. Chaos 8(6): 1107–1130. Dogaru R, Chua LO (1998) Edge of chaos and local activity domain of the Gierer– Meinhardt CNN, Int. J. Bifur. Chaos 8 (12): 2321–2340. Goyal S (2005) WMCSA 2004: 10 years of mobile and ubiquitous computing, Pervasive Comput., IEEE 4(2): 88–90 van der Poel CJ, Pessolano F, Roovers R, Widdershoven F, de Walle G, Aarts E, Christie P (2004), On ambient intelligence, needful things and process technologies, in Solid-State Circuits Conference, ESSCIRC 2004, 21–23 Sept. 2004, pp. 3–10. Muller-Schloer C (2004) Organic computing – on the feasibility of controlled emergence, in Hardware/Software Codesign and System Synthesis, CODES + ISSS 2004. International Conference on 8–10 Sept. 2004, pp. 2–5. Dogaru R (2003) Universality and Emergent Computation in Cellular Neural Networks. World Scientific, Singapore. Zuse K (1967) Rechnender Raum, Elektronische Datenverarbeitung, vol. 8, pp. 336–344. A scan is available via http://www.idsia.ch/~juergen/digitalphysics.html Wolfram S (2002) A New Kind of Science. Wolfram Media, Inc., Champaign IL, USA. Beyer WA, Sellers PH (1985) Stanislaw m. Ulam’s contribution to theoretical theory, in Lett. Math. Phys. 10: 231–242. von Neuman John (1966) Theory of Self-Reproducing Automata. Edited and completed by Arthur Burks, University of Illinois Press.

160 References 20. Fredkin E (1990) Digital mechanics, Physica D: 254–270. 21. Fredkin E (2001) Digital Philosophy web site. http://www.digitalphilosophy. org/physicists_model.htm 22. Fredkin E, Toffoli T (1982) Conservative logic, Int. J. Theor. Phys. 21: 219–253. 23. Berlekamp E, Conway JH, Guy RK (1982) Winning ways for your mathematical plays. Academic, New York, Chapter 2, vol. 2, pp. 817–850. 24. Turing, A (1936) On computable numbers with an application to the Entscheidungsproblem, Proceedings London Math. Soc., series 2, 43: 544–546. 25. Toffoli T (1998) Non-conventional computers, in Encyclopedia of Electrical and Electronics Engineering (John Webster ed.). Wiley, New York. 26. Weimar JR (2005) Personal homepage, http://www.jweimar.de/home3e. 27. Chua LO, Yang L (1988) Cellular neural networks: theory and applications, IEEE Trans. Circuits Syst. 35: 1257–1290. 28. Roska T, Chua LO (1993) The CNN universal machine: an analogic array computer, Circuits and Systems II: Analog and Digital Signal Processing, IEEE Trans. 40(3): pp. 163–173. 29. Chua LO, Roska T (2001) Cellular Neural Networks and Visual Computing – Foundations and Applications. Cambridge University Press, Cambridge, MA. 30. Roska T, Rodríguez-Vázquez A (2000) Review of CMOS implementations of the CNN universal machine-type visual microprocessors, Circuits and Systems, 2000. Proceedings ISCAS 2000 Geneva. The 2000 IEEE International Symposium on, vol. 2, pp. 120–123. 31. Roska T, Rodríguez-Vázquez A (2000) Towards the Visual Microprocessor: VLSI Design and the Use of Cellular Network Universal Machines. Wiley, New York. 32. CNN Software Library (CSL) Templates (Version 1.1), Analogic and Neural Computing Laboratory, MTA-SzTAKI, Budapest, Hungary, available from http://lab. analogic.sztaki.hu/Candy/csl.html 33. Shackleford B, Tanaka M, Carter RJ, Snider G (2002) High performance cellular automata random number generators for embedded probabilistic computing systems, in Evolvable Hardware, Proceedings NASA/DoD Conference on 15–18 July 2002, pp. 191–200. 34. Lafe O (1996) Data compression and encryption using cellular automata transforms, in Proceedings of the IEEE Intelligence and Systems, pp. 234–241. 35. Nagy Z, Szolgay P (2003) Configurable multilayer CNN-UM emulator on FPGA, in IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 50, Issue 6, pp. 774–778. 36. Rodriguez-Vazquez A, Linan-Cembrano G, Carranza, L, Roca-Moreno E, Carmona-Galan, R, Jimenez-Garrido F, Dominguez-Castro R, Meana SE (2004) ACE16k: the third generation of mixed-signal SIMD-CNN ACE chips toward VsoCs, in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 51, Issue 5, pp. 851–863. 37. Dogaru R, Chitu C, Glesner M (2003) A versatile cellular neural circuit based on a multi-nested approach: functional capabilities and applications, in IFIP WG 10.5 International Conference on Very Large Scale Integration of System-on-Chip, Darmstadt, Germany, 1–3 Dec 2003, pp. 356–361. 38. Forshaw M, Stadler R, Crawley D, Nikolic K (2004) A short review of nanoelectronic architectures. Nanotechnology 15: 220–223. 39. Snider GL, Orlov AO, Amlani I, Bernstein GH, Lent CS, Merz JL, Porod W (1999) Quantum-dot cellular automata. Microelectronic Eng. 47: 261–263.

References 161 40. Lent CS, Isaksen B, Lieberman M (2003) Molecular quantum-dot cellular automata. J. Am. Chem. Soc. 125: 1056–1063. 41. Toffoli T, Margolus N (1987) Cellular Automata Machines. MIT Press, Cambridge. 42. Roska T (2000) Analogic computing: system aspects of analogic CNN sensor computers, in Proceedings of the 2000 Sixth IEEE International Workshop on Cellular Neural Networks and Their Applications, pp. 73–78. 43. Roska T (2001) AnaLogic wave computers-wave-type algorithms: canonical description, computer classes, and computational complexity, in Proceedings of IEEE International Symposium on Circuits and Systems, ISCAS 2001, vol. 2, pp. 41–44. 44. Roska T (2002) Computational and computer complexity of analogic cellular wave computers, in Cellular Neural Networks and Their Applications Proceedings of the Seventh IEEE International Workshop, edited by Ronald Tetzlaff, World Scientific 2002. 45. Hänggi M, Moschytz GS (2000) Cellular Neural Networks: Analysis, Design, and Optimization. Kluwer, Dordecht. 46. A Java-based CNN simulator, web page: http://www.isiweb.ee.ethz.ch/haenggi/ CNNsim_adv_manual.html 47. Hänggi M, Moser S, Pfaffhauser E, Moschytz GS (1999) Simulation and Visualization of CNN Dynamics”, in Int. J. Bifur. Chaos, 9(7), pp. 1237–1262. 48. Analogic & Neural Computing Laboratory – Hungarian Academy of Sciences, web site: http://lab.analogic.sztaki.hu/ 49. CNN Simulator from the Frankfurt University – the Institute of Applied Physics, web page: http://www.uni-frankfurt.de/fb13/iap/e_ag_rt/SCNN/ 50. Kermit Sigmon, MATLAB Primer, Third Edition, available online: http://ise.stanford. edu/Matlab/matlab-primer.pdf 51. Sigmon K, Davis TA (2001) MATLAB Primer. Sixth Edition, CRC Press, West Palm Beach, FL. 52. Dogaru R, Chua LO (1999) Universal CNN Cells, Int. J. Bifur. Chaos, 9: 1–48. 53. Chua LO, Yoon S, Dogaru R (2002) A nonlinear dynamics perspective of Wolfram’s new kind of science part I: threshold of complexity, Int. J. Bifur. Chaos 12(12), pp. 2655–2766. 54. Ronald EMA, Sipper M, Capcarrere MS (1999) Design, observation, surprise! A test of emergence. Artificial Life 5(3): 225–239. 55. Wolfram S (2002) A New Kind of Science (Wolfram Media, Inc., Champaign Illinois USA), 2002, online version http://www.wolframscience.com/nksonline/toc.html 56. Wolfram S (1984) Universality and complexity in cellular automata, Physica D 10: 1–35. 57. Markus M, Hahn T, Kusch I (1997) A novel quantification of cellular automata, Parallel Comput. 23: 1635–1642. 58. Sutner K (2003) Cellular automata and intermediate degrees, Theor. Comput. Sci. 296: 365–375. 59. Barabási AL (2002) Linked. The new science of networks. Perseus, Cambridge MA. 60. Kauffman SA (1995) At home in the universe: the search for laws of self-organization and complexity. Oxford University Press, Oxford. 61. Dogaru R, Chua LO (2000) Mutations of the Game of Life: a generalized cellular automata perspective of complex adaptive systems, Int. J. Bifur. Chaos 10 (8): 1821–1866. 62. Dogaru R, Iftime A, Darloman D, Glesner M (2003) An exhaustive analysis of emergent behaviors in recurrent cellular computing systems with outer-totalistic cells, in Proceedings CAS2003, Sinaia, Romania, 28 Sept–2 Oct, vol. 2, pp. 391–394.

162 References 63. Draganescu M, Kafatos M Community and social factors for integrative science, available from http://www.racai.ro/~dragam 64. Varela F, Maturana H, Uribe R (1974) Autopoiesis: the organization of living systems, its characterization and a model, Biosystems 5: 187 65. Y. Lu (1995) Machine printed character segmentation – an overview. Pattern Recognition 28(1): 67–80. 66. Dascalu M, Franti E (2000) Implementation of totalistic cellular automata, in Proceedings CAS 2000: 273–276. 67. Gutowitz HA (1993) Cryptography with dynamical systems, Cellular Automata and Cooperative Phenomena (E. Goles at al. eds.). Kluwer, Dordecht. 68. Junshui Ma, Yi Zhao, and Stanley Ahalt, OSU SVM Classifier Matlab Toolbox (ver 3.00), available from http://www.ece.osu.edu/~maj/osu_svm/ 69. Dogaru R, Glesner M (2004) SORT: a fast and compact neural classifier based on a sorting preprocessor, in Proceedings of Second International IEEE Conference Intelligent Systems, vol. 1, pp. 71–75. 70. Dogaru R, Julian P, Chua LO, Glesner M (2002) The simplicial neural cell and its mixed-signal circuit implementation: an efficient neural-network architecture for intelligent signal processing in portable multimedia applications, IEEE Trans. Neural Netw. 13(4): 995–1008. 71. Martinez GJ, McIntosh HV, Seck Tuoh Mora JC (2003) Production of gliders by collisions in rule 110, in ECAL 2003, LNAI 2801, pp. 175–182. 72. Tomassini M, Perrenoud M (2000) Stream Cyphers with one- and two-dimensional cellular automata, in Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature: 722–731. 73. Wuensche A (1998) Classifying cellular automata automatically, Complexity 4 (3): 47–66. 74. Bilotta E, Lafusa A, Pantano P (2002) Is self-replication an embedded characteristic of artificial/living matter?, in Artificial Life VIII, Standish, Abbas, Bedau (eds), MIT Press, Cambridge, MA, pp. 38–48. 75. Lafusa A, Bossomaier T (2005) Hyperplane localisation of self-replicating and other complex cellular automata rules, in Proceedings of IEEE Congress on Evolutionary Computation, 2–5 Sept. 2005, vol. 1, pp. 844–849. 76. Chua LO, Sbitnev VI, Yoon S (2004) A nonlinear dynamics perspective of Wolfram’s new kind of science. Part III: Predicting the unpredictable, Int. J. Bifur. Chaos, 14, 3689–3820. 77. Chua LO, Sbitnev VI, Yoon S (2005) A nonlinear dynamics perspective of Wolfram’s new kind of science. Part IV: From Bernoulli shift to 1/f spectrum. Int. J. Bifur. Chaos 15(4): 1045–1183. 78. Langton CG (1984) Self-reproduction in cellular automata. Physica D 10: 135–144. 79. Jaeger H, Haas H (2004) Harnessing nonlinearity: predicting chaotic systems and saving energy in wireless communication, Science 304, pp.78–80. 80. Maass W, Natschläger T, Markram H, (2004) Computational models for generic cortical microcircuits, in Computational Neuroscience: A Comprehensive Approach, Ch 18, pp. 575–605. 81. Legenstein R, Maas W (2005) What makes a dynamical system computationally powerfull?”, in Haykin, Principe Sejnowsky and McWhirter (Eds.), New Directions in Statistical Signal Processing: From Systems to Brain, MIT Press, Cambridge, MA.

References 163 82. Fredkin E (1990), Digital mechanics: an informational process based on reversible universal CA, Physica D, vol. 45, p. 254. 83. Zadeh LA (1968) Fuzzy algorithms, Inf. Control 5: 94–102. 84. Cox E (1994) The Fuzzy Systems Handbook. ISBN 0-12-194270-8. 85. Dogaru R (2005) A double-sieve method to identify emergent computation in cellular nonlinear networks, in Proceedings of IEEE Eurocon – International Conference on Computer as a Tool, Belgrade, 21–24 Nov 2005, CD Proceedings. 86. Gödel K (2000) On Formally Undecidable Propositions Of Principia Mathematica And Related Systems, translation in English by Martin Hirzel, online: http://www.research. ibm.com/people/h/hirzel/papers/canon00-goedel.pdf 87. Heisenberg W (1927) Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik, Zeitschrift für Physik, 43 1927, pp. 172–198. English translation: J. A. Wheeler and H. Zurek, Quantum Theory and Measurement Princeton University Press, Princeton, NJ, 1983, pp. 62–84. 88. Dogaru R, Dogaru I, Glesner M (2005) A smart sensor architecture based on emergent computation in an array of outer-totalistic cells, in Proceedings of SPIE, vol. 5839 Bioengineered and Bioinspired Systems II, Editor(s): Ricardo A. Carmona, Gustavo Liñán-Cembrano, pp. 254–263. 89. Dogaru R (2007) Classification of temporal sequences with excitable membranes based on semitotalistic cellular automata, in Proceedings of CSCS-16, the 16th International Conference on Control Systems and Computer Science, May 22–26, 2007, Bucharest, Romania, vol. 1, pp. 87–92. 90. Calvin WH (1996) The Cerebral Code. MIT Press, Cambridge, MA. 91. Verstraeten D, Schrauwen B, Campenhout JV (2005) Recognition of isolated digits using a liquid state machine, in Proceedings of SPS-DARTS 2005 (The first IEEE BENELUX/DSP Valley Signal Processing Symposium), pp. 135–138 92. Sullivan GJ, Wiegand T (1998) Rate-distorsion optimization for video compression, IEEE Signal Process. Mag. 74–90. 93. Ostermann J, Bormans J, List P, Marpe D, Narroschke M, Pereira F, Stockhammer T, Wedi T (2004) Video coding with H.264/AVC: tools, performance, and complexity, IEEE Circuits Syst. Mag., pp. 7–28. 94. Grangetto M, Magli E, Martina M, Olmo G (2002) Optimization and implementation of the integer wavelet transform for image coding, IEEE Trans. Image Process, 11(6): 596–604. 95. Dogaru R, Tetzlaff R, Glesner M (2006) Semi-totalistic CNN genes for compact image compression, in The IEEE Proceedings of Tenth International Workshop on Cellular Neural Networks and Their Applications, Istanbul, Turkey, 28–30 August 2006, pp. 147–152. 96. Dogaru R (2007) CA-VQ: a simple compression scheme using codebooks generated by cellular automata, in Proceedings NSIP2007 (International Workshop on Nonlinear Signal and Image Processing), September 10–12, Bucharest, Romania, pp. 202–208. 97. Benkrid K, Crookes D (2003) New bit-level algorithm for general purpose median filtering, J. Electronic Imag. 12(2): 263–269.

Index

active area, 120, 121, 125, 126, 127, 129 artificial life, 8 average degree of separation, 40, 57 Boolean cells, 10, 25, 38, 57, 58, 59, 60, 85, 114, 123 cell identifier, 26 cells function of probability, 119, 123, 130 cellular automata, 8, 9, 10, 13, 17, 19, 21, 22, 23, 25, 35, 36, 38, 41, 42, 47, 48, 49, 51, 52, 61, 62, 64, 67, 70, 72, 73, 74, 77, 78, 79, 83, 85, 95, 97, 99, 101, 104, 107, 110, 111, 113, 120, 142, 143, 147, 148 cellular computing, 1, 5, 6, 7, 8, 9, 10, 13, 15, 40, 47, 77 cellular nonlinear network, 85 chaotic dynamics, 10, 52, 61, 63 clustering coefficient, 50, 51, 52, 54, 56, 61, 62, 63, 64, 68, 72, 73, 75, 77, 92, 93, 95, 98, 109, 116, 133, 151 design for emergence, 5, 6, 48, 77, 95, 96 edge of chaos, 4, 10, 21, 77, 80, 82, 90, 113 emergent computation, 1, 5, 8, 19, 60, 135, 142, 148 eternal life, 3 excitable membrane, 142, 145 expansion area, 120, 121, 124, 125, 126, 134 exponent of growth, 6, 50, 52, 53, 54, 77, 78, 79, 80, 81, 83, 85, 87, 88, 89, 92, 93, 95, 99, 102, 106, 115, 118, 120, 121, 124, 126, 127, 129, 131, 133, 143, 144, 151

families of CA, 55, 67, 69, 95 families of cells, 5, 36, 117 far from equilibrium, 3, 82 FPGA, 13, 142, 157 Fuzzy Logic, 96 gliders, 48, 50, 51, 53, 54, 55, 56, 62, 65, 67, 68, 70, 71, 73, 96, 99, 102, 103, 104, 105, 107, 111, 127, 128, 132, 133 Image compression, 147 input entropy, 61, 64, 65 local activity, 3, 4, 21, 47, 63, 79, 80, 113, 115, 130 local connectivity, 1, 45, 58 local rules, 8, 17, 19, 59, 60 local structural complexity, 36, 37, 60, 68 measure of emergence, 3, 56, 114, 116, 119 nano-technologies, 13 neural networks, 10, 18, 21, 25, 118, 139, 142 nonlinear filtering, 10, 79 optimization algorithms, 61, 68, 95, 147 overall parametrization quality, 116 parametrization, 114, 116, 117, 118, 131, 134 pattern recognition, 1, 6, 9, 18, 106 piecewise-linear, 5, 22, 23, 35, 38, 85, 119 probabilistic exponent of growth, 6, 130

166 Index Reaction-Diffusion, 20, 47, 79, 113, 130 small worlds, 57, 58, 89, 90 smart-sensor, 136 spatial cluster, 77, 78, 79, 80, 82, 83, 86, 90, 99, 104, 119 transient length, 3, 49, 54, 61, 62, 63, 64, 74, 77, 80, 92, 95, 117, 151

uncertainty, 6, 67, 99, 100, 101, 120, 121, 122, 124, 125, 126, 129, 131, 133, 134 universal computation, 8, 42, 48, 51, 67, 99, 104, 107, 133 vector quantization, 61, 147, 148 VLSI, 9, 13, 135, 140 voice recognition, 141