Paper: TAG Dynamic Programming and the Perceptron for Efficient Feature-Rich Parsing

ACL ID W08-2102
Title TAG Dynamic Programming and the Perceptron for Efficient Feature-Rich Parsing
Venue International Conference on Computational Natural Language Learning
Session Main Conference
Year 2008
Authors

We describe a parsing approach that makes use of the perceptron algorithm, in conjunction with dynamic programming methods, to recover full constituent-based parse trees. The formalism allows a rich set of parse-tree features, including PCFG- based features, bigram and trigram dependency fea- tures, and surface features. A severe challenge in applying such an approach to full syntactic pars- ing is the efficiency of the parsing algorithms in- volved. We show that efficient training is feasi- ble, using a Tree Adjoining Grammar (TAG) based parsing formalism. A lower-order dependency pars- ing model is used to restrict the search space of the full model, thereby making it efficient. Experiments on the Penn WSJ treebank show that the model achieves state-of-the-art performance, for both con- ...