Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks

Yikang Shen, Shawn Tan, Alessandro Sordoni, Aaron C. Courville

Introduction

Natural language is inherently hierarchical: words form phrases, which form clauses, which form sentences. While standard Recurrent Neural Networks (RNNs) and LSTMs excel at processing sequential data, they lack an explicit mechanism to represent these nested "tree" structures. In a true hierarchy, when a large constituent (like a sentence) ends, all the smaller constituents nested within it must also end. Standard LSTMs have gates that allow neurons to act at different time scales, but these neurons act independently without a strict "nested" constraint.

To bridge this gap, the ON-LSTM (Ordered Neurons LSTM) introduces a clever inductive bias. By ordering neurons such that high-ranking ones store long-term "global" information and low-ranking ones handle short-term "local" data, the model naturally learns to induce tree-like structures from raw text without any explicit supervision.

The Ordered Neurons Architecture

The core innovation of the ON-LSTM is the Ordered Neurons inductive bias, which hard-codes the nested logic of hierarchies into the network's architecture. This is implemented through two main components:

  1. The cumax() Activation Function: Unlike a standard softmax that outputs a probability distribution, cumax() (cumulative softmax) produces a vector that transitions smoothly from 0 to 1. This creates a distinct "split point" in the neuron vector, separating different hierarchical levels.
  2. Master Gates: The architecture introduces a master forget gate ($\tilde{f}_t$) and a master input gate ($\tilde{i}_t$).
  3. The master forget gate determines how much of the previous state to erase. Due to the cumax ordering, erasing a high-ranking neuron forces the erasure of all lower-ranking neurons. This mimics "closing" a high-level node in a parse tree.
  4. The master input gate dictates how much new information to write. A large "write" area indicates the current word contains long-term information that should be preserved.
ON-LSTM cell states illustrating hierarchical representation

By combining these master gates with the standard LSTM's fine-grained gates, the ON-LSTM can dynamically decide which "chunk" of its memory represents which level of the linguistic hierarchy.

Experiments and Key Insights

The researchers evaluated the ON-LSTM across four distinct challenges: Language Modeling (Penn Treebank), Unsupervised Parsing (WSJ), Targeted Syntactic Evaluation, and Logical Inference.

Syntax Emerges from Prediction

The most profound insight from the study is that the model is never shown a parse tree during training. It learns to "parse" simply because representing the hierarchical structure of language is the most efficient way to minimize prediction error (perplexity). Interestingly, the researchers found that the middle layer of a 3-layer model was the most "syntactic," as the first layer focused on local word-level features and the top layer on the final prediction task.

State-of-the-Art Unsupervised Parsing

On the WSJ test set, the ON-LSTM achieved an F1 score of 47.7, significantly outperforming previous unsupervised models like PRPN and RL-SPINN. It successfully induced tree structures that align closely with human-annotated parse trees.

Example of an induced parse tree

Superior Modeling and Generalization

  • Language Modeling: The model achieved a test perplexity of 56.17 on PTB, outperforming standard LSTMs of comparable size.
  • Long-Term Dependencies: ON-LSTM performed significantly better on tasks requiring long-term dependency tracking, such as matching a subject to a verb across a long relative clause.
  • Logical Inference: When trained on short sequences of logical formulas, the ON-LSTM generalized much better to longer, unseen sequences than a standard LSTM, proving it learned underlying recursive logic rather than just memorizing surface patterns.

Limitations and Future Work

While highly effective, the ON-LSTM does introduce computational overhead. The cumax operation and additional gates add complexity compared to a vanilla LSTM, though the authors mitigated this by "chunking" (sharing master gates across groups of neurons). Furthermore, while the model induces trees by finding constituent boundaries, it does not output traditional syntactic labels (like NP or VP). Future work may explore leveraging these induced trees to improve downstream tasks like machine translation or summarization.

Summary updated

Abstract

Natural language is hierarchically structured: smaller units (e.g., phrases) are nested within larger units (e.g., clauses). When a larger constituent ends, all of the smaller constituents that are nested within it must also be closed. While the standard LSTM architecture allows different neurons to track information at different time scales, it does not have an explicit bias towards modeling a hierarchy of constituents. This paper proposes to add such inductive bias by ordering the neurons; a vector of master input and forget gates ensures that when a given neuron is updated, all the neurons that follow it in the ordering are also updated. Our novel recurrent architecture, ordered neurons LSTM (ON-LSTM), achieves good performance on four different tasks: language modeling, unsupervised parsing, targeted syntactic evaluation, and logical inference.
BibTeX
@inproceedings{shen2019ordered,
  author = {Yikang Shen and Shawn Tan and Alessandro Sordoni and Aaron C. Courville},
  title = {{Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=pROLaXwOHl},
}
Figure