K-Best A* Parsing

A* parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k-best extraction methods can efficiently search for top derivations, but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A* parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A* methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A* parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of grammar types.

• Publication year

  2009

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2009-08-02

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1690219.1690281
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Hierarchical Search for Parsing

  2009cited by this paper
• The Generalized A* Architecture

  2007influential reference
• Approximate Factoring for A* Search

  2007cited by this paper
• Scalable Inference and Training of Context-Rich Syntactic Translation Models

  2006cited by this paper
• Effective Self-Training for Parsing

  2006cited by this paper
• Learning Accurate, Compact, and Interpretable Tree Annotation

  2006cited by this paper
• Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking

  2005cited by this paper
• Better k-best Parsing

  2005influential reference
• Minimum Bayes-Risk Decoding for Statistical Machine Translation

  2004cited by this paper
• What’s in a translation rule?

  2004cited by this paper
• Minimum Error Rate Training in Statistical Machine Translation

  2003cited by this paper
• A* Parsing: Fast Exact Viterbi Parse Selection

  2003influential reference
• Accurate Unlexicalized Parsing

  2003influential reference
• Squibs and Discussions: Weighted Deductive Parsing and Knuth’s Algorithm

  2003cited by this paper
• Factored A* search for models over sequences and trees

  2003influential reference
• Fast Exact Inference with a Factored Model for Natural Language Parsing

  2002cited by this paper
• Parsing and Hypergraphs

  2001cited by this paper
• Discriminative Reranking for Natural Language Parsing

  2000cited by this paper
• Computation of the N Best Parse Trees for Weighted and Stochastic Context-Free Grammars

  2000influential reference
• Learning to Parse Natural Language with Maximum Entropy Models

  1999cited by this paper
• Parsing Inside-Out

  1998cited by this paper
• Principles and Implementation of Deductive Parsing

  1994cited by this paper
• Building a Large Annotated Corpus of English: The Penn Treebank

  1993cited by this paper
• A Tree.Trellis Based Fast Search for Finding the N Best Sentence Hypotheses in Continuous Speech Recognition

  1990cited by this paper
• A Generalization of Dijkstra's Algorithm

  1977cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper

• Examining False Positives under Inference Scaling for Mathematical Reasoning

  2025cites this paper
• Uncertainty-Aware Semantic Decoding for LLM-Based Sequential Recommendation

  2025cites this paper
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models

  2024cites this paper
• InfAlign: Inference-aware language model alignment

  2024cites this paper
• Online Context-Free Recognition in OMv Time

  2024cites this paper
• On Finding the K-best Non-projective Dependency Trees

  2021influential citation
• Outside Computation with Superior Functions

  2021cites this paper
• Span-based Neural Structured Prediction

  2018cites this paper
• Value-based Search in Execution Space for Mapping Instructions to Programs

  2018cites this paper
• Valency-Augmented Dependency Parsing

  2018cites this paper
• Online learning of latent linguistic structure with approximate search

  2018cites this paper
• K-best Iterative Viterbi Parsing

  2017cites this paper
• Data Analysis Project: A Probabilistic Generative Grammar for Semantic Parsing

  2017cites this paper
• Leveraging MWEs in practical TAG parsing : towards the best of the two worlds

  2017cites this paper
• Dyna 2: Towards a General Weighted Logic Language

  2017cites this paper
• A Probabilistic Generative Grammar for Semantic Parsing

  2017cites this paper
• Global Neural CCG Parsing with Optimality Guarantees

  2016cites this paper
• Promoting multiword expressions in A* TAG parsing

  2016cites this paper
• Bimorphism Machine Translation

  2016cites this paper
• A Probabilistic Generative Grammar for Semantic Parsing

  2016cites this paper
• k -Best Enumeration

  2015cites this paper
• Imitation Learning of Agenda-based Semantic Parsers

  2015cites this paper
• Explorer Efficient CCG Parsing : A * versus Adaptive Supertagging

  2015cites this paper
• If the Current Clique Algorithms are Optimal, So is Valiant's Parser

  2015cites this paper
• Exact Decoding with Multi Bottom-Up Tree Transducers

  2015cites this paper
• Large-scale Exact Decoding: The IMS-TTT submission to WMT14

  2014cites this paper
• K-Best Enumeration

  2014cites this paper
• Automatic Pipeline Construction for Real-Time Annotation

  2013cites this paper
• Two Algorithms for Finding k Shortest Paths of a Weighted Pushdown Automaton

  2013cites this paper
• Iterative Viterbi A* Algorithm for K-Best Sequential Decoding

  2012influential citation
• Integrated Supertagging and Parsing

  2012cites this paper
• Two Algorithms for Finding $k$ Shortest Paths of a Weighted Pushdown Automaton

  2012cites this paper
• Constrained Decoding for Text-Level Discourse Parsing

  2012cites this paper
• Optimal Search Algorithms for Structured Problems in Natural Language Processing

  2012cites this paper
• Deciding the Twins Property for Weighted Tree Automata over Extremal Semifields

  2012cites this paper
• Preservation of Recognizability for Weighted Linear Extended Top-down Tree Transducers Deciding the Twins Property for Weighted Tree Automata over Extremal Semifields Ttt: a Tree Transduction Language for Syntactic and Semantic Processing Second Position Clitics and Monadic Second-order Transduction

  2012cites this paper
• Discontinuous Data-Oriented Parsing: A mildly context-sensitive all-fragments grammar

  2011cites this paper
• Constructing efficient information extraction pipelines

  2011cites this paper
• Attempts to verify written English

  2011cites this paper
• The Second Workshop on Statistical Parsing of Morphologically Rich Languages ( SPMRL

  2011cites this paper
• Discontinuous Data-Oriented Parsing through Mild Context-Sensitivity

  2011cites this paper
• An unsupervised learning approach for automatic detection of metaphors

  2011cites this paper
• Frontier Pruning for Shift-Reduce CCG Parsing

  2011cites this paper
• Application of Tree Transducers in Statistical Machine Translation

  2011cites this paper
• Efficient CCG Parsing: A* versus Adaptive Supertagging

  2011influential citation
• K⁎: A heuristic search algorithm for finding the k shortest paths

  2011influential citation
• Querying parse trees of stochastic context-free grammars

  2010cites this paper
• Discriminative training and variational decoding in machine translation via novel algorithms for weighted hypergraphs

  2010cites this paper
• Top-Down K-Best A* Parsing

  2010influential citation
• Millstream Systems – a Formal Model for Linking Language Modules by Interfaces N-best Parsing Revisited Workshop Program Preservation of Recognizability for Synchronous Tree Substitution Grammars Requirements on a Tree Transformation Model for Machine Translation Preservation of Recognizability for

  2010cites this paper
• Dyna: Extending Datalog for Modern AI

  2010cites this paper
• Weighted tree automata and transducers for syntactic natural language processing

  2010influential citation
• A Joint Rule Selection Model for Hierarchical Phrase-Based Translation

  2010cites this paper
• Efficient Inference through Cascades of Weighted Tree Transducers

  2010cites this paper
• n-Best Parsing Revisited

  2010cites this paper