Scalable Probabilistic Tensor Factorization for Binary and Count Data

Piyush Rai, Changwei Hu, Matthew Harding, Lawrence CarinIJCAI 2015

Introduction

Tensors are essential multi-way arrays for representing complex relationships, such as (Author × Word × Venue) interactions. While tensor factorization is a powerful tool for pattern discovery and missing entry prediction, traditional methods often assume real-valued data. However, real-world datasets are frequently discrete—social networks are binary, and purchase histories consist of counts. Applying standard Gaussian tools to such data typically yields suboptimal results. Furthermore, as datasets scale to millions of observations, traditional Bayesian methods like Gibbs sampling become computationally prohibitive.

Researchers at Duke University have addressed these challenges by developing PGCP (Polya-Gamma Canonical PARAFAC), a scalable probabilistic framework designed specifically for binary and count-valued tensor data.

Methodology

The PGCP framework is built upon three primary technical pillars:

  1. Polya-Gamma (PG) Augmentation: This core innovation utilizes a data augmentation strategy to "Gaussian-ify" non-conjugate likelihoods. By transforming logistic (binary) and negative binomial (count) distributions into a Gaussian-like form, the researchers enable simpler, closed-form parameter updates.
  2. Multiplicative Gamma Process (MGP) Prior: To avoid the manual selection of tensor rank, the MGP prior automatically shrinks redundant latent factors toward zero, allowing the model to learn the optimal rank directly from the data.
  3. Online Expectation-Maximization (EM): To achieve massive scalability, the authors implemented an online EM algorithm. By processing data in mini-batches and recursively updating sufficient statistics, the model eliminates the need to store the entire tensor in memory, facilitating the analysis of datasets with millions of entries.

Experimental Evaluation

The framework was evaluated across several diverse real-world datasets:

  • Binary Tensors: Kinship (social relationships), Digg (user-story-tag interactions), and DBLP (author-conference-keyword relationships).
  • Count Tensors: GDELT (geopolitical interactions), Scholars (author word usage), and Transactions (a massive dataset of 117,054 households and 67,095 items).

Results and Discussion

The proposed PGCP model demonstrated significant improvements in both accuracy and computational efficiency.

Convergence and Accuracy

In tensor completion tasks, PGCP consistently outperformed baselines such as Inf-Tucker and Poisson Tensor Factorization (PTF). A key finding is that the Online EM algorithm is not merely a faster alternative to Batch EM; it often discovers superior solutions by navigating the parameter space more dynamically.

Performance comparison on the DBLP dataset showing the rapid convergence of Online EM compared to Gibbs and Batch EM.

Scalability to Massive Data

The framework's scalability was most evident on the Transactions dataset. While traditional Bayesian methods often fail on data of this magnitude, the online EM approach handled it efficiently.

Convergence of held-out log-likelihood on the massive Transactions dataset, demonstrating the efficiency of the online EM approach.

Interpretability

By incorporating non-negativity constraints enabled by the PG augmentation, the model successfully extracted interpretable research topics from the Scholars dataset, such as "Machine Learning" and "Immunology."

Conclusion

PGCP provides a robust, generative framework for scalable tensor factorization of discrete data. By leveraging Polya-Gamma augmentation and online EM, it bridges the gap between probabilistic rigor and large-scale computational demands. Future work may extend this framework to categorical data and incorporate auxiliary side information to further enhance decomposition quality.

Summary updated

BibTeX
@inproceedings{rai2015scalable,
  author = {Piyush Rai and Changwei Hu and Matthew Harding and Lawrence Carin},
  title = {{Scalable Probabilistic Tensor Factorization for Binary and Count Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure