f: Learning Embeddings From Positive Unlabeled Data with BGD

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

Introduction

Training high-quality embedding models often relies on Positive Unlabeled (PU) data, where only positive interactions (e.g., a user clicking a link) are observed, while the remaining vast pool of data is unlabeled. Traditional approaches like Negative Sampling (NS) provide efficiency but introduce noise and sampling bias. Conversely, standard Batch Gradient Descent (BGD) is computationally prohibitive for large-scale datasets. This paper introduces $f_{BGD}$, a fast and generic BGD optimizer that achieves the accuracy of full-batch learning with the efficiency of stochastic methods.

The Challenge of Positive Unlabeled Learning

In domains such as recommendation systems or natural language processing, we typically lack explicit negative signals. The industry standard, Negative Sampling, treats a subset of unlabeled data as negatives. While fast, this approach ignores most of the available data and leads to high gradient variance.

The PU learning problem: sparse interaction matrix (left) and the corresponding dot-product embedding model (right).

Full BGD considers every possible pair, but its complexity is $O(|X||Y|g)$, where $|X|$ and $|Y|$ are the number of entities and $g$ is the embedding dimension. For a million users and items, this results in a trillion calculations per iteration, making it unusable for large-scale applications.

The $f_{BGD}$ Framework

The authors propose two primary innovations to overcome these hurdles:

  1. Mathematical Acceleration: By exploiting the dot-product structure of models like Matrix Factorization, the loss function is reformulated. Instead of iterating over every unlabeled pair, the algorithm computes the loss over all possible pairs and subtracts the known positives. Through precomputing vector "caches," the complexity is reduced to $O((|X|+|Y|)g^2)$, making BGD as fast as NS-based stochastic gradient descent.
  2. Stabilizing Sparse Gradients: Sparse data often leads to gradient instability in BGD. Frequent features can cause gradients to explode, while rare ones cause them to vanish. The authors implemented a specialized adaptive learning rate (similar to AdaGrad) to stabilize training in the full-batch setting.

Experimental Evaluation

The $f_{BGD}$ framework was evaluated across five benchmark datasets in three domains:

  • NLP: NewsIR and Text8 for word embeddings.
  • Information Retrieval: Yahoo Music and Lastfm for collaborative filtering.
  • Computer Vision: OpenImages for image classification.

Key Results and Insights

$f_{BGD}$ consistently outperformed state-of-the-art baselines, including Skip-gram (Word2Vec) and SVDFeature. The results demonstrate that the performance gap in modern embeddings is often due to sampling bias rather than model architecture. By utilizing 100% of the unlabeled data, $f_{BGD}$ finds superior optima.

NDCG@10 performance over training iterations, highlighting the critical impact of the adaptive learning rate on convergence and accuracy.

As shown in the figure above, the "Improved fBGD" with an optimized learning rate significantly outperforms standard configurations, reaching higher NDCG@10 scores much faster. Furthermore, the training time remains competitive; on the NewsIR dataset, $f_{BGD}$ completed an iteration in nearly half the time required by a comparable Skip-gram setup.

Conclusion and Future Work

The $f_{BGD}$ framework proves that full-batch learning is not only viable but superior for large-scale sparse embedding tasks. While currently optimized for dot-product models, future research may extend these acceleration techniques to deep non-linear architectures like Transformers and explore more dynamic weighting schemes for unlabeled data.

Summary updated

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