Bayesian Algorithm Execution (BAX)
Code for the paper:
Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information
Willie Neiswanger, Ke Alexander Wang, Stefano Ermon
International Conference on Machine Learning (ICML), 2021
arXiv:2104.09460
One-sentence summary
Extending Bayesian optimization from estimating global optima to
estimating other function properties defined by the output of algorithms.
Abstract
In many real world problems, we want to infer some property of an expensive black-box
function f, given a budget of T function evaluations. One example is budget constrained
global optimization of f, for which Bayesian optimization is a popular method. Other
properties of interest include local optima, level sets, integrals, or graph-structured
information induced by f. Often, we can find an algorithm A to compute the desired
property, but it may require far more than T queries to execute. Given such an A, and a
prior distribution over f, we refer to the problem of inferring the output of A using T
evaluations as Bayesian Algorithm Execution (BAX).
To tackle this problem, we present a procedure, InfoBAX, that sequentially chooses
queries that maximize mutual information with respect to the algorithm's output.
Applying this to Dtra's algorithm, for instance, we infer shortest paths in synthetic
and real-world graphs with black-box edge costs. Using evolution strategies, we yield
variants of Bayesian optimization that target local, rather than global, optima. On
these problems, InfoBAX uses up to 500 times fewer queries to f than required by the
original algorithm. Our method is closely connected to other Bayesian optimal
experimental design procedures such as entropy search methods and optimal sensor
placement using Gaussian processes.
Installation
This repo requires Python 3.6+. To install Python dependencies, cd into this repo and
run:
$ pip install -r requirements/requirements.txt
$ pip install -r requirements/requirements_gpfs.txt
Note that this installs dependencies for
GPflowSampling, which our implementation
uses to efficiently run algorithms on GP posterior function samples.
For some functionality, you'll also need to compile a Stan model
by running:
$ python bax/models/stan/compile_models.py
Examples
[WIP] More examples are in the process of being merged into this branch. Note that
the following API and functionality may undergo changes, as this library is still in the
early stages.
First make sure this repo directory is on the PYTHONPATH, e.g. by running:
$ source shell/add_pwd_to_pythonpath.sh
Example 1: Estimating shortest paths in graphs
For a demo on a 10x10 grid graph, run:
$ python examples/dijkstra/bax_grid10_viz_simple_demo.py
To produce images for an animation on a 20x20 grid graph, run:
$ python examples/dijkstra/bax_grid20_animation.py
Example 2: Bayesian local optimization
For a demo on a two-dimensional optimization problem, run:
$ python examples/branin/bax_viz2d_simple_demo.py
Example 3: Top-k estimation
For a demo on a top-10 estimation task over a discrete set of points, run:
$ python examples/topk/bax_simple_demo.py
Citation
Please cite our paper if you find this project
helpful:
@inproceedings{neiswanger2021bayesian,
title = {Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information},
author = {Neiswanger, Willie and Wang, Ke Alexander and Ermon, Stefano},
booktitle = {International Conference on Machine Learning},
year = {2021},
organization = {PMLR}
}
