The Kernel Interaction Trick: Fast Bayesian Discovery of Pairwise Interactions in High Dimensions

By Raj Agrawal, Jonathan Huggins, Brian L. Trippe, Tamara Broderick. 2019

30 citations recorded by the source corpus.

Discovering interaction effects on a response of interest is a fundamental problem faced in biology, medicine, economics, and many other scientific disciplines. In theory, Bayesian methods for discovering pairwise interactions enjoy many benefits such as coherent uncertainty quantification, the ability to incorporate background knowledge, and desirable shrinkage properties. In practice, however, Bayesian methods are often computationally intractable for even moderate-dimensional problems. Our key insight is that many hierarchical models of practical interest admit a particular Gaussian process (GP) representation; the GP allows us to capture the posterior with a vector of O(p) kernel hyper-parameters rather than O(p^2) interactions and main effects. With the implicit representation, we can run Markov chain Monte Carlo (MCMC) over model hyper-parameters in time and memory linear in p per iteration. We focus on sparsity-inducing models and show on datasets with a variety of covariate behaviors that our method: (1) reduces runtime by orders of magnitude over naive applications of MCMC, (2) provides lower Type I and Type II error relative to state-of-the-art LASSO-based approaches, and (3) offers improved computational scaling in high dimensions relative to existing Bayesian and LASSO-based approaches.

Subfields: Artificial Intelligence, Materials Chemistry, Molecular Biology, Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Neeraj Pradhan
2. Du Phan
3. Martin Jankowiak
4. Andrew Gordon Wilson
5. Wesley J. Maddox

In Probabilistic & Bayesian Methods

1. Neeraj Pradhan
2. Du Phan
3. Martin Jankowiak
4. Andrew Gordon Wilson
5. Wesley J. Maddox

Citations in the corpus

• Composable Effects for Flexible and Accelerated Probabilistic Programming in NumPyro (2019, methodology): “We use three benchmark models: i) a Hidden Markov Model (HMM) on a small synthetic dataset; ii) logistic regression on the Forest CoverType dataset [20]; and iii) a sparse kernel interaction model (SKIM) [21] on synthetic datasets with varying dimensionalities.”