Source-linked AI summary
Learning to Search for Dependencies
Kai-Wei Chang, He He, Hal Daumé III, John Langford
TL;DR
Dependency parsing raises a credit-assignment challenge: earlier mistakes, unequal error costs, and train/test prediction differences can undermine learning. The paper uses a learning-to-search compiler to generate machine-learning updates from a simple parser specification, reporting better performance across ten languages and an average labeled accuracy of 81.7 versus 80.3 for.
Problem
Credit assignment is difficult because systems may mishandle earlier errors, unequal error costs, or differences between training-time and test-time predictions.
Source: §1 · p. 1Method
A learning-to-search compiler turns a simple dependency-parser specification and labeled data into machine-learning updates, automatically handling credit assignment.
Source: §1 · p. 1Results
Takeaways & Limitations
The parser provides a simple, strong baseline for future dependency-parsing research.
Source: §1 · p. 2The framework assumes an oracle reference policy that always chooses the best action, assuming it controls all future decisions.
Source: §2 · p. 2
Abstract
from arXiv · showhide
We demonstrate that a dependency parser can be built using a credit assignment compiler which removes the burden of worrying about low-level machine learning details from the parser implementation. The result is a simple parser which robustly applies to many languages that provides similar statistical and computational performance with best-to-date transition-based parsing approaches, while avoiding various downsides including randomization, extra feature requirements, and custom learning algorithms.
1 Introduction
The paper applies a learning-to-search compiler to dependency parsing to handle credit assignment automatically, rather than relying on heuristic learning strategies. It reports competitive results across ten languages and presents the parser as a simple baseline for future work.
1 Introduction
- A learning-to-search compiler translates a simple dependency-parsing specification and labeled data into machine-learning updates, automatically handling credit assignment with known techniques.The paper frames this as an alternative to heuristic learning strategies.Source: §1 · p. 1
- Existing approaches may ignore earlier mistakes, unequal error costs, or train/test prediction differences, risking suboptimal learning when features are insufficient.The paper identifies these issues as sources of statistical inconsistency.Source: §1 · p. 1
- The compiler uses cost-sensitive learning, learned-policy roll-in and dynamic-oracle roll-out, and supports advanced learners through flags without extra implementation overhead.The implementation requires the test-time decoder and oracle; this parser is about 300 lines of C++.Source: §1 · p. 1
- Average labeled accuracy is 81.7 over 10 languages, versus 80.3 for.The experiments use English Penn Treebank and nine CoNLL-X languages.Source: §1 · p. 2
- The system is offered as a strong, simple baseline for dependency-parsing research, with the compiler approach potentially relevant to other complex prediction problems.The paper also identifies extending beyond greedy search as future work.Source: §1 · p. 2
2 Learning to Search
Learning to search formulates structured prediction as action selection in an explicit search space. In the imperative framework, developers specify a decoder, loss computation, and reference policy, while repeated executions explore alternatives and assess their losses.
2 Learning to Search
- Learning to search solves structured prediction by representing output production as an explicit state-and-action search space and learning a policy to select actions.The family includes methods such as the incremental structured perceptron, SEARN, and DAGGER.Source: §2 · p. 2
- Imperative learning to search asks developers to provide a task decoder, training-data loss annotation, and reference policy that suggests an action at each prediction point.The framework builds on advances intended to make novel structured-prediction frameworks easier to develop.Source: §2 · p. 2
- Repeated executions try different prediction policies to find one with low loss, exploring trajectories through roll-in choices, one-step deviations, and rollout completion.In Figure 1, the system collects loss after each deviation is completed by the rollout policy.Source: §2 · p. 2, Figure 1 · p. 2
- The framework assumes the reference policy is an oracle that chooses the best action at each state, assuming it also controls all future decisions.Source: §2 · p. 2
1. Execute RUNTAGGER on x with some rollin
The learning-to-search procedure explores trajectories by changing an action at a selected time step, then uses rollout losses to train the policy. Varying the policies and example construction lets the framework mimic algorithms such as DAGGER and SEARN.
1. Execute RUNTAGGER on x with some rollin
- At a selected time step, the procedure tries an alternative action, completes the trajectory with a rollout policy, and uses the resulting loss to form a classification or regression example.The example indicates how much better or worse the alternative action is than the original action in that context.Source: §1 · p. 3
- Executing the program repeatedly explores trajectories defined by the roll-in policy, the position of a one-step deviation, and the rollout policy.The example describes three executions and three trajectories.Source: §1 · p. 3
- Changing the roll-in policy, rollout policy, and example-construction method lets the framework mimic algorithms including DAGGER and SEARN.DAGGER uses the learned policy for roll-in and the reference policy for rollout; SEARN uses a stochastic mixture of learned and reference policies for both.Source: §1 · p. 3
3 Dependency Parsing by Learning to Search
The section formulates dependency parsing as search over parser configurations and describes an arc-hybrid parser with a dynamic oracle. Its implementation supplies a decoder, loss, and oracle while relying on the learning-to-search framework for prediction and learning.
3 Dependency Parsing by Learning to Search
- A transition-based parser represents each state by a stack, buffer, and generated arcs, and the arc-hybrid system applies actions until only the root remains and the buffer is empty.The available actions include SHIFT, REDUCE-LEFT, and REDUCE-RIGHT; the resulting arcs form a projective dependency tree.Source: §3 · p. 3
- The search space uses parser configurations as states and assigns each terminal state a loss based on the distance between the derived and gold trees.The dynamic oracle returns an optimal action in a state leading to a reachable end state with minimal loss.Source: §3 · p. 4
- The decoder extracts configuration-dependent features, identifies valid actions, predicts actions, updates configurations, and measures output loss.The feature templates draw on words and POS tags from the stack and buffer, as well as child information; feature hashing supports lookup.Source: §3 · pp. 4–5
- For labeled parsing, the parser predicts an arc label when applying REDUCE-LEFT or REDUCE-RIGHT and scores errors in parent assignments and labels.The stated loss is 2 for an incorrect parent, 1 for a correct parent with an incorrect label, and 0 otherwise.Source: §3 · p. 5
- The implementation uses about 300 lines of C++ because the learning-to-search framework supplies the learning algorithm and common functions.The framework also permits experiments with base learners and hyperparameters through command-line arguments without code changes; its reduction supports binary and multiclass classification methods.Source: §3 · p. 5
4 Experimental Results
The experiments compare the parser with recent strong baselines across English and nine other languages, and report comparable or better results across languages. They also examine learning algorithms and feature templates.
4 Experimental Results
- The parser is comparable to or better than recent strong baselines across languages; Table 3 reports UAS and LAS on PTB and CoNLL-X.The table’s caption notes that SNN performs substantially worse on languages with multi-root trees; excluding those languages, it reports average UAS/LAS of 85.6/81.8 for SNN and 88.5/84.3 for L2S.Source: §4 · p. 5, Table 3 · p. 6
4.1 Datasets
- Experiments use PTB and CoNLL-X data for nine additional languages, with standard PTB splits and the datasets’ provided CoNLL-X splits.The PTB evaluation uses Stanford-assigned POS tags; CoNLL-X uses gold POS tags.Source: §4.1 · p. 6
4.2 Setup and Parameters
- L2S mixes the learned policy with the dynamic oracle for roll-in and uses the dynamic oracle for roll-out.The reference-policy probability decreases by round as 1 − (1 − α)^t, with α = 10^-5 in all experiments.Source: §4.2 · p. 6
4.3 Results
- The parser achieves up to 4% improvement on both UAS and LAS.The authors report these measures with punctuation excluded from evaluation.Source: §4.3 · p. 7
- Using a strong base learner and cost-sensitive multiclass classification can improve performance.Table 4 reports performance for different base learning algorithms on the PTB corpus.Source: §4.3 · p. 7, Table 4 · p. 7
- A comprehensive feature set leads to a better dependency parser.Figure 5 compares the performance of different feature templates.Source: §4.3 · p. 7
5 Related Work
Prior transition-based parsing work studied transition systems, feature engineering, and predictors, while this paper focuses on the underlying learning technology. It treats dynamic-oracle parsing as a special case and presents a general programming interface implemented in C++ and Python.
5 Related Work
- Dynamic-oracle parsing is a special case of the paper’s learning-to-search approach: it uses a multiclass perceptron and no rollout to assign action costs.The paper instead uses cost-sensitive classification to evaluate the end result of non-optimal actions.Source: §5 · p. 7
- The authors describe their system as a general programming interface for structured prediction, implemented in C++ and Python rather than a new programming language.They characterize it as easily accessible.Source: §5 · pp. 7–8
6 Conclusion and Discussion
The paper concludes that a simple transition-based dependency parser built with learning to search is easier to implement and offers advanced training optimizations. Experiments show better performance across 10 languages, while future work includes moving beyond greedy search and speeding training through smarter rollout choices.
6 Conclusion and Discussion
- The parser consistently achieves better performance across 10 languages.The paper identifies extending beyond greedy search and choosing rollout points more efficiently as future directions.Source: §6 · p. 8
- The learning-to-search framework makes it easier to implement a high-performance dependency parser.The parser also offers a range of advanced optimization methods to choose from during training.Source: §6 · p. 8
- Future work includes extending the system beyond greedy search and speeding training by choosing where to roll out.Source: §6 · p. 8