Partial Multi-Label Learning via Large Margin Nearest Neighbour Embeddings

Xiuwen Gong, Dong Yuan, Wei Bao

Introduction

Partial Multi-Label Learning (PML) addresses a common real-world scenario where training instances are associated with a set of candidate labels, only some of which are ground-truth. The presence of "distractor" or noisy labels makes training robust models challenging. Traditional multi-label learning assumes perfect tagging, which is often unattainable in large-scale crowdsourced or web-scraped datasets.

The Challenge of Ambiguity

In PML, the primary hurdle is disambiguation. For instance, an image of a university campus might be tagged with cloud, tree, bird, grass, dog, river, people, and building. While building and grass might be true, bird or dog could be erroneous tags added by a noisy process.

An illustration of the Partial Multi-Label Learning problem, where an image is associated with several candidate labels, some of which are incorrect.

Existing methods often attempt to identify ground-truth labels directly during training, but these approaches are frequently misled by the noise. PML-LMNNE shifts the focus from explicit identification to leveraging the underlying data structure through low-dimensional embeddings.

Methodology: PML-LMNNE

The proposed framework, PML-LMNNE (Partial Multi-label Learning via Large Margin Nearest Neighbour Embeddings), utilizes a two-stage projection process:

  1. Feature Projection ($V$): Features are first projected into the label space to align dimensions.
  2. Large Margin Embedding ($W$): A second projection into a lower-dimensional space is learned using the Large Margin Nearest Neighbour (LMNN) principle. This ensures that an instance's features are significantly closer to its own ground-truth labels than to the labels of its neighbors.

The optimization is framed as a convex problem using a hinge loss function, solved efficiently via Singular Value Decomposition (SVD) and a proximal gradient method. Crucially, the authors provide a theoretical guarantee: as the training set grows, the model's error rate converges toward the optimal Bayes error.

Experimental Evaluation

The model was tested on a diverse array of datasets, including synthetic benchmarks (Enron, Corel5k, Eurlex, CAL500, Mediamill) and real-world ambiguous datasets (YeastBP, Music-emotion, Music-style, MIRFlickr).

Key Results

PML-LMNNE demonstrated superior performance across nearly all metrics compared to state-of-the-art baselines like PARTICLE, DRAMA, and MUSER.

Comparison of Average Precision across various datasets. PML-LMNNE (bold) consistently achieves the highest precision.

Key findings include:

  • Robustness: The model maintains high performance even as the number of candidate "distractor" labels increases.
  • Scalability: Strong results on high-dimensional datasets like Mediamill suggest the embedding approach effectively filters noise in complex spaces.
  • Data Efficiency: While performance is comparable on very small datasets, the model's advantages become pronounced as the number of instances increases, validating the theoretical convergence proofs.

Conclusion

PML-LMNNE offers a mathematically grounded and empirically robust solution for learning from ambiguous data. By prioritizing structural embedding over direct label identification, it effectively mitigates the impact of noisy candidate sets, making it a powerful tool for real-world multi-label applications.

Summary updated

Abstract

To deal with ambiguities in partial multi-label learning (PML), existing popular PML research attempts to perform disambiguation by direct ground-truth label identification. However, these approaches can be easily misled by noisy false-positive labels in the iteration of updating the model parameter and the latent ground-truth label variables. When labeling information is ambiguous, we should depend more on underlying structure of data, such as label and feature correlations, to perform disambiguation for partially labeled data. Moreover, large margin nearest neighbour (LMNN) is a popular strategy that considers data structure in classification. However, due to the ambiguity of labeling information in PML, traditional LMNN cannot be used to solve the PML problem directly. In addition, embedding is an effective technology to decrease the noise information of data. Inspried by LMNN and embedding technology, we propose a novel PML paradigm called Partial Multi-label Learning via Large Margin Nearest Neighbour Embeddings (PML-LMNNE), which aims to conduct disambiguation by projecting labels and features into a lower-dimension embedding space and reorganize the underlying structure by LMNN in the embedding space simultaneously. An efficient algorithm is designed to implement the proposed method and the convergence rate of the algorithm is analyzed. Moreover, we present a theoretical analysis of the generalization error bound for the proposed PML-LMNNE, which shows that the generalization error converges to the sum of two times the Bayes error over the labels when the number of instances goes to infinity. Comprehensive experiments on artificial and real-world datasets demonstrate the superiorities of the proposed PML-LMNNE.
BibTeX
@inproceedings{gong2022partial,
  author = {Xiuwen Gong and Dong Yuan and Wei Bao},
  title = {{Partial Multi-Label Learning via Large Margin Nearest Neighbour Embeddings}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20628},
}
Figure