Language Induction Tech Report Available

[Dan Clouse]

FTP-host: cs.ucsd.edu
FTP-filename: /pub/tech-reports/clouse.nnfir.ps.Z

The file clouse.nnfir.ps.Z is now available for copying from the
University of California at San Diego, Computer Science and Engineering
Department ftp server.  (20 pages, compressed file size 164K)

TITLE:
    Learning Large DeBruijn Automata with Feed-Forward Neural Networks

AUTHORS:
    Daniel S. Clouse, UCSD CSE Dept.
    C. Lee Giles, NEC Research Institute, Princeton, NJ.
    Bill G. Horne, NEC Research Institute, Princeton, NJ.
    Garrison W. Cottrell, UCSD CSE Dept.

ABSTRACT:
    In this paper we argue that a class of finite state machines (FSMs)
    which is representable by the NNFIR (Neural Network Finite Impulse
    Response) architecture is equivalent to the definite memory
    sequential machines (DMMs) which are implementations of deBruijn
    automata.  We support this claim by drawing parallels between
    circuit topologies of sequential machines used to implement FSMs and
    the architecture of the NNFIR.  Further support is provided by
    simulation results that show that a NNFIR architecture is able to
    learn perfectly a large definite memory machine (2048 states) with
    very few training examples.  We also discuss the effects that
    variations in the NNFIR architecture have on the class of problems
    easily learnable by the network.