Bayesian Probabilistic Numerical Integration with Tree-Based Models

Harrison Zhu, Xing Liu, Ruya Kang, Zhichao Shen, Seth Flaxman, François-Xavier Briol

Introduction: The Limits of Gaussian Processes in Bayesian Quadrature

Numerical integration—calculating the area under a curve for functions that lack a closed-form solution—is a cornerstone of modern statistics and machine learning. Bayesian Quadrature (BQ) treats this as an inference problem: by placing a prior over the function and observing sample points, we can compute a posterior distribution over the integral's value. This approach provides a principled way to quantify uncertainty in our estimates.

Historically, the "gold standard" prior for BQ has been the Gaussian Process (GP). While mathematically elegant, GPs suffer from three major "curses" in practice:

  1. The Smoothness Curse: GPs typically assume functions are smooth. If the integrand has jumps or discontinuities, GPs produce poor predictions and unreliable uncertainty estimates.
  2. The Computational Curse: GP inference scales cubically ($O(n^3)$) with the number of data points, making it prohibitively slow for large-scale problems.
  3. The Dimensionality Curse: GP-based integration rarely scales beyond 10 dimensions without significant manual tuning or restrictive assumptions.

To overcome these limitations, researchers have introduced BART-Int, a novel Bayesian probabilistic numerical integration method that replaces traditional GP priors with Bayesian Additive Regression Trees (BART).

The BART-Int Approach

BART-Int leverages a "sum-of-trees" structure to model the integrand.

  • Tree-Based Modeling: BART is an ensemble method that represents a function as a sum of many shallow decision trees. Because trees naturally partition the input space into discrete boxes, they are inherently better at modeling step functions and discontinuities than smooth GP kernels. They don't try to smooth over a jump; they simply place a split there.
  • Integration via MCMC: Unlike GPs, the posterior for a BART model isn't available in closed form. BART-Int uses Markov Chain Monte Carlo (MCMC) to sample from the posterior of the tree structures. To calculate the integral, the algorithm integrates each sampled tree ensemble against the target measure (which is straightforward for piecewise constant tree functions) and averages the results.
  • Sequential Design: BART-Int incorporates an active learning scheme. Instead of picking points at random, it can adaptively select new evaluation points where the model's uncertainty is highest, maximizing sample efficiency.

Key Advantages and Performance

Computational Efficiency

One of the most significant breakthroughs of BART-Int is its computational scaling. The cost is roughly $O(Tmn)$ (where $T$ is the number of trees and $m$ is MCMC iterations). This means it scales linearly with respect to the number of data points $n$, a massive improvement over the $O(n^3)$ cost of GPs.

Computation time comparison between GP and BART as sample size grows.

Empirical tests show that as $n$ grows, the runtime for GPs explodes, while BART-Int remains highly manageable. This enables integration with thousands of points where GPs would simply fail to run.

Handling Discontinuities and High Dimensions

The authors evaluated BART-Int against standard Monte Carlo (MI) and GP-BQ using several datasets, including the Genz functions (a standard set of synthetic benchmarks designed to test integration challenges like oscillation and discontinuity).

Performance comparison on Genz benchmark functions across different dimensions and function types.
  • Discontinuity Performance: On the "Step" and "Discontinuous" Genz functions, BART-Int achieved significantly lower Mean Absolute Percentage Error (MAPE) than GP-BQ.
  • High-Dimensional Scaling: BART naturally handles high-dimensional spaces by only splitting on relevant variables, performing automatic feature selection. In 10-dimensional Genz tests, BART-Int outperformed GP-BQ across all function types.
  • Real-World Application: In a 24-dimensional Bayesian Survey Design problem using US Census data, BART-Int provided the most accurate estimates and more realistic uncertainty intervals, whereas the GP-BQ model appeared overconfident at incorrect values.

Limitations and Future Work

While BART-Int is a powerful new tool, it is not a universal silver bullet. For very smooth, low-dimensional functions, GP-BQ remains the superior choice, as BART’s step-function nature is a poor fit for perfectly smooth curves (like a parabola). Additionally, while the empirical integration results are strong, the theoretical ergodicity of BART—how well the MCMC explores the massive space of all possible trees—remains an open question in the broader statistics community.

Future extensions may explore "Soft-BART" (using sigmoids instead of hard splits) to bridge the gap for smooth functions, and modifying tree models to handle categorical variables natively without requiring one-hot encoding.

Summary updated

Abstract

Bayesian quadrature (BQ) is a method for solving numerical integration problems in a Bayesian manner, which allows users to quantify their uncertainty about the solution. The standard approach to BQ is based on a Gaussian process (GP) approximation of the integrand. As a result, BQ is inherently limited to cases where GP approximations can be done in an efficient manner, thus often prohibiting very high-dimensional or non-smooth target functions. This paper proposes to tackle this issue with a new Bayesian numerical integration algorithm based on Bayesian Additive Regression Trees (BART) priors, which we call BART-Int. BART priors are easy to tune and well-suited for discontinuous functions. We demonstrate that they also lend themselves naturally to a sequential design setting and that explicit convergence rates can be obtained in a variety of settings. The advantages and disadvantages of this new methodology are highlighted on a set of benchmark tests including the Genz functions, on a rare-event simulation problem and on a Bayesian survey design problem.
BibTeX
@inproceedings{zhu2020bayesian,
  author = {Harrison Zhu and Xing Liu and Ruya Kang and Zhichao Shen and Seth Flaxman and François-Xavier Briol},
  title = {{Bayesian Probabilistic Numerical Integration with Tree-Based Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=OnLvGHtoGbu},
}
Figure