Bayesian Optimization is a search algorithm for finding the best place to sample for an expensive to calculate function. It usually uses a small sample of points to shepherd a collection tens of distinct smooth curves. Then for each point in the domain, you calculate the variance in the values given by the curves. Because the curves converge at known points, and tend to spread out in between known points, the algorithm can balance prioritizing its search between exploiting the best values found so far, against the value of exploring new areas to gather more information. Additionally, this balance can be tuned with a single input parameter.
The exploratory opt file was inspired by bayesian optimization, but instead of calculating the spread of a collection of smooth function, it just fits any one of several convex functions to pass through each pair of adjacent sampled points. The resulting piecewise function can be used to achieve a similar overall result that balances exploiting the best samples found so far against exploring unknown areas, again tunable with a single parameter.
#Further work to do:
- Benchmark the Exploratory Optimization against Bayesian Optimization, boh for time and memory complexity.
- This method requires having the samples at the outer bounds of the domain space, since it needs to compute a function between two known points. I'd like to find a way to modify it to not need this if possible.
- This implementation currently only applies to one dimensional data in a discrete domain, and I'd like to expand it to work for n dimensions and for continuous space.
- It currently outputs a new iteration of the plot, which I would like to change to an animation that is easier to use.
To run this program, you just need to invoke it from the command line with python "path/to/file/exploratory_opt.py"
You can also provide optional command line arguments that let the user to change the size of the domain, the complexity of the standin target function, and the number of iteration.