BARK: A Fully Bayesian Tree Kernel for Black-box Optimization

Toby Boyne, Jose Pablo Folch, Robert Matthew Lee, Behrang Shafei, Ruth Misener · 2025

Read BARK: A Fully Bayesian Tree Kernel for Black-box Optimization by Toby Boyne, Jose Pablo Folch, Robert Matthew Lee, Behrang Shafei, Ruth Misener (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05574.txt.

Introduction

Toby Boyne and co-authors published this study in 2025. It builds BARK, a tool for black-box optimization, where a costly function must be tuned by trial. The tool starts from BART, a model that fits data with ensembles of decision trees. BARK adds a kernel built on how much sampled trees agree. That yields full probability curves over functions, not just single fits.

With those curves, the team can build the choice rules that guide the search for better inputs. The tree view also handles mixed input types, where older smooth models struggle. Sampling explores not just function values but the tree shapes themselves. On synthetic and applied test problems, BARK performed strongly. The authors credit the fully Bayesian model plus their global search over it.

Catalog record

CREATORToby Boyne, Jose Pablo Folch, Robert Matthew Lee, Behrang Shafei, Ruth Misener
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05574

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BARK: A Fully Bayesian Tree Kernel for Black-box Optimization Toby Boyne, Jose Pablo Folch, Robert Matthew Lee, Behrang Shafei, Ruth Misener Abstract We perform Bayesian optimization using a Gaussian process perspective on Bayesian Additive Regression Trees (BART). Our BART Kernel (BARK) uses tree agreement to define a posterior over piecewise-constant functions, and we explore the space of tree kernels using a Markov chain Monte Carlo approach. Where BART only samples functions, the resulting BARK model obtains samples of Gaussian processes defining distributions over functions, which allow us to build acquisition functions for Bayesian optimization. Our tree-based approach enables global optimization over the surrogate, even for mixed-feature spaces. Moreover, where many previous tree-based kernels provide uncertainty quantification over function values, our sampling scheme captures uncertainty over the tree structure itself. Our experiments show the strong performance of BARK on both synthetic and applied benchmarks, due to the combination of our fully Bayesian surrogate and the optimization procedure. 1 Introduction Bayesian optimization (BO), which finds the optimal conditions of expensive-to-evaluate black-box functions ( Frazier, 2018 ; Shahriari et al., 2015 ; Wang et al., 2023c ) , is a leading approach for data-driven design of experiments. BO applications range from molecule design ( Griffiths et al., 2024 ) to battery and chemical reaction optimization ( Folch et al., 2023 ) . BO relies on a probabilistic surrogate modeling our belief and uncertainty about the black-box function. One class of surrogates are Gaussian processes (GPs), flexible models giving well-calibrated uncertainty estimates ( Rasmussen & Williams, 2005 ) . The most important hyperparameter choice when using a GP is the kernel, which fully defines the model’s covariance structure. Popular kernels such as the squared exponential and Matérn kernels are limited to continuous inputs and assume function stationarity. Tree regression provides a flexible model which is popular due to strong empirical performance, natural regularization and interpretability ( Hill et al., 2020 ; Loh, 2011 ) . Trees allow for mixed inputs and can model non-stationary functions, with hierarchical dependencies. A tree model defines a sequence of domain splits. A single input will go through all the splits until a leaf node is reached which assigns a value to the predictive model. A forest is an ensemble of trees, where each tree is regularized to be a weak learner to avoid overfitting. Despite their performance in regression tasks, tree models have limited application to BO since they lack explicit uncertainty quantification in their predictions, instead relying on empirical variance. Given an ensemble of m trees, and two inputs \mathbf{x} and \mathbf{x}^{\prime} , we can define a function representing how often the trees agree on the inputs belonging to the same leaf. This notion of tree agreement can be used to construct a valid kernel for use in a GP ( Balog et al., 2016 ; Davies & Ghahramani, 2014 ; Thebelt et al., 2022a ) . This allows us to use tree models in applications which require well-calibrated estimates such as Bayesian optimization. Tree kernels for model fitting and BO have previously been explored ( Balog et al., 2016 ; Thebelt et al., 2022a ) , but they have always used a two-step fitting process: first, a tree model is fitted on the data, and then the GP is trained using the tree kernel defined by the tree model. While this heuristic gives good results in a variety of benchmarks, it is not principled and hence potentially sub-optimal. Since the tree structure has an infinite number of parameters, it is at risk of overfitting when optimizing the log-marginal likelihood ( Rasmussen & Williams, 2005 ) . To overcome this challenge, we take inspiration from Bayesian tree methods which impose a prior on the tree structure. We obtain a posterior over the tree structure, from which we sample using Markov chain Monte Carlo (MCMC). {forest} {forest} {forest} {forest} {forest} {forest} MCMC \approx\int\alpha(x|T)p(T)dT Figure 1 : BARK uses MCMC to create samples of forests, each of which define a Gaussian process. We can then use all the GPs to obtain posterior samples of the process, to marginalize over the tree model uncertainty for the acquisition function. We motivate using tree-kernels by exploiting the strong modeling power of tree-based approaches, which can be used for mixed input spaces. Moreover, we can formulate acquisition functions with these tree models as optimization problems that can be solved globally, where gradient-based methods often struggle with discrete inputs. Contributions. Our work achieves tree-based GP BO through improved Bayesian modeling. Our main contributions can be summarized as: • We propose a fully Bayesian method for training tree Gaussian processes through Markov chain Monte Carlo, by exploiting connections between Bayesian tree models and Gaussian processes with tree kernels. We provide a brief summary of our approach in Fig. 1 . • We provide a computationally efficient training algorithm allowing for scalability and accelerating up the Markov chain sampling procedure. • We provide an empirical analysis of the benefits of our approach, showing its regression ability and achieving state-of-the-art results in a variety of Bayesian optimization benchmarks. 2 Related Work The relationship between Bayesian tree models and GPs has a long history. Chipman et al. (1998) ; Chipman et al. (2010) develop a Bayesian approach for fitting classification and regression trees (BART), which samples a tree structure, and leaf values with a Gaussian prior. Further work by several authors explores using GPs as tree leaf nodes ( Gramacy & Lee, 2008 ; Maia et al., 2024 ; Wang et al., 2023a ) , or within other partitions ( Luo et al., 2021 ; Luo et al., 2023 ) . These trees, or other spatial partitioning strategies, allow non-stationary models that may be effective for Bayesian optimization ( Eriksson & Jankowiak, 2021 ; Eriksson et al., 2019 ; Papenmeier et al., 2022 ; Wang et al., 2020 ; Ziomek & Bou Ammar, 2023 ) . The use of tree models as kernels has been investigated empirically ( Thebelt et al., 2022a ) and theoretically ( Scornet, 2016 ) . Balog et al. (2016) consider tree kernels in the context of Mondrian processes and show that the Mondrian kernel approximates the Laplace kernel while providing a connection to random forests. Linero (2017) shows that, under certain priors, BART converges to a GP with a Laplace kernel as the number of trees increases. Linero (2017) also mentions that the Laplace kernel GP is sub-optimal in practice compared to the tree model which has a lower computational cost, and better generalization. Bayesian optimization over mixed feature spaces has been extensively researched in recent years. Techniques include using RKHS embeddings ( Buathong et al., 2020 ) , diffusion kernels ( Deshwal et al., 2021 ) , multi-armed bandit style optimization ( Ru et al., 2020 ) , and a plethora of other methods ( Garrido-Merchán & Hernández-Lobato, 2020 ; Häse et al., 2021 ; Daxberger et al., 2021 ; Daulton et al., 2022 ; Deshwal et al., 2023 ; Wan et al., 2021 ) and benchmarks ( Dreczkowski et al., 2023 ) . This surge in interest also includes the provision of software packages for mixed feature BO such as SMAC ( Lindauer et al., 2022 ) and scikit-optimize ( Head

Read the complete text