Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing

Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing Tim Vieira and Jason Eisner Department of Computer Science, Johns Hopkins University {timv,jason}@cs.jhu.edu Abstract Pruning hypotheses during dynamic program- ming is commonly used to speed up inference in settings such as parsing. Unlike prior work, we train a pruning policy under an objective that measures end-to-end performance: we search for a fast and accurate policy. This poses a difficult machine learning problem, which we tackle with the LOLS algorithm. LOLS training must continually compute the ef- fects of changing pruning decisions: we show how to make this efficient in the constituency parsing setting, via dynamic programming and change propagation algorithms. We find that optimizing end-to-end performance in this way leads to a better Pareto frontier—i.e., parsers which are more accurate for a given runtime. 1 Introduction Decades of research have been dedicated to heuris- tics for speeding up inference in natural language processing tasks, such as constituency parsing (Pauls and Klein, 2009; Caraballo and Charniak, 1998) and machine translation (Petrov et al., 2008; Xu et al., 2013). Such research is necessary because of a trend toward richer models, which improve accuracy at the cost of slower inference. For example, state-of-the- art constituency parsers use grammars with millions of rules, while dependency parsers routinely use mil- lions of features. Without heuristics, these parsers take minutes to process a single sentence. To speed up inference, we will learn a pruning pol- icy. During inference, the pruning policy is invoked to decide whether to keep or prune various parts of the search space, based on features of the input and (potentially) the state of the inference process. Our approach searches for a policy with maximum end-to-end performance (reward) on training data, where the reward is a linear combination of problem- specific measures of accuracy and runtime, namely reward = accuracy−λ·runtime. The parameter λ ≥ 0 specifies the relative importance of runtime and accu- racy. By adjusting λ, we obtain policies with different speed-accuracy tradeoffs. For learning, we use Locally Optimal Learning to Search (LOLS) (Chang et al., 2015b), an algorithm for learning sequential decision-making policies, which accounts for the end-to-end performance of the entire decision sequence jointly. Unfortunately, executing LOLS naively in our setting is prohibitive because it would run inference from scratch millions of times under different policies, training examples, and variations of the decision sequence. Thus, this paper presents efficient algorithms for repeated inference, which are applicable to a wide variety of NLP tasks, including parsing, machine translation and sequence tagging. These algorithms, based on change propagation and dynamic programming, dramatically reduce time spent evaluating similar decision sequences by leveraging problem structure and sharing work among evaluations. We evaluate our approach by learning pruning heuristics for constituency parsing. In this setting, our approach is the first to account for end-to-end performance of the pruning policy, without making independence assumptions about the reward func- tion, as in prior work (Bodenstab et al., 2011). In the larger context of learning-to-search for structured …

Content truncated to 500 words