Iterative Map
An iterative map involves a function that is applied recursively at each time step in a simulation. It can be visualised using a cartesian plot of x(t) against x(t-1). The line x(t) = x(t-1) is used as a reference point for tracing a path through the system.
Analysis of the existence of stable cycles on iterative maps gave rise to the understanding of deterministic chaos. The archetype explanation is given using the logistic map to show the number of states in the steady cycles of an iterative map. We see that when the coefficent of the function moves beyond a certain value (approx 3.6) we lose regularity and instead see unpredicatable behaviour.
This behaviour can be visualised as an attractor in the phase space of system. When done so we can see that although unpredictable the system often restricts itself to a particular subset of the space and maintains a fractal structure within this space.
Stochastic Map
A stochastic map is an iterative map, for which there we have introduced some element of randomness to the function that generates the next state on each iteration.
Random Walk
A random walk is a stochastic model for which we have a fixed probability distribution for determining what the next value of a particular variable will be. For instance, we could model a particle that can either walk up or down with equal probability on each iteration as a two dimensional random. Even though on average it will hover around the starting point, it can move away in either direction. Looking at the ensemble of possible walks the particle could make we will end up with a probability distribution of final positions.Markov Chain
The markov chain is an iterative description on a system involving a finite set of states and a probability matrix defining the transitions between states. The long term behaviour of the system can be analysed by tools from linear algebra.
Although it is possible to construct a markov chain model that includes dependencies across multiple time steps, it is not possible to include all time steps.
Equilibrium is the long term state where the probability distribution becomes fixed, which can be found using the eigenvalues of the matrix. Systems with an equilibrium state generally arrive there exponentially.
Monte Carlo Process
The term Monte Carlo process refers generally to the use of statistical sampling within an algorithm for estimation. In application to simulations, it is a technique that can be employed within the update function to avoid performing all the calculations of the underlying dynamics. Instead the simulation needs only to perform the following:
- Choose one of the available next states randomly
- Evaluate the probability the system would move to this state
- Use a random number generator to decide whether this transition occurs.
This procedure can allow a simulation to include global constraints on the system dynamics, by their inclusion within the calculation of probability transitions. It generally allows for the simulation of systems with complicated dynamics without needing to explicitly enumerate and explore all possible states of the system.
Information Theory
Quantification of the amount of information in a given message. For n characters equally likely to occur this is:
I = log2n
However if the characters do not occur with equal probability this needs to be generalised to:
I = - ∑i=1n ( P(xi) * log2P(xi) )
Which reduces to the previous equation when the probailities are equal.
Fractal Dimension
A fractal is a geometrical object that is self similar at any scale of observation. The existence of fractals creates a problem for the use of calculus in science because calculus assumes that reality becomes smoother at finer scales.
A fractal has a dimenion which is not an integer. For instance, we can generate a Koch curve by taking the middle third of a line and replacing it with two sections of equal length as a partial triangle. We then repeat this process indefinately on all line segments. This object has a dimension greater than one because it is infinite in length, in effect it has no length. But it has a dimension less that two because it has no area.
The fractal dimension is calculated using the equation:
D = log N / log S
Where N is the number of smaller objects required to cover the whole object and S is the scaling relationship between the smaller objects and the whole.
This notion can be generalised to give a fractal dimension of objects that are not strictly self similar.
If we imagine covering the whole object with a single disc radius R1, and covering the object with n smaller discs discs of radius R2. Then the fractal dimension is given by:
D = log(n) / log(R1/R2)
For example the Koch curve can be covered by a single disc with a radius equal to half the length of the original line. It may also be cover by four discs with a radius one third of this larger disc, hence the fractal dimension is given by:
D = log(4)/ log(3) = 1.26
Renormalisation
Renormalisation is a technique from the analysis of physical systems, demonstrated using the Ising model. In the Ising model a lattice of magnetic particles are experiencing frustration because of their inability to find an equilibrium. As the system evolves over time particles flip their direction depending on the magnetic direction of their nearest neibours and the total magnetic field in which they are embedded.
Renormalisation involves changing the scale of observation by grouping together particular subsets of the particles and treating them as an individual particle. By then observing the behaviour of this aggregated system, we can see whether the dynamic behaviour of the system is sustained across a change in scale, or if and how it has changed.
Patterns in Brain & Mind
Attractor or auto-associative networks model content addressable memory by storing patterns that can be retrieved by partial information. A set of signals are imprinted on the network by Hebbian learning, and then retrived by presenting part of the original signal. The number of patterns that can be reliably imprinted is proportional to the number of nodes, approx 0.145N, if the network is fully connected.
In the human mind we find that networks of neurons are not completely connected which raises the question, why is the human mind an impartially connected or subdivided network.
The answer lies with the fact that if the subdivisions are done to deliberately exploit order in the world, then the subdivided pattern recognisers can be combined to expoit the combinatorics. For example a network of 100 nodes can recognise approx 14 patterns. Split into two networks, each can recognise 7 patterns, which allows 7 * 7 = 49 combinations of the two patterns.
It is crucial to note that in evolving to exploit external order this way, the brain has effectively impaired its ability to recognise patterns that do not fit with the assumed order.
References:
Y. Bar-Yam, Dynamics of Complex Systems. Perseus, 1997. Available Online
Y. Bar-Yam, Unifying Principles in Complex Systems, in Converging Technology (NBIC) for Improving Human Performance, M. C. Roco and W. S. Bainbridge eds, Kluwer, 2003.
Emergence
The notion of emergence is an attempt to describe the way that global properties of a systems come into existence due to the interactions of the components. It is somewhat dependant on the idea that these emergent properties are not disernible from the study of the components in isolation.
Indeed, there are many philosophical debates made about the exact definition of an emergent property, so I will outline two of the clarifying distinctions.
Local vs Global: Local emergence refers to properties that can be predicted by examining subsets of the system, i.e temperature by looking at a small sample of a gas. Global emergence refers to properties that require observation of the entire system, for example the homeostatic properties of cells cannot be predicted by examining any subset of the components.
Strong vs Weak: Weak emergence is the claim that these properties are merely surprising or counter intuitive. Strong emergence is the claim that the properties are in principle impossible to determine from knowledge of the parts and their relationhips alone.
Further reading
David Chalmers: Varieties of Emergence
Yaneer Bar-Yam: A Mathematical Theory of Strong Emergence using Multiscale Variety
Universality
During the process of model building it can be observed that there are classes or clusters of models which all produce behaviour that is qualitatively similar. As we move in The space of possible models we observe periods of relative stability, followed by a drastic change as we move into another class of model. These clusters describe classes of dynamical behaviour that are in some sense universal. Due to their relative stability over an area of model space, we can expect to observe them embodied in disparate systems.
Universality also provides hope for modelers. We can see that a model need not be a perfect representation of the system in order to capture the correct qualitative behaviour. Conversely it acts as a caution, observation of the correct behaviour does not indicate that the model is perfect.
Evolution
The complex systems critique of evolution focuses on the belief described as gene-centred Neo-Darwinism, which seeks to explain biological changes in terms of fluctuations of individual genes within a population.
Many naïve evolutionary models have made the following misleading assumptions about evolutionary process:
- That fitness can be adequately ascribed to each individual gene and maintains some constancy over time.
- That reproduction is at its essence random sampling from the population and we can thus model fluctuations in population genetics with random sampling.
- That there are no dynamical processes happening at the individual or group level that affect evolution and cannot be reduced to the fitness of individual genes.
As soon as we attempt to model evolution using epistatic gene interactions, with organisms spread in some spatial arrangement and reproduction being constrained by spatial considerations we begin to see predictions that differ radically from those given by Fisherian models.
Sometimes the long term behaviour of the models will be the same, however the spatial models will require logarithmic time to arrive at the equilibrium. This effectively means that under the time constraints of real evolving systems we will see fundamentally different dynamics.
References:
H. Sayama and Y. Bar-Yam: The gene centered view of evolution and symmetry breaking and pattern formation in spatially distributed evolutionary processes, Nonlinear Dynamics in the Life and Social Sciences, W. Sulis and I. Trofimova, eds., NATO Science Series A/320, pp.360-368, 2001, IOS Press.
H. Sayama, L. Kaufman and Y. Bar-Yam: Symmetry breaking and coarsening in spatially distributed evolutionary processes including sexual reproduction and disruptive selection, Physical Review E 62, pp.7065-7069, 2000;
Y. Bar-Yam: Formalizing the gene centered view of evolution, Advances in Complex Systems 2, pp.277-281, 1999; and my texbook (chapter 6).
Random Boolean Networks
Kauffman has a number of theories about biology which he uses the idealised RBN model to explore. The first is that some of the order of biological systems results from organisational dynamics rather than evolution. He calls this 'order for free'. Secondly that what constitutes a cell type is not a static pattern of genes being on or off, but an attractor in the phase space of gene regulation.
The NK RBNs consist of a network of N elements connected to K other elements. Each node has a boolean state and the entire network is isolated from any external interaction. The dynamical evolution of the network is described by a boolean function on each of the nodes in the network. This boolean function defines the state of the node in the next time step as a function of the states of the nodes that connect to it.
His approach consists of constructing ensembles of random networks with a specified values for N and K, and then exploring the structure and stability of the attractors that form. Structure is specified by the number of attrctors and their length. Stability is specified by the extent to which they return to the attractor when a single gene is flipped into the opposite state.
The dynamics of such networks are considered to become chaotic once the length of the attractors starts to increase toward the total number of states in the system.
Kauffman's essential finding was that for networks with a value of K equal to 2, we find that the attractors have a length of approx N1/2 and that they are relatively stable. For values of K greater than 2, we find much longer attractors, of the order 2N/2.
The other factor that affected the stability and size of the attractors was the proportion of canalysing functions. These are functions which have regions where the output is independent of a change in at least one of the inputs. For example, both AND and OR functions are canalysing wheras XOR is non-canalysing. A network with a higher proportion of canalysing functions will tend to have much more stable attractors.
Kauffman argues that the value of K in a biological system will almost inevitably grow with the complexity of the system because of the emergence of unpreditable interactions. However nature has managed to keep its cellular systems within the ordered regime by selecting for canalysing funtions.