Detecting Dependencies in Sparse, Multivariate Databases Using Probabilistic Programming and Non-parametric Bayes

Feras Saad, Vikash Mansinghka

Abstract: Datasets with hundreds of variables and many missing values are commonplace. In this setting, it is both statistically and computationally challenging to detect true predictive relationships between variables and also to suppress false positives. This paper proposes an approach that combines probabilistic programming, information theory, and non-parametric Bayes. It shows how to use Bayesian non-parametric modeling to (i) build an ensemble of joint probability models for all the variables; (ii) efficiently detect marginal independencies; and (iii) estimate the conditional mutual information between arbitrary subsets of variables, subject to a broad class of constraints. Users can access these capabilities using BayesDB, a probabilistic programming platform for probabilistic data analysis, by writing queries in a simple, SQL-like language. This paper demonstrates empirically that the method can (i) detect context-specific (in)dependencies on challenging synthetic problems and (ii) yield improved sensitivity and specificity over baselines from statistics and machine learning, on a real-world database of over 300 sparsely observed indicators of macroeconomic development and public health.

Introduction

Modern data science frequently encounters "sparse, multivariate" databases—large tables with hundreds of columns and significant missing data. Identifying genuine predictive relationships in such environments is difficult due to three primary factors: poor data quality requiring complex imputation, non-linear dependencies that standard tests miss, and the high risk of spurious correlations as variable counts increase. Calculating rigorous measures like Conditional Mutual Information (CMI) for every pair becomes computationally prohibitive at scale. This research introduces a framework to navigate these challenges automatically, providing a robust filter for data exploration.

Methodology

The proposed approach integrates three core components to handle high-dimensional, messy data:

  1. Non-parametric Bayes (CrossCat): Instead of assuming fixed distributions, the system uses CrossCat to automatically partition variables into "blocks" of related features. Structural independence is inferred if variables reside in different blocks.
  2. Probabilistic Programming (BayesDB): Users interact with the model via the Bayesian Query Language (BQL), an SQL-like interface that abstracts the complexity of Bayesian inference.
  3. CMI as a Random Variable: Unlike traditional point estimates, CMI is treated as a derived random variable. By analyzing the posterior distribution of CMI, the system quantifies both the strength of a relationship and the model's uncertainty.
Workflow for computing posterior distributions of the CMI using BayesDB and CrossCat.

A critical technical innovation is the CrossCat-Cmi algorithm (Algorithm 4a). It leverages the model's learned structure to optimize calculations. If CrossCat determines two variables are structurally independent, the system bypasses expensive Monte Carlo simulations, enabling significant speedups.

Empirical Evaluation

The framework was evaluated on synthetic Bayes Nets to verify its ability to identify marginal and context-specific independencies. It was also applied to the Gapminder dataset, which contains approximately 320 indicators for 200 countries with a 35% missing data rate.

The method demonstrated several key advantages:

  • Structural Sparsity: By identifying unrelated variables early, the system avoids unnecessary computation, scaling effectively to high-dimensional data.
  • Context-Specific Detection: The model can identify dependencies that only manifest under specific conditions (e.g., when a third variable is held at a certain value).
  • Robustness to Spuriousness: In the Gapminder data, the method correctly identified "personal computers" and "earthquake affected" as independent, whereas standard $R^2$ correlation flagged a false relationship due to outliers.
  • Causal Alignment: The model recovered complex economic dependencies, such as the decoupling of "imports" and "exports" when conditioned on "net trade balance."
Posterior distributions of MI and CMI across various contexts.

Discussion and Future Work

Treating CMI as a distribution allows users to set "predictive significance" thresholds (e.g., CMI > 0.1 nats) rather than relying solely on p-values. This provides a more nuanced understanding of data relationships than traditional frequentist methods.

However, the accuracy of CMI estimates depends on the underlying joint density estimator. If the non-parametric model fails to capture a subtle pattern, the CMI estimate will be affected. Future work aims to scale the approach to tens of thousands of variables and integrate these CMI estimators into advanced causal discovery algorithms to determine the directionality of relationships.

Summary updated

Abstract

Datasets with hundreds of variables and many missing values are commonplace. In this setting, it is both statistically and computationally challenging to detect true predictive relationships between variables and also to suppress false positives. This paper proposes an approach that combines probabilistic programming, information theory, and non-parametric Bayes. It shows how to use Bayesian non-parametric modeling to (i) build an ensemble of joint probability models for all the variables; (ii) efficiently detect marginal independencies; and (iii) estimate the conditional mutual information between arbitrary subsets of variables, subject to a broad class of constraints. Users can access these capabilities using BayesDB, a probabilistic programming platform for probabilistic data analysis, by writing queries in a simple, SQL-like language. This paper demonstrates empirically that the method can (i) detect context-specific (in)dependencies on challenging synthetic problems and (ii) yield improved sensitivity and specificity over baselines from statistics and machine learning, on a real-world database of over 300 sparsely observed indicators of macroeconomic development and public health.
BibTeX
@inproceedings{saad2017detecting,
  author = {Feras Saad and Vikash Mansinghka},
  title = {{Detecting Dependencies in Sparse, Multivariate Databases Using Probabilistic Programming and Non-parametric Bayes}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=HbdQYVFqDY},
}
Figure