Saturday, July 4, 2009

John Holland: Hidden Order

I started to read John H. Holland's book "Hidden Order - How Adaption Builds Complexity". A few major ideas of this work will be summarized in the following post.

Cities, immune systems, central nervous systems and ecosystems as examples of Complex Adaptive Systems (CAS). CAS consist of interacting agents. Each agent is described by stimulus-response rules. Clusters of rules can generate any behaviour that can be computationally described. The range of available stimuli and responses determines the set of possible rules. Agents adapt to their environment by changing their stimulus-response rules based on experience: Learning. A large part of the environment consists of other agents.

There are 7 basic properties or mechanisms common to all CAS:

  • Aggregation
In the first sense: In order to model a system, we aggregate similar things into categories and then treat them as equivalent. In the second sense: Agents aggregate to meta-agents with new emergent properties, giving rise to hierarchical structures typical of CAS.

  • Tagging
Often several agents in a system appear indistinguishable from the outside, i.e. without closer interaction their differences are hidden. The CAS can break this symmetry of the semi-identical objects by tagging them (e.g., writing symbols on identical looking white balls). Also, different looking objects can be tagged as identical for other purposes. Tagging facilitates selective interactions and thus provides a basis for filtering, specialization, cooperation and hierarchical structure formation.

  • Nonlinearity
Using standard definition of linear function f(x,y,z..) = ax + by + cz +... Example for nonlinear interaction: Bimolecular reaction rates, such as f(x,y) = d/dt z(t) = a x(t)y(t). Nonlinearities typically prevent mathematical aggregation (model simplification by coarse-graining). This section of Holland's book is slightly confusing, in my opinion. In order to demonstrate the impossibility of coarse-graining a nonlinear system in the same way as a corresponding linear system, I would prefer an example such as this.

  • Flows
Typically, a CAS has a network structure of nodes (the agents) and links (the selective connections between agents). The dynamics of the CAS consists, beside the occasional addition or removal of nodes and links, mainly in a flow of some "material" (bio mass, chemicals, signals, goods, money, ..) through this network. The agents process the incoming flux of material into new forms and distribute it to their output nodes. Holland mentiones two general effects connected to flows. First, the "multiplier effect": If one injects additional material into a specific node, this node will typically retain a part of the extra amount and pass on a fraction r to its output nodes. In a linear chain of identical agents, the total change in the system created by the injection would be 1+r+r^2+r^3+... = 1/(1-r) > 1. So the initial change is multiplied. Second, the "recycling effect": If extra material is injected into a node that is part of a (sub-) network with loops, then the circling of the material can further increase the total effect dramatically. Also, due to circling the material is remaining longer within the system (Example: Food webs in rain forests).

  • Diversity
Diversity, i.e. the emergence of ever different types of agents and interactions, comes about because the agents actively try to find and occupy new niches by adaption (mutation and selection). After removing an agent, such niches are automatically refilled by similar agents (persistent patterns). With each new type of agent, further opportunities for interactions are created. In systems with recycling the number of opportunities for participation are particularly large.

  • Internal Models
Complex agents learn to behave in a given environment in a way that increases the probability of future reward. This requires to build an internal model of (relevant aspects of) the world, allowing to predict the results of actions. Models can be tacit (hardwired into the agent's stimulus-response machinery) or overt (explicit internal comparison of alternatives). They can be improved by adaption (variation and selection).

  • Building Blocks
CAS in complex environments have to respond to ever changing situations. They deal with this variety by decomposing novel situations into simpler, re-occuring and thus reusable building blocks. With a modest repertoire of nA variants of type A building blocks and nB variants of type B building blocks one can already compose nA*nB different composed objects, so this method is extremely efficient.

No comments:

Post a Comment