Source-linked AI summary
Tree Transformer: Integrating Tree Structures into Self-Attention
Yau-Shian Wang, Hung-Yi Lee, Yun-Nung Chen
TL;DR
Transformer attention does not clearly capture hierarchical language structure, motivating a model that makes such structure more explicit. Tree Transformer induces constituency trees from raw text with Constituent Attention and constrains attention within constituents; it improves language modeling, unsupervised parsing, and attention interpretability, while relying on structural choices such as positional encoding and showing weaker parsing when initialized from BERT.
Problem
Transformer attention heads do not match human intuitions about hierarchical structure, while supervised parsing requires annotations that may be unavailable in low-resource or domain-shifted settings.
Method
Tree Transformer adds Constituent Attention to a bidirectional Transformer encoder to induce trees from raw text and constrain attention to words within the same constituents.
Results
Tree Transformer induces trees coherent with human expert annotations, improves masked-language-model perplexity, and yields more interpretable attention patterns than the original Transformer.
Takeaways & Limitations
Integrating induced tree structures into Transformer attention supports unsupervised parsing, better language modeling, and attention patterns that better reflect hierarchical structure.
Takeaways & Limitations
Parsing remains far from the best results when the Transformer is initialized with pre-trained BERT, and removing positional encoding lowers induced-tree quality.
Abstract
from arXiv · showhide
Pre-training Transformer from large-scale raw texts and fine-tuning on the desired task have achieved state-of-the-art results on diverse NLP tasks. However, it is unclear what the learned attention captures. The attention computed by attention heads seems not to match human intuitions about hierarchical structures. This paper proposes Tree Transformer, which adds an extra constraint to attention heads of the bidirectional Transformer encoder in order to encourage the attention heads to follow tree structures. The tree structures can be automatically induced from raw texts by our proposed "Constituent Attention" module, which is simply implemented by self-attention between two adjacent words. With the same training procedure identical to BERT, the experiments demonstrate the effectiveness of Tree Transformer in terms of inducing tree structures, better language modeling, and further learning more explainable attention scores.
1 Introduction
Tree Transformer addresses the mismatch between Transformer attention and hierarchical language structure by inducing latent trees from raw text and constraining attention within constituents. The approach improves masked-language-model perplexity, unsupervised parsing, and attention interpretability.
- Grammar induction seeks latent tree structures from raw text without human-annotated data, avoiding dependence on supervised parsers unavailable in low-resource or domain-shifted settings.
- Transformer attention does not reliably reflect the hierarchical structures that characterize human language.
- Tree Transformer integrates tree structures into a bidirectional Transformer encoder by constraining words to attend within the same constituents.
- Constituency trees are automatically induced from raw text through a self-attention-based Constituent Attention module that progressively joins smaller constituents into larger ones.
- The model adds a Constituent Attention module to the original Transformer encoder and achieves good performance on unsupervised parsing.
- Tree Transformer improves masked-language-model perplexity and produces attention patterns that better match human intuitions about hierarchical structure than the original Transformer.
2 Related Work
Grammar induction learns latent tree structures from raw text, often using a target task such as language modeling to encourage useful hierarchical encoding. Prior approaches primarily introduced structural biases into recurrent or recursive neural networks.
- Grammar induction is the task of inducing latent tree structures from raw texts without human-annotated data.
- Grammar-induction models are commonly trained on target tasks such as language modeling, using induced trees to guide hierarchical text encoding.
- Prior work included reinforcement-learning formulations in which an unsupervised parser selects parsing operations to maximize downstream-task rewards.
- PRPN and On-LSTM induced tree-like structure by adding syntactic-distance, memory-attention, gating, or activation biases to recurrent networks.
3 Tree Transformer
Tree Transformer induces a hierarchical structure over a sentence while progressively restricting attention within constituents. Neighboring constituents merge across layers until the top layer contains one constituent and attention becomes unrestricted.
- Tree Transformer induces a tree structure from an input sentence using Transformer blocks augmented with a Constituent Attention module.
- At lower layers, words in different constituents cannot attend to each other, while neighboring constituents can merge into larger constituents at higher layers.
- In the top layer, all words belong to one constituent, so Tree Transformer behaves like a typical Transformer encoder with unrestricted attention.
- For example, the model can merge “cute” with “dog” and “its” with “tail” before forming larger constituents in subsequent layers.
- The model can be trained end-to-end with BERT-style masked language modeling, allowing latent tree structures to emerge from the Constituent Prior.
4 Constituent Prior
Constituent Prior guides Tree Transformer attention by estimating whether word pairs belong to the same constituent. It multiplicatively suppresses attention between words assigned low same-constituency probabilities, with one shared prior per layer across heads.
- The underlying query and key matrices use dimension dk, while multi-head attention produces dmodel = h × dk.
- The attention probability matrix E is computed from query-key attention and guided by the Constituent Prior C through element-wise multiplication.
- C is an N by N symmetric matrix whose Ci,j value represents the probability that words wi and wj belong to the same constituency.
- Each Transformer layer has its own Constituent Prior, and all attention heads within that layer share the same C.
- Small Ci,j values reduce Ei,j, thereby suppressing attention between positions belonging to different constituents.
5 Constituent Attention
Constituent Attention builds constituent priors from adjacent-word linking probabilities, while neighboring attention and hierarchical constraints shape these probabilities across words and layers.
- 5 Constituent Attention: Constituent Attention estimates breakpoint probabilities between adjacent words, then derives the constituent prior from them.A small adjacent-link probability indicates a breakpoint between neighboring words.
- 5.1 Neighboring Attention: Neighboring Attention restricts each word to linking with either its right or left neighbor using a softmax over the two links.The softmax keeps the two directional probabilities summing to 1 and makes attention sparse.
- 5.1 Neighboring Attention: Adjacent words are considered linked only when they attend to each other, using the average of their two directional attention probabilities.The resulting symmetric link probability is passed forward to compute the adjacent-word sequence.
- 5.2 Hierarchical Constraint: Hierarchical Constraint carries lower-layer constituent links into higher layers, allowing smaller constituents to merge into larger ones.The current-layer link probability combines the previous-layer probability with the current layer’s neighboring-attention output.
6 Unsupervised Parsing from Tree Transformer
Tree Transformer extracts parses from neighbor-link probabilities across layers using recursive breakpoint selection, while discarding unreliable lower layers and thresholding weak breakpoints.
- 6 Unsupervised Parsing from Tree Transformer: Unsupervised parsing uses small neighbor-link probabilities as breakpoints in a top-down greedy procedure that recursively splits sentences.The procedure forms a parse tree by repeatedly splitting at the minimum link probability.
- 6 Unsupervised Parsing from Tree Transformer: The multi-layer parser starts at the top layer and moves downward after each breakpoint until reaching a tuned bottom layer m.It uses hierarchical information from link probabilities across layers rather than selecting one layer alone.
- 6 Unsupervised Parsing from Tree Transformer: Layers below m are discarded because the lowest layers produce poor representations and parsing results.The bottom layer m is usually set to 2 or 3.
- 6 Unsupervised Parsing from Tree Transformer: A minimum link probability is accepted as a breakpoint only when it falls below 0.8.The threshold is used because top layers often have link probabilities close to 1, and the model is reported to be insensitive to its exact value.
7 Experiments
Experiments evaluate Tree Transformer on unsupervised constituency parsing, induced-structure analysis, interpretable attention, and masked language modeling. The results show meaningful tree induction, layer-wise hierarchical structure, more interpretable attention, and better masked-language-modeling performance than the original Transformer.
- 7.2 Grammar Induction: Tree Transformer is evaluated on unsupervised constituency parsing using BERT masked-language-model training on WSJ data.The experiments use WSJ training data and compare against established unsupervised parsing systems and trivial or random trees.
- 7.2 Grammar Induction: Increasing the layer number improves parsing because deeper models can represent deeper trees, but performance stops improving above depth 10.The authors attribute the plateau to higher layers grouping words into the same constituent.
- 7.2 Grammar Induction: The induced trees preferentially recover noun phrases and adverb phrases, while verb phrases and adjective phrases are harder to identify.Constituent recall is analyzed by phrase label, with an example parse tree shown separately.
- 7.3 Analysis of Induced Structures: Parsing performance is best when syntactic information begins at layer 3; a single-layer parse reaches F1 49.07 versus 52.0 from Algorithm 1.Using lower layers provides less informative representations, while overly large minimum layers miss syntactic information.
- 7.4 Interpretable Self-Attention: Attention visualizations show constituents growing across layers and attention heads attending mainly within the constituent assigned to each layer.The visualized structures progress from adjacent-word subphrases to larger constituents and support the model’s tree-like organization.
- 7.5 Masked Language Modeling: Tree Transformer improves masked-language-modeling performance over the original Transformer despite adding about 10% more hyperparameters and running 1.2 times slower.The comparison controls training data, optimizer, and most hyperparameters, and also considers parameter-matched Transformer variants.
8 Conclusion
Tree Transformer integrates tree structures into Transformer by constraining attention within constituents and automatically inducing those structures from raw text. The paper reports coherent unsupervised parses and more interpretable attention, while noting that positional encoding affects parse quality.
- Tree Transformer constrains attention heads to attend within constituents, integrating tree structures into the Transformer architecture.
- The Constituent Attention module automatically induces tree structures from raw text by attaching constituents through self-attention.
- Unsupervised parsing produces tree structures coherent with human expert annotations.
- Removing positional encoding lowers the quality of induced parse trees.
A Visualization of Self-Attention
Tree Transformer attention becomes increasingly broad as constituents merge across layers, whereas the original Transformer shows neighboring-word attention mainly in its first layer. The accompanying heat maps visualize attention patterns, while the parse-tree figures show induced structures.
- Tree Transformer’s first-layer attention is local because constituents are small, with words attending mainly to adjacent words.
- As constituents attach into larger units, Tree Transformer attends to increasingly distant words across higher layers.
- Within Tree Transformer, words in the same phrase attend to one another, including the phrases “involve in” and “delta air line”.
- The original Transformer also shows neighboring-word attention in its first layer, but its third-layer heads attend to other words without the same apparent structure.
- Figure 6 presents Tree Transformer attention heat maps, while Figure 7 presents corresponding heat maps from the original Transformer.
- Figures 8 and 9 present parse trees induced by Tree Transformer.