CMU at SemEval-2016 Task 8: Graph-based AMR Parsing with Infinite Ramp Loss

Jeffrey Flanigan, Chris Dyer, Noah A. Smith, Jaime G. CarbonellSemEval @ NAACL 2016 · DOI · OpenReview

TL;DR

This paper introduces "infinite ramp loss," a novel training objective for structured prediction models that effectively handles "unreachable" training examples, a common issue in tasks like AMR parsing. By generalizing existing structured SVM losses, this new method allows for more robust training, leading to significant improvements in AMR parsing performance.

What Problem Does This Paper Address?

The paper tackles a fundamental challenge in training machine learning models for complex structured prediction tasks, such as Abstract Meaning Representation (AMR) parsing. AMR aims to represent the meaning of a sentence as a graph, which is a complex structure. Training models for such tasks often relies on large datasets of sentence-AMR graph pairs. However, a common problem arises when the model, given a sentence, cannot produce the correct AMR graph from the training data, even with the best possible decoding. These are called "unreachable examples." This can happen due to imperfect training data, limitations in the model's decoding capabilities, or issues with the definition of the output space. Standard training methods, like structured SVMs, struggle with these unreachable examples, potentially leading to suboptimal performance. The authors specifically address this in the context of AMR parsing, where concept identification (identifying the nodes in the AMR graph) is a crucial step.

Methods

The core contribution of this paper is the infinite ramp loss, a new loss function for structured prediction. It's presented as a generalization of the structured SVM loss and the latent structured SVM loss. The infinite ramp loss is designed to handle unreachable training examples by introducing a mechanism that allows the model to learn even when the gold standard output is not directly producible by the decoder.

Key aspects of their approach include:

  • Concept Fragment Expansion: They augment the existing sources of candidate concept fragments (lexicon, named entities, time expressions) with five new sources:
  • Frame file lookup: Matching word lemmas to AMR frame files.
  • Lemma: Using the word's lemma directly.
  • Verb pass-through: Adding verb lemmas with a specific suffix.
  • Named entity pass-through: Creating concept fragments for named entities of varying lengths.
  • They also define a set of features for concept identification, including relative frequency estimates, span length, and concept fragment source.
  • Infinite Ramp Loss Formulation: The loss function is mathematically defined to generalize structured SVMs. It uses a limit of a term involving the maximum over possible outputs and costs. In practice, they use a very large number instead of the limit. This loss function is designed to provide a margin in the SVM loss and update the model away from errors, similar to existing methods, but crucially, it handles unreachable examples.
  • Training Procedure: They train the concept identification stage using the infinite ramp loss with the AdaGrad optimization algorithm. The training involves decoding with current parameters and a cost function, then computing a subgradient to update the parameters.

Datasets

  • LDC2015E86: This dataset is used for training and evaluation, following a recommended train/dev/test split. The authors report results on the test set of this dataset.
  • SemEval 2016 Task 8: This is the primary benchmark for their submission. They report performance on the test set for this task.

The paper notes that the AMR annotation scheme underwent changes between the production of the LDC2015E86 training data and the SemEval test set, which might explain some performance differences.

Key Insights and Ideas

  • Unreachable Examples are a Real Problem: The paper highlights that in complex structured prediction tasks, it's not uncommon for the training data to contain examples that the model, even with a perfect decoder, cannot generate. This is a significant hurdle for standard training methods.
  • Infinite Ramp Loss as a Solution: The proposed infinite ramp loss offers a principled way to address unreachable examples by generalizing existing successful loss functions. This allows the model to learn from all training data, not just the "reachable" subset.
  • Concept Coverage is Key: Expanding the sources for candidate concept fragments significantly improves concept coverage, which is crucial for accurate AMR parsing. This demonstrates the importance of feature engineering and data augmentation in this domain.
  • Trade-offs in Data Sources: The authors acknowledge the challenge of balancing the use of a training data lexicon with other external concept sources to prevent overfitting, suggesting that careful cross-validation strategies are necessary.

Key Results

  • On the LDC2015E86 test set, their improved parser achieves 67% F₁ Smatch, a substantial improvement over the JAMR baseline of 55% F₁ Smatch.
  • On the SemEval 2016 Task 8 test set, their improved parser achieves 56% F₁ Smatch.
  • The authors hypothesize that the lower performance on the SemEval test set compared to the LDC dataset might be due to drift in the AMR annotation scheme between the training and test data.

Limitations and Future Work

  • Convexity: Both the infinite ramp loss and ramp loss are noted as non-convex. However, the infinite ramp loss is convex if the arg min cost function is unique.
  • Performance Discrepancy: The performance on the SemEval 2016 Task 8 test set is lower than on the LDC2015E86 test set, which the authors attribute to changes in the AMR annotation scheme.
  • Future Work: The paper doesn't explicitly detail future work, but the success of the infinite ramp loss suggests its potential applicability to other structured prediction tasks facing similar "unreachable example" challenges. The expansion of concept sources also points towards continued exploration of richer feature sets and external knowledge integration.

Summary updated

BibTeX
@inproceedings{flanigan2016cmu,
  author = {Jeffrey Flanigan and Chris Dyer and Noah A. Smith and Jaime G. Carbonell},
  title = {{CMU at SemEval-2016 Task 8: Graph-based AMR Parsing with Infinite Ramp Loss}},
  booktitle = {SemEval @ NAACL},
  year = {2016},
  doi = {10.18653/v1/s16-1186},
}
Figure