Advances in Using Grammars with Latent Annotations for Discontinuous Parsing

Kilian GebhardtACL 2020

TL;DR

This paper explores how to improve discontinuous parsing, a challenging task in natural language processing, by adapting techniques from probabilistic grammars with latent annotations. The authors find that using a Maximum-a-Posteriori (MAP) objective and ensemble models can boost accuracy, though they still lag behind modern neural network approaches.

What Problem Does This Paper Address?

Parsing, the process of analyzing the grammatical structure of a sentence, is fundamental to many Natural Language Processing (NLP) tasks. While context-free grammars (CFGs) are a common tool, they struggle with languages like German, which exhibit discontinuous constituents – phrases whose words don't form a contiguous block. To handle this, more expressive grammar formalisms like Linear Context-Free Rewriting Systems (LCFRS) and hybrid grammars have been developed. However, these formalisms often face challenges: they can be computationally expensive, and their accuracy doesn't always match simpler, continuous parsing methods.

This paper builds upon prior work that introduced latent annotations to these discontinuous grammar formalisms, aiming to improve their accuracy. The authors identify specific limitations in previous approaches, such as the potential for overfitting with a likelihood-based training objective and the lack of exploration of ensemble methods. They also question whether the initial choice of nonterminal labels significantly impacts the refinement process.

Methods

The core of this work involves applying and extending techniques from Probabilistic Context-Free Grammars with Latent Annotations (PCFG-LA) to discontinuous parsing formalisms: LCFRS and hybrid grammars.

Key methodological contributions include:

  • Maximum-a-Posteriori (MAP) Objective: Instead of solely relying on a likelihood-based objective during the Expectation-Maximization (EM) training of the split/merge algorithm, the authors incorporate a Dirichlet prior. This shifts the objective towards a MAP estimation, which is hypothesized to reduce overfitting.
  • Ensemble Models: Inspired by successful applications in continuous parsing, the researchers train multiple grammars with different random seeds and combine their predictions. This is done by averaging weights in a "max-rule-product" approach during parsing.
  • New Nonterminal Naming Scheme: To address the potential issue of initial nonterminal granularity, a "strict-Markov" labeling scheme is proposed for hybrid grammars. This scheme aims to find a better trade-off between the expressiveness of strict labeling and the potential for too many nonterminals in child labeling.
  • Split/Merge Refinement: The baseline grammars are refined using a variant of the split/merge algorithm, which adaptively refines the grammar's nonterminals. This process is applied with both the standard likelihood-based objective and the newly proposed MAP objective.
  • Max-Rule-Product (mrp) Parsing: For parsing unseen sentences, an approximate tractable objective called "max-rule-product" is used. This projects weights from the refined grammar to a sentence-specific coarse grammar and finds the most probable derivation.

Datasets

The experiments were conducted on two well-known German treebank corpora:

  • TIGER: Used with the SPMRL split and the HN08 split. Hyperparameters were optimized solely on the HN08 split.
  • NEGRA: Used with the split by Dubey and Keller (2003).

Key Insights and Ideas

  • MAP Training Helps: The MAP objective generally leads to improved accuracy compared to the likelihood-based objective, particularly for non-ensemble grammars. This suggests that controlling overfitting is crucial for discontinuous parsing.
  • Ensembles are Powerful: Ensemble models consistently outperform individual grammars, often by a significant margin, indicating that combining multiple perspectives is highly beneficial.
  • Nonterminal Granularity Matters: The choice of nonterminal labeling scheme for hybrid grammars has a notable impact. The "strict-Markov" scheme, which balances expressiveness and nonterminal count, performs well, outperforming LCFRS on the TIGER corpus. However, on the smaller NEGRA corpus, the "child" labeling scheme proves more effective, possibly due to reduced sparsity issues.
  • Grammar Formalism Choice is Key: The experiments reinforce that the choice of grammar formalism (LCFRS vs. hybrid) and the extraction algorithm are not rendered redundant by the split/merge refinement process.

Key Results

  • Accuracy Improvements: The proposed methods (MAP objective and ensemble models) lead to improved F1 scores on both the TIGER and NEGRA corpora. For instance, ensemble hybrid grammars achieve F1 scores in the low 80s on NEGRA and high 70s on TIGER.
  • Hybrid Grammars Competitive: Hybrid grammars with the Markovized strict labeling scheme outperform LCFRS on the HN08 dataset, contradicting previous findings.
  • Comparison to Prior Work: The ensemble of hybrid grammars performs competitively with other grammar-based approaches but is still outperformed by recent neural network models.

Limitations and Future Work

  • Neural Network Gap: The authors acknowledge that their models, while improved, do not reach the performance levels of recent discriminative parsers, particularly those utilizing neural networks.
  • Uncertainty in MAP Impact: While MAP training generally improves accuracy, the authors note that for ensemble models, there are cases where the MAP objective leads to slightly lower accuracy. They suggest that a larger sample size might be needed to reliably assess the influence of MAP training on discontinuous F1.
  • Future Directions: The paper suggests extending research to spectral algorithms for discontinuous parsing, which have been applied to related tasks but not yet to discontinuous syntactic parsing. They also propose further controlled experiments to investigate the impact of different grammar formalisms and extraction algorithms.

Summary updated

BibTeX
@inproceedings{gebhardt2020advances,
  author = {Kilian Gebhardt},
  title = {{Advances in Using Grammars with Latent Annotations for Discontinuous Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
}
Figure