fBGD: Learning Embeddings From Positive Unlabeled Data with BGD

Fajie Yuan, Xin Xin, Xiangnan He, Guibing Guo, Weinan Zhang, Tat-Seng Chua, Jose M. JoemonUAI 2018 · OpenReview

Abstract

Positive-Unlabeled (PU) learning is a common challenge in recommendation systems and natural language processing, where only positive interactions are observed and the remaining data is unlabeled. Traditional approaches rely on negative sampling, which often leads to information loss and high variance. This paper introduces fBGD (fast Batch Gradient Descent), a framework that enables efficient full-batch learning on PU data. By leveraging mathematical reformulations and data sparsity, fBGD achieves the accuracy of full-batch learning with the computational efficiency of stochastic methods.

Introduction

In many real-world applications—such as song recommendation, image classification, or word embedding—we primarily encounter "positive" data (e.g., a user playing a song). The vast majority of other potential interactions are "unlabeled," meaning they could be true negatives or simply positive instances that haven't occurred yet.

The PU learning framework: mapping a sparse interaction matrix with observed positives and unlabeled entries to latent embeddings.

The industry standard for handling this is Negative Sampling (NS), which pairs each positive example with a few randomly chosen unlabeled ones. However, NS suffers from significant information loss by ignoring the bulk of the data and introduces high variance during training. While Batch Gradient Descent (BGD) considers all data, it is typically too computationally expensive for large-scale datasets. fBGD bridges this gap by making full-batch learning feasible.

Methodology

fBGD achieves efficiency through three primary innovations:

  1. Mathematical Reformulation: The loss function is rewritten so that the error over unlabeled data is calculated as the difference between the error over all possible pairs and the error over only the positive pairs.
  2. Summation Rearrangement: By rearranging nested sums in the gradient calculation, the authors decouple parameters, allowing for the precomputation of "caches" for unlabeled data. This reduces time complexity from $O(|X||Y|g)$ to $O((|X|+|Y|)g^2)$, where $g$ is the embedding dimension.
  3. Adaptive Stabilization: BGD on sparse data often suffers from gradient instability because some features appear much more frequently than others. The authors integrated an adaptive learning rate (similar to Adagrad) to normalize updates for each parameter, preventing exploding or vanishing gradients.
Performance comparison showing the impact of adaptive stabilization (Improved fBGD) on convergence and accuracy compared to standard BGD with various learning rates.

Key Results and Insights

The researchers evaluated fBGD across Word Embedding (NewsIR, Text8), Collaborative Filtering (Yahoo Music, Lastfm), and Image Classification (OpenImages) domains.

  • Superior Accuracy: fBGD consistently outperformed Skip-gram, GloVe, and SVD-based models. In word analogy tasks on the Text8 dataset, fBGD achieved 41.3% accuracy, significantly higher than GloVe’s 34.5%.
  • Competitive Efficiency: Despite processing all data, fBGD's runtime is comparable to sampling-based SGD. On the Lastfm dataset, fBGD completed a training iteration in 26 seconds, compared to 156 seconds for a tuned SGD model.
  • Addressing Sampling Bias: The paper demonstrates that models like Skip-gram are highly sensitive to sampling ratios. fBGD eliminates this sensitivity by utilizing the entire dataset without the noise of stochastic sampling.
  • Handling Sparsity: While sparsity is usually a challenge, fBGD utilizes it to skip redundant calculations, making the "all-data" approach as fast as traditional sampling methods.

Limitations and Future Work

Currently, fBGD focuses on "shallow" embeddings (dot products). The mathematical optimizations used are specifically tailored to linear-style interactions, though extensions to deeper architectures may be possible. Additionally, while the authors proposed frequency-based weighting for unlabeled data, more sophisticated, task-specific weighting functions could further enhance performance. Finally, the caching mechanism requires storing intermediate sums, which may present memory challenges in extremely high-dimensional feature spaces.

Conclusion

fBGD represents a significant step forward for PU learning, proving that full-batch learning is not only possible but can be more efficient and accurate than traditional sampling methods. By stabilizing the gradients and optimizing the math behind the updates, fBGD provides a robust framework for learning high-quality embeddings from sparse, unlabeled data.

Summary updated

BibTeX
@inproceedings{yuan2018fbgd,
  author = {Fajie Yuan and Xin Xin and Xiangnan He and Guibing Guo and Weinan Zhang and Tat-Seng Chua and Jose M. Joemon},
  title = {{fBGD: Learning Embeddings From Positive Unlabeled Data with BGD}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=W5PY2vaz4MB},
}
Figure