Source-linked AI summary
Learning to Compose Words into Sentences with Reinforcement Learning
Dani Yogatama, Phil Blunsom, Chris Dyer, Edward Grefenstette, Wang Ling
TL;DR
The paper asks whether sentence representations should use explicitly learned hierarchical composition rather than sequential or externally supervised tree structures. It uses reinforcement learning to optimize valid latent trees for downstream tasks, finding improved task performance while inducing structures that are partly linguistically intuitive but differ from conventional English syntax.
Problem
Sentence representations must capture hierarchical language structure, but prior approaches either omit explicit trees or rely on provided or supervised composition structures.
Method
The model uses reinforcement learning to learn valid binary tree structures and task-specific composition orders for a Tree LSTM sentence representation.
Results
Learned representations outperform sequential and syntax-based tree models across sentiment analysis, semantic relatedness, natural language inference, and sentence generation.
Takeaways & Limitations
The induced trees capture some noun phrases and simple verb phrases, but also differ from conventional English syntax, including overall left-branching patterns.
Takeaways & Limitations
Training is substantially slower than with predefined structures, taking 3–4 days to converge on SNLI or IMDB and requiring smaller 100-dimensional models.
Abstract
from arXiv · showhide
We use reinforcement learning to learn tree-structured neural networks for computing representations of natural language sentences. In contrast with prior work on tree-structured models in which the trees are either provided as input or predicted using supervision from explicit treebank annotations, the tree structures in this work are optimized to improve performance on a downstream task. Experiments demonstrate the benefit of learning task-specific composition orders, outperforming both sequential encoders and recursive encoders based on treebank annotations. We analyze the induced trees and show that while they discover some linguistically intuitive structures (e.g., noun phrases, simple verb phrases), they are different than conventional English syntactic structures.
1 INTRODUCTION
The paper proposes learning latent, sentence-specific tree structures with reinforcement learning instead of relying on sequential composition or explicit syntactic supervision. It motivates this compromise as a way to improve task-specific sentence representations while allowing structures that may differ from conventional syntax.
- 1 INTRODUCTION: Sequential RNNs do not explicitly organize words hierarchically, while tree-structured models recursively compose words and phrases.The paper frames its method against these two predominant representation strategies.
- 1 INTRODUCTION: Reinforcement learning learns sentence-specific tree structures whose downstream-task performance serves as the reward signal.The approach combines latent hierarchical composition with task-based optimization rather than explicit tree supervision.
- 1 INTRODUCTION: The method relates to unsupervised grammar induction but uses semantic feedback through downstream performance rather than inferring grammar without semantic feedback.The authors describe it as a simpler alternative to prior semantically supervised grammar-induction models, while prioritizing downstream performance over conventional English syntax.
- 1 INTRODUCTION: Across sentiment analysis, semantic relatedness, natural language inference, and sentence generation, the learned representations outperform both left-to-right models and tree models based on linguistic syntax.The experiments also report linguistically intuitive structures alongside marked differences from conventional English analyses.
2 MODEL
The model uses a Tree LSTM sentence representation together with reinforcement learning to learn valid, task-specific binary composition trees rather than relying on supplied syntactic structures. A policy selects SHIFT and REDUCE operations, and downstream-task performance supplies the reward for learning those structures.
- Model overview: The model combines a sentence representation component with a reinforcement-learning algorithm that learns the tree structure used for composition.The representation model follows SPINN, while reinforcement learning selects the composition order.
- Tree LSTM: SPINN parses an N-word sentence with N SHIFT and N −1 REDUCE operations, using Tree LSTM to compose stack elements into the final sentence representation.SHIFT pushes the next word onto the stack; REDUCE combines two stack elements and pushes the result back.
- Design motivation: Unlike prior models that receive tree structures or learn to reproduce treebank annotations, this approach imposes only validity as a constraint and may discover nonconventional structures if they improve the task.The learned trees can be linguistically intuitive, heavily left- or right-branching, or other valid binary structures.
- Reinforcement learning: A policy network chooses SHIFT or REDUCE from the hidden states of the top stack elements and the embedding of the word at the current pointer.The policy is parameterized as π(a | s; WR) and uses a two-layer feedforward network.
- Reinforcement learning: REINFORCE learns the policy so that action sequences maximize downstream-task performance, with reward observed after the complete sentence representation is constructed.For classification, the reward is based on the probability of predicting the correct label from the resulting representation.
- Learning regimes: The experiments compare unsupervised tree learning with semi-supervised learning that temporarily rewards actions matching an external parser before optimizing only the downstream objective.The semi-supervised objective includes the action-prediction term for the first E epochs and then removes it.
3 EXPERIMENTS
The experiments compare fixed composition orders, syntax-guided trees, and reinforcement-learning methods across sentence representation tasks. Learned task-specific structures outperform predefined structures on sentiment and semantic relatedness, while latent syntax performs best on SNLI.
- Baselines: The study compares right-to-left, left-to-right, bidirectional, supervised-syntax, semi-supervised-syntax, and latent-syntax composition methods.The reinforcement-learning variants differ in whether predefined parse structures guide training.
- Tasks: The evaluation covers sentiment classification, semantic relatedness, natural language inference, and sentence generation.The datasets include Stanford Sentiment Treebank, SICK, SNLI, and an IMDB-based sentence-generation setup.
- Sentiment classification: The latent syntax model is best on sentiment classification, while latent and semi-supervised syntax outperform models with predefined structures.These results are reported from repeated runs with development-set model selection.
- Semantic relatedness: Learning tree structures improves semantic-relatedness performance, with semi-supervised syntax better than most comparison models except Tai et al.’s LSTM models.The task uses mean squared error on SICK, and the compared models may use different objectives.
- Natural language inference: On SNLI, latent syntax performs best, left-to-right composition beats supervised recursive composition, and the models underperform state-of-the-art systems with nearly four times as many parameters.Semi-supervised training narrows the gap with the supervised model but does not overcome its poor performance on this dataset.
4 DISCUSSION
The learned structures outperform predefined composition orders across tasks, while only partially matching conventional syntax. They often capture simple phrases and left-branching patterns, but can also produce unconventional groupings, and training is substantially slower.
- Learned Structures: The proposed method outperforms competing methods with predefined composition orders on all evaluated tasks.
- Learned Structures: The learned trees achieve bracketing F1 scores of 41.73 on SNLI and 40.51 on SST, near left-branching baselines.Right-branching baselines score 19.94 on SNLI and 12.96 on SST, while left-branching baselines score 41.37 and 38.56.
- Learned Structures: On SNLI, the model tends toward left-branching trees, sometimes discovering noun phrases and simple verb phrases.Examples include “a boy,” “his sleds,” “wearing sunglasses,” and “is frowning.”
- Learned Structures: The model also learns unconventional groupings that make little sense to humans, such as composing “playing frisbee in” and “outside a” as phrases.
- Training Time: Training takes about two or three times longer to converge than models with predefined structures, reaching three to four days on SNLI or IMDB.The slower training also limited experiments to smaller 100-dimensional Tree LSTM models.
5 CONCLUSION
The paper presents reinforcement learning for task-specific hierarchical sentence composition and evaluates both its task benefits and the structures it induces. The resulting trees combine linguistically intuitive phrases with departures from conventional English syntax.
- Reinforcement learning learns hierarchical structures and task-specific composition orders for sentence representations across four tasks.
- The induced trees contain noun phrases and simple verb phrases while differing from conventional English syntactic structures.