Better k-best Parsing

By Liang Huang, David Chiang. International Workshop/Conference on Parsing Technologies, 2005

388 citations recorded by the source corpus.

We discuss the relevance of k-best parsing to recent applications in natural language processing, and develop efficient algorithms for k-best trees in the framework of hypergraph parsing. To demonstrate the efficiency, scalability and accuracy of these algorithms, we present experiments on Bikel's implementation of Collins' lexicalized PCFG model, and on Chiang's CFG-based decoder for hierarchical phrase-based translation. We show in particular how the improved output of our algorithms has the potential to improve results from parse reranking systems and other applications.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/8dfdedcbeb3b67ecaa4d85ca4b9d1aff368b8e2a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Forest Reranking: Discriminative Parsing with Non-Local Features (2008, methodology): “Such a forest has a structure of a hypergraph (Klein and Manning, 2001; Huang and Chiang, 2005), where items like PP 3 , 6 are called nodes , and deductive steps like (*) correspond to hyperedges .”
Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking (2005, background): “Since this first draft of this paper we have become aware of two PCFG implementations of this algorithm (Jimenez and Marzal, 2000; Huang and Chang, 2005).”
Large-scale Exact Decoding: The IMS-TTT submission to WMT14 (2014, methodology): “k-best extractor From the translation derivation RTGs, a k-best list of derivations can be extracted (Huang and Chiang, 2005) very efficiently.”
SeqVAT: Virtual Adversarial Training for Semi-Supervised Sequence Labeling (2020, methodology): “To get the most possible label sequences, we apply a k-best Viterbi decoding (Huang and Chiang, 2005) on the original sequence in each training step.”
Online Large-Margin Training of Dependency Parsers (2005, methodology): “The Eisner (1996) algo-rithm can be modiﬁed to ﬁnd the k -best trees while only adding an additional O ( k log k ) factor to the runtime (Huang and Chiang, 2005).”
Modeling the effects of memory on human online sentence processing with particle filters (2008, background): “tational linguistics, such as probabilistic context-free g rammars (PCFGs), incremental processing algorithms exist that allow the exact computation of the posterior (implicitly represented) in polynomial time [10, 11, 12], from whichk-best structures [13] or samples from the posterior [14] can be e”
Confident Multiple Choice Learning (2017, methodology): “…proposed human-pose estimation methods which produce multiple predictions and then reﬁne them by employing a temporal model, and (Collins & Koo, 2005) proposed a sentence parsing method which re-ranks the output of an initial system which produces a set of plausible outputs (Huang & Chiang, 2005).”
Resolving Language and Vision Ambiguities Together: Joint Segmentation & Prepositional Attachment Resolution in Captioned Scenes (2016, methodology): “Our full model (M EDIATOR ) signiﬁcantly improves the accuracy of PPAR over the Stanford Parser by 17.91% for PASCAL-50S and by 12.83% for PASCAL-Context-50S, and achieves a small improvement on Semantic Segmentation over DeepLab-CRF for PASCAL-50S.”
Efficient Inference through Cascades of Weighted Tree Transducers (2010, methodology): “We already know of several methods for acquiring k-best trees from a WRTG (Huang and Chiang, 2005; Pauls and Klein, 2009), so we then must ask if, analogously to the string case, WTT s preserve recognizability 4 and we can form an application WRTG .”
Effective Self-Training for Parsing (2006, methodology): “However, the n-best parsing algorithm described in that paper has been replaced by the much more efficient algorithm described in (Jimenez and Marzal, 2000; Huang and Chang, 2005).”
Products of Random Latent Variable Grammars (2010, methodology): “To generate the candidate list, we produce k-best lists of Viterbi derivations with the efficient algorithm of Huang and Chiang (2005), and erase the subcategory information to obtain parse trees over unsplit categories.”
Hierarchical Phrase-Based Translation (2007, neutral): “We describe here how to do this using the lazy algorithm of Huang and Chiang (2005).”
Multiple Choice Learning: Learning to Produce Multiple Structured Outputs (2012, background): “In Natural Language Processing, this is the case for sentence parsing [8] and machine translation [26], where an initial system produces a list of M -Best hypotheses [12, 24] (also called k-best lists in the NLP literature), which are then re-ranked.”
Efficient Inference and Structured Learning for Semantic Role Labeling (2015, methodology): “the previous section, using the algorithm of Huang and Chiang (2005) and picking the best solution that satisfies all the constraints.”
Syntax Augmented Machine Translation via Chart Parsing (2006, methodology): “At initial submission time we simply re-scored a K-Best list extracted after first best parsing using the lazy retrieval process in (Huang and Chiang, 2005).”
Parsing with Compositional Vector Grammars (2013, methodology): “The k = 200-best parses at the top cell of the chart are calculated using the efficient algorithm of (Huang and Chiang, 2005).”
cdec: A Decoder, Alignment, and Learning Framework for Finite- State and Context-Free Translation Models (2010, methodology): “Although Viterbi and k-best extraction algorithms are often expressed as INSIDE algorithms with the tropical semiring, cdec provides a separate derivation extraction framework that makes use of a < operator (Huang and Chiang, 2005).”
Exact Decoding with Multi Bottom-Up Tree Transducers (2015, methodology): “…work on interpreted regular tree grammars (Koller and Kuhlmann, 2011), where arbitrary algebras can be used to compute a realization of the output tree. k-best extractor From the translation derivation RTGs, a k-best list of derivations can be extracted (Huang and Chiang, 2005) very efﬁciently.”