keyword

greedy parser

A greedy parser is an algorithm in natural language processing that analyzes the grammatical structure of a sentence by making a sequence of locally optimal decisions at each step without backtracking. Instead of evaluating multiple alternative parses concurrently or searching globally across all possible structures, it uses a classifier to immediately select and commit to the single highest-scoring transition action from the current parser state. This design allows the parser to operate in linear time relative to input length, achieving very high processing speeds. The primary trade-off is susceptibility to error propagation, as an incorrect decision made early in the sequence cannot be revised later in the parsing process.

1 item

A Fast and Accurate Dependency Parser using Neural Networks

Danqi Chen, Christopher D. Manning

OrganizationsStanford University

Why you should read this

Presents a greedy transition-based dependency parser powered by a neural network that replaces millions of sparse indicator features with compact dense representations, achieving high parsing accuracy while processing over 1,000 sentences per second.

Almost all current dependency parsers classify based on millions of sparse indicator features. Not only do these features generalize poorly, but the cost of feature computation restricts parsing speed significantly. In this work, we propose a novel way of learning a neural network classifier for use in a greedy, transition-based dependency parser. Because this classifier learns and uses just a small number of dense features, it can work very fast, while achieving an about 2% improvement in unlabeled and labeled attachment scores on both English and Chinese datasets. Concretely, our parser is able to parse more than 1000 sentences per second at 92.2% unlabeled attachment score on the English Penn Treebank.

Source

https://aclanthology.org/D14-1082.pdf

Added

2026-09-18