Preprint available

[Sreerupa Das]

The following paper has been placed in Neuroprose archive.

---------------------------------------------------------------------------
Learning Context-free Grammars: Capabilities and Limitations of a Recurrent
              Neural Network with an External Stack Memory
    -----------------------------------------------------------------


     Sreerupa Das               C. Lee Giles                Guo-Zheng Sun 
University of Colorado     NEC Research Institute       University of Maryland
Boulder, CO 80309-430        Princeton, NJ 08540        College Park, MD 20742
rupa at cs.colorado.edu      giles at research.nec.nj.com   sun at sunext.umiacs.umd.edu


			ABSTRACT

This work describes an approach for inferring Deterministic
Context-free (DCF) Grammars in a Connectionist paradigm using a
Recurrent Neural Network Pushdown Automaton (NNPDA).  The NNPDA
consists of a recurrent neural network connected to an external stack
memory through a common error function. We show that the NNPDA is able
to learn the dynamics of an underlying pushdown automaton from
examples of grammatical and non-grammatical strings.  Not only does
the network learn the state transitions in the automaton, it also
learns the actions required to control the stack.  In order to use
continuous optimization methods, we develop an analog stack which
reverts to a discrete stack by quantization of all activations, after
the network has learned the transition rules and stack actions.  We
further show an enhancement of the network's learning capabilities by
providing hints.  In addition, an initial comparative study of
simulations with first, second and third order recurrent networks has
shown that the increased degree of freedom in a higher order networks
improve generalization but not necessarily learning speed.

(To be published in the Proceedings of The Fourteenth Annual
Conference of The Cognitive Science Society, July 29 -- August 1,
1992, Indiana University.)

Questions and comments will be appreciated.
=====================================================================
File name: das.cfg_induction.ps.Z
=====================================================================
To retrieve the papers by anonymous ftp:

        unix> ftp archive.cis.ohio-state.edu  # (128.146.8.52)
        Name: anonymous
        Password: neuron
        ftp> cd pub/neuroprose
        ftp> binary
        ftp> get das.cfg_induction.ps.Z
        ftp> quit
        unix> uncompress das.cfg_induction.ps.Z
        unix> lpr das.cfg_induction.ps
=====================================================================

Sreerupa Das
Department of Computer Science
University of Colorado at Boulder
Boulder, CO 80309-430				
email:rupa at cs.colorado.edu
----------------------------------------------------------------------