Bayesian Mosaic: Parallelizable Composite Posterior

Ye Wang, David B. DunsonarXiv 2018 · DOI · arXiv

Abstract

This paper proposes Bayesian Mosaic, a parallelizable composite posterior designed for scalable Bayesian inference on multivariate discrete data models. By decomposing a complex posterior into a multiplication of component posteriors based on univariate or bivariate marginal densities, the framework enables "embarrassingly parallel" sampling. Unlike traditional Data Augmented Markov Chain Monte Carlo (DA-MCMC) methods, which suffer from slow mixing rates in the presence of imbalanced data, Bayesian Mosaic utilizes numerical integration to bypass latent variable augmentation. We demonstrate that Bayesian Mosaic is consistent and asymptotically normal, offering superior scalability to large sample sizes. The method's efficacy is validated through simulation studies and an application to a citation count dataset.

Introduction

Multivariate discrete data—such as counts, categories, or binary responses—are ubiquitous in fields like accident analysis, genomics, and online advertising. Modeling the dependencies between these variables typically involves latent Gaussian factors. However, the standard inference tool, Data Augmented Markov Chain Monte Carlo (DA-MCMC), faces two critical bottlenecks:

  1. The Imbalance Problem: In datasets where certain outcomes are rare (e.g., click-through rates where 99% of responses are zero), DA-MCMC mixes extremely slowly. The sampler's step size becomes negligible relative to the posterior space, leading to unreliable estimates.
  2. The Scalability Problem: The computational cost of DA-MCMC scales linearly with the number of observations ($n$). As datasets reach millions of records, this linear scaling becomes computationally prohibitive.

Bayesian Mosaic addresses these challenges by constructing a "surrogate posterior" that is both computationally efficient and theoretically sound.

The Bayesian Mosaic Framework

The core innovation of Bayesian Mosaic is the decomposition of the joint posterior into manageable, parallelizable pieces. The framework categorizes parameters into two types:

  • Knots: Parameters characterizing univariate marginal distributions (the behavior of individual variables).
  • Tiles: Parameters characterizing bivariate marginals (the pairwise relationships between variables).

By multiplying these component posteriors, the authors create a sparse dependence structure that can be represented as a Directed Acyclic Graph (DAG). This structure allows for a two-step parallel sampling strategy:

  1. Knot Sampling: All "knot" parameters are sampled independently and in parallel.
  2. Tile Sampling: The knot samples are plugged into the "tile" distributions, and relationship parameters are sampled independently.

Because these components only require evaluating one or two variables at a time, the method can utilize efficient numerical integration. This removes the need for the latent variable augmentation that slows down traditional MCMC.

Theoretical and Computational Advantages

Consistency and Normality

The mathematical validity of Bayesian Mosaic rests on the fact that the score functions of the marginal densities are unbiased. This ensures that the surrogate posterior remains consistent and asymptotically normal, meaning the estimates converge to the true values as the sample size increases.

Complexity and Cardinality

A significant advantage of Bayesian Mosaic for discrete data is that its computational complexity scales with the number of unique values (cardinality) rather than the total number of observations. In many common models, this shifts the complexity from $O(n)$ to $O(\log n)$, allowing the method to handle massive datasets that would stall traditional samplers.

Structural Parallelism

Unlike other parallel MCMC approaches that partition data into chunks, Bayesian Mosaic parallelizes the parameter space itself. This structural parallelism is more robust for models where global dependencies are difficult to split geographically or temporally.

Experimental Results

Simulation Studies

The authors tested the framework against DA-MCMC using two synthetic scenarios:

  • Imbalanced Poisson Mixture: In a dataset with 90% zeros, Bayesian Mosaic significantly outperformed DA-MCMC in Mean Square Error (MSE). Crucially, Bayesian Mosaic provided accurate uncertainty quantification with 95% empirical coverage, whereas DA-MCMC’s coverage dropped as low as 24% due to poor mixing.
  • Balanced Scalability: In a rounded multivariate Gaussian simulation, Bayesian Mosaic achieved accuracy comparable to DA-MCMC but demonstrated vastly superior computational scaling as the sample size increased.

Real-World Application: DBLP Citation Network

The method was applied to a DBLP dataset containing approximately 80,000 papers to analyze the citation trends of 11 prominent machine learning researchers. The model successfully captured the shifting landscape of the field. Specifically, it identified that while the citation log-odds for many established researchers trended downward over time, Deep Learning pioneers like Yoshua Bengio and Yann LeCun showed a distinct upward trend, reflecting the field's rapid expansion in the 2010s.

Limitations and Future Work

While powerful, Bayesian Mosaic has areas for refinement:

  • Uncertainty Underestimation: Using posterior means for knots during tile sampling (a faster variant) can lead to underestimated uncertainty in the relationship parameters.
  • Positive Definiteness: In Latent Gaussian models, the covariance matrix must be positive definite. Since tiles are sampled independently, the resulting matrix may require a post-processing projection step to ensure validity.
  • Dependence Structures: Current theoretical proofs focus on i.i.d. data. Extending these proofs to complex time-series or spatial dependencies is a primary goal for future research.

Summary updated

Abstract

This paper proposes Bayesian mosaic, a parallelizable composite posterior, for scalable Bayesian inference on a broad class of multivariate discrete data models. Sampling is embarrassingly parallel since Bayesian mosaic is a multiplication of component posteriors that can be independently sampled from. Analogous to composite likelihood methods, these component posteriors are based on univariate or bivariate marginal densities. Utilizing the fact that the score functions of these densities are unbiased, we show that Bayesian mosaic is consistent and asymptotically normal under mild conditions. Since the evaluation of univariate or bivariate marginal densities can rely on numerical integration, sampling from Bayesian mosaic bypasses the traditional data augmented Markov chain Monte Carlo (DA-MCMC) method, which has a provably slow mixing rate when data are imbalanced. Moreover, we show that sampling from Bayesian mosaic has better scalability to large sample size than DA-MCMC. The method is evaluated via simulation studies and an application on a citation count dataset.
BibTeX
@misc{wang2018bayesian,
  author = {Ye Wang and David B. Dunson},
  title = {{Bayesian Mosaic: Parallelizable Composite Posterior}},
  year = {2018},
  eprint = {1804.00353},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.00353},
}
Figure