Greed is Good if Randomized: New Inference for Dependency Parsing

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1013–1024, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Greed is Good if Randomized: New Inference for Dependency Parsing Yuan Zhang∗, Tao Lei∗, Regina Barzilay, and Tommi Jaakkola Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {yuanzh, taolei, regina, tommi}@csail.mit.edu Abstract Dependency parsing with high-order fea- tures results in a provably hard decoding problem. A lot of work has gone into developing powerful optimization meth- ods for solving these combinatorial prob- lems. In contrast, we explore, analyze, and demonstrate that a substantially simpler randomized greedy inference algorithm al- ready suffices for near optimal parsing: a) we analytically quantify the number of lo- cal optima that the greedy method has to overcome in the context of first-order pars- ing; b) we show that, as a decoding algo- rithm, the greedy method surpasses dual decomposition in second-order parsing; c) we empirically demonstrate that our ap- proach with up to third-order and global features outperforms the state-of-the-art dual decomposition and MCMC sampling methods when evaluated on 14 languages of non-projective CoNLL datasets.1 1 Introduction Dependency parsing is typically guided by param- eterized scoring functions that involve rich fea- tures exerting refined control over the choice of parse trees. As a consequence, finding the high- est scoring parse tree is a provably hard combina- torial inference problem (McDonald and Pereira, 2006). Much of the recent work on parsing has focused on solving these problems using powerful optimization techniques. In this paper, we follow a different strategy, arguing that a much simpler in- ference strategy suffices. In fact, we demonstrate that a randomized greedy method of inference sur- passes the state-of-the-art performance in depen- dency parsing. ∗Both authors contributed equally. 1Our code is available at https://github.com/ taolei87/RBGParser. Our choice of a randomized greedy algorithm for parsing follows from a successful track record of such methods in other hard combinatorial prob- lems. These conceptually simple and intuitive algorithms have delivered competitive approxi- mations across a broad class of NP-hard prob- lems ranging from set cover (Hochbaum, 1982) to MAX-SAT (Resende et al., 1997). Their success is predicated on the observation that most realiza- tions of problems are much easier to solve than the worst-cases. A simpler algorithm will therefore suffice in typical cases. Evidence is accumulating that parsing problems may exhibit similar proper- ties. For instance, methods such as dual decom- position offer certificates of optimality when the highest scoring tree is found. Across languages, dual decomposition has shown to lead to a cer- tificate of optimality for the vast majority of the sentences (Koo et al., 2010; Martins et al., 2011). These remarkable results suggest that, as a com- binatorial problem, parsing appears simpler than its broader complexity class would suggest. In- deed, we show that a simpler inference algorithm already suffices for superior results. In this paper, we introduce a randomized greedy algorithm that can be easily used with any rich scoring function. Starting with an …

Content truncated to 500 words