Steps to Excellence: Simple Inference with Refined Scoring of Dependency Trees

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 197–207, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Steps to Excellence: Simple Inference with Refined Scoring of Dependency Trees Yuan Zhang, Tao Lei, Regina Barzilay, Tommi Jaakkola Massachusetts Institute of Technology {yuanzh, taolei, regina, tommi}@csail.mit.edu Amir Globerson The Hebrew University gamir@cs.huji.ac.il Abstract Much of the recent work on depen- dency parsing has been focused on solv- ing inherent combinatorial problems as- sociated with rich scoring functions. In contrast, we demonstrate that highly ex- pressive scoring functions can be used with substantially simpler inference pro- cedures. Specifically, we introduce a sampling-based parser that can easily han- dle arbitrary global features. Inspired by SampleRank, we learn to take guided stochastic steps towards a high scoring parse. We introduce two samplers for traversing the space of trees, Gibbs and Metropolis-Hastings with Random Walk. The model outperforms state-of-the-art re- sults when evaluated on 14 languages of non-projective CoNLL datasets. Our sampling-based approach naturally ex- tends to joint prediction scenarios, such as joint parsing and POS correction. The resulting method outperforms the best re- ported results on the CATiB dataset, ap- proaching performance of parsing with gold tags.1 1 Introduction Dependency parsing is commonly cast as a max- imization problem over a parameterized scoring function. In this view, the use of more expres- sive scoring functions leads to more challenging combinatorial problems of finding the maximiz- ing parse. Much of the recent work on parsing has been focused on improving methods for solving the combinatorial maximization inference prob- lems. Indeed, state-of-the-art results have been ob- 1The source code for the work is available at http://groups.csail.mit.edu/rbg/code/ global/acl2014. tained by adapting powerful tools from optimiza- tion (Martins et al., 2013; Martins et al., 2011; Rush and Petrov, 2012). We depart from this view and instead focus on using highly expressive scor- ing functions with substantially simpler inference procedures. The key ingredient in our approach is how learning is coupled with inference. Our com- bination outperforms the state-of-the-art parsers and remains comparable even if we adopt their scoring functions. Rich scoring functions have been used for some time. They first appeared in the context of rerank- ing (Collins, 2000), where a simple parser is used to generate a candidate list which is then reranked according to the scoring function. Because the number of alternatives is small, the scoring func- tion could in principle involve arbitrary (global) features of parse trees. The power of this method- ology is nevertheless limited by the initial set of alternatives from the simpler parser. Indeed, the set may already omit the gold parse. We dispense with the notion of a candidate set and seek to ex- ploit the scoring function more directly. In this paper, we introduce a sampling-based parser that places few or no constraints on the scoring function. Starting with an initial candi- date tree, our inference procedure climbs the scor- ing function in small (cheap) stochastic steps to- wards a high scoring parse. …

Content truncated to 500 words