Bayesian optimization

Bayesian optimization is a sequential design strategy for global optimization of black-box functions, that does not assume any functional forms. It is usually employed to optimize expensive-to-evaluate functions. With the rise of artificial intelligence innovation in the 21st century, Bayesian optimizations have found prominent use in machine learning problems for optimizing hyperparameter values.

History

The term is generally attributed to Jonas Mockus and is coined in his work from a series of publications on global optimization in the 1970s and 1980s.

Early Mathematics Foundations

From 1960s to 1980s

The earliest idea of Bayesian optimization sprang in 1964, from a paper by American applied mathematician Harold J. Kushner, “A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise”. Although not directly proposing Bayesian optimization, in this paper, he first proposed a new method of locating the maximum point of an arbitrary multipeak curve in a noisy environment. This method provided an important theoretical foundation for subsequent Bayesian optimization.

By the 1980s, the framework we now use for Bayesian optimization was explicitly established. In 1978, the Soviet scientist Jonas Mockus, in his paper “The Application of Bayesian Methods for Seeking the Extremum”, discussed how to use Bayesian methods to find the extreme value of a function under various uncertain conditions. In his paper, Mockus first proposed the Expected Improvement principle (EI), which is one of the core sampling strategies of Bayesian optimization. This criterion balances exploration while optimizing the function efficiently by maximizing the expected improvement. Because of the usefulness and profound impact of this principle, Jonas Mockus is widely regarded as the founder of Bayesian optimization. Although Expected Improvement principle (IE) is one of the earliest proposed core sampling strategies for Bayesian optimization, it is not the only one, with the development of modern society, we also have Probability of Improvement (PI), or Upper Confidence Bound (UCB) and so on.

From Theory to Practice

In the 1990s, Bayesian optimization began to gradually transition from pure theory to real-world applications. In 1998, Donald R. Jones and his coworkers published a paper titled “Gaussian Optimization”. In this paper, they proposed the Gaussian Process(GP) and elaborated on the Expected Improvement principle(EI) proposed by Jonas Mockus in 1978. Through the efforts of Donald R. Jones and his colleagues, Bayesian Optimization began to shine in the fields like computers science and engineering. However, the computational complexity of Bayesian optimization for the computing power at that time still affected its development to a large extent.

In the 21st century, with the gradual rise of artificial intelligence and bionic robots, Bayesian optimization has been widely used in mechanical learning and deep learning, and has become an important tool for Hyperparameter Tuning. Companies such as Google, Facebook and OpenAI have added Bayesian optimization to their deep learning frameworks to improve search efficiency. However, Bayesian optimization still faces many challenges, for example, because of the use of Gaussian Process as a proxy model for optimization, when there is a lot of data, the training of Gaussian Process will be very slow and the computational cost is very high. This makes it difficult for this optimization method to work well in more complex drug development and medical experiments.

Strategy

Bayesian optimization of a function (black) with Gaussian processes (purple). Three acquisition functions (blue) are shown at the bottom.

Bayesian optimization is typically used on problems of the form ${\textstyle \max _{x\in A}f(x)}$, where ${\textstyle A}$ is a set of points, ${\textstyle x}$, which rely upon less (or equal to) than 20 dimensions (${\textstyle \mathbb {R} ^{d},d\leq 20}$), and whose membership can easily be evaluated. Bayesian optimization is particularly advantageous for problems where ${\textstyle f(x)}$ is difficult to evaluate due to its computational cost. The objective function, ${\textstyle f}$, is continuous and takes the form of some unknown structure, referred to as a "black box". Upon its evaluation, only ${\textstyle f(x)}$ is observed and its derivatives are not evaluated.

Since the objective function is unknown, the Bayesian strategy is to treat it as a random function and place a prior over it. The prior captures beliefs about the behavior of the function. After gathering the function evaluations, which are treated as data, the prior is updated to form the posterior distribution over the objective function. The posterior distribution, in turn, is used to construct an acquisition function (often also referred to as infill sampling criteria) that determines the next query point.

There are several methods used to define the prior/posterior distribution over the objective function. The most common two methods use Gaussian processes in a method called kriging. Another less expensive method uses the Parzen-Tree Estimator to construct two distributions for 'high' and 'low' points, and then finds the location that maximizes the expected improvement.

Standard Bayesian optimization relies upon each $x\in A$ being easy to evaluate, and problems that deviate from this assumption are known as exotic Bayesian optimization problems. Optimization problems can become exotic if it is known that there is noise, the evaluations are being done in parallel, the quality of evaluations relies upon a tradeoff between difficulty and accuracy, the presence of random environmental conditions, or if the evaluation involves derivatives.

Acquisition functions

Examples of acquisition functions include

• probability of improvement
• expected improvement
• Bayesian expected losses
• upper confidence bounds (UCB) or lower confidence bounds
• Thompson sampling

and hybrids of these. They all trade-off exploration and exploitation so as to minimize the number of function queries. As such, Bayesian optimization is well suited for functions that are expensive to evaluate.

Solution methods

The maximum of the acquisition function is typically found by resorting to discretization or by means of an auxiliary optimizer. Acquisition functions are maximized using a numerical optimization technique, such as Newton's method or quasi-Newton methods like the Broyden–Fletcher–Goldfarb–Shanno algorithm.

Applications

The approach has been applied to solve a wide range of problems, including learning to rank, computer graphics and visual design, robotics, sensor networks, automatic algorithm configuration, automatic machine learning toolboxes, reinforcement learning, planning, visual attention, architecture configuration in deep learning, static program analysis, experimental particle physics, quality-diversity optimization, chemistry, material design, and drug development.

Bayesian optimization has been applied in the field of facial recognition. The performance of the Histogram of Oriented Gradients (HOG) algorithm, a popular feature extraction method, heavily relies on its parameter settings. Optimizing these parameters can be challenging but crucial for achieving high accuracy. A novel approach to optimize the HOG algorithm parameters and image size for facial recognition using a Tree-structured Parzen Estimator (TPE) based Bayesian optimization technique has been proposed. This optimized approach has the potential to be adapted for other computer vision applications and contributes to the ongoing development of hand-crafted parameter-based feature extraction algorithms in computer vision.

See also

• Multi-armed bandit
• Kriging
• Thompson sampling
• Global optimization
• Bayesian experimental design
• Probabilistic numerics
• Pareto optimum
• Active learning (machine learning)
• Multi-objective optimization