Structured Prediction with Partial Labelling through the Infimum Loss

Vivien Cabannes, Alessandro Rudi, Francis Bach

TL;DR

This paper introduces a unified framework for learning with partial labels, a form of weak supervision where each data point is associated with a set of possible labels instead of a single ground truth. By leveraging structured prediction and a novel "infimum loss," the authors provide a principled approach that can recover fully supervised solutions under certain conditions and offers strong theoretical guarantees, outperforming existing methods in challenging scenarios.

What Problem Does This Paper Address?

Supervised learning typically requires large amounts of precisely labeled data, which is often expensive and time-consuming to acquire. Weak supervision offers a solution by using cheaper, less precise forms of labeling. Partial labeling is one such form, where instead of a single correct label, we are given a set of labels that is guaranteed to contain the true label. While partial labeling has been studied for specific tasks like classification or ranking, a general, unified framework for handling it across various learning problems and loss functions was missing. This paper aims to fill that gap by proposing a general framework that can be applied to a wide range of structured prediction problems.

Methods

The core contribution of this paper is a unified framework for partial labeling based on structured prediction and the infimum loss. The infimum loss, defined as $L(z, S) = \inf_{y \in S} l(z, y)$, captures the idea that when given a set of possible labels $S$, the model should aim to match the "best guess" within that set, rather than being penalized for not matching incorrect labels in $S$.

This infimum loss naturally leads to a variational framework. The authors prove that under certain "identifiability" assumptions (i.e., when the partial labeling process is not too ambiguous), this framework can recover the original fully supervised solution. They then derive an explicit, easy-to-implement algorithm based on structured prediction, which is shown to have strong theoretical guarantees, including consistency and learning rates. The algorithm essentially learns weights for each data point's partial label set and uses these weights to approximate the true data distribution, thereby enabling the recovery of the underlying supervised learning problem.

Datasets

The paper evaluates its proposed method on several standard datasets:

  • LIBSVM datasets: "dna", "svmguide2", "segment", and "vowel" were used for classification experiments. These datasets were artificially corrupted to simulate partial labeling scenarios.
  • MULAN datasets: The "scene" dataset was used for multi-label classification experiments, with supervision provided as Hamming balls.

The authors also introduce synthetic experiments for ranking and partial regression to showcase the method's behavior in specific scenarios.

Key Insights and Ideas

  • Unified Framework for Partial Labeling: The paper provides a general theoretical framework for partial labeling that transcends specific tasks and loss functions, unifying previous work and opening doors for broader applications.
  • The Power of the Infimum Loss: The infimum loss is a principled way to handle partial labels, effectively ignoring "bad" labels within a set and focusing on the most plausible ones. This is crucial for avoiding inconsistencies that can arise with simpler averaging approaches.
  • Recovering Fully Supervised Solutions: Under non-ambiguity conditions, the infimum loss framework can provably recover the original fully supervised solution, demonstrating its theoretical soundness.
  • Algorithmic Tractability: The proposed framework leads to an explicit algorithm that is not only theoretically sound but also practical to implement and train, offering strong statistical guarantees.
  • Adversarial Scenarios: The infimum loss approach shows superior performance in scenarios where the partial labeling process is more adversarial, highlighting its robustness.

Key Results

  • Theoretical Guarantees: The paper provides theoretical proofs for the consistency and learning rates of the proposed algorithm.
  • Superior Performance: Experiments on synthetic and real-world datasets (classification, ranking, partial regression, multi-label) demonstrate that the proposed infimum loss approach consistently outperforms common baselines, especially in scenarios where label corruption is more adversarial or unbalanced. For instance, in classification tests on "dna" and "svmguide2" datasets, the infimum loss method performed better when the most frequent label was corrupted. In ranking experiments, the infimum loss method significantly outperformed the average loss.

Limitations and Future Work

  • Identifiability Assumptions: The theoretical guarantees for recovering the fully supervised solution rely on certain "identifiability" assumptions about the partial labeling process. The paper acknowledges that these assumptions might not always hold in practice.
  • Computational Complexity: While the algorithm is efficient, certain aspects, like solving minimum feedback arc set problems for ranking, can be computationally intensive for large numbers of items.
  • Future Directions: The authors suggest extending the framework to other weakly supervised learning problems, such as imprecise labels from non-experts, more general constraints over label sets, or semi-supervised learning. They also mention the potential for active learning strategies to optimize the labeling process by selecting informative questions to ask annotators.

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, as partial labelling. This is a type of incomplete annotation where, for each datapoint, supervision is cast as a set of labels containing the real one. The problem of supervised learning with partial labelling has been studied for specific instances such as classification, multi-label, ranking or segmentation, but a general framework is still missing. This paper provides a unified framework based on structured prediction and on the concept of infimum loss to deal with partial labelling over a wide family of learning problems and loss functions. The framework leads naturally to explicit algorithms that can be easily implemented and for which proved statistical consistency and learning rates. Experiments confirm the superiority of the proposed approach over commonly used baselines.
BibTeX
@inproceedings{cabannes2020structured,
  author = {Vivien Cabannes and Alessandro Rudi and Francis 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