Greed is Good if Randomized: New Inference for Dependency Parsing

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