Abstract—In optimization problems, a typical assumption is that the objective function is cheap to evaluate. However, many problems are not conform to this assumption. When the objective function is expensive to evaluate, Bayesian optimization is a powerful strategy to estimate the optimum of the objective function. Typically, Bayesian optimization utilizes Gaussian process with an exponential kernel for the approximation of the objective function. However, the training time of Gaussian process scales cubically and prediction and memory requirement quadratically. This poses limitations on the number of utilized data points for the training of the Gaussian process. To potentially overcome this drawback, this paper analyzes the use of the histogram intersection kernel with approximation methods, which has been shown to scale linearly, as covariance function for the Gaussian process. The resulting algorithm is compared to the EGO optimization algorithm, which utilizes an exponential kernel, and random sampling on common optimization problems. The results show that the linear approximation of the histogram intersection kernel does not accurately approximate the error surface and introduces false minima which can prevent the algorithm to identify the global minimum of a function. However, the implemented algorithm performs better than random sampling and its potential for fast evaluation might make it attractive for time-limited optimization tasks.
Index Terms—Bayesian optimization, histogram intersection kernel, gaussian process.
Dennis Becker is with Institute of Information Systems, Leuphana Universitiy, Lüneburg, Germany (e-mail: dbecker@leuphana.de).
[PDF]
Cite: Dennis Becker, "Analysis of the Histogram Intersection Kernel for Use in Bayesian Optimization," International Journal of Modeling and Optimization vol. 7, no. 6, pp. 337-345, 2017.