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
In fields such as macroeconomics and public health, researchers frequently encounter "sparse" databases—large tables with hundreds of variables where a significant portion of the entries are missing. Traditional statistical tools often fail in these environments due to three primary challenges. First, most methods require complete data, necessitating imputation steps that can introduce significant bias. Second, standard tests like $R^2$ assume linear relationships, missing complex, non-linear dependencies. Finally, as the number of variables grows, the risk of "false positives"—spurious correlations arising by chance—increases dramatically.
This paper introduces a robust Bayesian framework designed to detect complex dependencies in these messy datasets. By integrating non-parametric Bayesian modeling with information theory, the authors provide a method to estimate the posterior distribution of Conditional Mutual Information (CMI), allowing for a clear distinction between true predictive relationships and coincidental correlations.
Methodology: BayesDB and CrossCat
The core of this approach is the BayesDB probabilistic programming platform, which utilizes a model called CrossCat. CrossCat is a Bayesian non-parametric method that automatically learns a partition of variables, grouping them into independent blocks. Within each block, a Dirichlet Process Mixture Model (DPMM) captures the joint distribution of the variables.
A key innovation in this framework is the use of structural optimization. If the CrossCat model learns that two variables belong to different independent blocks, the CMI is structurally zero. This allows the system to bypass expensive calculations for many pairs of variables, significantly increasing computational efficiency during exploratory data analysis.
CMI as a Random Variable
Rather than calculating a single point estimate or "score" for dependency, the authors treat Conditional Mutual Information (CMI) as a random variable. They use Monte Carlo integration to estimate its posterior distribution. This approach provides a measure of uncertainty: if data is sparse, the resulting distribution will be wide, signaling that the relationship is uncertain.
This distributional focus allows the method to handle heterogeneity naturally. Because the underlying CrossCat model is non-parametric, it can process a mix of data types—categorical, integer, and real-valued—without requiring manual normalization or pre-processing.
Experimental Evaluation
The paper evaluates the approach using several benchmarks:
- Synthetic Benchmarks: Canonical Bayesian network structures (common-cause and common-effect) were used to verify the model's ability to identify marginal and conditional (in)dependencies.
- Gapminder Dataset: A real-world database of approximately 320 macroeconomic indicators for 200 countries. This dataset features a ~35% missing data rate, making it a rigorous test for the framework's robustness.
- Mathematics Marks: A smaller dataset used to demonstrate "context-specific" independence, where variables are related only under specific conditions (e.g., 'analysis' scores predicting 'vectors' scores only within certain 'algebra' score ranges).
Key Results and Insights
The experimental results demonstrate that the proposed method offers superior sensitivity and specificity compared to standard baselines like $R^2$ and the Hilbert-Schmidt Independence Criterion (HSIC).
On the Gapminder data, the model successfully suppressed spurious correlations, such as the link between "personal computers" and "earthquake deaths," by assigning them a low probability of dependency. Conversely, it detected significant non-linear relationships, such as the link between "GDP per working hour" and "urban population," which linear methods failed to flag. Furthermore, the CrossCat optimization enabled the system to process 1,000 queries on an 8-dimensional dataset in seconds, a task that would take significantly longer using standard mixture models.
Conclusion
This work provides a powerful tool for exploratory data analysis in high-dimensional, sparse settings. By treating dependency detection as a Bayesian inference problem, it offers a principled way to manage uncertainty and missing data. Future work includes scaling the method to datasets with tens of thousands of variables and integrating it with causal discovery algorithms to determine the directionality of detected relationships.
Summary updated