3. Distributed dynamical systems


Probabilistic cellular automata provide useful toy models of a wide range of physical and biological systems. A cellular automatonMathworldPlanetmath consists of a collectionMathworldPlanetmath of cells, each equipped with neighbors. Two important important examples are

Example 2 (Conway’s game of life).

The cellular automaton is a grid of deterministicMathworldPlanetmath cells with outputs {0,1}. A cell outputs 1 at time t iff: (i) three of its neighbors outputted 1s at time t-1 or (ii) it and two neighbors outputted 1s at t-1. Remarkably, a sufficiently large game of life grid can implement any deterministic computation [3].

Example 3 (Hopfield networks).

These are probabilistic cellular automata [4, 1], again with outputs {0,1}. Cell nk fires with probability proportional to

p(nk,t=1|n,t-1)exp[1Tjkαjknj,t-1].

Temperature T controls network stochasticity. Attractors {ξ1,,ξN} are embedded into a network by setting the connectivity matrix as αjk=μ=1N(2ξjμ-1)(2ξkμ-1).

It is useful to take a finer perspective on cellular automata by decomposing them into spacetime coordinates or occasions [2]. An occasion vl=ni,t is a cell ni at a time point t. Two occasions are linked vkvl if there is a connection from vk’s cell to vl’s (because they are neighbors or the same cell) and their time coordinates are t-1 and t respectively for some t, so occasions form a directed graph. More generally:

Definition 4.

A distributed dynamical systemMathworldPlanetmathPlanetmath 𝐃 consists of the following data:

  1. 𝐃1.

    Directed graph. A graph G𝐃=(V𝐃,E𝐃) with a finite setMathworldPlanetmath of vertices or occasions V𝐃={v1vn} and edges E𝐃V𝐃×V𝐃.

  2. 𝐃2.

    Alphabets. Each vertex vlV𝐃 has finite alphabet Al of outputs and finite alphabet Sl:=ksrc(l)Ak of inputs, where src(l)={vk|vkvl}.

  3. 𝐃3.

    Mechanisms. Each vertex vl is equipped with stochastic map 𝔪l:𝒱Sl𝒱Al.

Figure 1: Mapping a cellular automaton to a distributed dynamical system.

Taking any cellular automaton over a finite time interval [tα,tω] initializing the mechanisms at time tα with fixed values (initial conditions) or probability distributions (noise sources) yields a distributed dynamical system, see Fig. 1. Each cell of the original automatonMathworldPlanetmath corresponds to a series of occasions in the distributed dynamical system, one per time step.

Cells with memory – i.e. whose outputs depend on their neighbors outputs over multiple time steps – receive inputs from occasions more than one time step in the past. If a cell’s mechanism changes (learns) over time then different mechanisms are assigned to the cell’s occasions at different time points.

The sectionsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath below investigate the compositional structureMathworldPlanetmath of measurements: how they are built out of submeasurements. Technology for tracking subsystems and submeasurements is therefore necessary. We introduce two closely related categoriesMathworldPlanetmath:

Definition 5.

The category of subsystems 𝚂𝚢𝚜𝐃 of 𝐃 is a Boolean lattice with objects given by sets of ordered pairsMathworldPlanetmath of vertices 𝐂2¯V𝐃×V𝐃 and arrows given by inclusions i12:𝐂1𝐂2. The initial and terminal objects are 𝐃= and 𝐃=V𝐃×V𝐃.

Remark 2.

Subsystems are defined as ordered pairs of vertices, rather than subgraphs of the directed graph of 𝐃. Pairs of occasions that are not connected by edges are ineffective; they do not contribute to the information-processing performed by the system. We include them in the formalism precisely to make their lack of contribution explicit, see Remark 3 (http://planetmath.org/4measurement#Thmrem3).

Let src(𝐂)={vk|(vk,vl)𝐂} and similarly for trg(𝐂). Set the input alphabet of 𝐂 as the productPlanetmathPlanetmathPlanetmathPlanetmath of the output alphabets of its source occasions S𝐂=src(𝐂)Ak and similarly the output alphabet of 𝐂 as the product of the output alphabets of its target occasions A𝐂=trg(𝐂)Al.

Definition 6.

The category of measuring devices 𝙼𝚎𝚊𝚜𝐃 on 𝐃 has objects Hom𝚂𝚝𝚘𝚌𝚑(𝒱A𝐂,𝒱S𝐂) for 𝐂2¯V𝐃×V𝐃. For 𝐂1𝐂2 define arrow

r21:Hom(𝒱A𝐂2,𝒱S𝐂2) Hom(𝒱A𝐂1,𝒱S𝐂1)
[𝒱A𝐂2𝑇𝒱S𝐂2] [𝒱A𝐂1πA𝒱A𝐂2𝑇𝒱S𝐂2πS𝒱S𝐂1],

where πA and πS are shorthands for projections as in Example 1 (http://planetmath.org/2stochasticmaps#Thmeg1)

The reason for naming 𝙼𝚎𝚊𝚜𝐃 the category of measuring devices will become clear in §4 (http://planetmath.org/4measurement) below. The two categories are connected by contravariant functorMathworldPlanetmath :

Theorem 4 (structure presheaf).

The structure presheafPlanetmathPlanetmathPlanetmath F taking

𝐃:𝚂𝚢𝚜𝐃𝚘𝚙𝙼𝚎𝚊𝚜𝐃:𝐂Hom(𝒱A𝐂,𝒱S𝐂) and i12r21

satisfies the gluing axiom but has non-unique descent.

Proof: Functor is trivially a presheaf since it is contravariant. It is an interesting presheaf because the gluing axiom holds.

For gluing we need to show that for any collection {𝐂j}j=1l of subsystems and sections 𝔪j𝐃(𝐂j) such that rj,ji(𝔪j)=ri,ji(𝔪i) for all i, j there exists section 𝔪𝐃(j=1l𝐂j) such that ri(𝔪)=𝔪i for all i. This reduces to finding a conditional distribution that causes diagram

in 𝙼𝚎𝚊𝚜𝐃 to commute. The vertices are conditional distributions and the arrows are marginalizations, so rewrite as

where p(x|w)=v,zp(x,z|v,w)pmaxH(v) and similarly for the vertical arrow. It is easy to see that

p(x,y,z|u,v,w):=p(x,y|u,w)p(x,z|v,w)p(x|w)

satisfies the requirement.

For to be a sheaf it would also have to satisfy unique descent: the section satisfying the gluing axiom must not only exist for any collection {𝐂j}j=1l with compatible restrictionsPlanetmathPlanetmath but must also be unique. Descent in is not unique because there are many distributionsPlanetmathPlanetmath satisfying the requirement above: strictly speaking r is a marginalization operator rather than restriction. For example, there are many distributions p(y,z) that marginalize to give p(y) and p(z) besides the product distribution p(y)p(z).

The structure presheaf depends on the graph structure and alphabets; mechanisms play no role. We now construct a family of sections of using the mechanisms of 𝐃’s occasions. Specifically, given a subsystem 𝐂𝚂𝚢𝚜𝐃, we show how to glue its occasions’ mechanisms together to form joint mechanism 𝔪𝐂. The mechanism 𝔪𝐃=𝔪 of the entire system 𝐃 is recovered as a special case.

In general, subsystem 𝐂 is not isolated: it receives inputs along edges contained in 𝐃 but not in 𝐂. Inputs along these edges cannot be assigned a fixed value since in general there is no preferred element of Al. They also cannot be ignored since 𝔪l is defined as receiving inputs from all its sources. Nevertheless, the mechanism of 𝐂 should depend on 𝐂 alone. We therefore treat edges not in 𝐂 as sources of extrinsic noise by marginalizing with respect to the uniform distributionMathworldPlanetmath as in Corollary 3 (http://planetmath.org/2stochasticmaps#Thmthm3).

For each vertex vltrg(𝐂) let Sl𝐂=ksrc(l)src(C)Ak. We then have projection πl:𝒱Sl𝒱Sl𝐂. Define

𝔪l𝐂:=[𝒱Sl𝐂πl𝒱Sl𝔪l𝒱Al]. (1)

It follows immediately that 𝐂 is itself a distributed dynamical system defined by its graph, whose alphabets are inherited from 𝐃 and whose mechanisms are constructed by marginalizing.

Next, we tensor the mechanisms of individual occasions and glue them together using the diagonal map Δ:S𝐂vltrg(𝐂)Sl𝐂. The diagonal map used here11which is surjectivePlanetmathPlanetmath in the sense that all rows contain non-zero entries generalizes XΔX×X and removes redundancies in lSl𝐂, which may, for example, include the same source alphabets many times in different factors.

Let mechanism 𝔪𝐂 be

𝔪𝐂:=[𝒱S𝐂ιΔvltrg(𝐂)𝒱Sl𝐂vltrg(𝐂)𝔪l𝐂𝒱A𝐂]. (2)

The dual of 𝔪𝐂 is

𝔪𝐂:=[𝒱A𝐂𝒱S𝐂]. (3)

Finally, we find that we have constructed a family of sections of :

Definition 7.

The quale 𝐪𝐃 is the family of sections of constructed in Eqs. (1), (2) and (3)

𝐪𝐃:={𝔪𝐂(𝐂)=Hom(𝒱A𝐂,𝒱S𝐂)|𝐂𝚂𝚢𝚜𝐃}.

The construction used to glue together the mechanism of the entire system can also be used to construct the mechanism of any subsystem, which provides a window – the quale – into the compositional structure of distributed processes.

References

  • 1 DJ Amit (1989): Modelling brain function: the world of attractor neural networks. Cambridge University Press.
  • 2 David Balduzzi (2011): Detecting emergent processes in cellular automata with excess information. preprint .
  • 3 ER Berlekamp, JC Conway & RK Guy (1982): Winning Ways for your Mathematical Plays. 2, Academic Press.
  • 4 JJ Hopfield (1982): Neural networks and physical systems with emergent computational properties. Proc. Nat. Acad. Sci. 79, pp. 2554–2558.
    Title 3. Distributed dynamical systems
    Canonical name 3DistributedDynamicalSystems
    Date of creation 2014-04-30 18:41:46
    Last modified on 2014-04-30 18:41:46
    Owner rspuzio (6075)
    Last modified by rspuzio (6075)
    Numerical id 15
    Author rspuzio (6075)
    Entry type Feature
    Classification msc 60J20
    Classification msc 81P15
    Classification msc 18F20