Structured prediction by joint kernel support estimation

Christoph H. Lampert, Matthew B. BlaschkoMachine Learning 2009 · DOI · OpenReview

Introduction

Structured prediction is a cornerstone of modern machine learning, tasked with predicting complex, interdependent outputs such as sequences, trees, or bounding boxes. Traditionally, this field has been dominated by discriminative models, most notably Conditional Random Fields (CRFs) and Structured Support Vector Machines (S-SVMs). While these models are powerful, they suffer from two significant drawbacks: extreme sensitivity to label noise and high computational costs during training.

This paper introduces Joint Kernel Support Estimation (JKSE), a method that reimagines structured prediction through the lens of one-class classification. By modeling the support of the joint probability distribution of inputs and labels rather than the full conditional density, JKSE provides a framework that is both exceptionally robust to corrupted training data and significantly faster to train than its discriminative counterparts.

The Limitations of Discriminative Structured Prediction

Discriminative models like S-SVMs operate by enforcing a margin between the ground truth label and all other possible labels in the output space. This approach leads to two primary "pain points":

  1. Sensitivity to Noise: Because S-SVMs try to strictly separate the correct label from the rest, even a small amount of label noise (incorrect ground truth) can cause the model to attempt to learn incorrect boundaries, leading to a collapse in generalization performance.
  2. Computational Complexity: Training S-SVMs is often an iterative process where each step requires an "inference" call—finding the most violating label in a potentially exponential output space. This makes training prohibitively slow for complex tasks.

Methodology: Support Estimation in the RKHS

JKSE sidesteps these issues by shifting the focus from classification to support estimation. Instead of modeling $p(y|x)$, the authors treat pairs of inputs and labels $(x, y)$ as points in a joint Reproducing Kernel Hilbert Space (RKHS).

One-Class SVM Adaptation

The core of JKSE is an adaptation of the one-class SVM. The model seeks to find a hyperplane in the RKHS that separates the "valid" $(x, y)$ pairs from the origin. This formulation results in a convex optimization problem, ensuring a globally optimal solution.

Decoupled Training and the $\nu$-Parameter

Unlike S-SVMs, JKSE does not require an inference step during training. The complexity of the training phase depends solely on the number of training samples ($n$), making it independent of the size of the label space. Furthermore, the model incorporates a parameter $\nu$, which serves as an upper bound on the fraction of outliers. This allows the model to automatically "ignore" noisy or incorrectly labeled examples, treating them as points outside the estimated support.

Experimental Evaluation

The authors evaluated JKSE on two distinct structured prediction tasks to test its limits and robustness.

UIUC Car Dataset (Object Localization)

In this task, the goal is to predict a bounding box ($y$) for a car within an image ($x$). To test robustness, the authors artificially introduced noise by "scrambling" labels—swapping bounding boxes between unrelated images.

  • Robustness: JKSE demonstrated remarkable resilience. Even with 90% of the training labels scrambled, the model maintained non-trivial performance. In contrast, S-SVM performance dropped to near-random levels once noise exceeded 50%.
  • Accuracy and Speed: Using a non-linear $\chi^2$ kernel, JKSE achieved an 8% equal-error rate (EER), significantly outperforming the linear S-SVM (18%). Crucially, JKSE trained in a matter of seconds, while the S-SVM required approximately five hours.

OCR Sequence Labeling

The second task involved handwritten word recognition, predicting a sequence of letters from image features. Here, JKSE encountered a significant hurdle, resulting in an 88.3% error rate.

Discussion: The "Distinctive" Assumption

The failure in the OCR task provides a critical insight into the requirements of JKSE. The method relies on the distinctive assumption: for a given $x$, the joint probability $p(x, y)$ must be significantly higher for the correct $y$ than for any incorrect $y$.

In the OCR task, the standard sequence kernels used did not satisfy this assumption. These kernels assigned high similarity scores to many incorrect labels, causing the estimated support to be too "blurry" to distinguish the correct sequence. This highlights that while JKSE is powerful, its success is heavily dependent on the design of joint kernels that can sharply isolate correct labels in the feature space.

Conclusion

Joint Kernel Support Estimation offers a compelling alternative to traditional structured prediction models, particularly in domains where training data is noisy or computational resources are limited. By focusing on the support of the joint distribution, JKSE achieves superior robustness and training efficiency. Future research will likely focus on developing specialized joint kernels that better satisfy the distinctive assumption, potentially expanding the applicability of support estimation to a wider array of complex structured tasks.

Summary updated

Abstract

Discriminative techniques, such as conditional random fields (CRFs) or structure aware maximum-margin techniques (maximum margin Markov networks (M3N), structured output support vector machines (S-SVM)), are state-of-the-art in the prediction of structured data. However, to achieve good results these techniques require complete and reliable ground truth, which is not always available in realistic problems. Furthermore, training either CRFs or margin-based techniques is computationally costly, because the runtime of current training methods depends not only on the size of the training set but also on properties of the output space to which the training samples are assigned. We propose an alternative model for structured output prediction, Joint Kernel Support Estimation (JKSE), which is rather generative in nature as it relies on estimating the joint probability density of samples and labels in the training set. This makes it tolerant against incomplete or incorrect labels and also opens the possibility of learning in situations where more than one output label can be considered correct. At the same time, we avoid typical problems of generative models as we do not attempt to learn the full joint probability distribution, but we model only its support in a joint reproducing kernel Hilbert space. As a consequence, JKSE training is possible by an adaption of the classical one-class SVM procedure. The resulting optimization problem is convex and efficiently solvable even with tens of thousands of training examples. A particular advantage of JKSE is that the training speed depends only on the size of the training set, and not on the total size of the label space. No inference step during training is required (as M3N and S-SVM would) nor do we have calculate a partition function (as CRFs do). Experiments on realistic data show that, for suitable kernel functions, our method works efficiently and robustly in situations that discriminative techniques have problems with or that are computationally infeasible for them.
BibTeX
@article{lampert2009structured,
  author = {Christoph H. Lampert and Matthew B. Blaschko},
  title = {{Structured prediction by joint kernel support estimation}},
  journal = {Machine Learning},
  year = {2009},
  doi = {10.1007/s10994-009-5111-0},
}
Figure