Recurrent neural networks for grammatical inference

Citation

Zeng, Zheng (1994) Recurrent neural networks for grammatical inference. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/BQBV-GE18. https://resolver.caltech.edu/CaltechETD:etd-12112007-090004

Abstract

In this thesis, various artificial recurrent neural network models are investigated for the problem of deriving grammar rules from a finite set of example "sentences." A general discrete network framework and its corresponding learning algorithm are presented and studied in detail in learning three different types of grammars.

The first type of grammars considered is regular grammars. Experiments with conventional analog recurrent networks in learning regular grammars are presented to demonstrate the unstable behavior of such networks in processing very long strings after training. A new network structure to force recurrent networks to learn stable states by discretizing the internal feedback signals is constructed. For training such discrete networks a "pseudo-gradient" learning rule is applied.

As an extension to the discrete network model, an external discrete stack is added to accommodate the inference of context-free grammars. A composite error function is devised to deal with various situations during learning. The pseudo-gradient method is also extended to train such a network to learn context-free grammars with the added option of operating on the external stack.

Another extension to the discrete network structure is made for the purpose of learning probabilistic finite state grammars. The network consists of a discrete portion which is intended to represent the structure of the grammar, and an analog portion which is intended to represent the transition probabilities. Two criteria for the network to verify the correctness of its solution during training are proposed. Theoretical analysis of the necessary and sufficient conditions for the correct solution is presented.

Experimental results show that the discrete network models have similar capabilities in learning various grammars as their analog counterparts, and have the advantage of being provably stable.

Thesis Files