Connecting First and Second Order Recurrent Networks with Deterministic Finite Automata
This provides insight into the properties of recurrent networks for researchers in machine learning and computational theory, though it is incremental in unifying existing models.
The paper tackles the problem of understanding recurrent networks by connecting them to regular grammars of varying complexity, introducing an entropy measure to categorize grammars and showing that a unified recurrent network improves grammar learning performance and matches more complex models on a real-world dataset.
We propose an approach that connects recurrent networks with different orders of hidden interaction with regular grammars of different levels of complexity. We argue that the correspondence between recurrent networks and formal computational models gives understanding to the analysis of the complicated behaviors of recurrent networks. We introduce an entropy value that categorizes all regular grammars into three classes with different levels of complexity, and show that several existing recurrent networks match grammars from either all or partial classes. As such, the differences between regular grammars reveal the different properties of these models. We also provide a unification of all investigated recurrent networks. Our evaluation shows that the unified recurrent network has improved performance in learning grammars, and demonstrates comparable performance on a real-world dataset with more complicated models.