Easy-First Dependency Parsing with Hierarchical Tree LSTMs

• Recursive neural tree encoders often require binary branching or a fixed arity, while alternatives that allow arbitrary branching may ignore modifier order.Source: §1 · p. 1
• The proposed tree encoding supports arbitrary branching and recursively composes recurrent encoders of left and right modifier sequences in a greedy, bottom-up dependency parser.Source: §1 · p. 1
• 92.6 UAS and 90.2 LAS on the PTB (Stanford dependencies), and 86.1 UAS and 84.4 LAS on the Chinese treebank, are reported without external embeddings and with greedy decoding.Source: §1 · p. 1
• The authors describe this as the first demonstration, to their knowledge, of competitive full-scale parsing using only recursive compositional tree representations and no reranking framework.Source: §1 · p. 1

2.1 Dependency-based Representation

• A dependency tree is a list of labeled head–modifier edges over sentence words, with one designated root and every other node having a parent.Source: §2.1 · p. 2
• PTB dependency trees are often shallow but wide: 93% have a node of arity 4 or more, and 56% have one of arity 6 or more.Source: §2.1 · p. 2

2.2 Recurrent Networks and LSTMs

• An RNN maps an input-vector sequence to state vectors, with each state conditioned on the inputs seen so far; its learned outputs are trained for prediction.Source: §2.2 · p. 2
• The method uses the LSTM variant, but its encoding and algorithm can transparently switch to another RNN variant.Source: §2.2 · pp. 2–3

3 Tree Representation

• For each node, separate RNNs encode its left and right modifiers in head-outward order; their states are concatenated, transformed, and reduced to the node representation.Source: §3 · p. 3

3.1 Representing words

• Bidirectional LSTM word representations capture word form, POS tag, and sentence context, and are trained jointly with the parsing network.Source: §3.1 · p. 4
• The main experiments emphasize random word-embedding initialization to assess what the architecture learns from the training corpus alone; pretrained embeddings are also evaluated.Source: §3.1 · p. 4

3.2 A note on the head-outward generation

• Head-outward order facilitates incremental tree construction and emphasizes outermost dependents, while a head-inward or bidirectional encoding may suit trees specified in advance.Source: §3.2 · p. 5
• Unlike prior approaches that use fixed modifier windows and treat left and right sequences independently, the model accesses both complete sequences jointly.Source: §3.2 · p. 5

4.1 Bottom-up Parsing

• Neighboring partial trees are attached in one of two directions until a single output tree remains after n −1 steps.The strategy is projective and follows an Easy-First-style bottom-up procedure.Source: §4.1 · p. 5

4.2 Bottom-up Tree-Encoding

• The parser maintains a vector encoding for every pending tree so the scoring function can condition on the subtrees it may connect.Algorithm 2 maintains these representations alongside the parsing algorithm.Source: §4.2 · p. 6

4.3 Labeled Tree Representation

• The labeled tree representation concatenates the node vector with an embedding for the relation connecting the subtree to its parent.The label embedding is learned; only the final encoding equation changes.Source: §4.3 · p. 6

4.4 Scoring Function

• The scoring function assesses head-modifier compatibility, modifier fit with the head’s existing modifiers, and whether the modifier subtree is complete.Neighboring subtree representations provide hints about modifiers that may still be acquired.Source: §4.4 · p. 6
• The scoring function considers a window of six subtree encodings, using them instead of extensive hand-engineered features.The experiments use k = 2 subtrees on each side of the head-modifier pair.Source: §4.4 · pp. 6–7
• The action score sums separate unlabeled and labeled attachment scores, with the unlabeled score serving as a fallback when the label is uncertain.Both components are modeled as multilayer perceptrons.Source: §4.4 · p. 7

4.5 Computational Complexity

• The BI-LSTM encoder, tree-representation updates, and MLP scoring retain the Easy-First parser’s O(n log n) complexity.The added encoding and scoring operations take constant time at each parsing step.Source: §4.5 · p. 7

5.1 Loss and Parameter Updates

• A margin-based hinge loss trains the scorer to rank the highest-scoring correct action above incorrect actions at each parsing step.The losses are summed across a sentence, with parameter updates at sentence boundaries because updates invalidate the tree encodings.Source: §5.1 · p. 7
• Parameters are updated after 50 errors to provide a sufficient number of gradients and reduce gradient instability.The authors use ADAM after finding SGD results unstable.Source: §5.1 · pp. 7–8

5.2 Error-Exploration and Dynamic Oracle Training

• Error-exploration training follows the highest-scoring action, including incorrect actions, and uses a dynamic oracle to define correct actions in the resulting states.The oracle treats actions as gold when they do not increase erroneous attachments beyond the minimum possible given previous errors.Source: §5.2 · p. 8
• When a modifier’s score trails a correct action by less than the margin, aggressive exploration chooses the incorrect action with probability paug = 0.1.This cost-augmentation scheme exposes the parser to more errors during training.Source: §5.2 · p. 8

5.3 Out-of-vocabulary items and word-dropout

• Frequency-based word dropout replaces training words with the unknown-word symbol to learn its representation while minimizing impact on sparse words.The replacement probability is inversely proportional to word frequency.Source: §5.3 · pp. 8–9

6 Implementation Details

• The Python implementation uses PyCNN for computation graphs, automatic differentiation, and parameter updates, and trains for 20 iterations.Non-projective sentences are skipped during training; sentences are shuffled between iterations.Source: §6 · p. 9
• Table 1 lists the hyperparameter values used for the reported experiments.The implementation uses the toolkit’s default initialization, step sizes, and regularization values.Source: Table 1 · p. 9, §6 · p. 9
• The authors made few hyperparameter-tuning attempts, using manual hill climbing until results seemed reasonable and then keeping those settings.They note this did not follow advice emphasizing careful tuning for top neural-parser accuracy.Source: §6 · p. 9

7 Experiments and Results

• English evaluation uses Penn Treebank Stanford Dependencies with predicted POS tags, while Chinese uses CTB5 with gold POS tags.Punctuation is excluded from English evaluation.Source: §7 · p. 9
• The comparison includes a head-word-only baseline, tree-encoding variants, BI-LSTM head encodings, and configurations with external embeddings or without POS tags.The Stack-LSTM parser of Dyer et al. is included as a strong greedy-model comparator.Source: §7 · p. 9
• Across English and Chinese, adding tree encodings brings results near state-of-the-art accuracy; BI-LSTM head encodings further improve English results, while external embeddings improve both parsers.Without POS tags, accuracy drops slightly for English and substantially for Chinese; the authors report a somewhat smaller drop than Dyer et al.’s model.Source: §7 · p. 10, Table 2 · p. 10, Table 3 · p. 10
• 0.4–0.8 accuracy points (0.58 average) are lost on unseen sentences without error-exploration training.The authors report this for training without error-exploration or the dynamic aspect of the oracle.Source: §7 · p. 10, Table 4 · p. 10

Comparison to other state-of-the-art parsers

• Some state-of-the-art comparisons are not direct because systems differ in dependency schemes, POS tags, and pre-trained embeddings.The authors estimate that Penn2Malt conversion results can be 0.3–0.4 points higher than Stanford Dependencies.Source: Comparison to other state-of-the-art… · p. 10, Table 5 · p. 11
• English results are in the state-of-the-art range and Chinese results surpass it, using greedy bottom-up parsing without search and compositional tree representations.Table 5 compares UAS results across systems and datasets.Source: Comparison to other state-of-the-art… · p. 11, Table 5 · p. 11

8 Related Work

• Many recursive tree encoders restrict node composition to fixed arity, while binarization can create deep trees and vanishing-gradient problems.Tree-LSTM adds gating to address vanishing gradients; other arbitrary-arity approaches may ignore modifier sequence.Source: §8 · p. 11
• The proposed encoder handles arbitrary branching by using LSTMs over modifier sequences; a related top-down encoder is less suited to parsing but suited to generation.The authors suggest combining bottom-up and top-down approaches in an encoder-decoder framework.Source: §8 · p. 11
• Parsing approaches include search-based local-feature models, greedy transition parsers, recursive bottom-up encoders, and parse reranking.Reranking first generates a k-best list using a traditional parser and then scores its trees with recursive vector encodings.Source: §8 · pp. 11–12
• The proposed parser uses subtree-composition vectors as its sole features, without an external k-best parser or grammar, and parses arbitrary sentences greedily bottom-up.The authors contrast it with prior bottom-up parsers limited to short sentences or reporting low accuracy.Source: §8 · p. 12
• Compared with Dyer et al.’s greedy transition parser, this parser uses a more elaborate composition function and fully bottom-up parsing without stack-and-buffer control.The authors report similar scores overall and somewhat better results without pre-trained embeddings.Source: §8 · p. 12

9 Conclusions and Future Work

• The paper proposes a compositional parse-tree representation built from recursive combinations of recurrent-neural-network encoders and demonstrates it in a bottom-up easy-first parser.Future parsing extensions include beam search, character embeddings for unknown words, and adaptation to constituency trees.Source: §9 · p. 12
• The authors plan to test the encoder on sentiment, semantic sentence similarity, and textual inference tasks.These are proposed as further evaluations of its semantic vector representations.Source: §9 · p. 12

Appendix: Training Algorithm Pseudocode

• The outer training algorithm takes sentences, tree annotations, and an epoch count, then processes sentence–tree pairs.The pseudocode includes a pointer to the single-sentence dynamic-oracle training algorithm.Source: Appendix: Training Algorithm Pseudocode · pp. 16–17
• Corpus training iterates over sentence–tree pairs and accumulates each sentence’s loss before calling ADAM to minimize the summed loss.The pseudocode checks whether the loss list exceeds 50 before updating.Source: Appendix: Training Algorithm Pseudocode · p. 16
• For each sentence, training takes the words, their input vectors, an annotated dependency tree, and a list for loss expressions.The sentence loop continues while more than one item remains in the pending list.Source: Appendix: Training Algorithm Pseudocode · p. 17
• The sentence procedure enumerates candidate index, direction, and relation actions, then places actions into the gold-compatible or incorrect set.It uses action scores and a margin condition with random augmentation when selecting an action.Source: Appendix: Training Algorithm Pseudocode · p. 17
• When a modifier attaches, its left and right encodings are combined, transformed with the relation, and appended to the head’s left or right modifier sequence.The pseudocode gives the composition as m.c = m.el ◦ m.er, followed by m.enc = g(W(m.c ◦ rel) + b).Source: Appendix: Training Algorithm Pseudocode · p. 17