Source-linked AI summary
Top-down Tree Long Short-Term Memory Networks
Xingxing Zhang, Liang Lu, Mirella Lapata
TL;DR
Neural language models predict word sequences, while many NLP tasks use syntactic trees. The paper introduces TreeLSTM to estimate sentence probability through dependency-tree generation, and reports results beyond the current state of the art on MSR sentence completion and competitive dependency-parsing reranking.
Problem
Neural language models predict word sequences, although many NLP tasks exploit syntactic information in dependency or constituent trees.
Source: §1 · p. 1Method
TreeLSTM estimates sentence probability through dependency-tree generation, using LSTMs to represent dependency edges explicitly.
Source: §1 · pp. 1–2Results
The model outperforms the best published results on the MSR sentence completion challenge and achieves performance on par with recently proposed dependency parsers.
Source: §1 · p. 2Takeaways & Limitations
The authors report that dependency-tree generation holds promise for text-generation applications and that the formulation could also apply to constituent trees or taxonomies.
Source: §4 · p. 9Using START/STOP symbols for dependent generation would add 2N symbols per N-word sentence and make training cost and memory consumption three times as high.
Source: §3.4 · p. 8
Abstract
from arXiv · showhide
Long Short-Term Memory (LSTM) networks, a type of recurrent neural network with a more complex computational unit, have been successfully applied to a variety of sequence modeling tasks. In this paper we develop Tree Long Short-Term Memory (TreeLSTM), a neural network model based on LSTM, which is designed to predict a tree rather than a linear sequence. TreeLSTM defines the probability of a sentence by estimating the generation probability of its dependency tree. At each time step, a node is generated based on the representation of the generated sub-tree. We further enhance the modeling power of TreeLSTM by explicitly representing the correlations between left and right dependents. Application of our model to the MSR sentence completion challenge achieves results beyond the current state of the art. We also report results on dependency parsing reranking achieving competitive performance.
1 Introduction
The paper addresses the mismatch between sequence-predicting neural language models and NLP tasks that use syntactic trees. It introduces TreeLSTM to model dependency-tree generation and reports strong sentence-completion and parsing-reranking results.
1 Introduction
- TreeLSTM estimates a sentence’s probability through its dependency-tree generation probability, using four LSTMs for dependency-edge types with shared hidden layers.At each step, an LSTM predicts the next word conditioned on the subtree generated so far.Source: §1 · p. 1
- Earlier syntactic language models use Markov assumptions and n-gram smoothing, while Mirowski and Vlachos (2015) treat sentences as sequences over trees but ignore the tree structures themselves.The paper distinguishes its aim from recursive networks that build phrase or sentence representations for classification tasks (Socher et al., 2011b; Socher et al., 2011a).Source: §1 · p. 2
- Unlike dependency-based language models that limit dependency depth or encode syntax as features, the model represents dependency edges explicitly and can generate dependency trees.The authors characterize it as an infinite-order dependency language model and say it avoids manually choosing dependency-tree features and embedding sizes.Source: §1 · p. 2
- The model outperforms the best published results on the MSR sentence completion challenge and achieves performance on par with recently proposed dependency parsers.The paper also describes the sentence-completion result as a new state of the art for a single model.Source: §1 · p. 2
2 Tree Long Short-Term Memory Networks
TreeLSTM estimates sentence probability through top-down generation of a dependency tree, representing each word by its dependency path. Four edge-specific LSTMs model tree structure, and an additional LSTM lets right dependents use information from left dependents.
2.1 Dependency Path
- NX-LEFT and NX-RIGHT edges link non-first dependents through adjacent siblings, allowing information to flow from the parent through earlier dependents.LEFT and RIGHT edges represent the first dependent on each side; the NX edges replace direct parent links for subsequent dependents.Source: §2.1 · p. 2
2.2 Tree Probability
- Tree probability is computed by top-down breadth-first generation, visiting each node’s left dependents before its right dependents, closest first.The sentence probability is factorized over words conditioned on their dependency paths, with ROOT’s probability ignored.Source: §2.2 · p. 3
2.3 Tree LSTMs
- Four LSTMs encode the four edge types: GEN-L and GEN-R generate first dependents, while GEN-NX-L and GEN-NX-R generate subsequent dependents.The NX LSTMs can be applied repeatedly, so the model handles any number of left or right dependents.Source: §2.3 · p. 4
- The four jointly trained LSTMs share hidden states, and only one is active at each time step, giving training and inference complexity no different from a regular LSTM.The model also ties its word embedding and output matrices across the four LSTMs to reduce parameters.Source: §2.3 · p. 4
2.4 Left Dependent Tree LSTMs
- The LD LSTM represents a node’s left dependents from furthest to closest and supplies that representation when predicting the first right dependent.Later right dependents can also use this information through the first right dependent’s hidden state; left dependents cannot use right dependents because they are generated first.Source: §2.4 · p. 5
2.5 Model Training
- Training uses negative log-likelihood on small datasets and noise contrastive estimation on large-vocabulary datasets where softmax computation is prohibitively expensive.For NCE, the model discriminates data words from sampled noise words and sets k = 20.Source: §2.5 · pp. 5–6
3 Experiments
Experiments evaluate sentence completion and dependency-parsing reranking, and demonstrate tree generation. LDTREELSTM sets a new MSR benchmark state of the art and performs competitively in parsing.
3.1 Training Details
- NCE trains models for MSR sentence completion, while NLL trains rerankers; two-layer models use dropout and gradients are rescaled above norm 5.Training uses back propagation through time and stochastic gradient descent.Source: §3.1 · p. 6
3.2 Microsoft Sentence Completion Challenge
- 60.67 accuracy for LDTREELSTM (d = 400) exceeds 58.9 for Skip-gram + RNNMEs, establishing a new MSR state of the art with a single model.LDTREELSTM consistently outperforms TREELSTM, indicating the importance of modeling interactions between left and right dependents.Source: Table 1 · p. 7, §3.2 · p. 7
3.3 Dependency Parsing
- Both rerankers outperform MSTParser, with LDTREELSTM best; it slightly exceeds the NN parser in UAS but trails S-LSTM.The comparison reports unlabeled and labeled attachment scores for the reranking models and other parsers.Source: Table 2 · p. 7, §3.3 · p. 8
3.4 Tree Generation
- 94.3%, 92.6%, 93.4%, and 96.0% are the respective accuracies of the four edge-type classifiers.Generation starts at ROOT; classifiers choose edge types, then corresponding LSTMs sample nodes from predicted word distributions. Figure 5 shows generated trees. The START/STOP alternative was avoided because it would triple training cost and memory; lower-dimensional input embeddings also yield slightly worse classifiers.Source: §3.4 · pp. 8–9, Figure 5 · p. 8
4 Conclusions
TREELSTM and LDTREELSTM predict tree structures rather than linear sequences. The experiments show improved MSR sentence completion over sequential LSTMs and competitive dependency-parsing reranking.
4 Conclusions
- TREELSTM and LDTREELSTM are neural architectures designed to predict tree structures rather than linear sequences.The paper reports experiments with dependency trees and says the formulation also permits other tree structures, such as constituent trees or taxonomies.Source: §4 · p. 9
- On MSR sentence completion, LDTREELSTM outperforms sequential LSTMs; parsing reranking results demonstrate potential for dependency parsing.Source: §4 · p. 9
- Generated dependency trees are presented as promising for text-generation applications such as sentence compression and simplification.Source: §4 · p. 9