Tree Transformer: Integrating Tree Structures into Self-Attention

Yau-Shian Wang, Hung-yi Lee, Yun-Nung Chen

Abstract: Yaushian Wang, Hung-Yi Lee, Yun-Nung Chen. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).

2019.

Introduction

While Transformers have revolutionized natural language processing, their core mechanism—self-attention—is essentially "flat." Standard attention allows any word to attend to any other word, often resulting in attention patterns that do not align with human intuitions about hierarchical language structure, where phrases are nested within phrases.

Previous attempts to integrate hierarchy into neural networks relied on Recursive Neural Networks (Tree-RNNs) or required expensive, human-annotated parse trees. The Tree Transformer addresses the challenge of grammar induction: learning latent hierarchical structures directly from raw text while maintaining the parallelization and efficiency of the Transformer architecture.

Methodology

The Tree Transformer modifies the bidirectional Transformer encoder with a novel "Constituent Attention" module that constrains the model to follow hierarchical language structures. This is achieved through three key components:

  1. Constituent Prior ($C$): In each layer, the model calculates a matrix $C$ where each entry $C_{i,j}$ represents the probability that words $i$ and $j$ belong to the same constituent (phrase). The standard attention matrix is element-wise multiplied by this prior, effectively "masking" attention so words primarily attend to others within their own phrase.
  2. Constituent Attention Module: This module estimates the "breakpoints" between constituents using Neighboring Attention to determine if adjacent words should be linked.
  3. Hierarchical Constraint: To ensure a tree structure, the authors enforce a rule: once two words are grouped into a constituent in a lower layer, they must remain in the same constituent in all higher layers. This causes constituents to grow and merge as information flows upward through the network.
Overview of the Tree Transformer architecture, showing hierarchical constraints (A), the modified block (B), and the resulting structured attention matrix (C).

The model is trained using the standard Masked Language Model (MLM) objective, similar to BERT, but without any supervised syntactic labels.

Key Insights and Results

Inductive Bias and Interpretability

By adding a constraint that encourages grouping, the model naturally discovers syntactic structures like noun phrases (NP) and adverb phrases (ADVP) that match human linguistics. Unlike standard Transformers, where attention maps can be chaotic, the Tree Transformer's attention maps are highly structured and "blocky," making the model's internal logic more interpretable.

An example of a tree structure induced by the Tree Transformer without any supervised syntactic labels.

Performance Benchmarks

The model was evaluated on standard grammar induction benchmarks, including the Penn Treebank (PTB) and the One Billion Word Benchmark.

  • Unsupervised Parsing: On the WSJ-test set, the Tree Transformer achieved an F1 score of 52.0, significantly outperforming older methods like PRPN (42.8) and On-LSTM (49.4), and remaining competitive with specialized models like URNNG (52.4).
  • Language Modeling: For a 12-layer model, the Tree Transformer reached a perplexity of 45.6, compared to 48.1 for a standard Transformer. This suggests that understanding the hierarchical "tree" of a sentence improves the model's ability to predict missing words.
  • Constituent Recall: The model is particularly effective at identifying Noun Phrases (67.6% recall) and Adverb Phrases (55.1% recall).

Limitations and Future Work

Despite its success, the authors noted several limitations. Initializing the model with pre-trained BERT weights actually hurt parsing performance, suggesting that BERT's internal representations are difficult to reconcile with strict hierarchical trees. Additionally, the Constituent Attention module adds approximately 10% more parameters and increases computation time by roughly 1.2x compared to a standard Transformer.

Future research may explore how these induced trees can be leveraged for downstream tasks like translation or summarization, where structural understanding is critical for maintaining meaning across complex sentences.

Summary updated

BibTeX
@inproceedings{wang2019tree,
  author = {Yau-Shian Wang and Hung-yi Lee and Yun-Nung Chen},
  title = {{Tree Transformer: Integrating Tree Structures into Self-Attention}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=85DQ5l29Wi6},
}
Figure