Awesome
Sequential Line Search
A C++ library for performing the sequential line search method (which is a human-in-the-loop variant of Bayesian optimization).
The core algorithm is implemented in include/sequential-line-search/*.hpp
and src/*.cpp
. This repository also contains the following example demos:
- bayesian_optimization_1d: A simple demo of the standard Bayesian optimization applied to a one-dimensional test function.
- sequential_line_search_nd: A simple demo of the sequential line search method applied to a multi-dimensional test function.
- bayesian_optimization_1d_gui: A visual demo of the standard Bayesian optimization applied to a one-dimensional test function.
- bayesian_optimization_2d_gui: A visual demo of the standard Bayesian optimization applied to a two-dimensional test function.
- preferential_bayesian_optimization_1d_gui: A visual demo of the preferential Bayesian optimization with a simple pairwise comparison query style applied to a one-dimensional test function.
- sequential_line_search_2d_gui: A visual interactive demo of the sequential line search method applied to a two-dimensional test function.
- sequential_line_search_photo: A visual interactive demo of the sequential line search method where a photograph is enhanced using six-dimensional parameters.
This library has a python binding, named pySequentialLineSearch
.
Project Web Site
https://koyama.xyz/project/sequential_line_search/
Publication
Yuki Koyama, Issei Sato, Daisuke Sakamoto, and Takeo Igarashi. 2017. Sequential Line Search for Efficient Visual Design Optimization by Crowds. ACM Trans. Graph. 36, 4, pp.48:1--48:11 (2017). (a.k.a. Proceedings of SIGGRAPH 2017) DOI: https://doi.org/10.1145/3072959.3073598
Dependencies
Required for Core Algorithms
- Eigen http://eigen.tuxfamily.org/ (
brew install eigen
/sudo apt install libeigen3-dev
) - NLopt https://nlopt.readthedocs.io/ (included via gitsubmodule)
- timer https://github.com/yuki-koyama/timer (included via gitsubmodule)
- mathtoolbox https://github.com/yuki-koyama/mathtoolbox (included via gitsubmodule)
- nlopt-util https://github.com/yuki-koyama/nlopt-util (included via gitsubmodule)
- parallel-util https://github.com/yuki-koyama/parallel-util (included via gitsubmodule)
Required for Command Line Demos
- (None)
To build these demos, the CMake variable: SEQUENTIAL_LINE_SEARCH_BUILD_COMMAND_DEMOS
should be set ON
.
Required for Visual Demos
- Qt5 http://doc.qt.io/qt-5/ (
brew install qt@5
/sudo apt install qt5-default
) - rand-util https://github.com/yuki-koyama/rand-util (included via gitsubmodule)
- tinycolormap https://github.com/yuki-koyama/tinycolormap (included via gitsubmodule)
To build these demos, the CMake variable: SEQUENTIAL_LINE_SEARCH_BUILD_VISUAL_DEMOS
should be set ON
.
Required for Photo Enhancement Demos
- Qt5 http://doc.qt.io/qt-5/ (
brew install qt@5
/sudo apt install qt5-default
) - enhancer https://github.com/yuki-koyama/enhancer (included via gitsubmodule)
- tinycolormap https://github.com/yuki-koyama/tinycolormap (included via gitsubmodule)
To build these demos, the CMake variable: SEQUENTIAL_LINE_SEARCH_BUILD_PHOTO_DEMOS
should be set ON
. They require runtime environments to support OpenGL 3.2 Core Profile and GLSL 3.3.
Required for Experimental Python Binding
- pybind11 https://github.com/pybind/pybind11 (included via gitsubmodule)
To enable python binding, the CMake variable: SEQUENTIAL_LINE_SEARCH_BUILD_PYTHON_BINDING
should be set ON
.
How to Compile and Run (C++)
We use cmake (3.3 or above) for managing the source codes. You can compile the core module and the demo applications at once by, for example,
git clone https://github.com/yuki-koyama/sequential-line-search.git --recursive
cd sequential-line-search
mkdir build
cd build
cmake ../
make
Then you can run the applications by, for example,
./demos/sequential_line_search_nd/SequentialLineSearchNd
We tested on macOS (10.15) only. We are aware that the visual demos cannot be built as it is in other OSs; some OpenGL paths etc. need to be resolved. Pull requests welcome.
How to Install (Python)
pySequentialLineSearch
is a subset of Python bindings of the C++ library. Tested on Python 3.6
, 3.7
, and 3.8
.
It can be installed via PyPI:
pip install git+https://github.com/yuki-koyama/sequential-line-search
Prerequisites
macOS
brew install cmake eigen
Ubuntu 18.04/20.04
sudo apt install cmake libeigen3-dev
Examples
Note: User interaction part is omitted from these examples.
C++
#include <iostream>
#include <sequential-line-search/sequential-line-search.hpp>
using Eigen::VectorXd;
using sequential_line_search::SequentialLineSearchOptimizer;
double AskHumanForSliderManipulation(const std::pair<VectorXd, VectorXd>& slider_ends)
{
// ...
// ...
return slider_position;
}
int main()
{
// Instantiate an optimizer
constexpr int dim = 6;
SequentialLineSearchOptimizer optimizer(dim);
// Iterate optimization steps
constexpr int num_iters = 15;
for (int i = 0; i < num_iters; ++i)
{
// Retrieve a slider space
const std::pair<VectorXd, VectorXd> slider_ends = optimizer.GetSliderEnds();
// Query slider manipulation
const double slider_position = AskHumanForSliderManipulation(slider_ends);
// Feed the slider manipulation result to the optimizer
optimizer.SubmitLineSearchResult(slider_position);
}
// Display the found solution
std::cout << optimizer.GetMaximizer() << std::endl;
return 0;
}
Python
import pySequentialLineSearch
import numpy
def ask_human_for_slider_manipulation(slider_ends):
# ...
# ...
return slider_position
def main():
optimizer = pySequentialLineSearch.SequentialLineSearchOptimizer(6)
for i in range(15):
slider_ends = optimizer.get_slider_ends()
slider_position = ask_human_for_slider_manipulation(slider_ends)
optimizer.submit_line_search_result(slider_position)
print(optimizer.get_maximizer())
if __name__ == '__main__':
main()
Supported Environments
We have tested the C++ portion of our codebase on macOS using the clang compiler and on Ubuntu 20.04 using the g++ compiler. As for the Python portion, it has been tested on versions 3.7 through 3.11.
Technical Details
Gaussian Process Kernel
- ARD Matern 5/2 kernel (default; recommended in [Snoek et al. NIPS 2011])
- ARD squared exponential kernel (used in [Koyama et al. SIGGRAPH 2017])
Gaussian Process Kernel Hyperparameters
The optimizer API takes a boolean named use_map_hyperparameters
as input. If this is true
, the optimizer calculates the kernel hyperparameters for every iteration via the MAP estimation, as described in [Koyama et al. SIGGRAPH 2017]. If this is false
, the optimizer just uses default values, making the optimization more efficient.
Finding Maximizer of Acquisition Function
Finding the global maximizer of the acquisition function is a difficult problem since it often has multiple local maxima and is high-dimensional.
This implementation offers two approaches for this problem:
- The first option is to perform DIRECT (a derivative-free global optimization algorithm) and then refine the solution using L-BFGS (a gradient-based local optimization algorithm).
- The second option is to perform L-BFGS multiple times with many different initial solutions and then pick up the best solution.
See src/acquisition-function.cpp
for details.
Acquisition Function Choices
The following acquisition functions are supported:
- Expected improvement (EI) [default; used in the original paper]
- Gaussian process upper confidence bound (GP-UCB)
Search Space
This implementation assumes that the search space is always [0, 1]^D. When you want to handle a different search space, you need to normalize the target space into [0, 1]^D manually.
Construction of Slider Space
A slider space is constructed by choosing two end points. One of the two end points is always selected by maximizing the acquisition function (i.e., x^{EI} when using EI as the acquisition function). The other end point is selected by one of the following options:
- The point that provides the largest expected value (i.e., x^{+}) (default; used in the original paper)
- The point that is selected in the last subtask (i.e., x^{chosen}) (suggested in [Koyama+, 2020])
See Also
Sequential Gallery (SIGGRAPH 2020) is a more recent publication on the same topic (i.e., human-in-the-loop design optimization).
- Project page: https://koyama.xyz/project/sequential_gallery/
- GitHub: https://github.com/yuki-koyama/sequential-gallery
BO as Assistant (UIST 2022) is a research project using this library for a different purpose (i.e., for generating design suggestions during slider manipulation).
- Project page: https://koyama.xyz/project/bo-as-assistant/
License
MIT License.
Contributing
Issue reports, suggestions, requests, and PRs are highly welcomed.
Contact
Yuki Koyama (yuki@koyama.xyz)