Media Technology Seminar: Generalized Higher-Order Dependency Parsing

Speaker: Ryan McDonald, NPL
UCL Contact: Sebastian Riedel (Visitors from outside UCL please email in advance).
Date/Time: 26 Feb 14, 16:00 - 17:00
Venue: TBA
Further Information:

If you're interested in NLP research feel free to register there to get NLP seminar announcements and help us with logistics by RVSPing.

Abstract

State-of-the-art graph-based dependency parsers use features over higher-order dependencies that rely on decoding algorithms that are slow and hyper-specialized. In contrast, transition-based dependency parsers can easily utilize such features without an increase in asymptotic complexity. To address this imbalance, we generalize the Eisner algorithm to handle arbitrary features by enriching chart signatures without changing the underlying dynamic programming algorithm. While this generalization is at the cost of efficiency, we can ameliorate this by employing cube-pruning, a common approximate decoding technique used in machine translation. To train the model, we develop a variant of the max-violation perceptron algorithm of Huang et al. (2012) generalized to approximate decoding over hypergraphs -- of which cube-pruned dependency parsing is a special case. Experiments show state-of-the-art results on a number of languages with competitive parsing speeds relative to linear transition-based parsing systems. The talk will conclude with some thoughts on how to extend the model to non-projective structures and some general opinions on the future of dependency parsing.

This is joint work with Hao Zhang (Google), Liang Huang (CUNY) and Kai Zhao (CUNY).

Ryan McDonald

Ryan leads the Google NLP lab, and is a super-star in NLP with several best paper awards to his name. Among other things, He has been extremely influential in teaching machines how to parse the syntax of a sentence, and his talk will address this question.