Discrete recurrent neural networks for grammatical inference

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Conventional analog recurrent neural networks struggle with long input strings due to unstable state representations.
• Previous work introduced discrete recurrent networks for finite-state automata, highlighting the need for extended models.

Purpose of the Study:

• To propose a novel neural architecture capable of learning deterministic context-free grammars (or deterministic pushdown automata).
• To address the instability issues in conventional recurrent networks by introducing stable state representations.
• To extend discrete recurrent networks with an external stack for enhanced grammatical learning.

Main Methods:

• Development of a discrete recurrent network architecture incorporating a discrete external stack and symbols.
• Introduction of a composite error function to manage diverse learning scenarios.
• Extension of the pseudo-gradient learning method for error function minimization.
• Empirical validation of the pseudo-gradient learning method with and without the external stack.

Main Results:

• The proposed networks demonstrate success in learning simple pushdown automata.
• Empirical trials validate the effectiveness of the extended pseudo-gradient learning method.
• Learned internal representations are provably stable, achieving 100% accuracy on unseen strings of arbitrary length.
• Challenges such as overfitting and non-convergent learning were observed.

Conclusions:

• The novel neural architecture offers a stable and effective approach for learning deterministic context-free grammars and pushdown automata.
• The extended pseudo-gradient learning method proves effective for training these complex networks.
• While successful, further research may be needed to mitigate issues like overfitting and non-convergence.