Extracting and Learning an Unknown Grammar with Recurrent Neural Networks
Clyde Lee Giles, CLIFFORD B. MILLER, D. Chen, Guo-Zheng Sun, H. H. Chen, Y. C. Lee · 1991
Simple second-order recurrent networks are shown to readily learn small known regular grammars when trained with positive and negative strings examples. We show that similar methods are appropriate for learning unknown grammars from examples of their strings. The training algorithm is an incremental real-time, recurrent learning (RTRL) method that computes the complete gradient and updates the weights at the end of each string. After or during training, a dynamic clustering algorithm extracts the production rules that the neural network has learned. The methods are illustrated by extracting rules from unknown deterministic regular grammars. For many cases the extracted grammar outperforms the neural net from which it was extracted in correctly classifying unseen strings. 1 INTRODUCTION For many reasons, there has been a long interest in "language" models of neural networks; see [Elman 1991] for an excellent discussion. The orientation of this work is somewhat different. The focus her...