Relating RNN Layers with the Spectral WFA Ranks in Sequence Modelling

Farhana Ferdousi Liza, Marek GrzesACL 2019

TL;DR

This paper investigates the impact of stacking multiple LSTM layers in Recurrent Neural Networks (RNNs) for sequence modeling. By comparing RNN performance against Weighted Finite-State Automata (WFA) trained with spectral learning, they find that additional RNN layers primarily improve the modeling of distributed hidden states, rather than significantly enhancing the ability to capture long-term dependencies. This work offers a novel perspective on understanding the benefits of deep RNN architectures.

What Problem Does This Paper Address?

Sequence prediction, the task of forecasting future elements based on historical data, is a fundamental problem in machine learning. Recurrent Neural Networks (RNNs), particularly those with multiple layers (like stacked LSTMs), have shown strong empirical performance on these tasks. However, the theoretical understanding of why these deeper architectures are beneficial remains somewhat elusive. While it's hypothesized that deeper networks can learn more complex feature representations, it's not entirely clear if this translates to a better ability to capture long-term dependencies, a known challenge for RNNs due to issues like vanishing gradients. This paper aims to bridge this gap by analyzing RNNs through the lens of Weighted Finite-State Automata (WFA), using spectral learning techniques to understand the relationship between RNN layer depth and the complexity of the underlying models represented by WFA ranks.

Methods

The authors employ two main types of models: Recurrent Neural Networks (RNNs) and Weighted Finite-State Automata (WFA).

For RNNs, they experiment with both single-layer and two-layer stacked LSTM architectures. These models are trained using stochastic gradient descent with momentum. Dropout is used as a regularization technique on non-recurrent layers.

For WFA, they utilize a spectral learning algorithm. This method involves building a Hankel matrix from the data, performing Singular Value Decomposition (SVD), and then using the resulting factors to recover the parameters of a minimal WFA. The "rank" of the WFA, which corresponds to the number of hidden states in the minimal WFA, is a key parameter of interest. The spectral learning approach is chosen for its computational efficiency compared to traditional methods like Expectation-Maximization.

The core of their analysis lies in comparing the performance of these RNN and WFA models across various datasets and then correlating the WFA rank (number of hidden states) with the impact of adding an extra RNN layer.

Datasets

The study evaluates their models on fifteen datasets from the Sequence Prediction Challenge (SPiCe) in 2016. These datasets are categorized as:

  • Synthetic: Eight datasets, with four generated artificially and four partially synthetic based on real data. These include datasets generated using Hidden Markov Models (HMMs) and the PAutomaC data generator.
  • Real-world: Seven datasets, including NLP tasks (English Verbs, Character Language Modelling, POS tagging), lemmatization, spelling correction, and protein family sequences.

Key Insights and Ideas

  • Distributed States vs. Long-Term Dependencies: The most significant finding is that stacking RNN layers primarily helps in learning more distributed representations of hidden states, leading to better overall modeling. However, this increase in layers has a less pronounced effect on the RNN's ability to capture long-term dependencies.
  • WFA as an Analytical Tool: The paper successfully demonstrates that WFA, particularly when trained with spectral learning, can serve as a valuable tool for analyzing the internal workings and complexity of RNNs. The WFA rank provides a quantifiable measure of model complexity that can be correlated with RNN architecture choices.
  • Dataset-Specific Benefits: The benefit of adding an extra RNN layer is not uniform across all datasets. Some datasets show significant improvements with a two-layer model, while others see minimal gains or even perform better with a single-layer network. This highlights the importance of dataset characteristics in determining the effectiveness of deeper RNNs.
  • High Rank WFA for Complex States: Datasets requiring a high WFA rank (many hidden states) suggest that the underlying process has complex hidden state dynamics, which can be captured by deeper RNNs. However, this doesn't automatically imply the need for long-term dependencies.

Key Results

  • On dataset 12, a challenging synthetic dataset, the two-layer RNN model achieved a significant score improvement (from 0.711 to 0.851) compared to the one-layer model. This dataset required a high WFA rank (n=95), indicating complex hidden states.
  • On dataset 5, a real-world NLP dataset known for long-term dependencies, the improvement from a one-layer to a two-layer RNN was minimal (from 0.7988 to 0.8107). This suggests that simply adding layers doesn't solve the long-term dependency problem if the architecture isn't inherently suited for it.
  • In many cases, the one-layer RNN model performed competitively with, or even better than, the two-layer model, particularly on datasets where the WFA analysis suggested simpler underlying structures or where long-term dependencies were not the primary challenge.
  • The paper provides a table (Table 1) comparing WFA hyperparameters and scores with RNN scores, showing that while RNNs generally perform well, the WFA analysis offers insights into why certain architectures succeed.

Limitations and Future Work

  • Intractability: The spectral learning algorithm for WFA can become computationally intractable when dealing with very large basis sizes (long substrings), limiting the analysis for certain complex datasets.
  • Focus on LSTM: The study primarily focuses on LSTM layers. Future work could explore other RNN variants and their relationship with WFA ranks.
  • Theoretical Justification: While empirical results are strong, the paper suggests that further theoretical work is needed to fully bridge the gap between classic RNNs, multilayer RNNs, and WFA, especially concerning long-term context capture.
  • Exploring Deeper Architectures: The paper focuses on one vs. two layers. Investigating the impact of even deeper RNN architectures and their relation to WFA complexity is a natural next step.
  • Alternative WFA Learning: Exploring other WFA learning algorithms beyond spectral learning could provide complementary insights.

Summary updated

BibTeX
@inproceedings{liza2019relating,
  author = {Farhana Ferdousi Liza and Marek Grzes},
  title = {{Relating RNN Layers with the Spectral WFA Ranks in Sequence Modelling}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
}
Figure