Parsing Algorithms and Metrics

Many different metrics exist for evaluating parsing results, including Viterbi, Crossing Brackets Rate, Zero Crossing Brackets Rate, and several others. However, most parsing algorithms, including the Viterbi algorithm, attempt to optimize the same metric, namely the probability of getting the correct labelled tree. By choosing a parsing algorithm appropriate for the evaluation metric, better performance can be achieved. We present two new algorithms: the "Labelled Recall Algorithm," which maximizes the expected Labelled Recall Rate, and the "Bracketed Recall Algorithm," which maximizes the Bracketed Recall Rate. Experimental results are given, showing that the two new algorithms have improved performance over the Viterbi algorithm on many criteria, especially the ones that they optimize.

• Publication year

  1996

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  1996-05-30

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/981863.981887arXiv cmp-lg/9605036
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient Algorithms for Parsing the DOP Model

  1996cited by this paper
• An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

  1994cited by this paper
• Natural Language Parsing as Statistical Pattern Recognition

  1994cited by this paper
• Using an Annotated Corpus as a Stochastic Grammar

  1993cited by this paper
• A corpus-based approach to language learning

  1993cited by this paper
• Efficiency, Robustness and Accuracy in picky Chart Parsing

  1992cited by this paper
• Inside-Outside Reestimation From Partially Bracketed Corpora

  1992cited by this paper
• Applications of stochastic context-free grammars using the Inside-Outside algorithm

  1990cited by this paper
• Trainable grammars for speech recognition

  1979cited by this paper

• Deep networks learn to parse uniform-depth context-free languages from local statistics

  2026cites this paper
• The Potential of Unsupervised Induction of Harmonic Syntax for Jazz

  2025cites this paper
• Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms

  2025cites this paper
• An L* Algorithm for Deterministic Weighted Regular Languages

  2024cites this paper
• Generating Diverse and High-Quality Texts by Minimum Bayes Risk Decoding

  2024cites this paper
• Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding

  2024cites this paper
• Model-Based Minimum Bayes Risk Decoding for Text Generation

  2023cites this paper
• Do Transformers Parse while Predicting the Masked Word?

  2023cites this paper
• Solving Tensor Low Cycle Rank Approximation

  2023cites this paper
• Epsilon Sampling Rocks: Investigating Sampling Strategies for Minimum Bayes Risk Decoding for Machine Translation

  2023cites this paper
• Follow the Wisdom of the Crowd: Effective Text Generation via Minimum Bayes Risk Decoding

  2022cites this paper
• Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

  2022cites this paper
• Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

  2022cites this paper
• Sampling-Based Approximations to Minimum Bayes Risk Decoding for Neural Machine Translation

  2021cites this paper
• Co-training an Unsupervised Constituency Parser with Weak Supervision

  2021cites this paper
• Sampling-Based Minimum Bayes Risk Decoding for Neural Machine Translation

  2021cites this paper
• PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols

  2021cites this paper
• Minimum Bayes Risk Decoding with Neural Metrics of Translation Quality

  2021cites this paper
• High Quality Rather than High Model Probability: Minimum Bayes Risk Decoding with Neural Metrics

  2021cites this paper
• A Joint Model for Document Segmentation and Segment Labeling

  2020cites this paper
• Thesis Proposal

  2020cites this paper
• Max-Margin Incremental CCG Parsing

  2020cites this paper
• Bayesian Analysis in Natural Language Processing, Second Edition

  2019cites this paper
• Iterative Search for Weakly Supervised Semantic Parsing

  2019influential citation
• A survey of 25 years of evaluation

  2019cites this paper
• Connecting Documents, Words, and Languages Using Topic Models

  2019cites this paper
• Bayesian Learning for Neural Dependency Parsing

  2019influential citation
• Monte Carlo Syntax Marginals for Exploring and Using Dependency Parses

  2018cites this paper
• Automatic Rule Learning for Autonomous Driving Using Semantic Memory

  2018cites this paper
• Policy Gradient as a Proxy for Dynamic Oracles in Constituency Parsing

  2018cites this paper
• Latent-Variable PCFGs: Background and Applications

  2017cites this paper
• Adapting Topic Models using Lexical Associations with Tree Priors

  2017cites this paper
• Expected F-Measure Training for Shift-Reduce Parsing with Recurrent Neural Networks

  2016influential citation
• Bayesian Analysis in Natural Language Processing

  2016cites this paper
• A tensor perspective on weighted automata, low-rank regression and algebraic mixtures

  2016cites this paper
• LSTM Shift-Reduce CCG Parsing

  2016cites this paper
• Weighted Tree Automata Approximation by Singular Value Truncation

  2015cites this paper
• Learning with Joint Inference and Latent Linguistic Structure in Graphical Models

  2015cites this paper
• Structured Prediction of Sequences and Trees Using Infinite Contexts

  2015cites this paper
• Refinements in Syntactic Parsing

  2015influential citation
• A statistical model for grammar mapping

  2015cites this paper
• Explorer Approximate PCFG Parsing Using Tensor Decomposition

  2015cites this paper
• Low-Rank Approximation of Weighted Tree Automata

  2015cites this paper
• Posterior calibration and exploratory analysis for natural language processing models

  2015cites this paper
• Diversity in Spectral Learning for Natural Language Parsing

  2015cites this paper
• Decoder Integration and Expected BLEU Training for Recurrent Neural Network Language Models

  2014cites this paper
• Sparser, Better, Faster GPU Parsing

  2014influential citation
• Empirical Evaluation of Tree distances for Parser Evaluation

  2014influential citation
• Spectral learning of latent-variable PCFGs: algorithms and sample complexity

  2014cites this paper
• Efficient Latent-variable Grammars : Learning and Inference

  2014influential citation
• Proposal Context Awareness and Personalization in Dialogue Planning

  2014cites this paper
• Head of Delegation

  2014cites this paper
• Structured Learning for Taxonomy Induction with Belief Propagation

  2014cites this paper
• Spectral learning of weighted automata

  2014cites this paper
• Data-oriented Parsing

  2013cites this paper
• Viterbi training in PRISM

  2013cites this paper
• Incremental Tree Substitution Grammar for Parsing and Sentence Prediction

  2013cites this paper
• Approximate PCFG Parsing Using Tensor Decomposition

  2013cites this paper
• Surface Web Semantics for Structured Natural Language Processing

  2013cites this paper
• Explorer Approximate PCFG Parsing Using Tensor Decomposition

  2013cites this paper
• Spectral Learning Algorithms for Natural Language Processing

  2013cites this paper
• Bayesian Tree Substitution Grammars as a Usage-based Approach

  2013cites this paper
• Detecting grammatical errors with treebank-induced, probabilistic parsers

  2012influential citation
• Training Factored PCFGs with Expectation Propagation

  2012cites this paper
• Spectral Learning of Latent-Variable PCFGs

  2012cites this paper
• Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

  2012cites this paper
• Spectral Learning for Non-Deterministic Dependency Parsing

  2012cites this paper
• An All-Fragments Grammar for Simple and Accurate Parsing

  2012influential citation
• Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

  2012cites this paper
• Parsing TCT with a Coarse-to-fine Approach

  2012cites this paper
• Improving NLP through Marginalization of Hidden Syntactic Structure

  2012cites this paper
• Contrasting objective functions for CYK chart decoding

  2012cites this paper
• Integrated Supertagging and Parsing

  2012cites this paper
• The Surprising Variance in Shortest-Derivation Parsing

  2011cites this paper
• Coarse-to-Fine Natural Language Processing

  2011cites this paper
• Training a Log-Linear Parser with Loss Functions via Softmax-Margin

  2011cites this paper
• A Discriminative Model for Joint Morphological Disambiguation and Dependency Parsing

  2011cites this paper
• Parsing Chinese by optimal contributive paths

  2011cites this paper
• A statistical confidence measure framework for probabilistic parsing

  2011influential citation
• Earley Parsers with Contributive Paths

  2011cites this paper
• Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization

  2010cites this paper
• Variational Inference for Adaptor Grammars

  2010cites this paper
• Unsupervised Syntactic Alignment with Inversion Transduction Grammars

  2010cites this paper
• Combinatory Categorial Grammar Parsing With One Structure Per n-gram

  2010cites this paper
• Statistical parsing of noun phrase structure

  2010cites this paper
• Simple, Accurate Parsing with an All-Fragments Grammar

  2010cites this paper
• Products of Random Latent Variable Grammars

  2010cites this paper
• Syntax-based language models for statistical machine translation

  2010cites this paper
• Discriminative Modeling of Extraction Sets for Machine Translation

  2010cites this paper
• Phrase Alignment Models for Statistical Machine Translation

  2010cites this paper
• Formalizing the Use and Characteristics of Constraints in Pipeline Systems

  2010cites this paper
• A U-DOP approach to modeling language acquisition

  2010cites this paper
• Shared Logistic Normal Distributions for Soft Parameter Tying in Unsupervised Grammar Induction

  2009cites this paper
• Fast Consensus Decoding over Translation Forests

  2009cites this paper
• Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs

  2009cites this paper
• Statistical Confidence Measures for Probabilistic Parsing

  2009cites this paper
• Asynchronous Binarization for Synchronous Grammars

  2009cites this paper
• Parsing German with Latent Variable Grammars

  2008cites this paper
• Exploiting non-linear probabilistic models in natural language parsing and reranking

  2008influential citation
• The Shared Logistic Normal Distribution for Grammar Induction

  2008cites this paper