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:
- 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.
- 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:
- Knot Sampling: All "knot" parameters are sampled independently and in parallel.
- 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