Structured Prediction with Partial Labelling through the Infimum Loss

Vivien Cabannes, Alessandro Rudi, Francis R. Bach

Annotating datasets is one of the primary bottlenecks and costs in modern supervised machine learning. While researchers often assume the existence of perfectly labeled datasets, real-world supervision is frequently "weak" or "partial." This paper, originally presented at ICML 2020, proposes a unified framework for learning from partial labels using the infimum loss, offering an algorithm that is both easy to implement and backed by strong theoretical guarantees.

The Challenge of Partial Labels

In standard supervised learning, we assume every input $x$ has a single, correct label $y$. In reality, obtaining that exact label is expensive. It is often much cheaper to provide partial labels, where each example is associated with a set of possible labels rather than a single ground truth. For instance, instead of identifying a specific species of lily, an annotator might just label an image broadly as "flower." In a recommendation system, a user might provide a partial ordering of items ("I like A more than B") rather than a full, exhaustive ranking.

The core challenge is that most existing methods for handling these ambiguous labels are highly task-specific—built exclusively for classification or exclusively for ranking. Furthermore, many lack theoretical "consistency," meaning there is no mathematical guarantee they will converge to the true solution even given infinite data. This paper seeks a general framework that works across different loss functions and output spaces while maintaining strict mathematical rigor.

A Unified Framework: The Infimum Loss

The authors introduce a variational framework based on two key pillars:

  1. The Infimum Loss (IL): Instead of trying to guess which label in a candidate set $S$ is correct, the infimum loss takes an "optimistic" approach. It defines the loss for a prediction $z$ as the best-case scenario: $$L(z, S) = \inf_{y \in S} \ell(z, y)$$ Essentially, it measures the distance to the closest point in the candidate set.

  2. Structured Prediction via Kernels: To translate this theory into a practical algorithm, the authors utilize a structured prediction approach. They estimate the conditional distribution of labels using Kernel Ridge Regression. This allows them to compute weights for each training example that represent how much a new input $x$ "looks like" the training points.

The resulting algorithm is surprisingly elegant: to make a prediction for a new point, the model simply solves a weighted version of the infimum loss over the training set.

Key Insights and Theoretical Guarantees

A common baseline in partial label learning is the "Average Loss" (AC), which averages the loss over all possible labels in a candidate set. The authors demonstrate that AC is inherently biased. If the labeling process is "adversarial"—for instance, if the most common labels are the ones most likely to be hidden or corrupted in a set—averaging will lead the model astray. By contrast, the Infimum Loss, by being optimistic, is significantly more robust to these imbalances.

The paper also formalizes a "minimum variability principle." It proves that under a "non-ambiguity" condition (where the intersection of all possible label sets for a point eventually narrows down to the truth), the infimum loss is guaranteed to recover the original fully supervised solution. Because it is built on structured prediction, this unified theory applies whether you are predicting a category, a real number, or a complex permutation.

Experimental Results

The authors evaluated their framework across three distinct types of problems: classification, ranking, and partial regression.

  • Adversarial Robustness in Classification: Using the "dna" and "svmguide2" datasets, the authors simulated partial labeling by corrupting ground truth labels into sets. When corruption was non-uniform (targeting the most frequent labels), the Infimum Loss significantly outperformed the Average Loss baseline as the corruption level increased.
Performance comparison of Infimum Loss (IL) vs. Average Loss (AC) on the dna and svmguide2 datasets across varying corruption levels.
  • Superior Ranking: In synthetic ranking tasks where items are ordered based on underlying utility functions, the IL approach showed a clear performance gap over the baseline. It maintained lower error rates even when 80-90% of the pairwise comparisons were missing.
  • Solving the Phase Problem: In a synthetic 1D regression task where the model only knows the magnitude of a signal but not its sign (e.g., the label is the set $\{-y, y\}$), the Average Loss regressed to the mean (zero), failing to capture the signal entirely. The Infimum Loss correctly "picked a side" and successfully recovered the underlying signal shape.

Limitations and Future Directions

While powerful, the framework does have limitations. The use of kernel methods involves an $n \times n$ matrix computation. While standard in kernel literature, this can become a bottleneck for massive datasets unless approximation techniques like Nyström sampling are employed. Additionally, the theoretical guarantees rely on the assumption that the partial labels aren't entirely vague; if the sets are always so large that they never point toward a specific solution, the problem remains unidentifiable.

Looking forward, this framework provides a strong foundation that could be extended to other forms of weak supervision, such as learning from imprecise labels provided by non-experts or broader semi-supervised learning tasks.

Summary updated

Abstract

Annotating datasets is one of the main costs in nowadays supervised learning. The goal of weak supervision is to enable models to learn using only forms of labelling which are cheaper to collect, a...
BibTeX
@inproceedings{cabannes2020structured,
  author = {Vivien Cabannes and Alessandro Rudi and Francis R. Bach},
  title = {{Structured Prediction with Partial Labelling through the Infimum Loss}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=_XxjW6HYnG},
}
Figure