Assessing the Unitary RNN as an End-to-End Compositional Model of Syntax

Jean-Philippe Bernardy, Shalom Lappin

TL;DR

This paper introduces and evaluates Unitary Recurrent Neural Networks (URNs) as a novel architecture for modeling syntactic structures. URNs, by avoiding non-linear activations and using unitary matrices, offer a more transparent and compositionally sound approach to learning syntax compared to standard LSTMs, demonstrating promising results on complex dependency tasks.

What Problem Does This Paper Address?

Deep learning models, particularly Recurrent Neural Networks (RNNs) like LSTMs, have shown promise in capturing linguistic dependencies. However, their "black-box" nature, stemming from non-linear activation functions, makes them difficult to analyze and understand. Furthermore, the compositionality of how these models combine representations of words and phrases to form sentence-level meaning is often unclear. This paper aims to address these issues by proposing and evaluating Unitary RNNs (URNs), which are designed to be more transparent, mathematically tractable, and inherently compositional, while still being capable of modeling complex syntactic patterns.

Methods

The core of this paper is the comparison between LSTMs and a specific type of Unitary RNN (URN).

  • LSTMs: The authors use a standard LSTM architecture, which relies on gating mechanisms (forget, input, output gates) and non-linear activation functions (sigmoid and tanh) to process sequential data.
  • URNs: The URN model replaces the non-linear activations of LSTMs with unitary transformations. Specifically, the hidden state at time t ($h_t$) is updated by multiplying the previous hidden state ($h_{t-1}$) with a unitary matrix ($Q_t$) derived from the input embedding. This unitary embedding ($Q_t$) is generated by taking the matrix exponential of a skew-symmetric matrix, which is itself constructed from the input word embedding. This design ensures that the transformations are always unitary, meaning no information is lost during processing.

The key novelty lies in the URN's architecture, which enforces unitary transformations and thus strict compositionality, where the representation of a concatenated sequence is the product of the representations of its parts.

Datasets

The paper uses synthetic datasets to abstract away from the noise of natural language and focus on specific linguistic phenomena:

  • Cross-Serial Dependencies: The authors construct languages of the form $C_k = \{a^m b^n c^m d^n | m+n < k\}$. They use a training set of 51,200 strings and a test set of 5,120 strings, drawn from $C_{10}$.
  • Generalised Dyck Languages: These languages consist of strings of matching parenthesis pairs (e.g., (), [], {}, <>). The task is to predict the correct closing parenthesis type. They train on 102,400 strings and test on 5,120 strings, with string lengths of exactly 20 characters and nesting depths varying from 3 to 9.

Key Insights and Ideas

  • Compositionality as a Design Principle: The URN's architecture is built around the principle of compositionality, where the representation of a sequence is a direct product of its constituent parts. This is a significant departure from LSTMs, where composition is less explicit.
  • Transparency and Tractability: By avoiding non-linear activations, URNs are more amenable to mathematical analysis using standard linear algebra tools, making them less of a "black box" than LSTMs.
  • No Information Loss: The unitary nature of URN transformations means that no information is lost during the processing of input sequences, which is hypothesized to be beneficial for tasks requiring long-term memory.
  • Bias Towards Syntactic Structure: Even when trained as general language models, URNs show a bias towards learning the underlying syntactic patterns, suggesting their architecture is well-suited for this type of task.
  • Potential for Hierarchical Structure Recognition: URNs demonstrate impressive generalization capabilities for hierarchical patterns, particularly in the Dyck language task, suggesting they can capture complex syntactic structures.

Key Results

  • Cross-Serial Dependencies: Both LSTMs and URNs can model training data, but URNs show better generalization to longer sequences. While LSTMs can overfit with more units, URNs tend to improve with more units.
  • Generalised Dyck Languages: URNs achieve high accuracy, especially with a large number of attractors (indicating deeper nesting), suggesting strong hierarchical learning. They also show a smoother decrease in error rate during training and are less prone to overfitting compared to LSTMs. For instance, a 32-unit URN can achieve an error rate below 0.4 with a training loss as high as 1.
  • Parameter Efficiency: URN models achieve high accuracy with significantly fewer parameters than comparable LSTM models. For example, an 8-unit URN has 370 parameters for cross-dependency tasks, while an 8-unit LSTM has 1218.

Limitations and Future Work

  • Generalization to Longer Sequences (Cross-Serial): While URNs show promise, they do not generalize perfectly to extended sequences in the cross-serial dependency task.
  • Inner Position Confusion (Dyck): URNs exhibit some confusion in inner positions of Dyck language strings, though this decreases with more units.
  • Computational Cost: The fully general matrix exponential implementation makes URNs computationally more expensive than some other methods.
  • Future Work: The authors suggest exploring URNs for other cognitively interesting NLP tasks, examining parallels with human language understanding, and investigating the possibility of implementing URNs as quantum circuits due to the mathematical similarity between URN matrices and quantum logic gates.

Summary updated

Abstract

We show that both an LSTM and a unitary-evolution recurrent neural network (URN) can achieve encouraging accuracy on two types of syntactic patterns: context-free long distance agreement, and mildly context-sensitive cross serial dependencies. This work extends recent experiments on deeply nested context-free long distance dependencies, with similar results. URNs differ from LSTMs in that they avoid non-linear activation functions, and they apply matrix multiplication to word embeddings encoded as unitary matrices. This permits them to retain all information in the processing of an input string over arbitrary distances. It also causes them to satisfy strict compositionality. URNs constitute a significant advance in the search for explainable models in deep learning applied to NLP.
BibTeX
@misc{bernardy2022assessing,
  author = {Jean-Philippe Bernardy and Shalom Lappin},
  title = {{Assessing the Unitary RNN as an End-to-End Compositional Model of Syntax}},
  year = {2022},
  eprint = {2208.05719},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.05719},
}
Figure