The dynamics of discrete-time computation, with application to recurrent neural networks and finite state machine extraction

被引:125
作者
Casey, M
机构
[1] Department of Mathematics, University of California, San Diego, San Diego
[2] Volen Center for Complex Systems, Brandeis University, Waltham
关键词
D O I
10.1162/neco.1996.8.6.1135
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Recurrent neural networks (RNNs) can learn to perform finite state computations. It is shown that an RNN performing a finite state computation must organize its state space to mimic the states in the minimal deterministic finite state machine that can perform that computation, and a precise description of the attractor structure of such systems is given. This knowledge effectively predicts activation space dynamics, which allows one to understand RNN computation dynamics in spite of complexity in activation dynamics. This theory provides a theoretical framework for understanding finite state machine (FSM) extraction techniques and can be used to improve training methods for RNNs performing FSM computations. This provides an example of a successful approach to understanding a general class of complex systems that has not been explicitly designed, e.g., systems that have evolved or learned their internal structure.
引用
收藏
页码:1135 / 1178
页数:44
相关论文
共 45 条
  • [1] [Anonymous], 1987, INTRO CHAOTIC DYNAMI
  • [2] [Anonymous], 1994, P C ADV NEUR INF PRO
  • [3] [Anonymous], COMPLEX SYST
  • [4] ON RELEVANCE OF ABSTRACT ALGEBRA TO CONTROL THEORY
    ARBIB, MA
    ZEIGER, HP
    [J]. AUTOMATICA, 1969, 5 (05) : 589 - &
  • [5] BEER RD, 1996, ADAPT BEHAV, V3, P471
  • [6] BOWEN R, 1975, EQUILIBRIUM STATES E, V470
  • [7] CASEY M, 1995, THESIS UC SAN DIEGO
  • [8] CASEY M, 1995, I NEURAL COMPUTATION, V9503
  • [9] CASEY M, 1993, P ANN RES S JUN, P78
  • [10] Finite State Automata and Simple Recurrent Networks
    Cleeremans, Axel
    Servan-Schreiber, David
    McClelland, James L.
    [J]. NEURAL COMPUTATION, 1989, 1 (03) : 372 - 381