Accelerated Training of Maximum Margin Markov Models for Sequence Labeling: A Case Study of NP Chunking

Xiaofeng Yu, Wai LamCOLING 2010 · OpenReview

Abstract

Maximum Margin Markov Networks ($M^3N$) offer a powerful framework for sequence labeling, combining the benefits of margin-based learning with the ability to capture complex dependencies through kernels. However, their adoption has been hindered by the high computational cost of traditional optimization methods like Structured Sequential Minimal Optimization (SMO). This paper proposes an efficient training approach using Stochastic Gradient Descent (SGD) accelerated by Stochastic Meta-Descent (SMD). Evaluated on the CoNLL 2000 Noun Phrase (NP) chunking task, the proposed method achieves state-of-the-art accuracy while delivering training speeds over 13 times faster than standard SMO-based approaches.

Introduction

Sequence labeling is a fundamental task in Natural Language Processing (NLP), essential for applications such as part-of-speech tagging and named entity recognition. While Conditional Random Fields (CRFs) are widely used, $M^3N$ models provide a compelling alternative due to their margin-maximizing properties and kernel-based flexibility. Despite these advantages, the standard training process for $M^3N$ involves solving a complex Quadratic Programming (QP) problem with an exponential number of constraints, making it difficult to scale to large datasets. This study addresses this scalability bottleneck by reformulating the $M^3N$ objective for optimization via Stochastic Gradient Descent.

Methodology

To overcome the limitations of batch optimization, the authors re-cast the $M^3N$ objective as a convex unconstrained optimization problem using a variant of the hinge loss.

Stochastic Meta-Descent (SMD)

To further accelerate convergence, the authors employ Stochastic Meta-Descent (SMD). SMD adaptively adjusts the learning rate for each parameter by utilizing second-order information. Crucially, this is achieved without the prohibitive cost of computing a full Hessian matrix, instead using efficient forward-mode algorithmic differentiation to calculate Hessian-vector products. This allows the optimizer to adapt to the local curvature of the loss surface.

Kernel Integration

The model retains the ability to utilize various kernels—including linear, polynomial, and neural kernels—to capture non-linear feature interactions. This flexibility is vital for achieving high predictive performance in complex NLP tasks.

Convergence of the objective function for different kernels: (a) linear, (b) neural, and (c) quadratic. SGD (red) consistently reaches the optimal value faster than structured SMO (green).

Experimental Results

The approach was evaluated on the CoNLL 2000 shared task for NP chunking, using a training set of 8,936 sentences.

Convergence and Speed

As shown in the convergence plots, SGD reaches a stable, low-error state significantly earlier than structured SMO across all kernel types. For a linear kernel, SGD completed training in just 89 seconds, compared to 1,176 seconds for SMO—a speedup of over 13x. This efficiency is particularly notable as the cost per update in SGD is independent of the total dataset size, facilitating better scaling for large-scale NLP applications.

Predictive Accuracy

The $M^3N$ model trained with SGD achieved an F1-score of 94.69%, outperforming the standard CRF baseline of 94.32%. The results indicate that the use of non-linear kernels, such as the quadratic kernel, provides a tangible boost in labeling accuracy by capturing complex feature correlations.

Performance comparison: (a) F-measure vs. training size and (b) Training time vs. training size for various kernels and CRFs.

Conclusion

This research demonstrates that Stochastic Gradient Descent is not merely an approximation but a superior optimization strategy for $M^3N$ models in sequence labeling. By significantly reducing training time without sacrificing accuracy, this method makes high-performance margin-based models viable for large-scale, real-world NLP tasks. Future work will explore the application of this framework to other sequence labeling challenges such as Named Entity Recognition and Part-of-Speech tagging.

Summary updated

BibTeX
@inproceedings{yu2010accelerated,
  author = {Xiaofeng Yu and Wai Lam},
  title = {{Accelerated Training of Maximum Margin Markov Models for Sequence Labeling: A Case Study of NP Chunking}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=iFLsVSRzxB},
}
Figure