Positive and Unlabeled Learning via Loss Decomposition and Centroid Estimation

Hong Shi, Shaojun Pan, Jian Yang, Chen Gong

Abstract

Positive and Unlabeled (PU) learning is a pervasive challenge in machine learning where only a subset of positive examples is labeled, while the remaining data is unlabeled and contains both positive and negative instances. This paper introduces LDCE (Loss Decomposition and Centroid Estimation), a novel framework that treats unlabeled data as noisy negatives. By decomposing the standard hinge loss into noise-robust and noise-sensitive components and employing a robust centroid estimator for the negative class, LDCE effectively mitigates the impact of label noise. Experimental results across synthetic, UCI benchmark, and real-world datasets demonstrate that LDCE consistently outperforms state-of-the-art PU learning methods, particularly under high noise conditions.

Introduction

In many real-world scenarios, such as fraud detection or medical diagnosis, obtaining confirmed positive instances is relatively straightforward, but identifying definitive negative cases is often costly or impossible. This scenario defines the Positive and Unlabeled (PU) learning problem. Traditional approaches typically rely on weighting unlabeled data or identifying "reliable" negatives in a two-step process. However, these methods are often sensitive to hyperparameter tuning and prone to error propagation from the initial labeling step.

The proposed LDCE method reframes the problem by acknowledging the inherent noise in the unlabeled set. Instead of individual point labeling, it focuses on the global properties of the classes—specifically the centroid of the negative distribution—to build a more robust classifier.

Methodology

The LDCE algorithm is built upon three core pillars:

  1. Loss Decomposition: The authors decompose the standard hinge loss into an "even" part, which is symmetric and naturally robust to label noise, and an "odd" part that captures the noise sensitivity.
  2. Centroid Estimation: To address the noise in the "odd" part of the loss, the algorithm estimates the centroid of the true negative class. Given that the unlabeled set is contaminated with positives, a Median-of-means estimator is used to provide a robust location for the negative center, preventing it from being skewed by hidden positive outliers.
  3. Optimization: The model iteratively updates the classifier weights and the estimated centroid. A covariance-based constraint is applied to ensure the estimated centroid remains within a plausible region of the feature space, enhancing generalization.
Visual comparison of decision boundaries on synthetic data. LDCE (c) achieves perfect separation, while other methods like UPU (d), W-SVM (e), and L-SVM (f) misclassify points near the boundary.

Experimental Results

The performance of LDCE was evaluated against several benchmarks, including W-SVM, Unbiased PU (UPU), and Non-negative PU (NNPU).

Synthetic and Benchmark Data

On synthetic Gaussian distributions, LDCE achieved 100% accuracy, successfully navigating the ambiguous regions where other specialized PU methods failed. On seven UCI benchmark datasets (e.g., breast cancer, banknote, mushroom), LDCE consistently ranked among the top performers. Its advantage became more pronounced as the "noise rate" ($\eta$)—the proportion of positives hidden in the unlabeled set—increased.

Real-World Applications

The method was further tested on the HockeyFight video dataset for violence detection and the USPS digit recognition dataset. In these complex scenarios, LDCE maintained superior F-measure scores compared to its competitors.

F-measure performance across different noise rates for real-world datasets. LDCE (blue) consistently maintains higher performance as noise increases compared to W-SVM, UPU, NNPU, and L-SVM.

As shown in the figures above, LDCE's ability to maintain a high F-measure even at a noise rate of 0.4 highlights its robustness. For instance, in the HockeyFight dataset, LDCE achieved an F-measure of 0.783, significantly higher than L-SVM's 0.671.

Conclusion and Future Work

LDCE provides a mathematically grounded and robust framework for PU learning by focusing on loss decomposition and class centroids. By isolating the noise-sensitive components of the loss function, it avoids the pitfalls of individual point weighting. While currently optimized for linear classifiers, future work aims to extend this approach to non-linear boundaries using kernel methods. Additionally, refining the selection of the noise rate parameter through automated cross-validation remains an area for further development.

Summary updated

Abstract

Positive and Unlabeled learning (PU learning) aims to train a binary classifier based on only positive and unlabeled examples, where the unlabeled examples could be either positive or negative. The state-of-the-art algorithms usually cast PU learning as a cost-sensitive learning problem and impose distinct weights to different training examples via a manual or automatic way. However, such weight adjustment or estimation can be inaccurate and thus often lead to unsatisfactory performance. Therefore, this paper regards all unlabeled examples as negative, which means that some of the original positive data are mistakenly labeled as negative. By doing so, we convert PU learning into the risk minimization problem in the presence of false negative label noise, and propose a novel PU learning algorithm termed ?Loss Decomposition and Centroid Estimation? (LDCE). By decomposing the hinge loss function into two parts, we show that only the second part is influenced by label noise, of which the adverse effect can be reduced by estimating the centroid of negative examples. We intensively validate our approach on synthetic dataset, UCI benchmark datasets and real-world datasets, and the experimental results firmly demonstrate the effectiveness of our approach when compared with other state-of-the-art PU learning methodologies.
BibTeX
@inproceedings{shi2018positive,
  author = {Hong Shi and Shaojun Pan and Jian Yang and Chen Gong},
  title = {{Positive and Unlabeled Learning via Loss Decomposition and Centroid Estimation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/373},
}
Figure