Thumbnail
Access Restriction
Subscribed

Author Omlin, Christian W. ♦ Giles, C. Lee
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1996
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Automata ♦ Connectionism ♦ Knowledge encoding ♦ Neural networks ♦ Nonlinear dynamics ♦ Recurrent neural networks ♦ Rules ♦ Stability
Abstract Recurrent neural networks that are $\textit{trained}$ to behave like deterministic finite-state automata (DFAs) can show deteriorating performance when tested on long strings. This deteriorating performance can be attributed to the instability of the internal representation of the learned DFA states. The use of a sigmoidel discriminant function together with the recurrent structure contribute to this instability. We prove that a simple algorithm can $\textit{construct}$ second-order recurrent neural networks with a sparse interconnection topology and sigmoidal discriminant function such that the internal DFA state representations are stable, that is, the constructed network correctly classifies strings of arbitrary length. The algorithm is based on encoding strengths of weights directly into the neural network. We derive a relationship between the weight strength and the number of DFA states for robust string classification. For a DFA with $\textit{n}$ state and $\textit{m}input$ alphabet symbols, the constructive algorithm generates a “programmed” neural network with $\textit{O}(\textit{n})$ neurons and $\textit{O}(\textit{mn})$ weights. We compare our algorithm to other methods proposed in the literature.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1996-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 43
Issue Number 6
Page Count 36
Starting Page 937
Ending Page 972


Open content in new tab

   Open content in new tab
Source: ACM Digital Library