Softmax-Margin CRFs: Training Log-Linear Models with Cost Functions

Kevin Gimpel, Noah A. SmithNAACL 2010 · OpenReview

TL;DR

This paper introduces "softmax-margin," a novel training objective for structured prediction models that effectively incorporates task-specific cost functions. This method offers a convex, differentiable, and probabilistic approach that improves upon standard conditional log-likelihood training and offers a principled way to optimize for evaluation metrics beyond simple accuracy.

What Problem Does This Paper Address?

Many natural language processing tasks, like named-entity recognition (NER), involve predicting structured outputs (e.g., sequences of labels for a sentence). Conditional Log-Likelihood (CLL) is a common training criterion for these models, but it optimizes for the probability of the correct output, not necessarily for a task-specific evaluation metric like F1-score. This means a model trained with CLL might not perform optimally according to the desired evaluation. While other methods like max-margin and risk minimization can incorporate cost functions, they often suffer from non-convexity or lack a probabilistic interpretation. The authors aim to bridge this gap by developing a training method that is convex, probabilistic, and directly optimizes for task-specific costs.

Methods

The core contribution is the "softmax-margin" training objective. This objective can be seen as a generalization of both CLL and max-margin learning. The key idea is to modify the standard log-linear model's exponentiated score by adding a "cost-augmented" term. Specifically, instead of just maximizing the probability of the correct output, it encourages higher scores for outputs that have a lower cost relative to the true output.

The authors show that softmax-margin:

  • Is a convex optimization problem, making it easier to train reliably.
  • Is differentiable, allowing for efficient gradient-based optimization.
  • Provides a probabilistic interpretation, similar to CLL.
  • Bounds the "risk" (expected cost) of the model, offering a principled way to optimize for evaluation metrics.
  • Can be implemented efficiently by adding "cost features" to existing CLL training frameworks with minimal changes.

They also introduce a "Jensen risk bound" (JRB) as a computationally cheaper alternative that also bounds risk.

Datasets

The experiments were conducted on the English data from the CoNLL 2003 shared task for Named-Entity Recognition (NER). This dataset consists of news articles annotated with four entity types: person, location, organization, and miscellaneous. No new datasets were introduced.

Key Insights and Ideas

  • Bridging the Gap: Softmax-margin successfully bridges the gap between probabilistic models (like CRFs trained with CLL) and models optimized for specific evaluation metrics (like those using cost functions).
  • Convexity is Key: The convexity of the softmax-margin objective is a significant advantage, ensuring reliable convergence during training, unlike some other cost-sensitive methods.
  • Probabilistic Interpretation: Maintaining a probabilistic interpretation is valuable for tasks where understanding the confidence or distribution of predictions is important.
  • Efficient Implementation: The ability to integrate softmax-margin into existing CLL frameworks with minor modifications makes it practical for researchers and practitioners.
  • Jensen Risk Bound: The JRB offers a compelling alternative for those prioritizing training speed while still benefiting from risk bounding.

Key Results

The paper demonstrates that softmax-margin training achieves statistically significant improvements in F1-score for Named-Entity Recognition compared to standard CLL and max-margin training. Specifically, on the CoNLL 2003 test set, softmax-margin achieved an F1-score of 85.84, which was statistically indistinguishable from MIRA and the Jensen risk bound (85.72 and 85.65 respectively), but significantly better than CLL (85.46), max-margin (85.28), and the perceptron (83.98). The Jensen risk bound performed comparably to risk minimization but trained roughly half as fast.

Limitations and Future Work

The primary limitation acknowledged is that all the discussed approaches, including softmax-margin, currently only support cost functions that "factor" in the same way as the model's features. This means complex, non-local cost functions might not be directly applicable. The authors suggest that future work could explore approximate inference techniques to handle more expressive cost functions.

Summary updated

Abstract

We describe a method of incorporating task-specific cost functions into standard conditional log-likelihood (CLL) training of linear structured prediction models. Recently introduced in the speech recognition community, we describe the method generally for structured models, highlight connections to CLL and max-margin learning for structured prediction (Taskar et al., 2003), and show that the method optimizes a bound on risk. The approach is simple, efficient, and easy to implement, requiring very little change to an existing CLL implementation. We present experimental results comparing with several commonly-used methods for training structured predictors for named-entity recognition.
BibTeX
@inproceedings{gimpel2010softmax,
  author = {Kevin Gimpel and Noah A. Smith},
  title = {{Softmax-Margin CRFs: Training Log-Linear Models with Cost Functions}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=B14zwXZuZB},
}
Figure