Paper: Greed is Good if Randomized: New Inference for Dependency Parsing

ACL ID D14-1109
Title Greed is Good if Randomized: New Inference for Dependency Parsing
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2014
Authors

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 eva...