NIPS*96 Workshop Announcement: Dynamical Recurrent Networks, Day 1
James Howse
jhowse at squid.lanl.gov
Thu Nov 21 14:48:38 EST 1996
NIPS*96 Workshop Announcement
Dynamical Recurrent Networks
NIPS*96 Postconference Workshop
Day 1
Organized by James Howse and Bill Horne
Friday, December 6, 1996
Snowmass, Colorado
Workshop Abstract
There has been significant interest in recent years in dynamic recurrent
neural networks and their application to control, system identification,
signal processing, and time series analysis and prediction. Much of this
work is simply an extension of techniques which work well for feedforward
networks to recurrent networks. However, when dynamics are added to a
system there are many complex issues which are not relevant to the study of
feedforward nets, such as the existence of attractors and questions of
stability, controllability, and observability. In addition, the
architectures and learning algorithms that work well for feedforward systems
are not necessarily useful or efficient in recurrent systems.
The first day of the workshop highlights the use of traditional results from
systems theory and nonlinear dynamics to analyze the behavior of recurrent
networks. The aim of the workshop is to expose recurrent network designers
to the traditional frameworks available in these well established fields. A
clearer understanding of the known results and open problems in these
fields, as they relate to recurrent networks, will hopefully enable people
working with recurrent networks to design more robust systems which can be
more efficiently trained. This session will overview known results from
systems theory and nonlinear dynamics which are relevant to recurrent
networks, discuss their significance in the context of recurrent networks,
and highlight open problems.
The second day of the workshop addresses the issues of designing and
selecting architectures and algorithms for dynamic recurrent networks.
Unlike previous workshops, which have typically focussed on reporting the
results of applying specific network architectures to specific problems,
this session is intended to assist both users and developers of recurrent
networks to select appropriate architectures and algorithms for specific
tasks. In addition, this session will provide a backward flow of
information -- a forum where researchers can listen to the needs of
application developers. The wide variety, rapid development and diverse
applications of recurrent networks are sure to make for exciting and
controversial discussions.
:::::::::::::
Format for Day 1
The format for this session is a series of 30 minute talks with 5 minutes
for specific questions, followed by time for open discussion after all of
the talks. The talks will give a tutorial overview of traditional results
from systems theory or nonlinear dynamics, discuss their relationship to
some problem in recurrent neural networks, and then outline unresolved
problems related to these results. The discussions will center around
possible ways to resolve the open problems, as well as clarifying the
understanding of established results. The goal of this session is to
introduce more of the NIPS community to ideas from control theory and
nonlinear dynamics, and to illustrate the utility of these ideas in
analyzing and synthesizing recurrent networks.
:::::::::::::
Web Sites for the Workshop
Additional information concerning Day 1 can be found at
http://flute.lanl.gov/NIS-7_home_pages/jhowse/talk_abstracts.html.
Information about Day 2 can be obtained at
http://running.dgcd.doc.ca/NIPS96/.
:::::::::::::
Schedule for Friday, December 6th
Morning Session (7:30-10:30am)
Structural Neural Dynamics and Computation
Xin Wang
Dynamical Recognizers: What Languages Can Recurrent Neural Networks Recognize
in Real Time?
Cris Moore
Decoding Discrete Structures from Fixed Points of Analog Hopfield Networks
Arun Jagota
Recurrent Networks and Supervised Learning
Jennie Si
Afternoon Session (4:00-7:00pm)
System Theory of Recurrent Networks
Eduardo D. Sontag
Learning Controllers for Complex Behavioral Systems
Shankar Sastry and Lara Crawford
Neural Network Verification of Hybrid Dynamical System Stability
Michael Lemmon
:::::::::::::
Talk Abstracts
Title: Structural Neural Dynamics and Computation
Author: Xin Wang
Xerox Corporation
Abstract: Dynamics and computation of neural networks can be regarded as two
types of meaning of mathematical equations that are used to describe
dynamical and computational behaviors of the networks. They are in
parallel to operational semantics and denotational semantics of
computer programs written in programming languages. Lessons learned
in study of formal semantics and impacts of structural programming
and object-oriented programming methodologies tell us that a
structural approach has to be taken, in order to deal with
complexity in analysis and synthesis caused by large-sized neural
networks.
This talk will start with presenting some small-sized networks that
possess very rich dynamical and bifurcational behaviors, ranging
from convergent to chaotic and from saddle to period-doubling
bifurcations, and then examine some conditions under which these
types of behaviors are preserved by standard constructions such as
Cartesian product and cascade.
----------
Title: Dynamical Recognizers: What Languages Can Recurrent Neural Networks
Recognize in Real Time?
Author: Cris Moore
Computation, Dynamics, and Inference
Santa Fe Institute
Abstract: There has been considerable interest recently in using recurrent
neural networks as dynamical models of language, complementary to
the standard symbolic and grammatical approaches. Numerous
researchers have shown that RNNs can recognize regular,
context-free, and even context-sensitive languages in real time.
We place these results in a mathematical framework by treating RNNs
with varying activation functions as iterated maps with varying
functional forms. We relate the classes of languages recognizable
in real time by these different types of RNNs directly to
"classical" language classes from computational complexity theory.
We prove, for instance, that there are languages recognizable in
real time with piecewise-linear or quadratic activations that linear
functions cannot, and that there are languages recognizable with
exponential or sinusoidal activations that are not recognizable by
polynomial activations of any degree. Our methods are essentially
identical to the Vapnik-Chervonenkis dimension.
We also relate these results to Blum, Shub and Smale's definition of
analog computation, as well as Siegelmann and Sontag's.
----------
Title: Decoding Discrete Structures from Fixed Points of Analog Hopfield
Networks
Author: Arun Jagota
Department of Computer Science
University of California, Santa Cruz
Abstract: In this talk we examine the relationship between the fixed points of
certain specialized families of binary Hopfield networks and certain
stable regions of their associated analog Hopfield network
families. More specifically, consider some specialized family
<I>F</I> of binary Hopfield networks whose fixed points have some
well-characterized structure. We consider an analog version of the
family <I>F</I> obtained by replacing the hard-threshold neurons by
sigmoidal ones and replacing the discrete dynamics of the binary
model by a continuous one. We ask the question: can discrete
structures identical to or similar to those that are fixed points in
the binary family <I>F</I> be recovered from certain stable regions
of the associated analog family? We obtain revealing answers for
certain families. Our results lead to a better understanding of the
recoverability of discrete structures from stable regions of analog
networks. They have applications to solving discrete problems via
analog networks. We also discuss many open mathematical problems
that our studies reveal.
Several of the results were obtained in joint work with Fernanda
Botelho and Max Garzon.
----------
Title: Recurrent Networks and Supervised Learning
Author: Jennie Si
Department of Electrical Engineering
Arizona State University
Abstract: After several years of adventure, researchers in the field of
artificial neural networks have reached a common consensus about
what neural networks can do and what their limitations are. In
particular, there has been some fundamental results on the existence
of artificial neural networks for function approximation and
nonlinear dynamic system modeling; on neural networks for
associative memory applications, etc. Some theoretical advances were
made in neural networks for control applications, in an adaptive
setting.
In this talk, the emphasis is given to some recent progress
aiming at a quantitative evaluation of neural network performance
for some fundamental tasks, e.g., static and dynamic approximation;
computation issues in training neural networks characterized by both
memory and computation complexities. All the above discussions will
be based on neural network models representing nonlinear static and
dynamic input-output systems as well as state space nonlinear
dynamic systems. Further applications of the fundamental neural
network theory to simulation based approximation technique for
nonlinear dyanmic progarmming will also be discussed. This technique
may represent an important and practically applicable dynamic
programming solution to complex problems that invoke the dual course
of large dimension and lack of an accurate mathematical model.
----------
Title: System Theory of Recurrent Networks
Author: Eduardo D. Sontag
Department of Mathematics
Rutgers University
Abstract: We consider general recurrent networks. These are described by
the differential equations
<I>x' = S(Ax+Bu) ,</I>
<I>y = Cx ,</I>
in continuous time, or the analogous discrete-time version. Here
<I>S(.)</I> is a diagonal mapping of the form <I>S(a,b,c,...) =
(s(a),s(b),s(c),...)</I> where <I>s(.)</I> is a scalar real map
called the "activation" of the network. The vector <I>x</I>
represents the state of the system, <I>u</I> is the time-dependent
input signal, and <I>y</I> represents the measurements or outputs of
the system.
Recurrent networks whose activation <I>s(.)</I> is the identity
function <I>s(x)=x</I> are precisely the linear systems studied in
control theory. It is perhaps an amazing fact that a nontrivial and
interesting system theory can be developed for recurrent nets whose
activation is the one typically used in neural net practice,
<I>s(x)=tanh(x)</I>. (One reason that makes this fact surprising is
that recurrent nets with this activation are, in a suitable sense,
universal approximators for arbitrary nonlinear systems.)
This talk will survey recent results by the speaker and several
coauthors (Albertini, Dasgupta, Koiran, Koplon, Siegelmann,
Sussmann) regarding issues of parameter identifiability,
controllability, observability, system approximation, computability,
parameter reconstruction, and sample complexity for learning and
generalization. We provide simple algebraic tests for many
properties, expressed in terms of the "weight" or parameter matrices
<I>(A,B,C)</I> that characterize the system.
----------
Title: Learning Controllers for Complex Behavioral Systems
Authors: Shankar Sastry and Lara Crawford
Electronics Research Laboratory
University of California, Berkeley
Abstract: Biological control systems routinely guide complex dynamical
systems, such as the human body, through complicated tasks, such as
running or diving. Conventional control techniques, however,
stumble with these problems, which have complex dynamics, many
degrees of freedom, and an only partially specified desired task
(e.g., "move forward fast," or "execute a
one-and-one-half-somersault dive"). To address
behaviorally-specified problems like these, we are using a
biologically-inspired, hierarchical control structure, in which
network-based controllers learn the controls required at each level
of the hierarchy, and no system model is required. The encoding and
decoding of the information passed between hierarchical levels,
including both controller commands and behavioral feedback, is an
important design issue affecting both the size of the controller
network needed and the ease with which it can learn; we have used
biological encoding schemes for inspiration wherever possible. For
example, the lowest-level controller outputs an encoded torque
profile; the encoding is based on the way biological pattern
generators for single-joint movements restrict the allowed control
torque profiles to a particular parametrized control family. Such
an encoding removes all time dependence from the controller's
consideration, simplifying the learning task considerably to one of
function approximation. The implementation of the controller
networks themselves could take several forms, but we have chosen to
use radial basis functions, which have some advantages over
conventional networks. Through a learning architecture with good
encodings for both the controls and the desired behaviors, many of
the difficulties in controlling complex behavioral systems can be
overcome.
In this talk, we apply the control structure described above, with
800-element networks and a form of supervised learning, to the
problem of controlling a human diver. The system learns open-loop
controls to steer a 16-DOF human model through various dives,
including a one-and-one-half somersault pike and a one-and-one-half
somersault with a full twist.
----------
Title: Neural Network Verification of Hybrid Dynamical System Stability
Author: Michael Lemmon
Department of Electrical Engineering
University of Notre Dame
Abstract: Hybrid dynamical systems (HDS) can occur when a smooth dynamical
system is supervised by discrete-event dynamical system. Such
systems are frequently found in computer-controlled systems. A key
issue in the development of hybrid system controllers concerns
verifying that the system possesses certain generic properties such
as safety, stability, and optimality. It has been possible to study
the verifiability of restricted classes of hybrid systems. Examples
of such systems include switched systems consisting of first-order
integrators [Alur et al.], hybrid systems whose "switching" surfaces
satisfy certain invariance properties [Lemmon et al.], and planar
hybrid systems [Guckenheimer]. The extension of these verification
methods to more general systems [Deshpande et al.], however, appears
to be computationally intractable. This is due in large part to the
complex behaviours that such systems can demonstrate. Simulation
experiments with a simple system consisting of switched integrators
(relative degree greater than 2) suggest that the $\omega$-limit
sets of these systems can be single fixed points, periodic points,
or Cantor sets.
Neural networks may provide one method for assisting in the analysis
of hybrid systems. A neural network can be used to approximate the
Poincare map of a switched hybrid system. Such methods can be
extremely useful in verifying whether a given HDS exhibits
asymptotically stable periodic behaviours.
The purpose of this talk are twofold. First, a summary of the
principal results and open research areas in hybrid systems will be
given. Second, the talk will discuss recent results on the use of
neural networks in the verification of hybrid system stability.
More information about the Connectionists
mailing list