Steps to excellence: Simple inference with refined scoring of dependency trees

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