Scalable Bayesian Modelling of Paired Symbols

Ulrich Paquet, Noam Koenigstein, Ole WintherarXiv 2014 · DOI · arXiv

Abstract

We present a novel, scalable and Bayesian approach to modelling the occurrence of pairs of symbols (i,j) drawn from a large vocabulary. Observed pairs are assumed to be generated by a simple popularity based selection process followed by censoring using a preference function. By basing inference on the well-founded principle of variational bounding, and using new site-independent bounds, we show how a scalable inference procedure can be obtained for large data sets. State of the art results are presented on real-world movie viewing data.

Introduction

In fields like recommender systems or natural language processing, we often need to model the probability of a pair $(i, j)$—for example, a user $i$ buying item $j$. The gold standard for this is the softmax distribution. However, the softmax has a massive "bottleneck": its normalizing constant requires summing over every possible combination of users and items ($I \times J$). When you have millions of users and hundreds of thousands of items, this $O(IJ)$ complexity makes standard Bayesian inference impossible.

Furthermore, these datasets are incredibly sparse. Most users only interact with a handful of items. Frequentist approaches, such as Maximum A Posteriori (MAP) estimation, tend to overfit this sparse data, failing to generalize to new recommendations. There is a critical need for a Bayesian approach that provides robustness through uncertainty quantification while remaining fast enough to handle "big data" scales.

Methodology

The authors propose a two-step generative model to circumvent the softmax bottleneck:

  1. Selection: A user $i$ and an item $j$ are chosen based on their base popularity ($\pi_i$ and $\psi_j$).
  2. Censoring: A "censor" decides whether to include this pair in the observed data based on a personalized preference function $\sigma(u_i^T v_j + b_i + b_j)$, where $u_i$ and $v_j$ are latent feature vectors.
The proposed graphical model illustrating the selection and censoring process.

To make inference scalable, the framework utilizes Variational Bayes (VB) with a key innovation: site-independent bounds. Instead of treating every unobserved pair as a unique data point, the model "ties" the variational parameters for the unobserved (censored) stream. This allows for the pre-calculation of "background caches"—global summaries of the item and user space. Consequently, updating a specific user's parameters only requires looking at the items they actually interacted with, plus these pre-computed global constants. This shifts the computational complexity from $O(IJ)$ to $O(D)$, where $D$ is the number of observed interactions.

Experimental Setup

The model was evaluated on several large-scale datasets to test its performance and scalability:

  • Xbox Movies: 56 million views from 6.2 million users across ~12,000 movies.
  • Netflix (4 and 5 stars): A standard benchmark used to simulate implicit feedback.
  • NIPS Co-authorship: A smaller dataset used for qualitative comparison against standard softmax models.
  • Windows 8 Phone App Installs: Used to demonstrate variational model pruning in production.

Results and Discussion

The proposed model outperformed several strong baselines, including Bayesian Personalized Ranking (BPR) and Random Graph models. On the Xbox movies dataset, it achieved an average rank of over 0.95, significantly higher than popularity-based or simpler latent factor models.

Average rank performance on Xbox movies and Netflix datasets compared to various baselines.

Efficiency is a major highlight: despite the complexity of Bayesian inference, the authors updated all item-related parameters for the Xbox dataset in just 69 seconds on a 24-core machine. Qualitatively, the Bayesian approach maintained healthy uncertainty in sparse scenarios (like the NIPS dataset), correctly assigning high probability to likely but unobserved pairs, whereas MAP estimates failed by "memorizing" training data.

Conclusion

This work provides a principled probabilistic framework that treats unobserved data as a censored stream rather than relying on heuristic negative sampling. While the current selection model is simple, future work could explore more complex mixture models. Additionally, while the ratio of censored data $D'/D = 1$ proved effective, further empirical study on hyperparameter sensitivity and comparisons with MCMC methods are warranted.

Summary updated

Abstract

We present a novel, scalable and Bayesian approach to modelling the occurrence of pairs of symbols (i,j) drawn from a large vocabulary. Observed pairs are assumed to be generated by a simple popularity based selection process followed by censoring using a preference function. By basing inference on the well-founded principle of variational bounding, and using new site-independent bounds, we show how a scalable inference procedure can be obtained for large data sets. State of the art results are presented on real-world movie viewing data.
BibTeX
@misc{paquet2014scalable,
  author = {Ulrich Paquet and Noam Koenigstein and Ole Winther},
  title = {{Scalable Bayesian Modelling of Paired Symbols}},
  year = {2014},
  eprint = {1409.2824},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.2824},
}
Figure