Divide and Recombine for Large and Complex Data: Model Likelihood Functions using MCMC

Qi Liu, Anindya Bhadra, William S. ClevelandarXiv 2018 · DOI · arXiv

Abstract

In Divide & Recombine (D&R), big data are divided into subsets, each analytic method is applied to subsets, and the outputs are recombined. This enables deep analysis and practical computational performance. An innovate D&R procedure is proposed to compute likelihood functions of data-model (DM) parameters for big data. The likelihood-model (LM) is a parametric probability density function of the DM parameters. The density parameters are estimated by fitting the density to MCMC draws from each subset DM likelihood function, and then the fitted densities are recombined. The procedure is illustrated using normal and skew-normal LMs for the logistic regression DM.

Introduction

In the era of "Big Data," calculating a likelihood function—the backbone of statistical inference—becomes a computational nightmare. When datasets are too large to fit on a single machine, researchers often turn to Divide and Recombine (D&R) strategies: split the data, analyze subsets in parallel, and merge the results.

This paper introduces an innovative D&R framework to estimate likelihood functions for massive datasets by modeling subset-level MCMC draws with Skew-Normal distributions. By moving beyond simple Gaussian approximations, the authors achieve significantly higher accuracy in capturing complex posterior shapes while reducing computation time by up to 80-fold compared to traditional multi-machine MCMC methods.

Methodology: Likelihood Modeling (LM)

A major gap exists in how we currently "recombine" data. Most existing methods assume that subset likelihoods are approximately Normal (Gaussian). While this is theoretically true for infinitely large samples, it often fails in practice. Subsets might be too small, or the underlying data model might be too complex, leading to skewed likelihood surfaces. If the subset models are wrong, the final recombined "all-data" likelihood will be biased.

Conceptual framework of the Divide and Recombine (D&R) procedure for likelihood modeling.

The authors propose a procedure called Likelihood Modeling (LM) within the D&R framework, as illustrated in the figure above. The process follows these steps:

  1. Divide: Split the large dataset into $R$ subsets.
  2. Model: For each subset, instead of just calculating a point estimate, run a Markov Chain Monte Carlo (MCMC) sampler to generate draws from the subset's likelihood function.
  3. Fit: Fit a parametric density function to these MCMC draws. Crucially, the Skew-Normal (SN) family is introduced as a flexible alternative to the standard Normal distribution, capturing asymmetry in subset likelihoods.
  4. Recombine: Because the subsets are independent, the full-data likelihood is the product of these fitted subset densities.
  5. Simplified Version (SSN): For cases with a very large number of subsets, a simplified version averages parameters to reduce the computational overhead of the recombination step.

To validate these models, the authors introduce the Contour Probability Algorithm (CPA). This diagnostic tool allows researchers to visualize and quantify how closely an approximate multivariate density matches the "true" density without needing to calculate difficult normalizing constants.

Evaluation and Results

The method was evaluated using both real-world and synthetic data:

  • 2016 California Democratic Primary Exit Polls: Data from 58 counties used to predict Hillary Clinton’s vote share. This demonstrated how the Skew-Normal model captures inherent skewness in small-sample hierarchical models.
  • Simulated Logistic Regression Data: Large-scale synthetic datasets (up to 600,000 observations) with varying covariates to test scalability.

Key Findings

  • Accuracy: In the Exit Poll analysis, the Skew-Normal Moment Matching (SNMM) method stayed significantly closer to the true posterior than both standard Normal and MLE-based methods.
  • Speed: In a head-to-head test on a 10-node cluster, the proposed Likelihood Modeling took roughly 2 hours, whereas a naive multi-machine MCMC approach took over 164 hours—an 80x speedup.
  • Scalability: The simplified SSN model showed that as the number of subsets ($R$) increases, the computational workload remains manageable without significant loss in approximation quality.

Discussion and Future Work

The "aha moment" of this research is demonstrating that even when the full-data likelihood looks Gaussian, the individual "building block" subsets often do not. Using a Normal approximation on skewed subsets leads to a shifted and inaccurate final result. The Skew-Normal distribution serves as a robust "drop-in" upgrade because it includes the Normal distribution as a special case (when the shape parameter $\alpha = 0$).

Furthermore, by treating likelihood estimation as a series of independent density-fitting problems, the method is "embarrassingly parallel," making it perfectly suited for modern distributed computing architectures like Hadoop or Spark.

However, limitations remain. The current framework assumes that observations are conditionally independent (i.i.d.). Modifying the method for non-i.i.d. data, such as time-series or spatial data, is a necessary next step. Additionally, the accuracy of the subset model depends on the quality of the MCMC draws; in very high-dimensional spaces, generating an effective sample can still be time-consuming.

Summary updated

Abstract

In Divide & Recombine (D&R), big data are divided into subsets, each analytic method is applied to subsets, and the outputs are recombined. This enables deep analysis and practical computational performance. An innovate D\&R procedure is proposed to compute likelihood functions of data-model (DM) parameters for big data. The likelihood-model (LM) is a parametric probability density function of the DM parameters. The density parameters are estimated by fitting the density to MCMC draws from each subset DM likelihood function, and then the fitted densities are recombined. The procedure is illustrated using normal and skew-normal LMs for the logistic regression DM.
BibTeX
@misc{liu2018divide,
  author = {Qi Liu and Anindya Bhadra and William S. Cleveland},
  title = {{Divide and Recombine for Large and Complex Data: Model Likelihood Functions using MCMC}},
  year = {2018},
  eprint = {1801.05007},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.05007},
}
Figure