Online Learning of Structured Predictors with Multiple Kernels

André Filipe Torres Martins, Noah A. Smith, Eric P. Xing, Pedro M. Q. Aguiar, Mário A. T. FigueiredoAISTATS 2011 · OpenReview

Introduction

Structured prediction involves tasks where the output is a complex object, such as a sequence or a tree. These tasks are computationally challenging because the output space is exponentially large. Traditionally, achieving high performance requires manual tuning of kernels or intensive feature selection. Multiple Kernel Learning (MKL) offers an automated alternative by learning the optimal combination of several base kernels. However, standard MKL algorithms are typically "wrapper-based," repeatedly solving a full batch learning problem in an inner loop, which is prohibitively slow for structured prediction.

This paper introduces SPOM (Structured Prediction by Online MKL), a fast and flexible algorithm that shifts from slow batch methods to an online proximal gradient scheme. SPOM learns model parameters and kernel combinations simultaneously, significantly reducing training times while maintaining or improving state-of-the-art accuracy.

Methodology: Structured Prediction by Online MKL (SPOM)

The core of the proposed approach is a general Online Proximal Gradient framework designed to handle composite regularizers. Unlike standard stochastic gradient descent (SGD), which can struggle with non-differentiable sparsity-promoting regularizers, SPOM utilizes proximal operators. This allows the algorithm to effectively zero out irrelevant feature groups or kernels.

SPOM achieves significantly faster convergence of the training objective compared to traditional wrapper-based MKL methods.

Key technical features include:

  • Proximal Steps: These steps enable the handling of non-smooth regularizers like Group-LASSO, allowing the model to "shrink" irrelevant components.
  • Block-Norm Regularization: The algorithm supports various sparsity patterns, facilitating both feature selection and sparse MKL.
  • Kernelization: The framework can be fully kernelized to handle high-dimensional or implicit feature spaces efficiently.
  • FOBOS Extension: The approach extends the Forward-Backward Splitting (FOBOS) scheme to handle multiple regularizers, improving upon previous regret bounds.

By interleaving gradient steps on the loss with proximal steps on the regularizer, SPOM eliminates the need for an expensive inner-loop solver, allowing for near-optimal learning in just a few passes over the data.

Experimental Setup

The authors evaluated SPOM on two primary benchmarks:

  1. Handwriting Recognition (OCR): A dataset of approximately 6,800 words (52,000 characters) where the task is to predict character sequences from binary images.
  2. Natural Language Dependency Parsing: Using the CoNLL-2008 dataset (approx. 39,000 sentences), this task involves predicting grammatical trees from a space of over 50 million potential feature templates.

Key Results and Discussion

SPOM demonstrates significant improvements in both speed and accuracy across the evaluated tasks.

Efficiency and Convergence

On the OCR task, SPOM reached near-optimal regions in just 20–30 passes over the data, whereas traditional wrapper-based methods like SimpleMKL required approximately 100 epochs. The stability of SPOM's convergence allows it to reach high-performance regions much faster than batch alternatives.

Predictive Performance

In handwriting recognition, the MKL approach achieved a test accuracy of 87.5%, significantly outperforming individual linear (71.8%), quadratic (85.5%), or Gaussian (84.1%) kernels. The ability to combine these kernels efficiently is central to the performance gain.

Test set accuracy vs. training runtime for various kernel combinations on the handwriting recognition task.

High-Dimensional Feature Selection

For dependency parsing, SPOM successfully managed a feature space of over 50 million features. It maintained a competitive accuracy of 90.67% UAS while automatically identifying and pruning irrelevant feature templates. This highlights MKL's role not just as a performance booster, but as a powerful tool for model interpretability and compactness.

Conclusion

SPOM provides a robust framework for online MKL in structured prediction. By avoiding the computational bottleneck of batch "wrapper" methods, it enables the use of complex kernel combinations on large-scale datasets. Future work may extend this framework to learning the structure of graphical models, such as automated edge selection in Markov Random Fields.

Summary updated

BibTeX
@inproceedings{martins2011online,
  author = {André Filipe Torres Martins and Noah A. Smith and Eric P. Xing and Pedro M. Q. Aguiar and Mário A. T. Figueiredo},
  title = {{Online Learning of Structured Predictors with Multiple Kernels}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=QBp180heESo},
}
Figure