Solving the Partial Label Learning Problem: An Instance-Based Approach

Min-Ling Zhang, Fei Yu

Introduction

Partial Label Learning (PLL) is a specialized supervised learning framework where each training instance is associated with a set of candidate labels, only one of which is correct. This ambiguity arises naturally in various real-world applications, such as automatic face naming in images or bird song classification, where annotations are often imprecise. The fundamental challenge in PLL is disambiguation: identifying the true ground-truth label from the candidate set without ever observing it directly during training.

Traditional approaches often rely on averaging the outputs of all candidate labels. However, this strategy is susceptible to noise, as "false positive" labels within the candidate set can easily overwhelm the signal of the single true label.

The IPAL Framework

This paper introduces IPAL (Instance-based PArtial Label learning), a novel approach that leverages local data density and iterative propagation to achieve effective disambiguation. IPAL operates in two distinct phases:

1. Disambiguation (Training Phase)

IPAL first constructs a directed, weighted graph where each training instance is linked to its $k$-nearest neighbors. Unlike standard methods that use simple Euclidean distance, IPAL determines weights by solving a linear reconstruction problem. This asks: "How can these neighbors be mathematically combined to best reconstruct this specific instance?" This method captures the local geometry of the feature space more effectively.

Once the graph is built, label confidences are initialized equally among all candidates in an instance's set. These confidences are then iteratively propagated across the graph. In each iteration, an instance’s label confidence is updated based on its neighbors' confidences, while remaining strictly constrained to the original candidate set. This process effectively "cleans" the training data by converging on the most likely true label for each example.

2. Classification (Testing Phase)

To classify a new, unseen instance, IPAL identifies its $k$-nearest neighbors within the now-disambiguated training set. It employs a minimum error reconstruction criterion, predicting the label that yields the smallest error when attempting to reconstruct the new instance using only neighbors assigned to that specific label.

Experimental Results

The authors evaluated IPAL against several state-of-the-art methods, including PL-kNN and LSB-CMM, using both controlled UCI datasets and real-world applications (e.g., face naming in Lost and Yahoo! News, bioacoustics in BirdSong).

Performance on Controlled Datasets

In controlled experiments, the complexity of the PLL problem was varied by adjusting the co-occurring probability of extra candidate labels ($\epsilon$) and the proportion of partially labeled examples ($p$).

Classification accuracy of IPAL compared to baseline methods across four UCI datasets (glass, segment, usps, letter) as the co-occurring probability $\epsilon$ increases.

As shown in the figure above, IPAL (represented by the black line with square markers) consistently maintains superior accuracy compared to other instance-based and model-based methods across different noise levels. In 112 statistical comparisons, IPAL outperformed PL-kNN and LSB-CMM in over 80% of cases.

Robustness to Labeling Proportion

IPAL also demonstrates significant robustness to the amount of ambiguous data in the training set.

Classification accuracy on the 'segment' dataset as the proportion of partially labeled examples ($p$) increases from 0.1 to 0.7.

Even as the proportion of partially labeled examples increases, IPAL's performance remains stable, highlighting its effective disambiguation capabilities.

Conclusion

IPAL represents a significant advancement in Partial Label Learning by prioritizing explicit disambiguation over simple averaging. By utilizing local reconstruction weights and iterative propagation, it effectively recovers ground-truth labels from noisy candidate sets. Future work may explore more sophisticated distance metrics or metric learning to further refine the initial graph construction and improve scalability for high-dimensional datasets.

Summary updated

Abstract

In partial label learning, each training example is associated with a set of candidate labels, among which only one is valid. An intuitive strategy to learn from partial label examples is to treat all candidate labels equally and make prediction by averaging their modeling outputs. Nonetheless, this strategy may suffer from the problem that the modeling output from the valid label is overwhelmed by those from the false positive labels. In this paper, an instance-based approach named IPAL is proposed by directly disambiguating the candidate label set. Briefly, IPAL tries to identify the valid label of each partial label example via an iterative label propagation procedure, and then classifies the unseen instance based on minimum error reconstruction from its nearest neighbors. Extensive experiments show that IPAL compares favorably against the existing instance-based as well as other state-of-the-art partial label learning approaches.
BibTeX
@inproceedings{zhang2015solving,
  author = {Min-Ling Zhang and Fei Yu},
  title = {{Solving the Partial Label Learning Problem: An Instance-Based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure