Subregular Complexity and Deep Learning

Abstract

This paper argues that the judicial use of formal language theory and grammatical inference are invaluable tools in understanding how deep neural networks can and cannot represent and learn long-term dependencies in temporal sequences. Learning experiments were conducted with two types of Recurrent Neural Networks (RNNs) on six formal languages drawn from the Strictly Local (SL) and Strictly Piecewise (SP) classes. The networks were Simple RNNs (s-RNNs) and Long Short-Term Memory RNNs (LSTMs) of varying sizes. The SL and SP classes are among the simplest in a mathematically well-understood hierarchy of subregular classes. They encode local and long-term dependencies, respectively. The grammatical inference algorithm Regular Positive and Negative Inference (RPNI) provided a baseline. According to earlier research, the LSTM architecture should be capable of learning long-term dependencies and should outperform s-RNNs. The results of these experiments challenge this narrative. First, the LSTMs' performance was generally worse in the SP experiments than in the SL ones. Second, the s-RNNs out-performed the LSTMs on the most complex SP experiment and performed comparably to them on the others.

References in corpus (1)

• Deep Learning in Neural Networks: An Overview

Cited by in corpus (7)

• Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
• Understanding Recurrent Neural Architectures by Analyzing and Synthesizing Long Distance Dependencies in Benchmark Sequential Datasets
• Connecting First and Second Order Recurrent Networks with Deterministic Finite Automata
• Neural Network Based Nonlinear Weighted Finite Automata
• Tensor Product Representations of Subregular Formal Languages
• Evaluating Attribution Methods using White-Box LSTMs
• How LSTM Encodes Syntax: Exploring Context Vectors and Semi-Quantization on Natural Text