Dynamical Systems
HOME LINKS RESEARCH PUBLICATIONS
Contents
Dynamical Automata by Tabor
Dynamical Recognizers: Real-Time Language Recognition by Analog Computers by Moore
Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems by Branicky
The Induction of Dynamical Recognizers by Pollack
Analysis of Dynamical Recognizers by Blair and Pollack
The aim of this article was to outline the work that has been carried out previously in the area of dynamical automata, and the author’s suggestion for a new approach to this area. The author looks at the metric space organisation (instead of simply the classification of the grammar), as well as the representation in real valued automata, which should allow better understanding of the computation that is carried out.
Informal and formal mathematical proof that pushdown dynamical automata (PDDA) are equivalent to pushdown automata (PDA). This required that first both PDA and PDDA be defined, and then shown to be equivalent. The simulations that were carried out as part of this research were designed to show that neural networks could function as PDDA. The network was created using signalling and gating units.
The author suggests a couple of new areas that should be followed up, based on the preliminary work that has been carried out in this article. These include looking at the Chomsky Hierarchy Relationships from a metric space point of view, attempting to approximate Infinite Machines, extending the work that has been carried out on PDDA in neural networks (so far, neural networks have been remakes of computers that can be built on standard machinery). The most value that was gained out of this article was the treatment of dynamical automata – some of the concepts were clearly and concisely explained and their relationship to neural networks outlined.
Go to Tabor’s Technical Report “Dynamical Automata”:
http://www.sp.uconn.edu/~ps300vc/papers.html
Reference details for “Dynamical Automata”:
Tabor, W., 1998, Dynamical Automata. Technical Report No. TR98-1694, Cornell Computer Science Department.
A pushdown automaton is a device with the following structure:
M = (Q, S, G, d, qo, Zo, F)
Where:
Q is a finite set of states
S is a finite alphabet (the input alphabet)
G is a finite alphabet (the stack alphabet)
qo is an element of Q (the initial state)
Zo is an element of G (the start symbol)
F is a subset of Q (the set of final states)
d is a mapping from Q x (S U {e}) x G to infinite subsets of Q x G*.
Moore – Dynamical Recognizers: Real-Time Language Recognition by Analog Computers
This article examines the mathematical foundations of an analog computer that can recognise languages in real time. The paper examines different classes of dynamical recognizers, and the corresponding classes of languages that they recognize. The classes of language are either deterministic or non-deterministic (denoted by N). Language classes are then defined as being recognized by recognizers that are linear (Lin), polynomial (Poly), piecewise linear with a finite number of components (PieceLin) or elementary functions (Elem).
A dynamical recognizer recognizes a language (the set of words accepted by the recognizer) by first being presented with an input word. It starts at an initial point and applies maps that act on continuous space (as defined by the language). The word is either accepted or rejected as part of the language, depending on the resulting point, if it lies in an accepted region of space. Moore also demonstrates a number of properties of the different classes of languages.
Moore briefly relates his results to recurrent neural networks – where grammars are represented dynamically, not symbolically. The results in this paper show the upper and lower limits of the capabilities of neural networks in real time (with complexities such as non linearity). Finally, Moore compares three different methods of analog computation: Blum, Shub and Smale’s analog machines, recurrent neural networks and dynamical recognizers. Based on the capabilities of the three, Moore concludes that the most effective machine would be one that combines elements of all three.
Go to Moore’s paper “Dynamical Recognizers: Real-Time Language Recognition by Analog Computers”:
http://www.santafe.edu/~moore/
Reference details for “Dynamical Recognizers: Real-Time Language Recognition by Analog Computers”:
Moore, C., 1998, Dynamical Recognizers: Real-time Language Recognition by Analog Computers in Theoretical Computer Science 201, pp 99-136.
L & R are integers representing the left and right half of a tape in an arbitrary Turing machine.
and
where
i is the position of the counter
a is the symbol that is being read
Branicky – Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems
This article looks at the computing power of different types of hybrid and continuous dynamical systems. The continuous dynamical systems are comprised of ordinary differential equations (ODEs). Firstly, four types of hybrid systems are examined (hybrid dynamical systems are ones that combine ODEs and discrete dynamics, such as finite automata). These are: Tavernini’s Model (a type of differential automata), Back-Guckenheimer-Myers Model (generalised version of Tavernini’s Model that allows jumps in the continuous state space), Nerode-Kohn Model (a system composed of interacting ODEs and finite automata) and Brockett’s Model (combination of continuous and discrete dynamics, by utilising a timer).
The author shows that all of the models are contained in either Tavernini’s Model or an autonomous version of Brockett’s Model. The remaining proofs in the paper are all related to these two models. The simulations that are carried out show that every type of computational machine (finite automata, pushdown automata and Turing machine) is equivalent to a discrete dynamical system, and that a discrete dynamical system exists that has the power of universal computation. The author then moves on to discuss the simulations with and without exact clocks and still have them behave correctly.
The main importance of this article was the clear nature of the comparison between different types of hybrid dynamical systems – the exact factors that distinguish between them. Also of value was a simple yet non-trivial example of how hybrid systems perform differently to continuous systems, and in some cases provide solutions where continuous systems cannot (the asynchronous arbiter problem).
Go to Branicky’s paper “Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems”:
http://citeseer.nj.nec.com/branicky95universal.html
Reference details for “Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems”:
Branicky, M.S., 1995, Universal Computation and Other Capabilities of Hybrid and Continuous Dynamical Systems, Theoretical Computer Science 138: 1, pp 67-100.
Pollack - The Induction of Dynamical Recognizers
The issues that were discussed in this article were the discoveries that were made by looking at higher order recurrent neural networks from a dynamical systems point of view. The main question that the author asks is how does a neural computation system (which has a slowly-changing structure and iterative processes) come to possess linguistic generative capacity (which requires dynamic representation and recursive processes)?
The experiments that were carried out in this paper included implementing a Sequential Cascaded Network, which consists of a master and slave network. The learning algorithm that was used was a variant of backpropagation (which the author calls the Backspace Trick). The aim of these simulations was to look at the learning and generalization ability of the network on different languages. The networks were able to recognize and generalize on almost all of the languages that it was trained and tested on (the author was critical of the two languages that the network could not learn properly).
The differences between these simulations and others that have been carried out include: the task that these networks had to carry out was a classification task (not a prediction task as others have used), and the network used had a higher order recurrence between states (others have used single order). The work that was carried out demonstrated the possibility of an alternative to recursive rules as a mechanism to describe language complexity, and provides the beginning of an answer to the question asked in the introduction.
Go to Pollack’s “The Induction of Dynamical Recognizers”:
http://www.demo.cs.brandeis.edu/papers/author.html#pollack
Reference details for Pollack’s “The Induction of Dynamical Recognizers”:
Pollack, J.B., 1991, The Induction of Dynamical Recognizers, Machine Learning 7, pp 227-252.
Forward pass computation for a Sequential Cascaded Network (without hidden units):
Eliminating the sigmoid and commuting the yj and zk terms from this equation gives a forward pass computation that is the same process used in an Iterated Function System:
Blair & Pollack – Analysis of Dynamical Recognizers
The aim of this article was to demonstrate that not all recurrent networks acting as dynamical recognizers produced regular languages and can therefore not be modelled completely by any Finite State Automaton (FSA). Analysis of the network was carried out at increasingly fine-grained resolutions to demonstrate when the language induced by the network changed from regular to non-regular behaviour.
The system that was used in these simulations consists of a gated recurrent neural network with two subnetworks, a gating device and a perceptron. The network is presented with a sequence, the gating device then chooses one of the subnetworks, based on whether the next input is 0 or 1. The final state is read through the perceptron, which produces the output of the network. The data sets that were used were the Tomita’s languages, although the empty string was not included. The networks were trained using backpropagation through time.
The analysis of the network was also aimed at showing how the network accomplished the task that it was assigned. The different resolutions of the FSA analysis demonstrated whether the FSA was larger than in a lower resolution – if so, then this was taken as an indication that the network was not regular. Some of the languages were regular, some were not, while one was initially thought to be irregular but proved to be regular under higher resolution. The important conclusion that the authors reach from this research is that there may be a discrepancy between languages which are simple for dynamical recognizers and those that are considered simple in automata theory.
Go to Blair & Pollack’s article “Analysis of Dynamical Recognizers”:
http://www.demo.cs.brandeis.edu/papers/author.html#pollack
Reference details for “Analysis of Dynamical Recognizers”:
Blair, A.D. & Pollack, J.B., 1997, Analysis of Dynamical Recognizers, Neural Computation (9): 5, pp 1127-1142.
Current real-valued hidden unit state vector xt-1 is fed through the subnetwork Wst to produce the next state xt= wst(xt-1), which is given by:
where
Other functions in the paper include:
