Fishwick P.A. (editor) Handbook of Dynamic System Modeling
Подождите немного. Документ загружается.
21-14 Handbook of Dynamic System Modeling
0
12 bits 20 bits
0
01
0
32
19
X
32
19
X
341024
273
138
2
19
X
2
19
X
02
19
3
02
19
2
0
138
273
41024
2
19
1
2
19
3
2
19
2
2
19
1
2
0
1
2
FIGURE 21.10 Collision table. The first 2
19
indices are divided into 12 and 20 bits. The left 12 bits denote the number
of collision outcomes, the rightmost 20 bits denote an index number from where the collision outcomes are stored in
the table. These collision outcomes start from index 2
19
. The figure shows an example for an equivalence class of size 3.
21.5.4 Some Applications
Lattice gases have been and are still being applied
6
to challenging problems of multiphase fluids in complex
(e.g., porous) flow domains. These typically include fluid mixtures and colloids, reaction diffusions
systems, immiscible fluids and phase separation, multiphase flows, fluids with free interfaces, magneto
hydrodynamics, nonideal fluids, etc. Because of the ease to define boundary conditions using the bounce
back rule, all such complex fluids have been studied in porous media. For details we refer to the LGCA
books and references therein (Rivet and Boon, 2001; Rothman and Zaleski, 1997; Chopard and Droz,
1998).
21.5.5 Lattice Boltzmann Method
Immediately after the discovery of LGCA as a model for hydrodynamics in 1986, it was criticized on
three points. LGCA have noisy dynamics, lack Galilean invariance, and have an exponential complexity
of the collision operator. The noisy dynamics is clearly illustrated in Figure 21.8 and the lack of Galilean
invariance was discussed above. Adding more velocities in an LGCA leads to increasingly more complex
collision operators, exponentially in the number of particles (remember the numbers for GBL and FCHC).
Therefore, another model, the lattice Boltzmann method (LBM), was introduced. This method is reviewed
in detail in Succi (2001).
The basic idea is that one should not model the individual particles n
i
, but immediately the particle
densities f
i
, i.e., one iterates the lattice Boltzmann equation (Eq. [21.11]). This means that particle densities
are streamed from cell to cell, and particle densities collide, immediately solving the problem of noisy
6
Although it must be said that the Lattice Boltzmann method, which will be mentioned in the next section, currently
is the preferred method over LGCAs, although in special situations LGCAs are still to be preferred.
Modeling Dynamic Systems with Cellular Automata 21-15
FIGURE 21.11 (a) Flow in a porous fiber mat; and (b) a porous medium composed of a dense random packing of
spheres.
dynamics. However, in a strict sense, we no longer have a CA with a Boolean state vector (in fact, the state
is now a vector of real numbers, so the state space per node is infinite). However, we can view LBM as a
generalized CA. By a clever choice of the equilibrium distributions f
0
i
, the model becomes isotropic and
Galilean invariant, thus solving the second problem of LGCA. Finally, a very simple collision operator can
be introduced. This so-called BGK collision operator models the collisions as a single-time relaxation τ,
toward equilibrium, i.e.,
BGK
i
(N) =−
1
τ
f
i
−f
0
i
(21.16)
Eq (21.11) and Eq. (21.16) together with a definition of the equilibrium distributions result in the Lattice-
BGK (L-BGK) model. The L-BGK model leads to correct hydrodynamic behavior in two and three
dimensions. The L-BGK not only applies to the triangular lattice, but also correctly works for other
lattices, e.g., 2- or 3D cubical lattices with nearest and next-nearest neighbor interactions. The LBM
and especially the L-BGK have found widespread use in simulations of highly complex fluid dynamical
problems, including turbulence, multiphase flows, spinal decomposition, etc. To get a flavor we refer
to Succi (2001). Below we present a few examples of successful L-BGK applications. All these L-BGK
simulations were routinely executed on parallel computers, using a highly efficient parallel implementation
of the L-BGK method (Kandhai et al., 1998).
The L-BGK method has played a significant role in studying flow in porous media. In Figure 21.11(a),
we show an example of flow in a porous medium that consists of randomly placed fibers. This fiber mat
is a model system for paper. Through L-BGK simulations, one can compute the permeability of such fiber
mats, as a function of the porosity (Kopenen, et al., 1998). The results showed a remarkable agreement with
experimental results. Since the permeability could be studied over a very large range of volume fractions,
much larger than accessible through experiments, the authors were able to check the quality of theoretical
approximations for this particular problem.
Another example of successful L-BGK simulations of flow in porous media was the transient dispersion
in homogeneous porous media. Figure 21.11(b) shows an example of a medium of a random distribution
21-16 Handbook of Dynamic System Modeling
FIGURE 21.12 (a) Flow in a static mixer reactor; and (b) flow in the lower abdominal aortic bifurcation at peak
systole.
of densely packed spheres. Here the flow around the spheres is computed, as well as advection-diffusion
of tracer particles in the flow, and diffusion of the tracer particles through a microporous structure of
the spheres. From these simulations, the authors could derive transient tracer dispersion curves, which
showed a very good agreement with propagators that were measured using nuclear magnetic resonance
(Kandhai et al., 2002a, 2002b).
L-BGK simulations have been compared extensively with traditional computational fluid dynamics
(CFD) codes. As an example, we mention flow through a static mixer reactor (see Figure 21.12[a]).
The flow fields as computed with L-BGK were in very good agreement with results stemming from a
commercial CFD package (FLUENT). The computed fluid flux through the system, as a function of the
applied pressure gradient, was in very good agreement with experimental data (Kandhai et al., 1999). It
turned out that preparing the computational grid for L-BGK is trivial (just a Cartesian grid), whereas
creating a body-fitted finite element grid for this geometry is very tedious.
As a final example we mention the application of L-BGK for simulation of blood flow. In Figure 21.12(b),
we show the results of L-BGK simulations of time periodic systolic flow through the bifurcation of the
lower abdominal aorta. The geometry is taken from MRI images of real patients. The results are in good
agreement with previously published studies of systolic flow in region of the arterial tree (Artoli et al.,
2005).
References
Artoli, A.M.M., A.G. Hoekstra, and P.M.A. Sloot. 2005. Mesoscopic simulations of systolic flow in the
human abdominal aorta. Journal of Biomechanics 39: 873–884.
Automata. 2005. 11th Workshop on Cellular Automata, Gdansk, 3–5 September 2005
http://iftia9.univ.gda.pl/∼CA2005/
Bandini, S. 2002. Special issue on cellular automata. Future Generation Computing Systems 18: 871–1004.
Berec, L. 2002. Techniques of spatially explicit individual-based models: Construction, simulation and
mean-field analysis. Ecological Modelling 150: 55–81.
Modeling Dynamic Systems with Cellular Automata 21-17
Boghosian, B.M. 1999. Lattice gas and cellular automata. Future Generation Computing Systems 16:
171–185.
Boon, J.P., D. Dab, R. Kapral, and A. Lawniczak. 1996. Lattice gas automata for reactive systems. Physics.
Reports 273: 556–647.
Burks, A.W. 1970. Essays on Cellular Automata. Urbana, IL: University of Illinois Press.
Chopard, B. and M. Droz. 1998. Cellular Automata Modeling of Physical Systems. Cambridge: Cambridge
University Press.
Deutsch, A. and S. Dormann. 2004. Cellular Automaton Modeling of Biological Pattern Formation. Basel:
Birkhauser.
d’Humières, D., Lallemand, P., and Frisch, U. 1986. Lattice gas models for 3-D hydrodynamics. Europhysics
Letters 2: 291–297.
Dubbeldam, D., A.G. Hoekstra, and P.M.A. Sloot. 1999. Computational aspects of multi-species lattice-
gas automata. In P.M.A. Sloot, M.T. Bubak, A.G. Hoekstra, and L.O. Hertzberger (Eds.), High-
Performance Computing and Networking, Amsterdam, The Netherlands, Lecture Notes in Computer
Science, 1593: 339–349. Berlin: Springer-Verlag.
Farmer, D., T. Toffoli, and S. Wolfram. 1984. Cellular Automata: Proceedings of an Interdisciplinary
Workshop. Amsterdam: North-Holland.
Forrest,S. 1990. Emergent computation: Self-organizing, collective, and cooperative phenomena in natural
and artificial computing networks. Physica D 42: 1–11.
Frisch, U., D. d’Humières, B. Hasslacher, P. Lallemand, P. Pomeau, and J.-P. Rivet. 1987. Lattice gas
hydrodynamics in two and three dimensions. Complex Systems 1: 649–707.
Frisch, U., B. Hasslacher, and Y. Pomeau. 1986. Lattice-gas automata for the Navier–Stokes Equation.
Physical Review Letters 56: 1505–1508.
Ganguly, N., B.K. Sikdar, A. Deutsch, G. Canright, and P.P. Chaudhuri. 2003. A survey on cellular
automata. Technical Report, Centre for High Performance Computing, Dresden University of
Technology. http://www.cs.unibo.it/bison/publications/CAsurvey.pdf
Grosfils, P., J.P. Boon, and P. Lallemand. 1992. Spontaneous fluctuation correlations in thermal lattice gas
automata. Physical Review Letters 68: 1077–1080.
Gutowitz, H.A. 1990. Cellular Automata. Cambridge, MA: MIT Press.
Hardy, P., O. de Pazzis, and Y. Pomeau. 1976. Molecular dynamics of a classical lattice gas: Transport
properties and time correlation functions. Physical Review A 13: 1949–1961.
Hardy, P. and Y. Pomeau. 1972. Thermodynamics and hydrodynamics for a modeled fluid. Journal of
Mathematical Physics 13: 1042–1051.
Hardy, P., Y. Pomeau, and O. de Pazzis. 1973. Time evolution of a two-dimensional model system. I.
Invariant states and time correlation functions. Journal of Mathematical Physics 14: 1746–1759.
Hénon, M. 1987. Isometric collision rules for the 4-D FCHC lattice gas. Complex Systems 1: 475–494.
Ilachinski, A. 2001. Cellular Automata, a Discrete Universe. Singapore: World Scientific.
Jesshope, C., V. Jossifov, and W. Wilhelmi. 1994. International Workshop on Parallel Processing by Cellular
Automata and Arrays (Parcella’94). Berlin: Akademie Verlag.
Kaandorp, J.A., C.P. Lowe, D. Frenkel, and P.M.A. Sloot. 1996. The effect of nutrient diffusion and flow
on coral morphology. Physical Review Letters 77: 2328–2331.
Kadanoff, L.P. and J.Swift. 1968. Transport coefficientsnear the critical point: A master-equation approach.
Physical Review 165: 310–322.
Kandhai, B.D., D. Hlushkou, A.G. Hoekstra, P.M.A. Sloot, H. van As, and U. Tallarek. 2002a. Influence
of stagnant zones on transient and asymptotic dispersion in macroscopically homogeneous porous
media. Physical Review Letters 88: 234501.
Kandhai, B.D., A. Koponen, A.G. Hoekstra, M. Kataja, J. Timonen, and P.M.A. Sloot. 1998. Lattice
Boltzmann hydrodynamics on parallel systems. Computer Physics Communications 111: 14–26.
Kandhai, B.D., U. Tallarek, D. Hlushkou, A.G. Hoekstra, P.M.A. Sloot, and H. van As. 2002b. Numerical
simulation and measurement of liquid hold-up in biporous media containing discrete stagnant
zones. Philosophical Transactions: Mathematical, Physical & Engineering Sciences 360: 521–534.
21-18 Handbook of Dynamic System Modeling
Kandhai, B.D., D.J.-E. Vidal, A.G. Hoekstra, H.C.J. Hoefsloot, P. Iedema, and P.M.A. Sloot. 1999. Lattice-
Boltzmann and finite element simulations of fluid flow in a SMRX mixer. International Journal for
Numerical Methods Fluids 31: 1019–1033.
Koponen, A., D.B. Kandhai, E. Héllen, M. Alava, A.G. Hoekstra, M. Kataja, K. Niskanen, P.M.A. Sloot, and
J. Timonen. 1998. Permeability of three-dimensional random fibre webs. Physical Review Letters 80:
716–719.
Kurzweil, R. 2002. Reflections on Stephen Wolfram’s ‘A New Kind of Science’. http://www.kurzweilai.net/
meme/frame.html?main=/articles/art0464.html
May, R.M. 1976. Simple mathematical models with very complicated dynamics. Nature 261: 459–467.
Mitchell, M. 1998. Computation in cellular automata: A selected review. In T. Gramss, S. Bornholdt,
M. Gross, M. Mitchell, and T. Pellizzari (Eds.), Nonstandard Computation, pp. 95–140. Weinheim:
VCH Verlagsgesellschaft.
Naumov, L. 2004. CAMEL—Cellular Automata Modeling Environment & Library. Cellular Automata.
6th International Conference on Cellular Automata for Research and Industry. Lecture Notes in
Computer Science, 3305: 735–744. Heidelberg: Springer.
NKS Conference. 2005. http://www.cs.indiana.edu/∼dgerman/2005midwestNKSconference/index.html
Rivet, J.-P. and J.P. Boon. 2001. Lattice Gas Hydrodynamics. Cambridge: Cambridge University Press.
Rothman, D.H. and S. Zaleski. 1997. Lattice-Gas Cellular Automata, Simple Models of Complex
Hydrodynamics. Cambridge: Cambridge University Press.
Sloot, P.M.A. 1999. High performance simulation with cellular automata. In N. Piskunov (Ed.),
Proceedings of HiPer’99, pp. 169–207. Computer Centre University of Tromso, Tromso, Sweden.
Sloot, P.M.A., F. Chen, and C.A. Boucher. 2002. Cellular automata model of drug therapy for HIV infection.
Lecture Notes in Computer Science 2493: 282–293.
Sloot, P.M.A., B. Chopard, and A.G. Hoekstra. 2004. Cellular Automata: 6th International Conference on
Cellular Automata for Research and Industry, ACRI 2004, Amsterdam, The Netherlands, October
2004. Lecture Notes in Computer Science, 3305. Heidelberg: Springer.
Sloot, P.M.A. and A.G. Hoekstra. 2001. Cellular automata as a mesoscopic approach to model and simulate
complex systems. Lecture Notes in Computer Science, 2074 (II): 518–527. Heidelberg: Springer.
Sloot, P.M.A., J.A. Kaandorp, A.G. Hoekstra, and B.J. Overeinder. 2001a. Distributed cellular automata:
Large scale simulation of natural Phenomena. In A.Y. Zomaya, F. Ercal, and S. Olariu (Eds.),
Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences, pp. 1–46.
Wiley: New York.
Sloot, P.M.A., B.J. Overeinder, and A. Schoneveld. 2001b. Self-organized criticality in simulated correlated
systems. Computer Physics Communications 142: 76–81.
Sloot, P.M.A., A. Schoneveld, J.F. de Ronde, and J.A. Kaandorp. 1997. Large scale simulations of complex
systems Part I: Conceptual framework. SFI Working Paper: 97-07-070, Santa Fe Institute for Complex
Studies.
Succi, S. 2001. The Lattice Boltzmann Equation, for Fluid Dynamics and Beyond. Oxford: Clarendon Press.
Turing, A.M. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceed-
ings of the London Mathematical Society, Ser. 2, Vol. 42; and extract On computable numbers, with
an application to the entscheidungsproblem. A correction. Proceedings of the London Mathematical
Society, Ser. 2, Vol. 43, 1937.
Ulam, S. 1952. Random processes and transformations. Proceedings of the International Congress on
Mathematics 2: 264–275.
Ulam, S. 1962. On some mathematical problems connected with patterns of growth of figures. Proceedings
of Symposia in Applied Mathematics, Vol. 14, pp. 215–224. Providence: American Mathematical
Society.
von Neumann, J. 1951. The general and logical theory of automata. In L.A. Jeffress (Ed.), Cerebral
Mechanisms and Behavior: The Hixon Symposium, pp. 1–41. Wiley: New York.
von Neumann, J. 1966. Theory of Self-Reproducing Automata. Urbana, IL: University of Illinois Press.
Modeling Dynamic Systems with Cellular Automata 21-19
Wiener, N. and Rosenbleuth, A. 1946. The mathematical formulation of the problem of conduction of
impulses in a network of connected excitable elements, specifically in cardiac muscle. Archivos del
Instituto de Cardiologica de Mexico 16: 202–265.
Wolf-Gladrow, D.A. 2000. Lattice-Gas Cellular Automata and Lattice Boltzmann Models. Heidelberg:
Springer
Wolfram, S. 1986a. Theory and Applications of Cellular Automata. Singapore: World Scientific.
Wolfram, S. 1986b. Journal of Statistical Physics 45: 471–526.
Wolfram, S. 2002. A New Kind of Science. Champaign, IL: Wolfram Media.
Zuse, K. 1982. The computing universe. International Journal of Theoretical Physics 21: 589–600.
Zuse, K. 1967. Rechnender Raum. Elektronische Datenverarbeitung 8: 336–344. See also: http://www.idsia.
ch/∼juergen/digitalphysics.html
22
Spatio-Temporal
Connectionist Networks
Stefan C. Kremer
University of Guelph
22.1 Introduction .................................................................. 22-1
22.2 Connectionist Networks (CNs) .................................... 22-2
Basic Approach
•
Function Approximation
•
Learning
22.3 Spatio-Temporal Connectionist Networks .................. 22-4
Basic Approach
•
Specific Architectures
22.4 Representational Power ................................................ 22-6
22.5 Learning ......................................................................... 22-6
22.6 Applications ................................................................... 22-8
22.7 Conclusion .................................................................... 22-9
22.1 Introduction
In this chapter, we look at a popular class of dynamical systems that are based on simplified models of
how the brain processes information. These systems fall under the heading of artificial neural networks
called spatio-temporal connectionist networks (SCNs). SCNs are particularly interesting because they
are capable of representing all dynamical systems and all models of computation. This means that they
are as powerful (in terms of what they can do) as all other dynamical and computational systems. In
addition, these systems also typically embody adaptive mechanisms. That means they are capable of
changing over time to suit a particular task. In particular, the systems incorporate algorithms that allow
themtobetrained to match a dataset of example behavior. Furthermore, they are able to both interpolate
and extrapolate. This means that they can perform well, not only on the data that was used to train the
system, but also on other data that has never been seen. In short, regularization can serve to address data
points beyond those available during the adaptation process and SCNs are thus able to generalize to novel
situations.
The chapter is organized as follows. In Section 22.2, we begin with a brief exposition of connectionist
(also called neural) networks, the basic model underlying all SCNs. We also examine the role of SCNs
within this paradigm. We follow this, in Section 22.3, with a generalized and comprehensive SCN model
to formalize the definition of SCNs and also present some specific examples popularized in the literature.
Then, in Section 22.4, we examine the representational power of this class of dynamical systems. Next, in
Section 22.5, we address the issue of adapting SCNs including a discussion of the challenges involved in
this type of inference. In Section 22.6, we present a brief survey of some applications to which SCNs have
been applied. Finally, in Section 22.7 we give some concluding remarks and avenues for future research.
Throughout the chapter, we present references to the source literature so that the reader can follow up
with a more extensive examination of the materials.
22-1
22-2 Handbook of Dynamic System Modeling
22.2 Connectionist Networks (CNs)
Computer models of how neurons in the brain process information date back to the 1940s (McCulloch
and Pitts, 1943). More recently these models have been used for two different (though not necessarily
exclusive) purposes: either (1) to provide a model of brain function designed to correlate with actual
brain behavior (in other words, to model real brains) or (2) to provide a computational architecture for
systems designed to mimic intelligent behavior (or, to build “artificial intelligence”). While biologists and
neuroscientists typically focus on the former goal, cognitive scientists, computer scientists, and engineers
usually focus on the latter.
In an attempt to build a computational system designed to exhibit intelligent behavior, a number of
models have been developed. These models focus on analog computation, parallel implementation
and distributed information representation and processing. This means that they process real-valued
(continuous) numbers as opposed to the binary representations common in most computer systems.
They also process multiple streams of information in parallel and store pieces of information, not just
in one location, but spread across many venues. We shall refer to these models as CNs as this reflects
their essential character though the terms artificial neural networks, PDP systems, and others are also in
popular use.
22.2.1 Basic Approach
The key to CNs as a computational paradigm is their difference from the typical von Neumann architecture.
Specifically, CNs consist of many small and simple processing elements (PEs) that have an internal state
and communicate with each other through connections to achieve complex tasks. The basic operation of
a PE can be summarized by the following equation:
a
i
= f
j
w
ij
·a
j
(22.1)
where, a
i
represents the state or activation of PE i, f () is a transfer function, j an index over all PEs
connected to PE i, w
ij
the weight of the connection from j to i, and a
j
the activation value of PE j.The
transfer function is typically a sigmoid function such as tanh or the logistic: 1/(1 +e
−x
). Basically, we
compute a weighted average of the activations of units a
j
and then feed the average to an s-shaped transfer
function, which limits the output of each process into the range from zero to one.
To prevent circular definitions of the activation (where an activation directly or indirectly depends on
itself), we enforce a specific constraint. This constraint says that the nodes in the network must be ordered,
and that no higher-ordered node can connect to any lower-ordered node, i.e., we requiring that w
ji
=0
∀j ≤i. In mathematical terms, this ensures that the connectivity is limited to a directed acyclic graph (i.e.,
connections have a direction and there are no loops).
In practice, connection schemes more restrictive than directed acyclic graphs are implemented in the
form of layered architectures. That is, the PEs of the CN are organized into layers with connections only
existing between successive layers. Input information to the CN is encoded in a special layer (usually
called the input layer) that has its activation values explicitly set rather than obeying Eq. 22.1 like layers
of PEs. Also one special element in the network, called a bias, has its activation permanently set to a
value of 1. This provides a zero-offset to the summation in Eq. 22.1. Without this offset every hidden
unit would produce a value of 0.5 whenever the input values are all zeros. The inclusion of the bias with
a trainable weight makes it possible to generate any activation in the hidden units when the inputs are
all zero.
By far the most common connectionist network consists of an input layer of elements that encode the
input information, connected to a layer of hidden (or internal) elements, connected to a layer of output
elements which provide the resulting data. In such networks, each input unit is connected to each hidden
unit and each hidden unit is connected to each output unit (see Figure 22.1).
Spatio-Temporal Connectionist Networks 22-3
Input layer
Hidden layer
Output layer
FIGURE 22.1 A typical connectionist network (CN).
There are a few variations on the basic PE presented here, one of the more notable of which is the
use of second-order connections replace the linear summation in Eq. 22.1 by a quadratic (Giles and
Maxwell, 1987):
a
i
= f
j,k
w
kji
·a
k
·a
j
(22.2)
Because this equation multiplies two activations together, it can be viewed as a generalization of the AND
function in the sense that input activations of 0 and 1 elicit responses of 0 and 1 that are consistent with
the Boolean AND function.
22.2.2 Function Approximation
Another way to view a CN is as a continuous function, mapping from input data to output data. Since both
input and output data are expressed as real-valued activation values of PEs, the operation can be expressed
as a function mapping a vector in the n-dimensional input space to a vector in the m-dimensional output
space:
n
→
m
. Under this formulation, it is natural to ask, “for a given network architecture (defined
by connectivity scheme), what is the class of vector functions that can be implemented”?
It turns out that simple networks of PEs are surprisingly powerful. For example, simple CNs with a
single layer of PEs between an input and an output layer are universal function approximators (Hornik
et al., 1989). This speaks to the computational versatility of this approach and suggests that more elaborate
connection schemes, PEs, are not necessary.
22.2.3 Learning
One of the most exciting features of CNs is that many define an adaptation mechanism in addition to their
computational specification. These are typically referred to as learning algorithms. Such algorithms can be
broadly classified into two categories: (1) unsupervised and (2) supervised. Adaptation in unsupervised
learning algorithms is based solely on their input data and typically performs tasks such as clustering,
nearest neighbor identification, and data completion. In contrast, supervised learning algorithms rely on
an external mechanism to provide additional information about the desired output values. Often the exact
output vector for each input vector is provided. (One other alternative, that of semisupervised training
methods, has recently received some attention in the CN paradigm,but has thus far not had much influence
in the spatio-temporal versions we will discuss below.)
By far the most common learning algorithms for CNs are based on approaches that compute an error
gradient in weight space. By defining the error as the Euclidean difference between target, a
∗
, and actual,
a, output vectors,
E =|a
∗
−a| (22.3)