Bayesian Probabilistic Numerical Integration with Tree-Based Models

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

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, and on a Bayesian survey design problem.

Introduction

Numerical integration—calculating the integral of a function—is a fundamental task in statistics and machine learning, essential for computing posterior expectations and solving differential equations. While classical methods like Monte Carlo integration (MI) are widely used, they often lack a formal framework for quantifying uncertainty given a finite number of function evaluations. Bayesian Quadrature (BQ) addresses this by treating the unknown integrand as a stochastic process.

Traditionally, BQ has relied on Gaussian Processes (GPs). However, GPs suffer from three significant limitations: they struggle with discontinuous functions due to smoothness assumptions, their computational cost scales cubically ($O(n^3)$) with the number of evaluations, and they often fail in high-dimensional spaces. This work introduces BART-Int, a novel Bayesian integration algorithm that utilizes Bayesian Additive Regression Trees (BART) to overcome these hurdles.

Methodology

BART-Int employs BART as a prior for the integrand. BART is a sum-of-trees model that represents a function as a sum of many shallow decision trees. This structure is inherently well-suited for capturing discontinuities and step-like behavior that GPs typically smooth over.

Unlike GPs, which often allow for closed-form integration, BART requires Markov Chain Monte Carlo (MCMC) to sample the posterior distribution of the function. The authors derive a method to transform these MCMC samples into a posterior distribution for the integral itself, providing both a point estimate and a measure of uncertainty. Furthermore, BART-Int incorporates a sequential design strategy (active learning), adaptively selecting evaluation points where model uncertainty is highest. Theoretical analysis provided in the paper also establishes explicit convergence rates for the algorithm across various settings.

Experimental Evaluation

The performance of BART-Int was benchmarked against standard Monte Carlo Integration (MI) and GP-based Bayesian Quadrature (GP-BQ) using several datasets, including the Genz functions, step functions, and high-dimensional US Census data.

Performance on Benchmark Functions

In high-dimensional settings ($d=10$), BART-Int consistently outperformed GP-BQ across the Genz function suite, particularly on discontinuous and non-smooth integrands. As shown in the performance comparison below, BART-Int achieves lower error rates in many complex scenarios compared to traditional methods.

Performance comparison on Genz functions for $d=1$ and $d=10$.

Computational Efficiency

A key advantage of BART-Int is its computational scaling. While GP-BQ's runtime increases cubically with the number of points $n$, BART-Int's complexity is roughly linear ($O(n)$). This allows for much larger evaluation budgets in practical applications.

Computational scaling of GP and BART models as sample size $n$ increases.

Key Results and Discussion

BART-Int demonstrated significant advantages in high-dimensional and non-smooth problems. On a 24-dimensional US Census data survey design problem, BART-Int achieved a Mean Absolute Percentage Error (MAPE) of 4.66e-02, significantly outperforming both MI (5.68e-02) and GP-BQ (9.73e-02).

The method's robustness is also noteworthy; while GP-BQ can become overconfident in the presence of discontinuities, BART-Int's credible intervals remain reliable. However, for very smooth, low-dimensional functions, GPs still offer faster convergence. Additionally, like other tree-based models, BART-Int can struggle with extrapolation near the boundaries of the integration domain.

Conclusion

BART-Int represents a significant step forward for Bayesian Probabilistic Numerical Integration. By leveraging the flexibility and efficiency of tree-based models, it provides a robust alternative to GP-based methods, particularly for high-dimensional and non-smooth integrands where traditional approaches falter. Future work may explore "Soft-BART" to improve performance on smooth functions and direct handling of categorical variables.

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, 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