Paper: New Ranking Algorithms For Parsing And Tagging: Kernels Over Discrete Structures And The Voted Perceptron

ACL ID P02-1034
Title New Ranking Algorithms For Parsing And Tagging: Kernels Over Discrete Structures And The Voted Perceptron
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2002
Authors

This paper introduces new learning al- gorithms for natural language processing based on the perceptron algorithm. We show how the algorithms can be efficiently applied to exponential sized representa- tions of parse trees, such as the “all sub- trees” (DOP) representation described by (Bod 1998), or a representation tracking all sub-fragments of a tagged sentence. We give experimental results showing sig- nificant improvements on two tasks: pars- ing Wall Street Journal text, and named- entity extraction from web data.