A Consistent Regularization Approach for Structured Prediction

Carlo Ciliberto, Lorenzo Rosasco, Alessandro Rudi

Introduction

Structured prediction involves predicting outputs with internal dependencies, such as sequences in natural language, graphs in chemistry, or pixel grids in images. Unlike simple binary classification, the "correctness" of a prediction isn't just a binary yes/no; it’s measured by complex loss functions like edit distance or ranking error.

Historically, researchers had to develop ad-hoc algorithms and theoretical proofs for every new type of structured output. While methods like SVMstruct are popular, they often lack general "universal consistency" guarantees—the mathematical promise that with enough data, the algorithm will eventually find the best possible predictor. This paper introduces a unified, "loss-agnostic" regularization framework for structured prediction that works across a vast range of loss functions, providing the first general proof of universal consistency for such a broad class of structured problems.

The "Loss Trick" and Two-Step Algorithm

The authors propose a two-step algorithm based on a surrogate loss approach. By embedding structured outputs into a linear Hilbert space, they transform complex prediction tasks into a manageable multi-output ridge regression problem.

  1. The "Loss Trick": They identify a massive class of loss functions ($\Delta$) that can be decomposed into an inner product in a Hilbert space. Crucially, you don't need to explicitly know the complex mapping into this space. As long as you can calculate the loss between two points, you can use the "loss trick" (analogous to the kernel trick in SVMs).
  2. Step 1: Learning (Ridge Regression): The algorithm first solves a standard kernel ridge regression to compute a set of input-dependent weights ($\alpha_i(x)$). This essentially learns how much each training example should influence the prediction for a new input $x$.
  3. Step 2: Prediction (Decoding): To make a prediction, the algorithm finds the output $y$ that minimizes the weighted sum of losses against the training labels: $$\hat{f}(x) = \text{argmin}_{y \in \mathcal{Y}} \sum_{i=1}^n \alpha_i(x) \Delta(y, y_i)$$

This approach turns a complex structured problem into a vector-valued regression problem, decoupling the "learning" from the "structure". The learning step doesn't care about the structure of the output; the structure is only handled during the final decoding (argmin) step.

Key Results across Domains

The authors evaluated their approach on three distinct types of problems, demonstrating its versatility and strong performance.

1. Ranking (MovieLens) The goal was to predict a user's movie preferences (an ordering of 1,682 movies). The proposed algorithm ("Alg. 1") achieved a normalized rank loss of 0.396, significantly outperforming SVMstruct (0.451) and other surrogate methods.

Rank loss comparison on the MovieLens dataset.

2. Robust Estimation (Simulated Data) They tested the algorithm's ability to handle heavy outliers by using the non-convex Cauchy loss function. In the presence of outliers, their method significantly outperformed standard Kernel Ridge Regression (KRR). As the sample size increased to $n=1000$, Alg. 1's error dropped to 0.07, compared to KRR's 0.19.

Robust estimation performance comparing Alg. 1, RNW, and KRR in the presence of outliers.

3. Image Reconstruction (USPS Digits) The task was to predict the bottom half of a digit image given the top half. By treating the image as a histogram and using the Hellinger distance (which their framework naturally accommodates), they achieved better digit recognition on reconstructed images (Error: 0.193) compared to standard Kernel Dependency Estimation (Error: 0.294).

Limitations and Future Work

While the framework provides the "holy grail" of universal consistency, it has practical limitations. The primary bottleneck is the prediction step: solving an argmin over a complex output space $\mathcal{Y}$ (like rankings) is often NP-hard, requiring approximation heuristics.

Additionally, while universal consistency is guaranteed, the authors note that the "speed" of convergence (generalization bounds) could be improved by applying more specific conditions. Future work may explore alternative surrogate frameworks, such as those used in multi-task learning, to achieve tighter bounds or more efficient computation.

Summary updated

Abstract

We propose and analyze a regularization approach for structured prediction problems. We characterize a large class of loss functions that allows to naturally embed structured outputs in a linear space. We exploit this fact to design learning algorithms using a surrogate loss approach and regularization techniques. We prove universal consistency and finite sample bounds characterizing the generalization properties of the proposed method. Experimental results are provided to demonstrate the practical usefulness of the proposed approach.
BibTeX
@inproceedings{ciliberto2016consistent,
  author = {Carlo Ciliberto and Lorenzo Rosasco and Alessandro Rudi},
  title = {{A Consistent Regularization Approach for Structured Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=SkELuv-uWH},
}
Figure