Label Ranking under Ambiguous Supervision for Learning Semantic Correspondences

Antoine Bordes, Nicolas Usunier, Jason Weston

Introduction

This paper introduces a novel method for learning semantic correspondences—matching text to structured data—from "ambiguous supervision." In ambiguously supervised scenarios, each training sentence is paired with a set of potential meanings rather than a single verified correct one. By reframing the problem as a label ranking task, the authors demonstrate that a simple discriminative model can outperform complex generative models on standard benchmarks.

What Problem Does This Paper Address?

In traditional supervised machine learning, we assume every input has a single, verified "gold" label. However, creating these meticulously annotated datasets is expensive and time-consuming. An alternative is to use "ambiguous supervision," where data is collected automatically from the environment.

For example, a sports broadcast provides a stream of commentary (text) and a stream of game events (data records). We know a sentence likely refers to an event happening around the same time, but we don't know which specific event it describes, or if it describes an event at all.

Examples of ambiguous supervision in the RoboCup and Weather datasets.

The core challenge is learning the true mapping (semantic correspondence) when the training data is noisy and "one-to-many." Previous approaches often relied on complex generative models using Expectation-Maximization (EM) to guess the hidden alignments. This paper asks: Can we skip the complex "guessing" phase and use a simpler ranking approach instead?

The ARank Method

The authors propose a framework called ARank (Ambiguous Rank). The central concept is task-transfer: instead of trying to isolate the exact correct label among the candidates, the model learns to rank the entire set of candidate labels higher than a set of randomly sampled "negative" labels drawn from the rest of the dataset.

Key components of the framework include:

  • Label Scoring Function (LSF): A linear model that assigns a score to a (text, record) pair based on joint features.
  • Negative Sampling: For every training instance, the algorithm samples "negative" records that are explicitly not in the current candidate set.
  • Ranking Loss: The model is trained using a regularized convex loss (similar to SVM-rank) that penalizes the model if a random negative record is scored higher than a candidate record.
  • Theoretical Justification: The authors provide a "Coherence" theorem. It mathematically proves that if the true label appears in the candidate sets more consistently than incorrect labels do, a model that learns to rank candidates highly will naturally learn to push the correct label to the very top.

Datasets

The paper evaluates the approach on two established benchmarks for semantic correspondence:

  1. RoboCup Sportscasting: 1,872 scenarios matching soccer commentary to game engine logs (e.g., "pink4 passes to purple6"). It is "incomplete," meaning 15% of sentences have no correct record in their candidate set.
  2. Weather Forecasts: 22,146 scenarios matching local weather reports to meteorological data records. This dataset is significantly noisier, with an average of 36 candidate records per sentence compared to RoboCup's 2.4.

Key Insights and Results

ARank shifts the paradigm from generative modeling (trying to model how the text was produced from the data) to discriminative modeling. It focuses only on the boundary between "likely correct" and "definitely wrong." Because you don't need to know which candidate is "Gold" to learn, simply pushing all candidates "up" and random negatives "down" allows the true signal to receive the most consistent upward pressure across the whole dataset.

F1 scores comparing ARank to the generative baseline across both datasets.

The ARank model demonstrated strong performance against the then-state-of-the-art generative model by Liang et al. (2009):

  • RoboCup: ARank achieved an $F_1$ score of 83.7, significantly outperforming Liang et al.'s 80.5.
  • Weather Forecasting: ARank achieved an $F_1$ score of 76.6, slightly outperforming the generative baseline (75.0).
  • Ranking Accuracy: On RoboCup, the model placed the correct record in the top slot 91.9% of the time, compared to a 59% random baseline.

Limitations and Future Work

While highly effective, the ARank approach has a few limitations:

  • Hyperparameter Sensitivity: The performance depends on the size of the negative set ($s$) and the regularization constant ($C$). Setting these without "gold" validation data remains an open research question.
  • Heuristic Predictions: Because the model only ranks labels, it doesn't inherently know how many labels to pick for a given sentence. The authors had to use post-processing heuristics (e.g., "always pick the top 1") to generate final predictions.
  • Feature Engineering: The model relies on a joint feature function $\phi(x, y)$. While a bag-of-words approach worked well for these benchmarks, more complex semantic tasks might require sophisticated deep learning architectures.

Summary updated

Abstract

This paper studies the problem of learning from ambiguous supervision, focusing on the task of learning semantic correspondences. A learning problem is said to be ambiguously supervised when, for a given training input, a set of output candidates is provided with no prior of which one is correct. We propose to tackle this problem by solving a related unambiguous task with a label ranking approach and show how and why this performs well on the original task, via the method of task-transfer. We apply it to learning to match natural language sentences to a structured representation of their meaning and empirically demonstrate that this competes with the state-of-the-art on two benchmarks.
BibTeX
@inproceedings{bordes2010label,
  author = {Antoine Bordes and Nicolas Usunier and Jason Weston},
  title = {{Label Ranking under Ambiguous Supervision for Learning Semantic Correspondences}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=Sk-YFoZdbS},
}
Figure