Discrete dynamical systems

Publication date 8 October 1995

Published in Mathématiques \& Applications (Berlin) (Search for Journal in Brave)

Boolean matrix cycle directed graph discrete iterations Hopfield neuronal network iterations metric

Neural networks for/in biological studies, artificial life and related topics (92B20) Research exposition (monographs, survey articles) pertaining to systems and control theory (93-02) Discrete-time control/observation systems (93C55) Applications of graph theory to circuits and networks (94C15)

Review text

The French Society for Applied and Industrial Mathematics (SMAI) is publishing a series of books, each of which is usually based on courses of lectures given by the respective authors. While the content may be fairly new, each book is therefore intended to have a pedagogical function. This book is one of that series, and carries out its aims admirably. In 1986, an earlier version appeared in English (``Discrete iterations: a metric study) also published by Springer. It has been revised and completed to form Chapters 2-7 and 10 of the present work (which has five other chapters as well). The author motivates the mathematics by imagining a finite set of \(n\) processors (automata, neurones, \dots) at the vertices of a directed graph \(\Gamma\), such that vertex \(i\) can be in one of two states, and produces output \(f_i (x_1, \dots, x_n)\) which depends only on the input-states received from the edges ending at \(i\). Thus we obtain a mapping \(F\) from the Cartesian product \(X= \{0, 1\}^n\) to itself. The incidence-matrix of \(\Gamma\) yields the Boolean matrix \(B(F)\), which gives crude information about \(F\). Each element of \(X\) is a vector \(x= (x_1, \dots, x_n)\), thought of as a vertex of the unit cube in \(n\)-space, and we form the (directed) iteration graph \(I\) of \(F\) by joining \(x\) to \(y\) whenever \(y= F(x)\). This graph then consists of several connected components, each invariant under \(F\), and will contain either a unique fixed point, or a cycle, to which any orbit of iterates of \(F\) will terminate after a finite number of steps. The object is to decide the structure of the orbits by means of economical algorithms, and the author provides a theory which resembles the standard ``continuous theory of metrics, norms and contractions; but the proofs are simpler and all the relevant objects are finitely computable. He also considers various analogues of Gauss-Seidel (``series-parallel) iteration to compare speeds of approach to a steady state. As substitute for a metric, the author uses a ``metric tool \(d\) with values in \(X\) itself, to formulate a basic contracting condition that uses the Boolean order-relation and takes the form: \(d(F(x), F(y))\leq Md (x, y)\), where \(M\) is a boolean matrix of 0's and 1's with eigenvalue zero. The necessary material on Boolean is developed, and contains analogues of the Perron-Frobenius and Stein-Rosenberg theorems. Next, we meet a Boolean matrix \(F' (x)\) which behaves very much like the derivative in calculus, with a mean value theorem; and there is a ``local chain rule for a composition of mappings, which is sufficient for a treatment of attracting periodic cycles and fixed points. This purely local validity is used in Chapter 11 to show why there cannot be a complete analogy between this finite theory and that for \(n\)-space. In Chapter 12, we meet the author's principal model -- that of Hopfield for a network of neurons. \(F\) is defined in terms of a vector of ``thresholds, and a matrix \(W\) of ``weights; for example, if \(W\) is symmetric then there is always a 2-cycle. A problem of ``associative memory is then formulated, to design a system that will ``correct five faulty images given in terms of pixels on a screen. (The images are presented as a set \(S\) of five vectors in \(X\), ``close to a set \(T\) of five perfect vectors.) When the faults are 20\% in error, their iterates reach \(T\) within only 3 steps; but when the error is 30\%, the iterates stabilize to other vectors. This raises several interesting questions, and the author refers readers to the literature. He concludes with a chapter on discrete asynchronous iterations of his standard system, in which the finite character is partly lost by evaluating the components of \(F\) at different times. Some of the earlier theory is still preserved. (The author also uses the term ``chaotic for asynchronous, but without linking with convential chaos theory. The reviewer would like to have seen the theory applied, if it has been done, to a finite numerical calculator that exhibits chaos in the usual sense.) Finally, the text returns to a whimsical example which begins the book, and concerns the eight possible states of a system consisting of a married couple and a Mother-in-law. The system is analysed in terms of the preceding results, and adjustments are suggested to make life pleasanter for the three actors. Then follows a series of extended exercises and problems. The book is very reader-friendly. The French is clear in the best sense, not at the cost of mystifying abstraction. The author makes interesting asides about modelling and has a moral tone. Examples abound, with diagrams of the relevant networks, to illustrate each concept and to show counter-examples. Their detailed calculations are often (rightly) omitted, and it could be a pleasant exercise for students to complete them. Each chapter also ends with a ``Conclusion, which summarizes the main points achieved. The book could be useful for those who advocate ``Mathematics without calculus, and it would be interesting to test whether students find the material easier before or after exposure to calculus. One test-case would be this: the afore-mentioned contraction criterion is a delightful analogue to one who knows the classical criterion, but it may well be meaningless to one who doesn't. How do students take it? Al it is easy to be carried away by the pure mathematics, but young students would probably be impatient to see more examples of applications of the theory, and not only to neuronal networks. Anyway, the reviewer enjoyed the book.

Recommendations

Cited in

(36)

This page was built for publication: Discrete dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899198)