Accurate max-margin training for structured output spaces

Sunita Sarawagi, Rahul GuptaICML 2008 · OpenReview

Introduction

Structured prediction tasks—such as sequence labeling, image segmentation, or dependency parsing—require predicting complex, interdependent outputs. Training these models often relies on the "max-margin" framework, which ensures the score of the correct answer is higher than any incorrect answer by a specified margin.

Traditionally, there are two ways to achieve this:

  1. Margin Scaling: Popular due to its computational efficiency (using standard MAP inference), but it is sensitive to the scale of the error function and often over-emphasizes outliers with massive errors.
  2. Slack Scaling: Theoretically superior because it is scale-invariant and focuses on labelings near the decision boundary. However, it is rarely used because its inference step is computationally difficult and incompatible with standard algorithms.

This paper bridges this gap by making slack-like training efficient and proposing a more granular approach to handling errors in structured spaces, introducing a novel framework called PosLearn.

Methodological Innovations

The authors make two primary technical contributions to improve max-margin training:

1. Approximate Slack Scaling

The authors derive a variational upper bound for the notoriously difficult slack scaling objective. This mathematical maneuver allows them to solve the "hard" inference problem using a simple line search over standard, "easy" loss-augmented MAP inference calls. This approximation retains the accuracy advantages of slack scaling without the computational bottleneck.

2. PosLearn (The Position Learner)

PosLearn is the paper's core innovation. Traditional methods define loss based on a single "most violating" labeling for an entire instance. PosLearn argues this global perspective is insufficient. Instead, it associates a different slack variable with every position in a decomposable loss function (e.g., every node in a Markov chain).

  • The Logic: If a sentence has three errors, PosLearn ensures the model learns from all three positions simultaneously, rather than just the single "worst" global labeling.
  • Efficiency: For many models, finding these violators only takes about twice the time of a single MAP inference, making it highly practical.

Key Insights and Performance

The authors evaluated their methods across three distinct structured tasks: sequence labeling (Cora, Address, CoNLL’03), text segmentation, and unlabeled dependency parsing (Danish, Dutch, Swedish).

Error rates across different training percentages

Accuracy Gains and Speedups

PosLearn consistently outperformed margin scaling. As shown in the evaluations, it reduced test error by up to 25% on sequence labeling tasks and 7-10% on segmentation.

Comprehensive error and F1 scores across tasks

Counter-intuitively, PosLearn is often faster to train than margin scaling. Even though it generates more constraints, it finds "useful" constraints much earlier in the process. Margin scaling often wastes iterations trying to separate high-loss labelings that are already far enough from the margin. On the Cora dataset, PosLearn was up to 5x faster than standard margin scaling.

Furthermore, the "ApproxSlack" method performed nearly identically to exact slack scaling, proving that the variational approximation is a robust, efficient alternative for researchers who want the benefits of slack scaling without the computational headache.

The "Most Violating" Fallacy

Standard max-margin training is bottlenecked by looking at only one incorrect labeling at a time. PosLearn’s "per-position" approach provides a much richer gradient for the optimizer, leading to better models. Because slack-based methods (including PosLearn) are invariant to the scaling of the error function, they are also much easier to tune.

Limitations and Future Work

The authors noted that PosLearn provides the biggest gains when features strongly couple multiple variables (like edge features in a Conditional Random Field). In tasks like dependency parsing, where features and errors decompose in the exact same way, the benefits of PosLearn were negligible.

While the empirical results are strong, a formal theoretical analysis of PosLearn’s generalization bounds compared to standard slack or margin scaling remains an open and compelling direction for future research.

Summary updated

Abstract

Tsochantaridis et al. (2005) proposed two formulations for maximum margin training of structured spaces: margin scaling and slack scaling. While margin scaling has been extensively used since it requires the same kind of MAP inference as normal structured prediction, slack scaling is believed to be more accurate and better-behaved. We present an efficient variational approximation to the slack scaling method that solves its inference bottleneck while retaining its accuracy advantage over margin scaling. We further argue that existing scaling approaches do not separate the true labeling comprehensively while generating violating constraints. We propose a new max-margin trainer PosLearn that generates violators to ensure separation at each position of a decomposable loss function. Empirical results on real datasets illustrate that PosLearn can reduce test error by up to 25% over margin scaling and 10% over slack scaling. Further, PosLearn violators can be generated more efficiently than slack violators; for many structured tasks the time required is just twice that of MAP inference.
BibTeX
@inproceedings{sarawagi2008accurate,
  author = {Sunita Sarawagi and Rahul Gupta},
  title = {{Accurate max-margin training for structured output spaces}},
  booktitle = {International Conference on Machine Learning},
  year = {2008},
  url = {https://openreview.net/forum?id=S1VFjjbOZS},
}

Loading related content...

Figure