Preprint

[Guo-Zheng Sun]

Reprint: THE NEURAL NETWORK PUSHDOWN AUTOMATON: MODEL, STACK AND LEARNING
SIMULATIONS

The following reprint is available via the NEC Research Institute ftp
archive external.nj.nec.com. Instructions for retrieval from the archive
follow the abstract summary. Comments and remarks are always appreciated.

-----------------------------------------------------------------------------
..............................................................................
                     "The Neural Network Pushdown Automaton:
		      Model, Stack and Learning Simulations"

           G.Z. Sun(a,b), C.L. Giles(b,c), H.H. Chen(a,b), Y.C. Lee(a,b) 

(a) Laboratory for Plasma Research and (b) Institute for Advanced Computer
Studies, U. of Maryland, College Park, MD 20742  (c) NEC Research Institute,
4 Independence Way, Princeton, NJ 08540

In order for neural networks to learn complex languages or grammars, they
must have sufficient computational power or resources to recognize or
generate such languages.  Though many approaches have been discussed, one
obvious approach to enhancing the processing power of a recurrent neural
network is to couple it with an external stack mem ory - in effect creating
a neural network pushdown automata (NNPDA). This paper discusses in detail
this NNPDA - its construction, how it can be trained and how useful
symbolic information can be extracted from the trained network.

In order to couple the external stack to the neural network, an
optimization method is developed which uses an error function that connects
the learning of the state automaton of the neural network to the learning
of the operation of the external stack. To minimize the error function
using gradient descent learning, an analog stack is designed such that the
action and storage of information in the stack are continuous. One
interpretation of a continuous stack is the probabilistic storage of and
action on data. After training on sample strings of an unknown source
grammar, a quantization procedure extracts from the analog stack and neural
network a discrete pushdown automata (PDA). Simulations show that in
learning deterministic context-free grammars - the balanced parenthesis
language, 1n0n, and the deterministic Palindrome - the extracted PDA is
correct in the sense that it can correctly recognize unseen strings of
arbitrary length. In addition, the extracted PDAs can be shown to be
identical or equivalent to the PDAs of the source grammars which were used
to generate the training strings.

UNIVERSITY OF MARYLAND TR NOs. UMIACS-TR-93-77 & CS-TR-3118, August 20,
1993.

---------------------------------------------------------------------------

                          FTP INSTRUCTIONS

                unix> ftp external.nj.nec.com (138.15.10.100)
                Name: anonymous
                Password: (your_userid at your_site)
                ftp> cd pub/giles/papers
                ftp> binary
                ftp> get NNPDA.ps.Z
                ftp> quit
                unix> uncompress NNPDA.ps.Z

		(Please note that this is a 35 page paper.)

-----------------------------------------------------------------------------