Implications on self-organisation and memory

for the degree of D.Phil at

THE UNIVERSITY OF SUSSEX

School of Cognitive and Computing Sciences

The thesis consists of 239 pages with 71 figures + appendices figures.

You can download a scanned pdf -- 38.9M.

I believe the university charges about 10 pounds + postage.

for a hard copy of the complete thesis - please contact:

Celia McInnes, Librarian

School of Cognitive and Computing Sciences

University of Sussex, Falmer, Brighton BN1 9QH, UK

tel: +44 1273 606755, ext. 2405

FAX: +44 1273 671320

email: celiam@cogs.susx.ac.uk

Only the abstract, contents, overview and selected references are included below: See also

RBN and CA provide contrasting notions of self-organisation. RBN provide models of hierarchical categorisation in biology, for example memory in neural and genomic networks. CA provide models at the lower level of emergent complex pattern. New measures and results are presented on CA attractor basins and how they relate to measures on local dynamics and the Z parameter, characterising ordered to "complex" to chaotic behaviour. A method is described for classifying CA rules by an entropy-variance measure which allows glider rules and related complex rules to be found automatically giving a virtually unlimited sample for further study.

The dynamics of RBN and intermediate network architectures are examined in the context of memory, where categorisation occurs at the roots of subtrees as well as at attractors. Learning algorithms are proposed for "sculpting" the basin of attraction field. RBN are proposed as a possible neural network model, and also discussed as a model of genomic regulatory networks, where cell types have been explained as attractors.

It can be argued that the dynamics of non-equilibrium parallel processing systems composed of discrete interacting components create and maintain much of the complex biological phenomena that dominate our world. Various types of discrete dynamical networks are increasingly being applied as idealised models of physical and biological phenomena. For this reason, and also because of their intrinsic interest as mathematical/physical systems, finding general principles underlying the dynamics of the idealised networks themselves has become an important task. Their behaviour is difficult to describe by classical mathematics using its tools of partial differential equations and continuous dynamics.

This thesis applies computer simulation tools developed by the author, known as "

The capability of constructing attractor basins depends on reverse algorithms invented by the author for directly computing the predecessors (known as pre-images) of network states. Different reverse algorithms apply to CA and RBN, though the RBN method encompasses CA.

These methods are in general orders of magnitude faster than the brute force method, constructing an exhaustive map resulting from network dynamics. This exhaustive method rapidly becomes computationally intractable with increasing network size so is limited to small systems. It applies to all network types and also allows the attractor basins of random maps to be constructed. These three independent methods together form a valuable reality check on the correctness of the computed pre-images and attractor basins.

The CA reverse algorithm forms the basis for a trajectory convergence parameter, named the Z parameter (Wuensche and Lesser 1992a, Wuensche 1994a), a sort of inverse Liaponov exponent, which predicts the bushiness of sub-trees in attractor basins. Measures of bushiness are captured by "garden-of-Eden" density and more generally by the distribution of in-degree. It is shown that these measures correlate with the quality of dynamics, ordered to chaotic, where order turns out to be the most bushy, chaos the least. A histogram of the in-degree distribution shows contrasting profiles for order and chaos, for complex rules the distribution seems to follow a power law.

Whereas RBN provide models in biology because of their non-local connections and heterogeneous rules, CA provide models in physics with its notions of continuous space and universal laws. Contrasting notions of self-organisation are apparent between the two systems. RBN provide models of hierarchical categorisation in biology, for example memory in neural, genomic, and immune networks. CA provide models of self-organisation at the lower level of emergent interacting space-time configurations, particles or "gliders", metaphors for the emergence of life from the stuff of inanimate physics by a process of self-organisation.

In general, coherent space-time configurations cannot emerge in RBN because of their non-locality. On the other hand, a CA's ability to flexibly categorise distributed patterns is subject to severe symmetry constraints. Different and contrasting "edge-of-chaos", or phase transition, notions are seen to apply to CA and RBN. In the case of CA, this is the phase in rule-space where glider behaviour might emerge, quantified by rule parameters such as the lambda parameter (Langton 1990) and the author's Z parameter, measures on the dynamics such as the "input-entropy" and its variance, and by measures on the topology of attractor basins and sub-trees, such as the distribution of in-degree (Wuensche 1994a).

In RBN, as applied to gene regulatory networks (Kauffman 1969, Somogyi and Sniegoski 1996), the phase transition represents the phase in the wiring/rule setup where categorisation of patterns of gene activation, the network's memory, is sufficiently versatile for adaptive behaviour but short of chaotic to ensure reliable behaviour. Tuning the degree of "canalisation" at the level of rules (Kauffman 1984, Harris et al 1997) moves behaviour across the transition, though the characteristics of network connections also plays a role. A measure at the level of dynamics is given by the Derrida plot (Derrida and Stauffer 1986), analogous to the Liaponov exponent in continuous dynamics. There are further measures such as damage spreading, the percolation of frozen regions, input-entropy over time relating to single genes, and the transient/frozen skeleton/attractor characteristics.

The body of the thesis goes on to discuss these ideas in depth, based on published work by the author and work in progress. The introductory chapter describes and defines simple discrete dynamical networks ranging from CA to RBN and explains how network dynamics can be understood globally in terms of attractor basins. Comparisons are made with attractor basins in classical continuous dynamics. Previous work and applications in the field are discussed. Ideas of emergence, phase transitions and various measures and parameters relating to CA and RBN dynamics are introduced.

Chapter 2 looks more closely at the methods for constructing and portraying attractor basins.

Chapter 3 considers discrete dynamical networks and their attractor basins in the mathematical context of directed maps in random graph theory. Discrete dynamical networks are a subclass of random maps. Attractor basins of random maps, possibly incorporating some bias in the random mapping, are amenable to probabilistic analysis, which can be checked against a numerical reconstruction using

Chapter 4 focuses on CA and develops ideas first presented in the paper "Complexity in One-D Cellular Automata" (Wuensche 1994a) and subsequent work. The reverse algorithm for generating pre-images, and the Z parameter which derives from this procedure, are reviewed. The chapter looks in particular at new measures and results on attractor basins and how they relate to measures on local dynamics, characterising ordered to "complex" to chaotic behaviour, where complex behaviour corresponds to Wolfram's class 4 (Wolfram 1984a). A method is described for classifying CA rules by a measure of the variance of input-entropy over time. The method allows glider rules that support coherent interacting configurations and related complex rules to be found automatically giving a virtually unlimited sample for further study. Glider dynamics in CA is of prime interest as an example of self-organisation and emergence in simple systems, where all aspects of the system can be fully defined.

Chapters 5 focus on RBN, and develops ideas first presented in the papers "The Ghost in the Machine" (Wuensche 1993a) and "The Emergence of Memory" (Wuensche 1994b). Recent collaborative work on RBN as models of genomic regulatory networks is also described.

The reverse algorithm for generating pre-images in RBN is explained. The dynamics of RBN and intermediate network architectures are examined, in particular in the context of memory. The notion of memory far from equilibrium, categorisation by the roots of subtrees as well as by attractors is proposed. Algorithms for learning by "sculpting" the basin of attraction field are described. The inverse problem of finding the set of minimal RBN that will satisfy a predetermined set of transitions is discussed. Alternative methods for solving the inverse problem have recently been formulated independently by Manor Askenazi (1996) and John Myers (1996). The biological implications of memory far from equilibrium, and RBN or networks of RBN as the basis of a neural network model is discussed.

Chapter 5 goes on to discuss RBN as applied to model genomic regulatory networks, where cell types are explained as attractors or "frozen skeletons" in the dynamics of the network.

The thesis concludes with an overview of future work and open questions.