Evaluating the Ability of LSTMs to Learn Context-Free Grammars

Luzi Sennhauser, Robert BerwickEMNLP 2018

TL;DR

This paper investigates whether Long Short-Term Memory (LSTM) networks, commonly used for sequential data, can truly learn the hierarchical structures inherent in human language. By training LSTMs on a Dyck language task (well-formed bracket sequences), the authors found that while LSTMs can achieve good performance, they appear to rely on statistical correlations rather than inferring the underlying grammatical rules, suggesting limitations in their ability to generalize to unseen structures.

What Problem Does This Paper Address?

Human language is fundamentally hierarchical, with complex meanings derived from nested structures. While LSTMs excel at processing sequential data and have shown promise in various NLP tasks, it's unclear if they can grasp these underlying hierarchical rules or if their success is merely a result of learning superficial statistical patterns. This paper aims to bridge this gap by rigorously testing an LSTM's ability to learn context-free grammars (CFLs), a foundational concept in linguistics and computer science that captures this hierarchical structure. Understanding this is crucial for developing AI systems that can truly comprehend and generate natural language.

Methods

The authors employ a Long Short-Term Memory (LSTM) network as their primary model. The core of their approach involves training the LSTM on a synthetic corpus designed to mimic context-free grammar structures. Specifically, they use a Dyck language with two types of brackets ([] and {}) to represent hierarchical nesting.

Key methodological aspects include:

  • Dyck Language Task: The LSTM is tasked with predicting the next closing bracket given a sequence of opening and closing brackets. This requires understanding the nesting depth and matching pairs.
  • Corpus Generation: Sentences are generated using a grammar where rule probabilities are non-uniform, introducing a degree of complexity and making simple statistical memorization less effective. Sentences are fixed at a length of 100 characters.
  • Analysis Model: To understand what the LSTM learns, an "analysis model" is used. This model takes the internal states (hidden and cell states) of the trained LSTM and attempts to predict specific features of the input, such as the nesting depth or previous characters. This helps determine if the LSTM is storing relevant structural information.
  • Varying Model Complexity: Experiments are conducted by varying the number of hidden units in the LSTM to observe its impact on performance and memory demand.
  • Generalization Evaluation: The authors specifically test generalization by training on a subset of sentences (in-sample) and evaluating on unseen sentences (out-of-sample) under different conditions: regular interpolation, random interpolation, and extrapolation.

Datasets

The paper does not use pre-existing natural language datasets. Instead, it generates a synthetic corpus based on a Dyck language with two types of brackets ([] and {}). This corpus consists of 1 million sentences, each of length 100 characters. The generation process uses non-uniform probabilities for grammar rules to make the task more challenging than a simple uniform distribution.

Key Insights and Ideas

  • Exponential Memory Demand: LSTMs exhibit an exponential increase in memory demand as sentence complexity (measured by distance and embedded depth) grows, even though a sub-linear memory should theoretically suffice for context-free grammars.
  • Efficient Nuisance Variable Handling: Despite the high memory demand, the analysis model shows that LSTMs are very effective at forgetting irrelevant information (e.g., closed bracket pairs) quickly. This suggests the memory is used efficiently for the task at hand, but not necessarily for storing explicit structural rules.
  • Poor Generalization: The most striking finding is the poor generalization performance of the LSTMs. Out-of-sample accuracy is significantly worse than in-sample accuracy, especially for extrapolation tasks, indicating that the model struggles to apply learned patterns to novel, unseen structures.
  • Statistical Approximation vs. Rule Inference: The authors conclude that LSTMs likely learn a "sequential statistical approximation" to the problem rather than inferring the underlying context-free rules. This is supported by the observation that the model can distinguish relevant from irrelevant information but fails to generalize robustly.
  • Initialization Sensitivity: The performance of the LSTM is highly sensitive to weight initialization, suggesting the presence of many local minima in the loss landscape.

Key Results

  • Error Rate: The basic model achieves an error rate of 0.38% with 50 hidden units. However, generalization performance is much worse.
  • Generalization Discrepancy: For regular interpolation, the out-of-sample error rate is on average 5.4 times higher for distance and 5.9 times higher for embedded depth compared to the in-sample error. For random interpolation and extrapolation, the model generalizes "much worse or not at all."
  • Relevant vs. Irrelevant Character Recovery: The analysis model shows a significant difference in accuracy when recovering relevant versus irrelevant characters. Relevant characters are recovered with an error rate below 1.8%, while irrelevant characters have an error rate of 33% for bracket type prediction. Irrelevant information becomes unrecoverable after a few characters.
  • Depth Prediction: The error in predicting nesting depth decreases from an average of 7.04 with 2 hidden units to 1.34 with 50 hidden units, indicating some ability to track depth.

Limitations and Future Work

Limitations:

  • Generalization Failure: The primary limitation is the inability of LSTMs to generalize well to unseen context-free structures, suggesting they don't learn the underlying rules.
  • Exponential Memory: The observed exponential memory demand is inefficient for tasks that theoretically require sub-linear memory.
  • Initialization Sensitivity: The reliance on good initialization points to potential issues in finding optimal solutions.

Future Work:

The authors suggest that to truly understand and generate natural language, which relies heavily on hierarchical structure, researchers need to explore fundamentally new models and architectures that can more directly leverage this structural nature. This implies moving beyond purely sequential processing models.

Summary updated

BibTeX
@inproceedings{sennhauser2018evaluating,
  author = {Luzi Sennhauser and Robert Berwick},
  title = {{Evaluating the Ability of LSTMs to Learn Context-Free Grammars}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
}
Figure