AUC Optimization from Multiple Unlabeled Datasets

Zheng Xie, Yu Liu, Ming Li

This paper, presented at AAAI-24, introduces a novel framework for a particularly thorny problem in machine learning: how to build a high-performing ranking model when you have plenty of data, but none of it is labeled. The authors propose $U^m$-AUC, the first algorithm designed to optimize the Area Under the ROC Curve (AUC) using only multiple unlabeled datasets.

Problem Statement: Learning from Unlabeled Bags

In many real-world scenarios—such as predicting disease morbidity across different hospitals or voting rates across different districts—individual labels (e.g., "this person has the disease") are unavailable. Instead, researchers often have access to "bags" of unlabeled data where only the proportion of positive instances varies between bags. This is known as $U^m$ learning (learning from $m$ unlabeled datasets).

While existing $U^m$ methods typically focus on classification accuracy, accuracy is often a poor metric for imbalanced data or ranking tasks. For these applications, AUC is the gold standard. However, optimizing AUC in this context presents two major challenges:

  1. Information Scarcity: AUC optimization usually requires knowing positive and negative labels, which are absent in $U^m$ learning.
  2. Computational Complexity: Standard AUC optimization involves pairwise comparisons, leading to a quadratic $O(n^2)$ time complexity that scales poorly.

Methodology: The $U^m$-AUC Framework

The authors address these challenges through three key innovations. First, they provide a consistency proof showing that minimizing a specific "U-AUC" risk is equivalent to minimizing the true Positive-Negative (PN) AUC risk, provided the relative order of class priors (which bag is "more positive") is known.

Second, they employ a multi-label transformation. As shown in the comparison below, a naive solution would require solving $m(m-1)/2$ pairwise subproblems. $U^m$-AUC simplifies this into a multi-label problem with only $m-1$ labels, significantly reducing architectural complexity.

Comparison between the naive pairwise solution and the proposed Um-AUC framework, highlighting the reduction in subproblems.

Finally, to solve the $O(n^2)$ bottleneck, they convert the pairwise ranking loss into a point-wise min-max optimization problem. By utilizing auxiliary variables and a square surrogate loss, the model can be trained using stochastic gradient descent in linear time $O(n)$.

Experimental Evaluation

The method was evaluated using $U^m$ scenarios synthesized from three benchmarks: K-MNIST (Japanese characters), CIFAR-10, and CIFAR-100 (image recognition). The researchers simulated various real-world conditions by distributing data into 10 or 50 bags using different prior distributions—Uniform ($\mathcal{D}_u$), Biased ($\mathcal{D}_b$), Concentrated ($\mathcal{D}_c$), and Biased-Concentrated ($\mathcal{D}_{bc}$)—to test robustness against class imbalance.

Key Results and Discussion

$U^m$-AUC consistently outperformed state-of-the-art $U^m$ classification methods (such as LLP-VAT and $U^m$-SSC) across nearly all tested distributions. As seen in the results table, $U^m$-AUC achieved significantly higher AUC scores, particularly in complex scenarios like CIFAR-100.

Experimental results comparing Um-AUC against baselines across multiple datasets and distribution types.

Key takeaways from the results include:

  • Superior Ranking Performance: On CIFAR-10 with 10 bags, $U^m$-AUC achieved an AUC of 0.905, while the best baseline reached only 0.860.
  • Efficiency and Scalability: By reducing complexity to $O(n)$, the method is practical for large-scale datasets where quadratic algorithms are unfeasible.
  • Robustness: The model maintained high performance even when bag sizes were reduced or randomized, demonstrating its effectiveness in handling real-world data noise.

Conclusion

$U^m$-AUC provides a theoretically grounded and computationally efficient solution for ranking tasks in unlabeled data environments. While it requires knowing the relative order of class priors, it eliminates the need for exact metadata or individual labels. Future work may explore extending this framework to multi-class ranking and investigating alternative surrogate loss functions to further enhance performance.

Summary updated

Abstract

Weakly supervised learning aims to make machine learning more powerful when the perfect supervision is unavailable, and has attracted much attention from researchers. Among the various scenarios of weak supervision, one of the most challenging cases is learning from multiple unlabeled (U) datasets with only a little knowledge of the class priors, or U^m learning for short. In this paper, we study the problem of building an AUC (area under ROC curve) optimal model from multiple unlabeled datasets, which maximizes the pairwise ranking ability of the classifier. We propose U^m-AUC, an AUC optimization approach that converts the U^m data into a multi-label AUC optimization problem, and can be trained efficiently. We show that the proposed U^m-AUC is effective theoretically and empirically.
BibTeX
@inproceedings{xie2024auc,
  author = {Zheng Xie and Yu Liu and Ming Li},
  title = {{AUC Optimization from Multiple Unlabeled Datasets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i14.29538},
}
Figure