  High dimensional integration is essential to many areas of science, ranging
from particle physics to Bayesian inference. Approximating these integrals is
hard, due in part to the difficulty of locating and sampling from regions of
the integration domain that make significant contributions to the overall
integral. Here, we present a new algorithm called Tree Quadrature (TQ) that
separates this sampling problem from the problem of using those samples to
produce an approximation of the integral. TQ places no qualifications on how
the samples provided to it are obtained, allowing it to use state-of-the-art
sampling algorithms that are largely ignored by existing integration
algorithms. Given a set of samples, TQ constructs a surrogate model of the
integrand in the form of a regression tree, with a structure optimised to
maximise integral precision. The tree divides the integration domain into
smaller containers, which are individually integrated and aggregated to
estimate the overall integral. Any method can be used to integrate each
individual container, so existing integration methods, like Bayesian Monte
Carlo, can be combined with TQ to boost their performance. On a set of
benchmark problems, we show that TQ provides accurate approximations to
integrals in up to 15 dimensions; and in dimensions 4 and above, it outperforms
simple Monte Carlo and the popular Vegas method.
